5.5.2. Принципы декодирования кодов бчх
Коды БЧХ относятся к классу циклических, что позволяет применять для их декодирования любые методы, разработанные для циклических кодов. Однако для кодов БЧХ получены специальные эффективные методы декодирования, называемые алгебраическими.
Для
уяснения принципа декодирования этими
методами обратимся к двоичным кодам
БЧХ 
,
исправляющим двукратные ошибки 
.
В соответствии с (5.25) и (5.26) эти коды можно задать при помощи проверочной матрицы
|
(5.27) |
.
и
порождающего полинома 
имеющего
своими корнями элементы конечного
поля
.
Последовательность
принятых символов 
описывается
многочленом 
степени
,
который можно представить через
порождающий многочлен
следующим
образом:
|
|
.
где 
–
полином степени
,
соответствующий вектору ошибки (см.
5.4.1) 
.
Векторы
исправляемых ошибок кратности 
представляются
полиномом
|
|
.
В
двоичном случае ненулевые компоненты
вектора ошибки 
и 
равны
1, поэтому задача декодирования кода
БЧХ, исправляющего двукратные ошибки,
сводится к определению номеров
и
позиций
ошибочных символов в принятом слове
.
При этом оценка 
переданного
кодового слова
может
быть получена в виде 
,
где 
–
оценка вектора ошибки, а 
–
знак суммирования по модулю 2.
Как
будет видно из дальнейшего изложения,
более удобно пользоваться не
значениями
и
,
а однозначно связанными с этими номерами
некоторыми элементами
и
конечного
поля
,
причем 
, 
.
Поскольку порядок примитивного
элемента
равен
длине кодового слова
,
то элементы
и
действительно
однозначно сопоставляются номерам
и
.
Значения
и
принято
называть локаторами, т.е. указателями
искаженных позиций последовательности
символов
.
Процедура декодирования двоичного кода БЧХ начинается с вычисления синдрома
|
(5.28) |
,
являющегося 
-символьной
комбинацией: 
.
В соответствии с (5.14) и (5.19)
|
|
,т.е. синдром не зависит от принятой комбинации , а определяется только вектором ошибки .
Подставив в (5.28) матрицу (5.27) кода БЧХ, получим
|
|
.
Поскольку
при максимальной заданной кратности
ошибок 
вектор
имеет
лишь два ненулевых компонента на позициях
с номерами
и
,
то
|
|
.Используя введенные выше локаторы и получим следующую систему уравнений:
|
(5.29) |
.Теперь можно указать один из путей решения задачи декодирования кода БЧХ, исправляющего двукратные ошибки. Действительно, по принятой комбинации символов в соответствии с (5.28) можно вычислить значение синдрома. Тогда система (5.29) будет содержать два линейно-независимых уравнения с двумя неизвестными и , а значит, может быть решена (в конечном поле относительно этих неизвестных.
Для
отыскания локаторов
и
оказывается
удобным преобразовать систему (5.29) с
тем, чтобы свести задачу к поиску корней
некоторого многочлена: 
,
где учтено, что вычитание в
равносильно
сложению.
Преобразуем второе уравнение системы (5.28):
|
|
.
Теперь
квадратное уравнение представимо в
виде 
.
Решая его, можно найти значения
локаторов
и
,
однако по причинам, которые будут
изложены в 5.5.3, отыскиваются корни
уравнения
|
|
.
Многочлен
в левой части уравнения называется
многочленом локаторов ошибок. Корни
этого многочлена 
и 
являются
обратными к локаторам, т.е. 
и 
.
Обычно
многочлен локаторов ошибок обозначается 
и
имеет вид
|
|
,
где
–
вес вектора ошибки 
.
В
рассматриваемом случае коэффициенты
этого многочлена равны соответственно 
; 
; 
.
Наконец,
для решения задачи декодирования
двоичного кода БЧХ необходимо отыскать
корни
и
многочлена
локаторов ошибок с известными
коэффициентами 
, 
и 
.
Очевидно, это можно сделать, вычисляя
его значения при 
,
равном всем ненулевым элементам
.
Следует отметить, что стратегия декодирования, изложенная на примере двоичного кода БЧХ, исправляющего только ошибки до кратности 2, с успехом может быть обобщена и использована для случая кодов БЧХ, исправляющих произвольную кратность ошибок.
Декодирование
недвоичных кодов БЧХ 
представляет
собой более сложную задачу. Это обусловлено
тем, что при декодировании таких кодов
необходимо не только определить номера
символов, в которых произошла ошибка,
но и вычислить
-ичные
значения компонентов вектора ошибки
.
Особенности выполнения этих операций
применительно к
-ичным
кодам Рида-Соломона приведены в следующем
разделе.