s[x) = g (х) d (х), выписывая многочлены d (х), з{х) и g (л) через компоненты векторов v и V и элемент ш.

Показать, что использование для вычисления линейной свертки двух последовательностей длины п/2 алгоритма Кука - Тоома с п. точками pj = (e ) приводит к тому же самому алгоритму, что и использование преобразования Фурье и теоремы о свертке.

Указать две различные причины того, что сочетание алгоритма Рейдера для простых чисел с алгоритмом Винограда вычисления свертки приводит к лучшему БПФ-алгоритму, чем сочетание алгоритма Блюстейна с алго-pin-MOM Винограда вычисления свертки. Можете ли Вы указать третью причину?

Найти простые целые числа лип, такие что л < л, но п-точечный БПФ-алгоритм Винограда содержит больше умножений, чем л-точечный БПФ-алгоритм Винограда.

Сколько умножений содержит 25-точечный БПФ-алгоритм Винограда, если все составляющие свертки оптимальны? Как это соотносятся с процедурой, основанной на алгоритме Кули - Тьюки, сочетающем два 5-точечных БПФ-алгоритма Винограда?

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

Даны вычисляемые непосредственно 2-точечное и 5-точечное преобразования Фурье (с 4 и 25 умножениями соответственно).

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

4.7. 4.8.

4.9. 4.10

Использовать всюду, где можно, алгоритм Гуда - Томаса: в других случаях использовать алгоритм Кули - Тьюки. Найти число умножений, включая тривиальные (на ±1, ±/).

б. Найти число умножений без учета тривиальных умножений на ±\, ±j.

в. Теперь предположим, что имеется подпрограмма вычисления 2-точечного преобразования Фурье без нетривиальных умножений и подпрограмма 5-точечного преобразования Фурье с пятью (нетривиальными) умножениями. Повторить п. б) задачи.

4.12. Из того, что возникающие в алгоритме Рейдера свертки вычисляются оптимальными алгоритмами, еще не вытекает оптимальность БПФ-алгоритма Винограда. Это следует и из того, что коэффициенты фильтра Рейдера не произвольные числа, а степени элемента to, которые, вообще говоря, могут оказаться зависимыми, и эта зависимость может быть использована для уменьшения числа умножений, А именно, мы видели, что комплексные умножения сводятся к вещественным и иногда коэффициенты оказываются равными нулю. Доказать, что 5-точечный БПФ-алгоритм Винограда оптимален по критерию числа умножений.

4.13. 16-точечный БПФ-алгоритм Винограда содержит 18 умножений, 8 из которых тривиальны, и 74 сложения.

а. Построить 256-точечный БПФ-алгоритм, используя для построения 16-точечный БПФ-алгоритм Винограда и алгоритм Кули - Тьюки.

б. Сколько умножений потребуется, если входные данные вещественны?

в. Сколько умножений потребуется, если входные данные комплексны?

Замечания

