Устранение последовательностей в сообщении

Question

У меня есть нечетный канал связи, и мне нужно обнаружить ошибки, а также исключить определенные последовательности в канале.

Каждое сообщение имеет длину 12 бит, разделенное на 3 куска (по 4 бита каждый). Мне нужно извлечь по меньшей мере 450 различных кодов из этого, так что я могу иметь расстояние от помех до 3.

Однако, у меня не может быть двух полубайтов в последовательности одинаковых, поэтому следующие последовательности недействительны:

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 

Кроме того, сообщения могут следовать друг за другом без перерыва, поэтому начало одной последовательности не могут иметь один и тот же первый клев как конец последней последовательности:

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

Но следующие последовательности штраф:

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

И следующая серия сообщений в порядке:

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

Моя первая мысль заключается в использовании 9 бит для моего сообщения, разделить на три 3 битовых частей, как верхние биты каждого кусочкам:

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

Затем создайте таблицу ввода 512, которая дает мне три бита, чтобы заполнить c тем, что создаст расстояние для хамминга, устраняя неприятные последовательности.

Однако это будет работать на низкопробном встроенном процессоре, и если я смогу использовать арифметику для генерации бит «c» на лету, это сэкономит память (взамен большего времени процессора), что является более ценным в этом дело.

Есть ли какая-то математика, которую я могу выполнить, чтобы решить эту проблему без таблицы?

С другой стороны, существует ли другой способ упаковки с математикой, отвечающий требованиям?

Answer 1

Самый простой способ:
0mmm 1mmm 0mmm - нет повторяющихся грызет, быстрый кодирования/декодирования, без контрольной суммы

Но я бы рекомендовал следующий метод:
У вас есть 3600 = 16 * 15 * 15 возможных грызунов триплетов (первый кусок имеет 16 вариантов, второй имеет 15, третий имеет 15).
У вас может быть 2 бита для контрольной суммы и 3600/4 = 900 кодов для домена.

кодер (декодер является обратной от него):

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 

Деление на 15 так же просто, как умножение на 0.000100010001 если вы еще не операция DIV.

Декодер:

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 для новых условий:
нет контрольной суммы, 8 * 14 * 8 = 896 возможных кодов

кодера (декодера является обратной от него) :

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 

Декодер:

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