10.7. ДЛИННЫЕ коды НАД Л\АЛЫЛ\И ПОЛЯЛ\И 349

над GF (256) и исправляет все случайные конфигурации ошибок из восьми 8-битовых байтов, а также все конфигурации ошибок из 64 8-битовых байтов, образующие низкоплотностные пакеты из восьми искаженных столбцов, каждый из которых содержит восемь искаженных байтов.

Двумерные проверочные частоты этого кода задаются парами (/, /) для / = 1, 16 и / = 1, 16. Основанная на теореме 10.6.1 процедура декодирования сводится к следующему. По данному принятому слову \vii-} вычисляются компоненты синдрома Sjj по формулам

255 255

Sir = 2] S afarvlr, j, г = 1,. .., 16.

г=0 i=0

Алгоритм Берлекэмпа-Месси с последующим рекуррентным продолжением используется для вычисления всех компонент синдрома в /-Й строке.

После такой обработки в декодере каждой из 16 строк оказываются вычисленными компоненты Зц- синдрома для / = = 1, 255 и / = 1, 16. Обратное преобразование Фурье каждой из этих 16 строк содержит ненулевые символы только в тех восьми (или менее) столбцах, которые содержат ошибки. Пометим эти восемь столбцов. Преобразование Фурье этих 16 строк в каждом из помеченных восьми столбцов дает 16 элементов Т/* поля i = 1, 255, / = 1, 16. Стоящие в г-м столбце элементы этого поля можно выразить через величины ошибок и строчные локаторы для этого столбца:

гр> = z{> + z> (хП + ... + z<?o {х[%,У,

где V (i) - число ошибок в i-ш столбце. Если v (i) <: 8 для каждого i, то эта система уравнений может быть решена с помощью алгоритма Берлекэмпа-Месси, что и завершает декодирование.

Можно также построить код, дуальный к коду-произведению для кодов БЧХ. Но такие коды содержатся в более мощных кодах с тем же минимальным расстоянием и той же способностью исправлять низкоплотностные пакеты «ошибок. В общем случае предпочтительнее эти последние коды; опишем их.

Для иллюстрации этой идеи рассмотрим частный случай двоичного кода с / = 8, п = 255 и длиной == 65 025. Как показано на рис. 10.7, а, выберем проверочные частоты так, чтобы в блоке

17 18 19 20 21

Рис. 10.7. Двумерные проверочные частоты, а - расположение проверочных символов по строкам; б - другой выбор проверочных символов.

10.7. ДЛИННЫЕ коды НАД МАЛЫМИ ПОЛЯМИ 351

с у = 1, 2/ и j = \, 2t можно было бы вычислить все компоненты синдрома. Тогда, согласно теореме 10.4.2, можно будет вычислить и остальные компоненты синдрома.

Для построения кода, исправляющего восемь ошибок, надо соответствующим образом выбрать 128 проверочных частот. Сначала выберем в качестве проверочных частот пары (1, 1), (1, 2), .... (1, 20, так что Сц = Cia = ... = Ci,2t = 0. Все выбранные так проверочные частоты лежат в разных классах сопряженных элементов, и каждый класс содержит восемь элементов, так что каждая из этих частот эквивалентна восьми прове-рочным битам. Если произошло не более = 8 ошибок, то вычисленные в этих частотах компоненты синдрома могут быть продолжены до компонент 5i/-, / = 1, п. Далее, используя ограничения сопряженности для этой верхней строки, заполняем строки с номерами 2, 4, 8 и 16. Выберем теперь в качестве проверочных частот пары (3, 1), (3, 2), (3, 2t). Это дает еще 16 X 8 проверочных битов. Вычисление компонент синдрома в третьей строке дает также значения компонент синдрома в строках 6 и 12.

Продолжая таким образом, выберем все приведенные на рис. 10.7 проверочные частоты. Это дает возможность вычислить все компоненты синдрома для частот, заполняющих угловой квадрат 2t X 2t, а тем самым и все компоненты синдрома (напомним, что произошло не более / ошибок). Каждый проверочный символ эквивалентен восьми проверочным битам, так что всего получаем 1024 проверочных битов. Таким образом построен (65 025, 64 001, 17)-код, характеристики которого лучше, чем у (65 535, 65 407, 17)-кода БЧХ. Достоинство этого кода состоит в том, что, несмотря на его большую длину, для него существует сравнительно простой алгоритм декодирования, позволяющий исправлять большое число пакетов ошибок (такой алгоритм будет сейчас описан).

Декодер для этого кода аналогичен описанному ранее. По принятому двумерному слову вычисляется двумерное преобразование Фурье в 128 проверочных частотах. Это дает спектральные компоненты Ej,- вектора ошибок в проверочных частотах. Покажем, как по этим известным компонентам вычислить остальные компоненты спектра ошибок. Результат применения алгоритма Берлекэмпа-Месси к первой строке рекуррентно продолжим на все 255 компонент этой строки и, используя ограничения сопряженности, заполним строки с номерами 2, 4, 8 и 16. То же самое проделаем с третьей строкой, заполняя строки с номерами 3, 6 и 12. Повторим вычисления для пятой строки и т. д. до тех пор, пока не будут заполнены 2t строк.

После заполнения 2t строк начинается декодирование столбцов. Один из способов состоит в использовании алгоритма Бер-