В цифровой обработке снгналов алгоритмы быстрого преобразования Фурье начали широко использоваться в результате работы Кули и Тьюки [1) (1965) и близкой к ней работы Синглтона [2] (1969). Однако другие алгоритмы БПФ, основанные на китайской теореме об остатках, появились в более ранних работах Гуда [3] (1960) и Томаса [4] (1963). Различия в этнх работах были описаны Гудом [5] (1971). Эффективная организация алгоритма Кули - Тьюки была предложена Рейдером и Бреннером [6] (1976) и модифицирована Преусом 7] (1982). Рейдер [81 (1968) иБлюстейн [9] (1970) описали метод сведения преобразования Фурье к свертке. Целью работы Рейдера было вычисление дискретного преобразования Фурье, длина которого равна большому простому числу; но, по иронии судьбы, этот метод оказался наиболее важным для длин, равных малым простым числам. Обобщение алгоритма Рейдера на случай длин, равных степени простого числа, было сделано Виноградом [П] (1978).

БПФ-алгоритм Винограда был анонсирован в работе [10] в 1976 г. и с подробностями опубликован в 1978 г. Наше изложение не отражает всей значимости оригинальной работы; развитие ее результатов включено в другие темы. Мы затабулировали те БПФ-модули для малых длин, которые представляются нам наиболее полезными. БПФ-модули для больших длин были построены Джонсоном и Баррасом (12] (1981). Другие методы вычисления преобразования Фурье изучались Герцелем [131 (1968) и Сервейтом [141 (1978).

ТЕОРИЯ ЧИСЕЛ

И АЛГЕБРАИЧЕСКАЯ

ТЕОРИЯ ПОЛЕЙ

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

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

5.1. Элементарная теория чисел

В кольце целых чисел Zq по модулю q некоторые элементы взаимно просты с 7, а некоторые делят q. Нам важно знать, сколько именно элементов относится к каждому типу.

Определение 5.1.! (Эйлер). Функция Эйлера, обозначаемая ф (q), для q > 1 определяется как число ненулевых элементов в Zq, взаимно простых ч q; <f (q) = \ для i; = 1.

Если q = р простое, то все ненулевые элементы кольца Zq взаимно просты с q, так что ф (р) = р - 1. Если q равно степени простого числа, q = р , то не взаимно простыми с q являются только те элементы, которые кратны р. Следовательно, ф (р ) = = р - (р - 1). Все остальные значения функции Эйлера можно получить, используя следующую теорему.

Теорема 5.1.2. Если НОД (q, q ) = 1, mo ф (qq ) = ф (q) ф (q ).

Доказательство. Занумеруем элементы кольца z,v индексом I для 1 = О.....qq - 1, а затем выпишем их в виде двумерной

таблицы, нумеруя каждый элемент кольца z,;- парой индексов по правилу

Г = I (mod q), i = i (mod q ),

0.1. элементарная теория чисел

так ЧТО i И i являются соответственно элементами колец z и Zj-. Так как НОД (</, ? ) = 1, то отображение индекса i в пару индексов (;, < ) является взаимно однозначным, и для некоторых Q и Q выполняются равенства

I = qQ + i. i = q-Q + Г.

Предположим, что ( не имеет общих делителей с i;, а Г не имеет общих делителей с q. Тогда i не имеет общих делителей ни с 17, ни с q, и, следовательно, общих делителей с qq . Следовательно,

ф (qQ ) > <Р (?) Ч> (? )

Обратно, если i не имеет общих делителей с q q , то i не имеет общих делителей ни с i;, ни с q . Следовательно, Г не имеет общих делителей с а Г не имеет общих делителей с q . Таким образом, ф iqq ) < Ч> (?) Ф (? ). и теорема доказана. □

Следствие 5.1.3. Если разложение числа q на простые множители дается равенством q = pxPi ... р/, то

Ф(1?) = р; р2

(/!,- 1)(Р2- 1) ... (рт- 1). □

Часто оказывается полезным другое важное свойство функции Эйлера. Предположим, что d делит q и обозначим через / (q) некоторую функцию от q. Под символом Yi f (d) будем понимать

сумму значений f (d) для всех d, делящих q. Очевидно, что

так как (q/d) делит q всякий раз, когда d делит q. Более удивительной является следующая теорема.

Теорема 5.1.4. Функция Эйлера удовлетворяет равенству Еф() = 9.

Доказательство. Для каждого d, делящего q, рассмотрим в Zq множество {/ I НОД (i, q) = d). Каждый элемент кольца Zq принадлежит точно одному такому множеству. Следовательно, суммируя числа элементов во всех этих множествах, мы должны получить q.

Теперь рассмотрим эквивалентное определение этого же множества, Г НОД --) = 1 j. Это множество содержит

точно ф iq/d) элементов. Суммируя по всем подмножествам, получаем

d 11?

откуда вытекает утверждение теоремы. □

Элементы кольца z, относительно сложения образуют группу. Относительно умножения ненулевые элементы кольца Zq также могут образовывать группу, хотя и не обязательно. Однако в Z, всегда можно указать подмножество, образующее относительно умножения в кольце группу, и, следовательно, являющееся подгруппой группы ненулевых элементов кольца z, в том случае, когда ненулевые элементы также образуют подгруппу относительно умножения.

Пусть а - произвольный элемент кольца Zg. Порождаемая элементом а циклическая группа равна множеству \а, а, а, ...

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

Теорема 5.1.5 (теорема Эйлера). Если НОД (а, д) = \, то = 1 (modi?), так что порядок элемента а делит ф ((?).

Доказательство. Утверждение вытекает из теоремы 2.1.5, так как группа G, содержит ф (д) элементов. □

Следствие 5.1.6 (теорема Ферма). Если р простое, то для. каждого а выполняется равенство а - = 1 (mod р), или, эквивалентно, а = а (mod р).

Доказательство является тривиальным следствием теоремы Эйлера, так как if (р) = р - 1 для любого простого р. О

Теорема Ферма является также простым следствием следующей теоремы.

Теорема 5.1.7. Если р просто, то относительно умножения по модулю р ненулевые эле.иенты кольца z/(p) образуют циклическую группу, порождаемую примитивным элементом п.

Доказательство сразу вытекает из теоремы 5.6.2, которую мы . оставляем на конец главы. □

Согласно теореме Эйлера, если аид взаимно просты, то по- \ рядок элемента а делит ф (д), но не обязательно равен ф [д). Сле- дующая теорема дает более подробную информацию об этом для :

случая д, равного степени простого числа. Это весьма сложная теорема теории чисел, и ее доказательство занимает всю оставшуюся часть настоящего раздела. Оно опирается на еще не доказанную теорему 5.1.7, что, однако, не создает порочного круга, так как в доказательстве теоремы 5.1.7 не используется теорема 5.1.8.

Прежде чем переходить к этой теореме, приведем два примера. Пусть (7 = 9; тогда G9 = {1, 2, 4, 5, 7, 8\. Легко проверить, что порядок элемента 2 равен 6, так что его можно использовать в качестве образующей циклической группы G9,

Пусть 9=16. Тогда С = 1, 3, 5, 7, 9, II, 13, 15). Перебирая все элементы, можно убедиться, что наибольший порядок всех элементов равен 4. (Таким элементом порядка 4 является элемент 3.) Следовательно, группа С не является циклической.

Так как в следующей теореме q равно степени простого числа р, ? = р , то ф (р ) = р - р - = р - (р - 1).

Теорема 5.1.8. Пусть число р простое; тогда:

(i) Если р нечетно, то группа Gm является циклической и изоморфной группе Zm~i

(ii) Если р = 2 и р &, то группа G не является циклической и изоморфна группе Zi X Zm-i-

(iii) Если р = 4, то группа Gm изоморфна группе Z.

Доказательство. Утверждение п. (iii) теоремы тривиально, так как существует только одна группа с двумя элементами. Дока-загельство остальных утверждений теоремы разбивается на пять шагов. Шаг 1 и шаг 2 содержат доказательство п. (i). На шаге 1 доказывается, что для нечетного р найдется элемент порядка р -; на шаге 2 доказывается, что для нечетного р найдется элемент порядка р - 1. Так как р и (р - 1) взаимно просты, то произ-вгдеиие этих двух элементов является элементом порядка Р {Р - 1). что и доказывает п. (i) теоремы.

Доказательство п. (ii) теоремы дается шагами 3 и 4. На шаге 3 доказывается, что если р = 2, то порядок каждого элемента делит 2 . На шаге 4 доказывается. Что найдется элемент порядка 2 --.

Начнем с доказательства на шаге О одного полезного соотношения.

Шаг 0. Для всех целых чисел аи b и произвольной степени р простого числа р выполняется сравнение

{a+bpf- -а - (modp ).

Доказательство этого шага проведем индукцией по т. Для т = 1 утверждение проверяется непосредственной проверкой.