Removing sequences in a message

Question

I have an odd communication channel, and I need to detect errors and also exclude certain sequences in the channel.

Each message has a length of 12 bits, divided into 3 pieces (4 bits each). I need to extract at least 450 different codes from this, so that I can have a distance from interference of up to 3.

However, I cannot have two nails in the sequence the same, so the following sequences are not valid:

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 

In addition, messages can follow each other without interruptions, so the beginning of one sequence cannot have the same first piece 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 in order:

 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 in order:

 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, broken 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 create an input table 512 that gives me three bits to fill c so that it creates distance for hamming, eliminating unpleasant sequences.

However, this will work on a low-performance embedded processor, and if I can use arithmetic to generate c bits on the fly, it will save memory (instead of more processor time), which is more valuable in this case.

Is there some math I can do to solve this problem without a table?

Alternatively, is there another math packaging method that meets the requirements?

Answer 1

The easiest way:
0mmm 1mmm 0mmm - no duplicate nibbles, fast encoding / decoding, checksum

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

Encoder (reverse decoder):

 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 do not have a 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 (reverse decoder):

 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