Способы декодирования с исправлением ошибок и схемная реализация декодирующих устройств
Декодирование
циклического кода в режиме исправления ошибок можно осуществлять различными
способами. Ниже излагаются два способа, являющиеся наиболее простыми.
В основу первого способа положено использование таблицы синдромов
(декодирования), в которой каждому многочлену или образцу ошибок ei(x), соответствует
определенный синдром Si(x), представляющий остаток от деления принятого кодового
слова 
и соответствующего ему
ei(x) на g(x). Процедура декодирования следующая. Принятое кодовое слово делится
на g(x), определяется Si(x) и соответствующий ему многочлен ei(x), а затем
суммируется с ei(x). В результате получаем
исправленное кодовое слово, т.е. 
.
Структурная схема декодера, выполняющего рассмотренный алгоритм исправления
ошибок, представлена на рисунке 6. В состав декодера входят: вычислитель синдрома
(ВС), два регистра сдвига RG1 и RG2, постоянное запоминающее устройство (ПЗУ),
котороесодержит 
слова длины n, соответствующие многочленам ошибок ei(x).
Принятое кодовое слово поступает
на вход вычислителя синдрома, где осуществляется деление его на g(x) и формирование
Si(x), и одновременно - на вход RG2, где накапливается. Синдром Si(x) используется в качестве адреса,
по которому из ПЗУ в регистр RG1 записывается ei(x), соответствующий синдрому
Si(x). Перечисленные операции завершаются за n тактов. В течение последующих
n тактов происходит поэлементное суммирование содержимого RG2 и RG1, т.е.
операция , и исправление ошибок.
В основе второго способа исправления ошибок, позволяющего
значительно сократить объем используемых табличных синдромов и существенно
упростить схему декодера, лежат следующие положения:
1. Синдром Si(x), соответствующий принятому кодовому слову равен остатку от
деления на g(x), а также остатку
от деления соответствующего многочлена ошибок ei(x) на g(x), т.е. 
.
2. Если Si(x) соответствует и
ei(x), то x( Si(x) является синдромом, который соответствует 
и 
или 
.
3. При исправлении ошибок используются синдромы образцов ошибок только с ненулевым
коэффициентом в старшем разряде.
Поэтому при реализации этого способа множество всех образцов
ошибок разбивается на классы эквивалентности. Каждый класс представляет циклический
сдвиг одного образца ошибок, а синдром этого класса соответствует образцу
ошибок с ненулевым старшим разрядом. Если вычисленный синдром принадлежит
одному из классов эквивалентности образцов исправляемых ошибок, то старший
символ кодового слова исправляется. Затем принятое слово и синдром циклически
сдвигается, а процесс нахождения в предыдущей по старшинству позиции повторяется.
Для исправления ошибок, принадлежащих данному классу эквивалентности, нужно
произвести n циклических сдвигов.
На рисунке 7 представлена схема декодера циклического кода
с исправлением ошибок (декодер Меггитта). В состав декодера входят: вычислитель
синдрома, осуществляющий деление кодового слова на g(x) и формирование соответствующего синдрома; блок
декодеров (ДК), который настроен на синдромы всех образцов исправляемых ошибок
с ненулевыми старшими разрядами; регистр сдвига RG.
При поступлении на вход схемы кодового слова его символы заполняют регистр RG, а в вычислителе формируется
соответствующий синдром Si(x). Вычисленный синдром сравнивается со всеми табличными
синдромами, заложенными в схему блока ДК, и в случае совпадения с одним из
них на его выходе формируется сигнал, который исправляет ошибочный символ,
находящийся в старшем разряде регистра. После этого содержимое вычислителя
и RG циклически сдвигается на один шаг. Этот сдвиг реализует операции 
и
. Если новый синдром совпадает с одним
из табличных синдромов, то это означает, что произошла ошибка во втором по
старшинству символе кодового слова, который, перейдя в старший разряд RG,
исправляется. Затем производится новый циклический сдвиг на одну позицию и
новая проверка на совпадение синдромов. После повторения этого процесса n
раз в RG будет сформировано исправленное кодовое слово. Введение обратной
связи для RG не обязательно, так как в процессе исправления ошибок символы
кодового слова поступают на выход декодера.