Синдромное декодирование циклических кодов

Поскольку любой полином циклического кода (и только он) делится на порождающий полином, т.е. дает нулевой остаток от деления, то синдромное декодирование циклических кодов может быть организовано с ориентацией на данное свойство. Пусть – полином наблюдения, коэффициентами которого являются элементы вектора наблюдения . Согласно (6.10) , где – вектор ошибок, тогда

, (7.9)

где, в свою очередь, – полином ошибок.

Назовем синдромным полиномом (или полиномом синдрома) остаток от деления полинома наблюдения на . Из (7.9) очевидным образом следует, что синдром определяется только полиномом . Поскольку , то возможны различных полиномов , тогда как число векторов ошибки – . Это означает, что вновь существует смежных классов полиномов ошибки с одинаковыми синдромами и в каждом классе имеется свой лидер (полином ошибки минимального веса). Следовательно, синдромное декодирование циклических кодов может быть реализовано в три этапа:

1. Производится вычисление полинома синдрома посредством деления полинома наблюдения на порождающий полином ;

2. По вычисленному полиному находится лидер смежного класса, а, значит, оценивается возможный полином ошибки ;

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

Совершенно очевидно, что данная процедура аналогична приведенной в параграфе 6.9, только описанная на языке полиномов. Поскольку вычисление синдрома связано с нахождением остатка от деления полиномов, то реализация этой операции может быть осуществлена на основе регистра сдвига, использованного при циклическом кодировании, только с незначительной модификацией (см. рис. 7.4).

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

Пример 7.6.1. Для (7,4) кода примера 7.4.1 вычислитель синдрома реализуется структурой, изображенной на рис. 7.5, где приведена и таблица состояний. Пусть вектор наблюдения представим в виде , которому соответствует полином . Полином синдрома, найденный как остаток от деления на , будет . Из полиномов ошибки единичного веса указанный синдром дает . Тогда декодированное слово получается изменением пятого элемента вектора , и значит, , что подтверждает пример 7.5.1.

В заключении отметим, что учет цикличности облегчает аппаратурную реализацию декодеров (например, декодер Мэггита и др.). Однако в настоящее время подобный подход является не столь популярным, как несколько десятилетий ранее.