Циклические коды, исправляющие кратные ошибки

Циклические коды, исправляющие кратные ошибки, обычно называются кодами БЧХ (от фамилий авторов: Боуз, Чоудхури, Хоквенгем). Хорошие корректирующие свойства и простота построения кодирующих к декодирующих устройств (особенно при необходимости обнаруживать ошибки) обеспечили кодам БЧХ широкое практическое применение. Согласно ГОСТ 17422-72, основанному на рекомендации МККТТ V×41, в системах передачи данных с решающей обратной связью предписывается использовать циклические коды со следующими параметрами: n=140, 260, 500 и 980, порождающий многочлен х¹⁶+х¹²+х⁵+1.

Алгоритмы декодирования кодов БЧХ довольно сложны, и их рассмотрение не входит в программу данного курса. В некоторых случаях при небольших длительностях кодовых комбинаций для исправления ошибок может быть применен описанный в подразделе 3.3.6. алгоритм декодирования в более развитом виде. В циклических кодах, исправляющих ошибки до кратности р, при расположении всех ошибок в проверочных разрядах синдром ошибок будет содержать не более р единиц, находящихся в разрядах с ошибками. Это значит, что исправлять ошибки в таком случае можно суммированием остатка с исправляемой комбинацией. Ошибкам в информационных разрядах соответствуют синдром с количеством единиц, большим чем р.

На основании изложенного методика исправления кратных ошибок кодом БЧХ при небольших длинах кодовых комбинаций может сводиться к следующему.

1. Принятая комбинация делится на порождающую.

2. Определяется количество q единиц в остатке:

а) если q≤p, где p - максимальное количество ошибок, исправляемых данным кодом, то ошибок в информационных разрядах нет;

б) если q>p, ошибки есть в информационных разрядах. В этом случае к остатку приписывается необходимое количество нулей, деление продолжается, подсчитывается количество нулей в новом остатке, и при необходимости аналогичная процедура повторяется до получения остатка с количеством единиц p=q.

3. Декодируемая комбинация сдвигается циклически влево на количество разрядов, равное количеству нулей, приписанных в процессе деления, остаток суммируется со сдвинутой комбинацией, после чего комбинация сдвигается в противоположную сторону, т.е. вправо, на то же количество разрядов.

Пример. Применен код БЧХ 15,5, способный исправлять почти все ошибки тройной кратности. Порождающий многочлен кода записывается так: р(х)=х¹⁰+х⁸+х⁵+х⁴+х³+х+1, что эквивалентно комбинации 10100110111. Требуется декодировать принятую комбинацию 100001101110101.

Производим деление:

100001101110101 / 10100110111

Å 10100110111

==10000000001

Å 10100110111

==10011011001

Å 10100110111

==11110111000

Å 10100110111

=10100011110

Å 10100110111

=====101001

В остатке три единицы, следовательно, на этом деление прекращаем. В процессе деления к делимой комбинации было дописано три нуля, поэтому для исправления ошибки декодируемую комбинацию сдвигаем на три разряда влево, суммируем с остатком:

Å 101001

001101110000101

и сдвигаем на три разряда вправо: 101001101110000. Ошибки исправлены. В соответствии с видом синдрома ошибки имели место в 1, 4 и 6-м разрядах сдвинутой комбинации, т.е. в 1, 3 и 13-м разрядах принятой комбинации.

Указанная методика пригодна, например, для кода (15,7), исправляющего одиночные и двойные ошибки. В коде (15,5), исправляющем и тройные ошибки, данная методика позволяет исправлять почти все тройные ошибки (не исправляются тройные ошибки только в случае их расположения в следующих разрядах: a_i, a_i+5, a_i+10, где i≤1¸5).

Литература:

[1] стр. 247-255. [2] стр. 285-289. [3] стр. 149-154.

Контрольные вопросы:

1. Являются ли циклические коды групповыми?

2. Какими дополнительными свойствами, упрощающими технику кодирования и декодирования, обладают циклические коды по сравнению с групповыми?

3. Какими свойствами должен обладать порождающий многочлен циклического кода?

4. Как проще всего определять синдромы ошибок в циклических кодах.

Задачи:

1. Записать все разрешенные комбинации циклического кода (7,4) с порождающим многочленом 1011.

2. Записать все разрешенные комбинации циклического кода (7,4) с порождающей комбинацией 1101.

3. Задан циклический код (7,4) с порождающей комбинацией 1011. Записать синдромы всех исправляемых кодом ошибок. Декодировать полученную комбинацию 1011111.

4. Получена комбинация 1111010, закодированная циклическим кодом (7,4) с порождающей комбинацией 1101. Код используется для обнаружения одиночных и двойных ошибок. Указать возможные варианты ошибок в полученной комбинации.

5. Используется код БЧХ с порождающим многочленом

х¹⁰+х⁸+х⁵+х⁴+х³+х+1

Закодировать комбинацию 11111, ввести в закодированную комбинацию три ошибки и исправить их по указанной методике.

Сверточные коды

В корректирующих сверточных кодах избыточность вводится без разбивки последовательности символов на отдельные блоки. Кодовые символы определяются по мере поступления информационных с помощью некоторых рекуррентных соотношений, выбор которых определяет разновидность кода. Иногда такие коды называют рекуррентными, цепными, непрерывными. В общем используемые соотношения могут быть как линейными, так и нелинейными. В настоящее время на практике используются преимущественно линейные сверточные коды, причем для декодирования наиболее часто применяется алгоритм Витерби, что обусловлено преимуществами алгоритма, рассматриваемыми далее.

Сверточные коды также делятся на систематические и несистематические. В технике связи в настоящее время применяются и те, и другие, поэтому рассмотрим кратко оба вида.