Многочлен g {х) фиксирован. Многочлен а (х) получается из многочлена v (х) отбрасыванием первого коэффициента и перестановкой остальных. Коэффициенты многочлена V (х) получаются из коэффициентов многочлена b (х) в естественном порядке. Алгоритм приведен на рис. 9.10. Для выполнения циклической свертки можно выбрать любой удобный метод.

В заключение данного параграфа приведен алгоритм вычисления преобразования Фурье в поле Галуа, основанный на том, что элемент конечного поля содержит в этом поле много сопряженных элементов. Выполнение этого алгоритма требует около п log п умножений в GF [q"), но также около сложений; поэтому он называется полубыстрым алгоритмом. Он представляет собой аналог в конечном поле алгоритма вычисления комплексного преобразования Фурье, известного в теории обработки дискретных сигналов под названием алгоритма Герцеля. Этот алгоритм требует не более log п умножений и п log п сложений символов поля для вычисления одной спектральной компоненты. При вычислении всех компонент спектра это приводит не более чем к п log п умножениям и log п сложениям элементов поля.

Величина Vj = Цгаиг, /-я компонента преобразования Фурье, представляет собой значение многочлена v (х) в точке ai. Пусть /; (х) обозначает минимальный многочлен элемента ai. Степень mj этого многочлена не превосходит т. Можно записать

V (х) = fj {х) Q (X) + г W,

и, следовательно,

V (ai) = fj (ai) Q (ai) + r (ai) = r (ai).

Таким образом, для вычисления Vj надо разделить v (х) на fj (х) и вычислить значение полученного остатка г (х) в точке ai. Поскольку fj (х) - многочлен степени mj над полем GF (q), деление на fj (х) требует (п - mj) mj умножений элементов поля GF (q") на элементы поля GF (q) и (п - mj) mj сложений в поле GF ((?"). Степень многочлена-остатка г (х) не превосходит mj - 1, так что вычисление величины г (ai) требует mj - 1 умножений и столько же сложений в GF (q"). Следовательно, одну компоненту Vj можно вычислить по V (х) с помощью m - 1 умножений в поле GF (q"), (п - mj) т умножений элементов поля GF (q") на элементы поля GF (q) и (п - m• + 1) mj- - 1 сложений в поле GF

Поскольку преобразованный вектор содержит п компонент, такие вычисления нужно проделать п = q" - 1 раз, что дает не более т {q< - 1) умножений в поле GF (q). Если два элемента сопряжены, то они имеют общий минимальный многочлен и, следовательно, общий остаток г (х). Поэтому нет необходимости каждый раз вычислять промежуточный многочлен г (х), а можно вычислить его один раз для всего класса сопряженных элементов.

ЗАДАЧИ 323

в частности, если q = 2, то необходимое число умножений в поле GF (2") не превосходит п log, (л + 1). В отличие от алгоритма быстрого преобразования Фурье это остается верным даже тогда, когда 2*" - 1 является простым числом. С другой стороны, число сложений не превосходит величины (п - I) п + т (п - 1) = = + пт - 2п, так что необходимое число сложений является величиной О (п).

Если входной вектор принадлежит малому полю GF (q), то его преобразование (хотя оно является вектором в поле GF (q")) может быть вычислено без умножений в поле GF [q"). Это происходит потому, что в таком случае v [х) является многочленом над GF (q) и вычисление величины Vj сводится к умножению элементов из GF (q) на элементы из GF (?"). Например, если q = 2, то это означает сложение элементов из GF (2"), выбираемых в соответствии с ненулевыми компонентами многочлена г (х). Таким образом, для двоичного кода синдром вычисляется без всяких умножений в поле GF (2") не более чем с п log п сложениями в GF (2) и неболее чем с logn сложениями в GF (2").

ЗАДАЧИ

9.1.а. Построить декодер для (15, 8)-кода Препараты, дополняя алгоритм Берлекэмпа-Месси для двоичного случая еще одной итерацией.

б. Используя результат, полученный в п. а, построить декодер для кода Препараты во времениой области.

9.2. Описать, как исправлять стирания в принятом слове с 2t стираниями, дважды используя декодер для исправления только ошибок в двоичном коде. Как использовать такой декодер для одновременного исправления ошибок и стираний?

9.3. Заново решить задачу 7.3.6 из гл. 7, используя описанный в § 9.1 алгоритм Евклида.

9.4. Построить блок-схему декодера ошибок и стираний во временной области.

9.5. Построить блок-схему декодера во временной области для расширенного на одну позицию кода Рида-Соломона.

9.6. Если допустить возможность выполнения обратного преобразования Фурье для Q (х) и Л (х), то во временной области можно построить декодер с 2t тактами работы, использующий алгоритм Форни. Выписать итеративные уравнения для вычисления многочленов й (х) и Л (х), аналогичные итеративному алгоритму Берлекэмпа-Месси. Использовать обратное преобразование Фурье этих уравнений для построения декодера с 2t тактами работы во временной области.

9.7. Построить алгоритм Фории для произвольного /о, комбинируя решение задачи 8.1 и утверждение теоремы 7.5.2.

9.8. Выписать полностью уравнения пятиточечного преобразования Фурье в поле GF (16), вычисляемого по алгоритму Рейдера. Построить диаграмму перестановки компонент векторов и блок-схему КИО-фильтра с указанием весовых множителей.

9.9. Использовать алгоритм Герцеля для вычисления в поле GF (8) преобразования Фурье вектора, задаваемого многочленом

V (х) = аЗд« + ах. + х*+ ах +aV х+1.

ЗАМЕЧАНИЯ

Предложенный Ридом и Соломоном [1960] метод декодирования аналогичен описанному в данной главе методу декодирования в частотной области, но первоначально он разрабатывался для временной области. Для частотной области декодер впервые предложил Мандельбаум [1971], хотя он использовал терминологию китайской теоремы об остатках. Программная реализация такого декодера была сделана Пашбургом [1974].

Первое обсуждение декодирования со спектральной точки зрения можно найти у Гора [1973]. Он заметил, что информация может быть закодирована в частотной области и что спектр вектора ошибок можно вычислять с помощью рекуррентного продолжения. Реализация декодеров с преобразованиями областей рассматривалась также Михельсоном [1976]. Общее обсуждение спектральных методов декодирования можно найти у Блейхута [1979]. Отображение этих декодеров обратно во временною область было проведено в работах Блейхута [1979, 1980]. Оайзванный на алгоритме Евклида метод декодирования предложен Мандельбаумом [1977].

Замечания о канале со стираниями принадлежат Элайсу [1954]. Ранние работы по обобщению алгоритмов декодирования кодов БЧХ на случай не только ошибок, но и стираний выполнены Блюмом и Вейсом [1960], а также Форни [1965]. Описанный в настоящей главе подход принадлежит Блейхуту [1979].

Декодирование расширенных кодов было впервые описано в работах Вулфа [1969] и Касахары с соавторами [1975]. Описанный в настоящей главе вариант принадлежит Блейхуту [1980]. Декодирование альтернантных кодов и кодов Гоппы разработано Паттерсоном [1975] и Хельгертом [1977]. Дельсарт [1975] указал, что эти коды можно декодировать с помощью декодера для кодов Рида- Соломона.

Декодирование за пределами границы БЧХ предложили Берлекэмп [1968], Хартман [1972] и Блейхут [1979]. Алгоритм полного алгебраического декодирования кодов БЧХ с исправлением двух ошибок описан Берлекэмпом [1968], а алгоритм полного алгебраического декодирования некоторых кодов БЧХ с исправлением трех ошибок-Вандерхорстом и Бергером [1976].

Алгоритмы Блюстейна [1970], Рейдера [1968] и Герцеля [1958] были предложены этими авторами в связи с задачами дискретной обработки комплексно-значных сигналов. Дополнительные сведения об этих алгоритмах можно найти в монографиях Оппенгейма и Шафера [1975] или Рабииера и Голда [1975]. Сервейт [1978] предложил свой вариант полубыстрого алгоритма.