z = a"* обратной корню a полинома o{z). Формальная производная находится по формулам (5.68) и (5.69). В данном случае имеем для

GF(2):

если

o{z) = 2 д. 2 =ао +1 +а2 + . - - +

/ = о

(6.16)

а; (2) = Xa.z =1 +Азг + ... + Д21 z2:

где i = int 0,5 (и- 1).

3- Таким образом, на втором этапе находится вектор ошибок Е =

= (л - 1» 2 * • о) Коррекция искаженного кодового вектора по вектору ошибок Е и извлечение сообщения (2 тривиальны - кодовое слово и восстанавливается путем покомпонентного суммирования: и ~ С4 затем при систематическом кодировании из t/исключаются проверочные символы. Оставшиеся символы и образуют Q,

Вернемся еще раз к первому этапу. На этом этапе декодироваш1я вычисляются компоненты синдрома 5. Однако при этом неизвестны не только позиции / и величины е/ ошибок, но даже и их число и. Для нахождения перечисленных величин необходимо решить систему из т нелинейных уравнений:

2 6/.а =5., у = I/, 1 + 1,... ,т + I/ - 1, (6.17)

/ G т

гдеТ= [1,2,...,и"\; ре[ол) •

Приведение системы нелинейных уравнений к ганкелевой (тепли-

ценой) системе линейных уравнений. Назовем величину = а локатором ошибки, действующей на позиции Ц в заданном кодовом слове, где а - примитивный элемент поля GF(q). Составим полином локаторов a(z), корнями которого 5шляются значения Х, обратные локаторам:

а(2) = (1-2X0(1-X2) ... (1 -zX) =

= a„z" + а„ 1 z" - + ... + ai 2 +ао; ао = 1. (6.18)

Степень полинома локаторов (6.18) равна v - числу ошибок и не превышает величины Umax = 0,5m. Будем считать,что длина кода n<q =

= р. Следовательно, среди локаторов Xf = а , О < / < и, не может быть равных, а уравнение локаторов a{z) =0 не имеет кратных корней.

Переобозначим также величины ошибок: €i = . В введенных обозначениях система (6.17) нелинейных уравнений запишется в виде

i - i

/ = 1

(6Л9)

где YiyXi - неизвестные величины, a Sj - известные (вычисленные на первом этапе декодирования) параметры,i = 1,2,... ,u; / = l,2,.,.,m.

Прямые методы решения системы (6.19) нелинейных уравнений неизвестны и используются "обходные" пути, основанные на переходе к ганкелевой (теплицевой) системе линейных уравнений относительно коэффициентов о- полинома локаторов (6.18). Покажем, как это может быть сделано. Подставим в полином (6.18) значение его корня Z =Х[\ при этом полином обратится в нуль. Умножив обе части образовавшегося тождества на УХ/ получим

YioXJ +ох1 + .. . + aiX/+/") =0, (6.20)

где 1 < г < i;; 1 < / < i;.

Просуммируем равенства (6.20) по всем / в диапазоне 1 < / < и, в котором эти равенства выполняются, поскольку полином o{z) имеет V корней Xf \ раскроем скобки и вынесем коэффициенты а,- за знак суммы:

а/ 2 " У.Х/ + о„ / Б " YiX/ + 2 " Yx/ = О, (6.21)

где / = 1,2,.. - ,и.

Согласно формулам (6.19), каждая сумма в равенстве (6.21) является той или иной компонентой синдрома; следовательно, относительно

систему

ных уравнений:

+а„ 1 52 + . + =-5 + 1 при / = 1; 2 + а„ 1 5з + . .. + 5„ +1 = -5 +2 при / = 2; 22)

Ou5ij +Ov +1 + ... + Oiiu - 1 = -S2V при /

При использовании полей GF(2) знаки минус в правых частях уравнений (6.22) опускаются. Полученная система является ганкелевой

и ей соответствует расширенная ганкелева* матрица типа (2.21) размера и X (и + 1), имеющая вид

, v<0m. (6.23)

Матрица (6-23) не вырождена, если число и ошибок, в действительности внесенных в кодовое слово Uy строго равно и, где и < 0,5 (л - к), т. е. способность по помехоустойчивости для данного кода не нарушена. Заметим, что подобная ганкелева система уравнений получается при декодировании не только РС-кодов, но и более широкого класса кодов - кодов БЧХ [36, 40].

Методы решения ганкелевой (тешшцевой) системы линейных уравнений. Так как матрица (6.23) не вырождена (до тех пор, пока число ошибок не превьппает заданного предела), то система уравнений (6-22) однозначно разрешима и задача решенця этой системы сводится в конечном счете к обращению соответствующей ганкелевой (теплицевой) матрицы. В настоящее время весьма интенсивно разрабатываются

методы обращения матриц над бесконечными полями [7, 18, 42]. При декодировании кодов над конечными полями наибольшее распространение получили следующие методы решения ганкелевой (теплицевой) системы уравнений:

1) прямой, или определительный, метод, назьюаемый также методом Питерсона - Горенштейна - Цирлера [5, 6, 22, 40];

2) итеративный метод Тренча - Берлекэмпа - Месси (ТБМ-метод), получивший наибольшее применение на практике [8, 62];

3) метод Сугиямы, основанный на алгоритме Евклида и пригодный для декодирования не только БЧХ- и РС-кодов,но и ряда других альтер-нантных кодов [61].

Суть первого метода состоит в вычислении ряда угловых квадратных определителей для матрицы (6.23) и нахождении ее ранга. Затем система уравнений решается каким-либо стандартным способом: методами Крамера, Гаусса, обращения матриц и др.

В работе [5] показано, что результаты промежуточнь1Х вычислений угловых определителей могут быть использованы также для нахождения величин ошибок. К сожалению, прямой метод практически целесообра-

Если изменить порядок слагаемых в уравнениях (6.22) на обратный, то по-

лучим теплицеву матрицу.