Eliminating sequences in a message

Question

I have an odd communications channel, and I need to detect errors as well as eliminate certain sequences in the channel.

Each message is 12 bits long, split into 3 nibbles (of 4 bits each). I need to extract at least 450 different codes out of this, so I can have a hamming distance of up to 3.

However, I cannot have two nibbles in sequence be the same, so the following sequences are invalid:

0xf 0xf 0xf - Three of the same nibbles in sequence
0x8 0x8 0x0 - Two of the same nibbles in sequence
0xf 0x3 0x3 - Two of the same nibbles in sequence

Further, messages can follow each other without breaks, so the beginning of one sequence can't have the same first nibble as the end of the last sequence:

0x327 0x743 - Even though they are not in the same message, two sequential nibbles are the same in the message stream

But the following sequences are fine:

0x1 0x2 0x1 - Two nibbles same, but separated by another nibble
0x0 0x1 0x2 - All nibbles different
0xf 0x8 0x3 - All nibbles different

And the following series of messages is fine:

0x121 0x012 0xf83 - No two adjacent nibbles are the same is the stream of messages

My first thought is to use 9 bits for my message, split into three 3 bit parts as the top bits of each nibble:

mmmc mmmc mmmc - Each character is a bit, m bits are message, c bits are checksum/parity/etc

Then design a 512 entry table that gives me the three bits to fill c with that will create the hamming distance while eliminating the troublesome sequences.

However, this will be running on a low end embedded processor, and if I can use arithmetic to generate the c bits on the fly, it will save memory (in exchange for more processor time) which is more valuable in this case.

Is there a bit of math I can perform that would solve this problem without a table?

Alternately, is there another packing method with math that would meet the requirements?

Answer 1

The simplest method:
0mmm 1mmm 0mmm - no repeating nibbles, fastest encoding/decoding, no checksum

But I'd recommend the following method:
You have 3600 = 16*15*15 possible nibble triplets (first nibble has 16 variants, second has 15, third has 15).
You can have 2 bits for checksum and 3600/4 = 900 domain-specific codes.

Encoder (decoder is the reverse of it):

C = 0..899 -- your code to be encoded  
C = C * 4  -- appending a "hidden checksum"
N3 = C mod 15  -- 0..14
C = C div 15
N2 = C mod 15  -- 0..14
N1 = C div 15  -- 0..15
nibble1 = N1
nibble2 = (nibble1 + 1 + N2) mod 16
nibble3 = (nibble2 + 1 + N3) mod 16  

Dividing by 15 is as simple as multiplying by 0.000100010001₂ if you haven't DIV operation.

Decoder:

nibble1, nibble2, nibble3 -- your three nibbles
N1 = nibble1
N2 = (nibble2 - nibble1 - 1) mod 16
N3 = (nibble3 - nibble2 - 1) mod 16
C = (N1*15 + N2)*15 + N3
if C mod 4 != 0 then CHECKSUM ERROR
C = C/4  -- 0..899

---

UPD for new conditions:
no checksum, 8*14*8 = 896 possible codes

Encoder (decoder is the reverse of it):

C = 0..895 -- your code to be encoded  
N1 = C mod 8
C = C div 8
N2 = (C div 8) + 1 + N1
N3 = (C mod 8) + 8
if N2 >= N3 then N2 = N2 + 1
nibble1 = N1   -- 0..7
nibble2 = N2 mod 16
nibble3 = N3   -- 8..15

Decoder:

nibble1, nibble2, nibble3 -- your three nibbles (0..7, 0..15, 8..15)
N1 = nibble1
N2 = (nibble2 - nibble1 - 1) mod 16
N3 = nibble3
if N1 + N2 >= N3 then N2 = N2 - 1
C = (N2*8 + N3 - 8)*8 + N1  -- 0..895