Глава 10. Недвоичное обобщение Горенстейна-Цирлера БЧХ-кодов в случае метрики Хэмминга

10.1. Обобщенные БЧХ-коды и алгоритм их декодирования

Циклические коды над где степень произвольного простого числа, определяются точно так же, как и циклические коды над . В качестве порождающего многочлена выбираются некоторые делители многочлена над Кодовые слова исчерпываются всеми кратными порождающего многочлена, степень которых меньше, чем Как и в двоичном случае, порождающий многочлен -ичного БЧХ-кода, исправляющего ошибок, с блоковой длиной равен произведению различных минимальных многочленов элементов где а — примитивный корень степени из единицы над где — мультипликативный порядок числа Поле называется полем символов, полем локаторов.

Такое обобщение БЧХ-кодов на недвоичный случай впервые было предложено Горенстейном и Цирлером [1961]. Частный случай рассматривался ранее с другой точки зрения Ридом и Соломоном [1960].

Если кодер передает кодовое слово, символы которого совпадают с коэффициентами многочлена

а в канале к нему добавляется вектор шума, заданный многочленом

то декодер получает слово

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

Заметим, что БЧХ-код с исправлением ошибок строится таким образом, что являются корнями порождающего многочлена кода и, следовательно, корнями любого кодового многочлена. Таким образом, первым шагом процедуры декодирования БЧХ-кодов является вычисление суммы для

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

Второй многочлен, так называемый многочлен значений ошибок, задается равенством

Заметим, что определения 10.11 и 10.12 в двоичном случае сводятся к определениям 7.21 и 7.22. В противоположность многочлену локаторов ошибок для негациклических кодов, рассмотренных в гл. 9, многочлен локаторов ошибок (10.11) не имеет кратных корней. Ностепень многочлена локаторов ошибок (10.11) равна числу ошибок в метрике Хэмминга, подобно тому, как степень многочлена локаторов ошибок в гл. 9 равна числу ошибок в метрике Ли и степень многочлена ошибок (7.21) равна числу ошибок в двоичном канале. Отметим также, что многочлен значений ошибок (10.12) зависит и от локаторов и от значений ошибок, в то время как многочлен локаторов ошибок (10.11) зависит только от локаторов ошибок.

Так как то можно определить производящую функцию отношения Ее коэффициенты задаются соотношением

где Значит,

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

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

Декодер может решить это уравнение относительно многочленов и используя алгоритм 7.4. Это дает второй шаг процедуры декодирования.

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

Найдя локаторы ошибок, декодер может вычислить значение многочлена в точке

Таким образом, на четвертом шаге процедуры декодирования декодер определяет ошибки в соответствии с формулой

Знак для обозначения взаимного многочлена не следует путать со знаком которым мы обозначили нечетную часть функции.

Подытожим описанную процедуру декодирования для недвоичных БЧХ-кодов в виде алгоритма 10.15.

10.15. Алгоритм декодирования.

10.151. Определить взвешенные степенные симметрические функции по формулам где остаток от деления полученного многочлена на минимальный многочлен элемента над

10.152. Составить ключевое уравнение (10.13) для найденной функции и решить его, согласно алгоритму 7.4, относительно многочленов

10.153. Используя процедуру Ченя определения корней степени из единицы над найти взаимные корни многочлена локаторов ошибок Это определит локаторы ошибок.

10.154. По формуле (10.14) найти значения ошибок.