9.8. ВЫЧИСЛЕНИЕ ПРЕОБРАЗОВАНИЙ В КОНЕЧНЫХ ПОЛЯХ

Рассмотрим преобразование Фурье

где а — элемент порядка в ноле Для малых значений его можно вычислять в том виде, в каком оно записано, но так как вычисление содержит умножений, то оно становится практически неприемлемым при больших длинах. Необходимы эффективные методы вычисления преобразования Фурье, и мы располагаем некоторыми такими методами Одним из наиболее мощных методов, пригодных для многих значений длин, является переход от одномерного преобразования к многомерному преобразованию Фурье. Все такие методы известны под общим названием быстрого преобразования Фурье. Изучение этих методов мы отложим до гл. 11; в этом же параграфе мы рассмотрим другие методы вычисления преобразования Фурье, а именно chirp-алгоритм Блюстейна, алгоритм Рейдера для простых значений длин преобразования и алгоритм Герцеля.

Представлепные на рис. 9.9 алгоритмы Блюстейна и Рейдера являются различными способами перехода от преобразования Фурье к свертке; первый из них переводит точечное преобразование Фурье в -точечную свертку, а второй (который применяется в случае, когда простое число) переаодит -точечное преобразование Фурье в -точечную свертку.

Во всех случаях, когда элемент а. имеет квадратный корень, может использоваться chirp-алгоритм Блюстейна. Согласно теореме 4.6 15, каждый элемент поля Галуа имеет квадратный корень. Для полей характеристики так как

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

и всегда четно. Если характеристика поля отлична от 2, то квадратный корень из а лежит либо в либо в

Chirp-алгоритм Блюстейна определяется выражением

где квадратный корень из а.

В этом варианте преобразования Фурье производятся следующие вычисления:

Заметим, что chirp-преобразование состоит из поточечного умножения на (я умножений) с последующей циклической сверткой (КИО-фильтр с отводами), за которой снова следует поточечное умножение на ( умножений). Поэтому полное число операций по-прежнему имеет порядок так что chirp-алгоритм асимптотически не эффективнее прямого преобразования Фурье. Однако в некоторых приложениях он допускает более простую аппаратурную реализацию. Кроме того, как будет показано в § 11.1, прямое вычисление свертки можно заменить алгоритмом быстрой свертки.

Алгоритм Рейдера можно использовать для вычисления преобразования Фурье в произвольном поле если только длина является простым числом. Так как я — простое число, можно использовать структуру поля Это простое поле не следует путать ни с полем ни с любым ограничением или расширением этого ноля.

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

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

Тогда может быть записано в следующем виде:

Так как задает перестановку, можно положить и выбрать к в качестве индекса суммирования; это дает

или

где переставленные компоненты входных и выходных последовательностей данных соответственно. Теперь мы получили уравнения для вычисления циклической свертки последовательностей Таким образом, переставляя индексы входных и выходных данных, мы записали преобразование Фурье в виде свертки. Как видно из формул, необходимое для вычисления число операций опять имеет порядок Однако, так же, как и для алгоритма Блюстейна, свертка может быть вычислена при помощи алгоритма быстрой свертки, который будет описан в § 11.1.

Используя алгоритм Рейдера и равенство построим двоичное пятиточечное преобразование Фурье; задача состоит в вычислении величин

Это преобразование нужно вычислить в поле так как наименьшее для которого 5 делит равно 4. Элемент 2 является примитивным в поле и в этом поле имеем равенства

задающие перестановку индексов. Таким образом,

Рис. 9.10. Вычисление пятиточечного преобразования Фурье с помощью алгоритма Рейдера.

Здесь суммирование является четырехточечной циклической сверткой. Полагая коэффициенты равными фильтр Рейдера можно описать многочленом над ; тогда при

Вход и выход фильтра также можно описать многочленами, коэффициенты которых задаются соответственно переставленными компонентами векторов

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

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

Величина компонента преобразования Фурье, представляет собой значение многочлена в точке а. Пусть обозначает минимальный многочлен элемента Степень этого многочлена не превосходит Можно записать

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

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

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

В частности, если то необходимое число умножений в ноле не превосходит В отличие от алгоритма быстрого преобразования Фурье это остается верным даже тогда, когда является простым числом. С другой стороны, число сложении не превосходит величины так что необходимое число сложений явлиется величиной

Если входной вектор принадлежит малому полю то его преобразование (хотя оно является вектором в поле может быть вычислено без умножений в ноле Это происходит потому, что в таком случае является многочленом над и вычисление величины сводится к умножению элементов из на элементы из Например, если то это означает сложение элементов из выбираемых в соответствии с ненулевыми компонентами многочлена Таким образом, для двоичного кода синдром вычисляется без всяких умножений в поле не более чем с сложениями в и не более чем с сложениями в

ЗАДАЧИ

(см. скан)

ЗАМЕЧАНИЯ

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

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

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

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

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

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