9.6. ДЕКОДИРОВАНИЕ КОДОВ БЧХ

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

Пусть для начала двоичный -код БЧХ с нечетным конструктивным расстоянием Предположим, что передавалось кодовое слово и получено искаженное слово где -вектор ошибок (рис. 9.2).

Рис. 9.2. Общий вид системы связи

Декодирование можно разбить на три этапа. (I). Вычисление синдрома. (II). Нахождение многочлена локаторов ошибок Нахождение корней многочлена Опишем по очереди каждый из этапов.

Этап (I). Вычисление синдрома. Проверочную матрицу можно положить равной

Как обычно, пусть Синдром вектора у равен (§ 1.4):

где (Заметим, что ) Декодер может легко вычислить значения по многочлену следующим образом. Разделим многочлен на минимальный многочлен элемента

Тогда равно значению многочлена в точке Схема, выполняющая эти вычисления, приведена в § 3.4 и 7.8.

Например, рассмотрим -код из гл. 3. Предположим, что получен многочлен Для вычисления разделим на (см. § 4.4) и вычислим значение остатка в точке Схема, выполняющая эти вычисления, показана в верхней половине рис. 9.3. Для вычисления многочлен надо разделить на и найти остаток Тогда

Схема, выполняющая эти вычисления, показана в нижней половине рис. 9.3.

Таким образом, к концу первого этапа в декодере вычислены При необходимости также легко могут быть найдены величины

Этап (II). Определение многочлена локаторов ошибок Предположим, что вес вектора ошибок равен и ненулевыми его компонентами являются так что вектор у содержит ошибки в координатах Как и в конце § 1, определим локаторы и многочлен локаторов ошибок

Рис. 9.3. Этап (I) декодера — вычисление синдрома

Для имеем:

так как согласно определению кода БЧХ с конструктивным расстоянием Следовательно,

На этапе (I) алгоритма декодер вычислил степенные суммы Задача этапа (II), являющегося наиболее сложной частью алгоритма, состоит в определении многочлена по уже вычисленным Коэффициенты многочлена и величины связаны тождествами Ньютона (которые могут быть записаны двумя способами: равенствами или из упражнений (52) и (54) гл. 8). Однако, как мы видели в § 1.3, синдром, т. е. величины определяет вектор или многочлен неоднозначно. Декодер должен определить вектор наименьшего веса или, что эквивалентно, многочлен наименьшей степени, удовлетворяющий тождествам Ньютона. (Именно эта неопределенность относительно делает столь трудным второй этап алгоритма.)

Известно несколько методов нахождения

(страница отсутствует)

и, следовательно, многочлен локаторов ошибок равен:

что совпадает с (9.22).

В общем случае уравнения (9.23) могут быть решены методом итераций, основанным на следующей теореме. Теорема 14. (Питерсон.) Пусть

-матрица

невырождена, если или и вырождена, если

Доказательство (i). Предположим, что Тогда из (9.23) следует, что

и, следовательно, матрица вырождена.

(ii). Предположим, что Тогда

Действительно, если положить то согласно Следовательно, и нетрудно показать, что эта константа должна равняться 1.

(iii). Наконец, если то невырожденность матрицы следует из

Используя эту теорему и предполагая, что произошло ошибок, для кода БЧХ с конструктивным расстоянием имеем следующий итеративный алгоритм для определения

Предположим, что произошло ошибок, и попытаемся решить уравнения (9.23), полагая в них Если действительно произошло или ошибок, то по теореме 14 решение существует можно перейти к этапу (III). Если же произошло меньше чем ошибок, то уравнения не будут иметь решения. В этом случае

положим и снова попытаемся решить уравнения (9.23), заменив теперь на И так до тех пор, пока решение не будет найдено.

Трудность этого метода состоит в том, что он требует многократных вычислений большого определителя над Поэтому, если велико (например, больше чем 3 или 4), то более предпочтителен следующий метод.

Метод (2). Использование обобщенных тождеств Ньютона — алгоритм Берлекэмпа. Если произошло ошибок, то величины связаны между собой уравнениями (8.12) и (8.13). Уравнение (8.12) можно интерпретировать так, как показано на рис. 9.4: величины являются выходом линейного регистра сдвигов с обратной связью, состоящего из до ячеек, находящихся в начальных состояниях

Рис. 9.4. Вычисление величин на регистре сдвигов

Регистр показан в момент, когда в ячейках содержатся а на выходе формируется

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

Берлекэмп предложил эффективный алгоритм построения такого регистра сдвига (и, следовательно, многочлена локаторов ошибок В гл. 12 мы опишем один из вариантов этого алгоритма, пригодный для широкого класса кодов, включая коды Гоппы и другие обобщения кодов БЧХ.

Какой бы из методов не использовался, в конце этапа (II) декодер знает многочлен локаторов ошибок

Этап (III). Нахождение корней многочлена Так как то величины являются обратными корням многочлена и ошибки содержатся в координатах

Если степень многочлена равна 1 или 2, то его корни находятся непосредственно (см. § 7). Но в общем случае проще всего подставить каждую степень элемента а и проверить, является ли она корнем многочлена Эту часть алгоритма

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

На рис. 9.5 показаны все три этапа работы декодера. Для иллюстрации работы схемы декодера на этапе (III) рассмотрим опять -код. Соответствующая часть схемы показана на рис. 9.6.

Рис. 9.5 Полный декодер

Первым символом, приходящим в точку является и ошибка в этом символе содержится в том и только в том случае, когда Следующим приходит символ у 13, и он ошибочен тогда и только тогда, когда

Рис. 9.6 Этап (III)

Схема, приведенная на рис. 9.6, в точности выполняет эти требования. В начальный момент в три рассматриваемых регистра введены соответственно 1, о и вычисленные на этапе Обратная связь во втором регистре осуществляет умножение на и, а обратная связь в третьем регистре — умножение на После одного цикла работы регистры содержат соответственно и выход элемента ИЛИ (внизу рисунка) равен 0 тогда и

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

Спустя один цикл, 1 приходит в точку тогда и только тогда, когда ошибочен символ у 13, и т. д.

Таким образом, на этапе (III) определяются корни многочлена и исправляются ошибки, произошедшие в у.

Декодирование недвоичных кодов БЧХ. Этап (I) совпадает о этапом (I) для двоичных кодов—декодер вычисляет этапе (II) вместо тождеств Ньютона (8.16) надо использовать уравнения (8.13). После нахождения можно использовать уравнение (8.19) для вычисления многочлена значений ошибок со (2). Можно поступить и иначе, используя алгоритм Берлекэмпа для одновременного вычисления многочленов На этапе (III) после нахождения корней многочлена указывающих место ошибок, для вычисления значений ошибок надо использовать уравнение (8.18).

Исправление более чем t ошибок. Описанные выше алгоритмы декодирования позволяют исправлять только или меньшее число ошибок для кодов БЧХ с конструктивным расстоянием Для всех кодов БЧХ, исправляющих две ошибки, и для некоторых кодов, исправляющих три ошибки, известны (см. замечания к гл.) полные алгоритмы декодирования (см. § 1.5); однако следующая задача остается нерешенной.

Задача (нерешенная). (9.3). Найти полный алгоритм декодирования для всех кодов БЧХ.

Упражнение. (5). Для кода БЧХ, исправляющего три ошибки, найти выражение многочлена аналогичное (9.22), в случае, когда произошли ровно три ошибки.