Математические принципы кодирования и декодирования

Для того, чтобы закодировать слово, нужно составить матрицу Н^Т, состоящую из двух матриц, расположенных одну над другой: R размерности kx(n-k) и I_n-k размерности (n-k)x(n-k). Затем производится умножение информационного блока на эту матрицу. Получить ее можно посредством деления X^n-1, X^n-2,…X^n-k на порождающий многочлен. При этом, при делении первых k членов мы получим k проверочных блоков, образующих матрицу R, а при последующем делении получим единичную матрицу I_n-k. Вместе эти матрицы образуют матрицу H^T.

 

 

Например, произведем деление первого члена X²⁰ на порождающий многочлен:

x²⁰ x⁷ + x⁴ +x³+x²+x+1

x²⁰ + x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴+x¹³ x¹³ + x¹⁰ + x⁹ + x⁸ + x⁶ + x⁵ + x⁴ + 1

x¹⁷ + x¹⁶ + x¹⁵ + x¹⁴+x¹³

x¹⁷ + x¹⁴ +x¹³ + x¹² + x¹¹+x¹⁰

x¹⁶ + x¹⁵ +x¹² + x¹¹ + x¹⁰

x¹⁶ + x¹³ +x¹² + x¹¹ + x¹⁰+x⁹

x¹⁵ + x¹³+x⁹

x¹⁵ + x¹² +x¹¹ + x¹⁰ + x⁹+x⁸

x¹³ + x¹² +x¹¹ + x¹⁰ + x⁸

x¹³ + x¹⁰ +x¹⁹ + x⁸ + x⁷+x⁶

x¹² + x¹¹ + x⁹ + x⁷+x⁶

x¹² + x⁹ +x⁸ + x⁷ + x⁶+x⁵

x¹¹ + x⁸ + x⁵

x¹¹ + x⁸ +x⁷ + x⁶ + x⁵+x⁴

x⁷ + x⁶ + x⁴

x⁷+x⁴+x³+x²+x+1

x⁶+x³+x²+x+1

Остаток от деления записан формально в виде многочлена. Представим его следующим образом, записав коэффициенты при членах как 0 и 1:

 

Поделим остальные члены ряда X^n-1, X^n-2,…X^n-k на порождающий многочлен, и в результате получим матрицу H^T:

 

Эта матрица представляет собой записанные в байтовую ячейку проверочные символы и единичную матрицу. Так как проверочные символы занимают (n-k) =7 разрядов, то младший разряд данной байтовой ячейки обнуляется.

Для получения проверочного блока нужно умножить информационный блок на матрицу R:

X – информационный блок, Y – проверочный блок.

 

Для декодирования нужно умножить кодовое слово (с ошибками) на всю матрицу H^T, причем кодовое слово можно представить в виде суммы по модулю 2 истинного кодового слова и вектора ошибок:

r – кодовое слово с ошибками, v – истинное кодовое слово, e – вектор ошибок.

Вектор е представляет собой вектор длины n, в котором 1 находятся там, где допущена ошибка в кодовом слове.

При этом произведение v* H^T=0 (нулевой вектор).

После перемножения r* H^T получаем синдром s, который зависит только от вектора ошибок (v* H^T=0 ) и представляет собой строку матрицы H^T (если ошибка одна) или сумму по модулю 2 строк этой матрицы. С помощью синдрома можно определить нужный вектор ошибок (все они загружены в память), затем прибавить его к слову r:

Таким образом, получаем кодовое слово v с исправленными ошибками, а затем просто отделяем от него младшие 8 разрядов и получаем информационный блок.

 

 

 

рис. 9 Структурная схема микроконтроллера M68HC11

 

 

 

 

Код программы

cpu 6811

org $00ee ;вектор прерывания

jmp $d100 ;скачок на подпрограмму прерывания

org $d000 ;основная программа

ldx #$d200 ;ячейка для использования индексной ;адресации x

ldd #%10011110

std 0,x

ldd #%11010000

std 1,x

ldd #%01101000

std 2,x

ldd #%00110100

std 3,x

ldd #%00011010

std 4,x

ldd #%10010010

std 5,x

ldd #%11010110

std 6,x

ldd #%11110100

std 7,x

ldd #%00111010

std 8,x

ldd #%10100010

std 9,x

ldd #%11001110

std 10,x

ldd #%11111000

std 11,x

ldd #%01111110

std 12,x

ldd #%00111110

std 13,x

 

ldd #$0080 ;Единичная матрица

std 14,x ;

ldd #$0040 ;

std 15,x ;

ldd #$0020 ;

std 16,x ;

ldd #$0010 ;

std 17,x ;

ldd #$0008 ;

std 18,x ;

ldd #$0004 ;

std 19,x ;

ldd #$0002

std 20,x ;