6.5. ВЫЛАВЛИВАНИЕ ОШИБОК

Описанный в конце предыдущего параграфа вариант декодера содержит таблицу синдромов, которая, как сразу видно, содержит только слова веса На самом деле эти синдромы очень положи на исправляемые конфигурации ошибок, левая часть которых содержит только нулевые символы и опущена. Такой декодер известен иод названием декодера с вылавливанием ошибок. Декодер с вылавливанием ошибок является модификацией декодера Меггитта, применимой к некоторым циклическим кодам.

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

На рис. 6.24 приведен вылавливающий ошибки декодер для (15, 7)-кода БЧХ. Для полного исправления двойных ошибок требуется 45 тактов работы декодера: 15 для генерирования синдрома, 15 для исправления первой ошибочной позиции и 15 для исправления второй ошибочной позиции. На рис. 6.25 представлен конвейерный вариант декодера, в котором использованы три генератора синдромов. Он позволяет декодировать непрерывно поступающие 15-битовые блоки с тактовой линейной скоростью. На рис. 6.26 расписаны 45 тактов работы декодера с вылавливанием ошибок для типичной конфигурации ошибок (ошибки вылавливаются на тактах номер 28 и 33).

В качестве второго примера декодера с вылааливанием ошибок рассмотрим декодер для (7, 3)-кода Рида-Соломона над с порождающим многочленом

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

где элементы ноля заданы в виде степеней примитивного элемента . В гл. 7, где рассматриваются коды Рида-Соломона,

(кликните для просмотра скана)

Рис. 6-26. (см. скан) Пример вылавливания ошибок для -кода БЧХ.

будет показано, что этот код исправляет две ошибки. Сейчас мы примем это утверждение без доказательства.

Исправляемые конфигурации ошибок содержат не более двух ненулевых символов и задаются многочленом степени не выше 6. Их всегда можно циклически сдвинуть в многочлен степени не выше 3. Так как степень синдромного многочлена не превосходит 3, то можно применить декодирование с вылавливанием ошибок.

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

передачи данных в каждый момент времени передают три бита. Элементы умножения на на и на (т. е. на ) в цепи обратной связи являются просто определяемыми устройствами двоичной логики с тремя входами и тремя выходами. Для исправления всех ошибок такому декодеру необходим всею 21 такт. Первые семь тактов уходят на вычисление синдрома; следующие семь тактов требуются на исправление хотя бы одной ошибки, а иногда и обеих ошибок. Последние семь тактов уходят на исправление второй ошибки (если она еще не исправлена).

На рис. 6.28 отдельные операции влгоритма декодирования отслеживаются в деталях. Это очень ценный пример, так как он демонстрирует технику вылавливания ошибок и одновременно представляет собой конкретный пример взаимосвязи абстрактных понятий теории полей Галуа и практического построения логических цепей, использующих регистры сдвига.

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

Рис. 6-27. Вылавливлние ошибок для (7, 3)-кода Рида-Соломона,

Рис. 6.28. (см. скан) Пример вылавливания ошибок.

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

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

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

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

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

Рис. 6.29. Декодер с вылавливанием ошибок для кода-перемежения, неправ» ляющего пакеты ошибок.

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