Укороченные коды Хэмминга: кодирование, декодирование, построение кодеков

В большинстве циклических кодов длина кодовых слов однозначно определяется степенью выбранного примитивного мно­гочлена. Это обстоятельство накладывает большие ограничения на число информационных разрядов в кодируемом блоке. Между тем, в используемых в настоящее время стандартах передачи данных, дли­на информационных блоков может колебаться в довольно широких пределах. В соответствии с этим, кодирование также должно быть достаточно гибким.

В этом могут помочь укороченные коды, построенные на основе циклических кодов. Пусть, например, нами выбран много­член с т = 5. На базе этого многочлена можно построить цикличе­ский (31,26)-код Хэмминга. Подмножество слов этого ко­да, содержащее все кодовые слова с тремя нулями в старших разря­дах образует укороченный (28,23)-код Хэммин­га. Укороченный код сохраняет все свойства циклического (31,26)- кода, так как в процессе декодирования мы можем дописать к кодо­вым словам три недостающих нуля и рассматривать их как векторы основного (31,26')-кода Хэмминга.

Метод кодирования и декодирования кода, получен­ного укорочением (7,4)-кода Хэмминга.

Выберем из множества кодо­вых слов базового кода все кодовые слова, начинающиеся с символа «О». Выбрасываемые при укорочении символы полагаются равными нулю и, поэтому, не передаются. Таким образом получаем укорочен­ный (6,3)-код. В левой части таблицы 3.3 приведены кодовые слова (7,4)-кода Хэмминга, у которых старший разряд равен нулю. Выбра­сывая из этих слов лишние нули, получаем кодовые слова укорочен­ного (6,3)-кода (см. табл. 3.9).

Таблица 3.3. Циклический (7,4)-код, образованный порож­дающим многочленом в систематическом виде.

Таблица 3.9. (6,3)-код.

За основу кодера систематического (6,3)-кода может быть при­нята схема кодера систематического циклического (7,4)-кода с порождающим многочленом . Так как (6,3)-код образуется укорочением (7,4)-кода Хэмминга, схема рис. 3.8 суще­ственно упрощается: из регистров удаляются разряды u₃ и v₆ и ко­дирование заканчивается уже после третьего такта.

Для практической реализации декодера укороченного кода име­ются три альтернативы:

1. Для декодирования (6,3)-кода можно, в принципе, использо­вать декодер базового (7,4)-кода Хэмминга. В этом случае, к принятому слову приписывается недостающий ноль и процесс декодирования занимает столько же тактов, сколько требуется для декодера базового кода.

Для декодирования кодов с l -кратным укорочением необходимо затратить l дополнительных тактов. В случае, когда l велико (как, например, в случае кода Файера) такой метод декодиро­вания неприемлем.

2. При коррекции ошибок и модификации синдрома принимают­ся во внимание особенности конструкции укороченного кода. Схема декодера (6,3)-кода приведена на рис. 3.22. Здесь векто­ру ошибки е = (000 001) в компоненте r₅, согласно табл. 3.6, соответствует синдром s = (1,1,1), поэтому, схема распознава­ния ошибок настраивается на этот синдром (а не на синдром (101) в случае (7,4)-кода). Рассмотрим теперь алгоритм моди­фикации синдрома. В нижнем регистре вычисляются синдро­мы всех сдвигов ошибки в слове базового (7,4)-кода (эта схема «не знает об укорочении») и следующим за синдромом «111» будет синдром «101». В соответствии с его числовым вектором и производится модификация текущего синдрома на рис. 3.22.

Рис. 3.22. Декодер Меггитта укороченного (6,3)-кода Хэммига.

3. Этот вариант построения декодера Меггита особенно интере­сен для практики, так как используемые в нем алгоритмы рас­познавания ошибок и коррекции синдрома не зависят от дли­ны укорочения l и строятся с наименьшими затратами. Длина укорочения учитывается путем умножения принятого слова на некоторый многочлен, зависящий от l.