7.2. ДЕКОДЕР ПИТЕРСОНА-ГОРЕНСТЕЙНА- ЦИРЛЕРА

Коды БЧХ являются циклическими, и, следовательно, к ним применимы любые методы декодирования циклических кодов. Имеются, однако, существенно лучшие алгоритмы, разработанные специально для декодирования кодов БЧХ. Рассматриваемый в данном параграфе алгоритм впервые был предложен Питерсоном для двоичных кодов (мы опишем его общий случай, разработанный Горенстейном и Цирлером). Доказав, что этот алгоритм позволяет исправлять t ошибок, мы тем самым докажем, что описанное в предыдущем параграфе построение кодов БЧХ приводит к коду, исправляющему t ошибок. Для упрощения уравнений всюду полагается /о = 1, хотя все выкладки без изменения идей могут быть проделаны для произвольного /п.

Предположим, что в основе конструкции кода БЧХ лежит элемент а поля, возможно не примитивный. Многочлен ошибок равен

е {X) = e„ ix"-i + е„.2Х"-2 Н-----h + 0,

где не более t коэффициентов отличны от нуля. Предположим, что на самом деле произошло v ошибок, О < v < f, и что этим ошибкам соответствуют неизвестные позиции ij, ig, Iv Многочлен ошибок можно записать в виде

е{х) = е,/1 + d/ Н----+ ei/\

где - величина /-й ошибки (в двоичном случае е, = 1). Мы не знаем ни i, к, ни е,, е;; в действительности мы даже не знаем числа v. Для исправления ошибок нужно вычислить все эти числа. Чтобы получить компоненту синдрома Si, надо найти значения полученного многочлена в точке а:

Si = &(а) = с(а) -{-е{а) = е(а) = = etakei/A-----h/-

Принятые здесь обозначения слишком громоздки. Для их упрощения определим для всех / = 1, v величины ошибок Yi = и локаторы ошибок Xi = аЧ, где ii - истинное положение 1-й ошибки, а Xi - элемент поля, ассоциированный с этим положением. Заметим, что так как порядок элемента а равен п, то все локаторы рассматриваемой конфигурации ошибок различны.

В этих обозначениях Si запишется в виде

Si = YiX, + + ... + nX,.

Аналогично можно вычислить значения принятого многочлена при всех степенях а, входящих в определение g (х). Для /= 1, 2t определим синдромы равенствами

= V (а/) = с (а/) -f е (а/) = е (ai).

Тогда получим следующую систему из 2t уравнений относительно V неизвестных локаторов Х, Ху и v неизвестных величин ошибок Fj, К:

Si = YiXi 4- KoXg -f- ... + YyXy, S, = Y,X\ + Y,Xl + • • • + YyXl,

S2t = YiXf -{- Y2X2 + • • + Yy/XV.

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

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

Рассмотрим многочлен от х:

Л (х) = A,xv + Ay ix- Н-----{-Aix+l,

известный под названием многочлена локаторов ошибок и определяемый как многочлен, корнями которого являются обратные к локаторам ошибок величины Xj для / = 1, v. Итак,

Л (х) = (1 - xXi) (1 - хХ.) .. (1 - хХ,).

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

Умножим обе части равенства, определяющего этот многочлен, на YiXi" и положим х = ХТ. Тогда левая часть обратится в нуль, и мы получим

О = YiX+ (1 + Л.ХГ + Л2X7 -1- • • • + Av-iX7 + Л.ХГ),

Это равенство выполняется при каждом / и при каждом /. Просуммируем эти равенства по / от 1 до v. Для каждого у это дает

h Yi {ХГ + Л.Х{+- + ... + Л.Х) = 0.

I + Л, i: + ... -f Л, Г i"/X{ 0.

Каждая сумма в левой части последнего равенства является компонентой синдрома, так что уравнение приводится к виду

Так как v < , то для / в интервале 1 <; / <: v все индексы задают известные компоненты синдрома. Таким образом, получаем систему уравнений

AiSj v i + A2S.v-2 Л-----h Ki = - Si+v. / = 1. • . V,

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

Если матрица невырождена, то эту систему можно решить путем обращения матрицы. Докажем, что если произошло v ошибок, то матрица невырождена. Первым шагом этого доказательства служит доказательство невырожденности матрицы Вандермонда.

Теорема 7.2.1. Матраца Вандермонда, определяемая как произвольная матрица вида