10.7. ДЛИННЫЕ КОДЫ НАД МАЛЫМИ ПОЛЯМИ

Для кодов с очень большой длиной и высокой скоростью сложность декодера может являться более важным фактором, чем скорость кода. С практической точки зрения разница между скоростями 0,98 и 0,99 может быть не столь уж существенной,

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

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

Первым примером является произведение двух кодов БЧХ, а именно -кода и -кода, и, следовательно, является кодом с параметрами Например, произведение расширенного -кода Рида-Соломона на самого себя дает (65 536, 53 824, 625)-код над который позволяет исправлять -битовых байтов, пакеты длины -битовых байтов, а также многие конфигурации ошибок более чем из 312 байтов. Вместо этого можно воспользоваться (65 536, 64 289, 625)-кодом БЧХ, который позволяет также исправлять 312 случайных байтов и обеспечивает при этом существенно большую скорость, но его декодирование требует вычислений в -битовой арифметике поля Код-произведение компенсирует это другим преимуществом, позволяя помимо 312 случайных байтов исправлять многие другие конфигурации ошибок, чего не может код БЧХ. Декодировать код-произведение можно описанным в § 10.3 способом.

Второй пример дается кодом, дуальным к коду-произведению двух кодов Рида Соломона или их подкодов над подполями. Дуальный код исправляет случайные ошибки, а также конфигурации многократных иизкоплотпостных пакетов, определяемых как конфигурации, состоящие из сегментов ошибок, вес которых больше типичного. Исправляющие многократные низко-плотностные пакеты ошибок коды полезны для тех каналов, в которых происходит ритмичное изменение вероятности ошибки, например для каналов с замиранием.

В частности, дуальный к квадрату (255, 239, 25)-кода Рида-Соломона код представляет собой (65 025, 64 769, 17)-код

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

Двумерные проверочные частоты этого кода задаются парами для Основанная на теореме 10.6.1 процедура декодирования сводится к следующему. По данному принятому слову вычисляются компоненты синдрома по формулам

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

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

где число ошибок в столбце. Ксли с 8 для каждого то эта система уравнений может быть решена с помощью алгоритма Берлекэмпа-Месси, что завершает декодирование.

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

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

(кликните для просмотра скана)

с можно было бы вычислить все компоненты синдрома. Тогдв, согласно теореме 10.4.2, можно будег вычислить и остальные компоненты синдрома.

Для построения кода, исправляющего восемь ошибок, надо соответствующим образом выбрать 128 проверочных частот. Сначала выберем в качестве проверочных частот пары , так что Все выбранные так проверочные частоты лежат в разных классах сопряженных элементов, и каждый класс содержит восемь элементов, так что каждая из этих частот эквивалентна восьми проверочным битам. Если произошло не более ошибок, то вычисленные в этих частотах компоненты синдрома могут быть продолжены до компонент Далее, используя ограничения сопряженности для этой верхней строки, заполняем строки с номерами 2, 4, 8 и 16. Выберем теперь в качестве проверочных частот пары Это дает еще 16 X 8 проверочных битов. Вычисление компонент синдрома в третьей строке дает также значения компонент синдрома в строках 6 и 12.

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

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

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

Берлекэмпа-Месси для заполнения всех входов таблицы Обратное двумерное преобразование Фурье завершает декодирование. Более простой процедурой является следующая. Вычислим одномерное обратное преобразование Фурье для известных строк символов Это лает множество из компонент синдрома для каждого столбца; ненулевые компоненты могут иметь не более столбцов и только к ним необходимо применить алгоритм Берлекэмпа-Месси.

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

ЗАДАЧИ

(см. скан)

ЗАМЕЧАНИЯ

Произведение кодов ввел Элайс [1954], доказавший, что минимальное расстояние кода-произведения равно произведению минимальных расстояний исходных кодов. Бартон и Узлдон [1965] доказали, что при взаимно простых длинах произведение двух циклических кодов является циклическим кодом. В этой же работе изучалось исправление пакетов ошибок и независимых ошибок кодами-произведениями. Методы декодировании кода-произведении описали Рета и Робинсон [1972], а также Уэлдоп [1971] В § 10.4-10.6 развиваются идеи автора (Блейхут [1979]). Использовать дуальный код-произведение для кратных низкоплотностных пакетов предложили Чень и Но [1973|