10.5. БЫСТРЫЕ КОДЫ БЧХ

Как мы видели в гл. 9, кодер и декодер для кодов БЧХ обычно содержат два преобразования Фурье. В следующей главе будет показано, что в случае составного использование алгоритмов быстрого преобразования Фурье позволяет существенно уменьшить объем вычислений. Но БПФ-алгоритм Кули-Тьюки

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

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

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

Теорема 10.5.1. В двумерном случае класс сопряженных элементов для содержит такое же число элементов, как и класс

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

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

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

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

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

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

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

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

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

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