п + 1 всегда четно. Если характеристика поля отлична от 2, то квадратный корень из а лежит лгбо в GF (д"), либо в GF (q"). Chirp-алгоритм Блюстейна определяется выражением

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

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

ру- (р-у,) =2J iVi = 5 uJiVi = Vj.

1=0 1=0 i=0

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

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

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

= Ц V,,

п- I п- I

V} = v,+ a}iVi = Н- S (« - 1)г/. / = 1, -. ., n - 1.

Пусть г (i) обозначает единственное для каждого г от 1 до п - 1 целое число, такое, что в поле GF (п) выполняется равенство я<) = i. Функция г (/) является перестановкой на множестве

ft-I

где Vl - Vi и v = vn-k-i - переставленные компоненты входных и выходных последовательностей данных соответственно. Теперь мы поЛучили уравнения для вычисления циклической свертки последовательностей {vk} и - 1}. Таким образом,

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

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

Vj= i]co4-> / = 0, 4.

Это преобразование нужно вычислить в поле GF (16), так как наименьшее т, для которого 5 делит 2" - 1, равно 4. Элемент 2 является примитивным в поле GF (5), и в этом поле имеем равенства

20 2» = 1,

2 = 2, 2-1 = 3,

22 = 4, 2-2 = 4,

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

V[-Voiico-"~-\)vl.

ft=0

1, 2, п - 1}. Тогда Vj может быть записано в следующем виде:

Так как г (i) задает перестановку, можно положить / = г (/) и k = п - 1 -г (i) и выбрать k в качестве индекса суммирования; это дает

Вхо9

0, Vj, t/J Ii

Перестановка вхоЭных символов

Ци}лическая свертка bix)=g(x)a(x) rmod х*-\)

ВыхоЭ

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

Здесь суммирование является четырехточечной циклической сверткой. Полагая коэффициенты gu равными со - 1, фильтр Рейдера можно описать многочленом g {х) над GF [Щ; тогда при со = «8

g {х) = (со - 1) х + (со* -~\)х + (со - 1) л; + (со - 1) =

= аРх + aV -оРх Л- о}.

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

а (х) = Vg} + vx + vx + Vi,

Ъ (x) = (V, - Vo) x + (4 - Vo) x" + (Уз -V,)x + (Vi - П), b (x) = g- (x) a (x) (mod x* - 1).