5 = е.у; {Hi-yA

требует введения некоторых регулирующих вычисление членов, а БПФ-алгоритм Гуда-Томаса - некоторой перестановки адресов. Во избежание этого мы сейчас несколько изменим определение кода БЧХ (что приведет к эквивалентному коду) и назовем полученный вариант кода БЧХ быстрым кодом БЧХ, так как он уменьшает работу декодера. Он приспособлен к алгоритму Гуда- Томаса (который будет рассматриваться в § 112), причем во временной области сохраняется порядок символов, полученный после перестановки

Пусть п = ПхЩ = д" - 1, где П1 и щ взаимно просты, и пусть код состоит из всех двумерных GF (д)-значных временных функций \cii-, i = О, rii - 1, i = О, П2 - 1}, таких, что их двумерные преобразования удовлетворяют проверочным соотношениям

Сц = Саг = = .. . = Cit, 2t = О,

где индексы вычисляются по модулям Пх и соответственно. Это определение задает линейный исправляющий t ошибок код, тривиальным образом отличающийся от кода БЧХ. Скорость и минимальное расстояние остаются без изменений. Неизменяемость скорости вытекает из следующей теоремы.

Теорема 10.5.1. В двумерном случае класс сопряженных элементов для j (mod ni) и j (mod n) содержит такое же число элементов, как и класс j (mod пПд).

Доказательство. Пусть г - наименьшее целое положительное число, такое, что д7 = / (mod ni) и qj = (mod п). Пусть s представляет собой наименьшее целое положительное число, такое, что qj = j (mod пф)- Тогда

qrj апхп. + / и qj = Ьпп + /

для некоторых а и Ь. Очевидно, что такие наименьшие г и s равны. □

Доказательство того, что минимальное расстояние не меньше 2 -f- 1, дается следующей процедурой декодирования / ошибок. Для принятого слова с двумерным преобразованием Х;-,- определим компоненты синдрома равенствами

S/ == V(j mod / mod Пг) / ~ 1,. • ., 2.

Если одиночная ошибка величины е,у- располагается в строке с номером h и столбце с номером if, то

-63-

Пройолженная виагональ

Рис. 10.6. Спектр быстрого кода БЧХ. а - спектр (63, 33, 31)-кода Рида-Соломона; б -двумерный спектр быстрого (63, 33, 31)-кода Рида-Соломона,

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

Si = S YkXi

k=.\

и задают единственное решение, если произошло не более t ошибок. Воспользуемся алгоритмом Берлекэмпа-Месси и его рекуррентным продолжением для вычисления всех Sj, / = 1, п, и положим

E(j mod III, i mod Пг) ~ Sj, j - 1,. . ., tt.

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

и выполняя двумерное обратное преобразование Фурье, завершаем декодирование.

В графической интерпретации вся эта процедура выполняется вдоль продолженной диагонали (пу X пУтаблтцл, показанной на рис. 10.6. На этой продолженной диагонали определяются 2t проверочных частот. Алгоритм Берлекэмпа-Месси работает вдоль продолженной диагонали, и так как Пу и щ взаимно просты то рекуррентное продолжение восстанавливает все элементы таблицы, двумерное преобразование Фурье которой дает таблицу ошибок.

lO.e. ДЕКОДИРОВАНИЕ Л\НОГОЛ1Е1НЫХ КОДОВ 346

10.6. ДЕКОДИРОВАНИЕ МНОГОМЕРНЫХ КОДОВ

Двумерное кодовое слово задается двумерным спектром, у которого некоторые спектральные компоненты равны нулю. Один такой пример был рассмотрен в предыдущем параграфе. Предположим, что код определен так, что для некоторых пар индексов (/*, ]"к), помеченных индексом k, выполняются условия

"l -1 "2 - 1

1=0 i-=0

Тогда соответствующая компонента двумерного синдрома для конфигурации ошибок \ец\ веса / определяется равенством

Iklk l=0

и может быть вычислена по принятому слову \иц-\.

Опишем теперь конфигурацию ошибок, используя строчные локаторы, столбцовые локаторы и величины ошибок. Локаторы в строке ii и столбце 1] определяются соответственно равенствами

Xi = р п Yi = 7. Величину ошибки обозначим Z,. Компоненты синдрома при этом принимают вид

Двумерные коды естественно определять так, чтобы система выписанных выше уравнений была разрешима относительно Xi, Yi и Z; при / = 1, ... t. Например, проверочные частоты можно выбрать так, чтобы получилась следующая система уравнений:

Sii = ZjXiFi -- ZX + • • • + v-vv == -ii

5,2 = Z,X,r? -I- ZXYl -b .. . + Z-,XY% = £,2,

Si, 2t = Z\X)Y\ -j-ZX-2 -f • • ~f~ ZXvYv - £1,

которая уже встречалась в описании алгоритма декодирования кода Рида-Соломона. Имеется только одно отличие: Yi не обязательно различны, так как в одном и том же столбце может произойти несколько ошибок. Можно, однако, сгруппировать ошибки с одинаковыми Yj, и это приведет к аналогичной системе с меньшим V, которое также удовлетворяет условию v < Тогда опять можно воспользоваться алгоритмом Берлекэмпа-Месси и рекуррентным продолжением для вычисления Ец, Е, -Ещ. хотя