/ (°(+л/2 - ,)/12sin (2л7/1)1 = 1.....л/2 - I

л/2-1

л = 2 i * = о..... /2 -

..rt/2-l

Vji+I = - /!j + = о.....п12 - 1

Рис. 4.6. БПФ-алгоритм Рейдера-Бреннера.

ТО величины Vtti и Лд связаны равенствами

V24-H = - + (V - V /2).

Таким образом, умножение на комплексные константы ia удалось заменить иа умножения на мнимые константы 12/ sin (2jni/n) 1 , что уменьшает вычислительную сложность. Необходимо,! однано, проследить, чтобы не произошло переполнение по длике слова потому, что когда п велико, а i мало, новые константы становятся весьма большими.

Вкратце форма алгоритма показана на рис. 4.6. Каждое из двух (п/2)-точечных дискретных преобразований Oypbi можно в свою очередь разбить точно таким же образом. На каждом шаге алгоритма требуется (п/2) - 2 умножений комплексных чисел на мнимые, для чего в итоге используется п - 4 вещественных умножений. (Мы предпочли избежать умножения на 1/2 при 1, равном /1/4.) На каждом шаге алгоритма всего имеется 2п комплексных или in вещественных сложений. Характеристики алгоритма Рейдера-Бреннера описываются рекуррентными уравнениями

Мв(п) = п-4 + 2М (п/2). An (п) = 4п + 2Лп(п/2) при начальных условиях /Ид (4) = О, А (4) = 16. Здесь не учтены имеющиеся на двух самых внутренних шагах умножения на (±1) и (±j).

Вместе с другими формами БПФ-алгоритма Кули-Тьюки на рис. 4.5 приведены характеристики БПФ-алгоритма Рейдера-Бреннера. Отметим, что полностью оптимизированные БПФ-алгоритмы по основанию 2 для малых длин содержат меньше сложений. Это позволяет предложить гибридный алгоритм: разбивать преобразование Фурье по алгоритму Рейдера-Бреннера до тех пор, пока не достигнем длины 16, а затем переходить на полиостью оптимизированный алгоритм. Использование на самом внутреннем этапе рассматриваемого в разд. 4.6 16-точечного БПФ-алгоритма Винограда позволяет еще больше улучшить

результаты. Характеристики гибридного алгоритма описываются теми же рекуррентными уравнениями, но с начальными условиями /Ив (16) = 20, Л (16) = 148.

Очень популярны также БПФ-алгоритмы Кули-Гьюки по основанию 4. Они могут быть использованы в случаях, когда длина преобразования п равна степени 4, и получаются ее разложением в виде 4-4 - или 4 -i. Мы рассмотрим БПФ-алгоритм Кули-Тьюки по основанию 4 с прореживанием по времени. Уравнения этой формы БПФ можно получить простой подстановкой п = 4 и п = п/4 в приведенные на рис. 4.1 общие уравнения БПФ-алгоритма Кули-Тьюки. При k = О, .... п/4 - 1 соответственно имеем

1 -J -1

-1 -i

Для каждого из п/4 рассматриваемых значений индекса k такое матричное уравнение определяет четыре компоненты преобразования. Этот метод позволяет п-тоЧечное преобразование Фурье заменить четырьмя (п/4)-точечными преобразования Фурье и некоторыми дополнительными вычислениями. Из выписанного уравнения следует, что для каждого к имеется только три различных комплексных умножения и 12 комплексных сложений. Самый внутренний шаг - 4-точечное преобразование Фурье - вообще не содержит умножений.

Число сложений можно еще уменьшить. Для этого перепишем последние уравнения для = О, .... п/4 - 1 в виде

10-1 о 0 10 1

о -1

/4-1

Мп {п) = ~п\

Характеристики БПФ-алгор1тма Кули-Тьюки подытожены на рис. 4.7.

Основной алгоритм комплексного БПФ по основанию 4

Полностью оптимизированное * комплексное БПФ по основанию 4

яых сложений. Тривиальные умн

на ±1 или ±1

Рис. 4.7. Характеристики некоторых БПФ-алгоритмов по основанию 4.

БПФ-алгоритм Гуда-Томаса (1960-1963)

п = пп , где п и п взаимно просты Перестановка входных индексов:

i = i (mod rt) i = i (mod It ) Перестановка выходных индексов f = N-k (mod л) k = Nk (mod n )

i = iNn + rNn (mod n), где

Nn + Nn = 1.

k, k -

Число умножений n (п + л )

* = nk + nk (mod Л),

Pnc. 4.8. БПФ-алгоритм Гуда-Томаса.

Разложив исходную (4х4)-матрицу в произведение двух, мы получили 8 сложений вместо 12. Это дает окончательную форму БПФ-алгоритма Кули-Тьюки по основанию 4. Характеристики алгоритма описываются равенствами

Nm, in) = (3/4) п (log4 - 1) = (3/8) п (log, п - 2), Ai{n) = 2n log, n = n logj n

для числа комплексных умножений и сложений соответственно.

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

Mr in) (9/8) п (log, п - 2), Ar (п) = (25/8) п log, п - (9/4) п.

Можно получить и лучшие результаты, если вложить в программу способность выловить все умножения на (±1) и на (±/) или на нечетные степени элемента (1/>2) (1 - /), поскольку они не требуют трех вещественных умножений, и убрать их из алгоритма. Тогда характеристики будут даваться равенствами

4.3. Алгоритм Гуда-Томаса

быстрого преобразования Фурье

Алгоритм Гуда-Томаса с использованием простых делителей представляет собой БПФ-алгоритм второго типа. Концептуально он несколько сложнее алгоритма Кули-Тьюки, но в вычислительном отношении несколько проще. Показанный на рис. 4.8 алгоритм Гуда-Томаса представляет собой другой способ отображения линейной последовательности , из п = пп целых чисел в (п X п )-таблицу, преобразующего одномерное преобразование Фур.ье в двумерное преобразование Фурье. Лежащая в основе отображения идея сильно отличается от идеи алгоритма Кули- Тьюки. Теперь числа п и п должны быть взаимно простыми, а основой отображения линейной последовательности в таблицу служит китайская теорема об остатках. Обращаясь к рис. 4.9, мы видим, как переупорядочены входные данные. В двумерную таблицу они выписываются, начиная с верхнего левого угла, вдоль расширенной диагонали . Поскольку число строк таблицы взаимно просто с числом ее столбцов, расширенная диагональ последовательно проходит через все элементы таблицы. После выполнения над этой таблицей двумерного преобразования Фурье компоненты преобразования оказываются записанными в двумерной таблице по иному правилу, чем были записаны компоненты преобразуемого вектора. Способ упорядочивания входной и выходной таблиц будет описан ниже.

индексы 15 точек на входе

индексы 5 точек на выходе

отображение

вьчисяение

отображение

Рис. 4.9. Примеры переиндексации по методу Гуда-Томаса.

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

Г = 1 (mod п), i = ( (mod п ).

Это правило представляет собой отображение индекса i на расширенную диагональ двумерной таблицы, элементы которой занумерованы парами индексов (Г, Г). Согласно китайской теореме об остатках, существуют такие целые числа N и N, что выполняется равенство

i = iNn + iNn (mod n),

Nn + Nn = 1. Выходные индексы определяются несколько иначе. Пусть

к = N k (mod п), к = Nk (mod л). Эти равенства можно переписать в эквивалентном виде к = {{N mod п) k mod ti), к = ((W mod n ) к mod л). Выходные индексы к вычисляются по правилу

к = п к + пк (mod л). Для проверки этого равенства выпишем-.

к = п {Nk + Qin) -I- л (Л/А -I- (Эгл ) (mod лл ) = = к {nN + nN) (mod л) = к.

Б ЭТИХ новых индексных обозначениях формула

преобразуется к виду

Vn-k-.;,.*. = Б Е < + + <- -.--к- -л..

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

п-1 гГ~\

= Е Е <-.

где р = а ! и V = <!>>< >. Элементы Рит являются простыми корнями из единицы степеней л и л , задающими л-точечное преобразование Фурье и п-точечное преобразование Фурье соответственно. Чтобы увидеть это, достаточно заметить, что Р = (щ ) . Так как а = е-/ / и Л/п = 1 по модулю л, то р = е-! ! . Аналогичное утверждение справедливо и- для элемента у.

Уравнение теперь записано в форме двумерного (л X л )-точечного преобразования Фурье. Число умножений и число сложений равно примерно п (л + л ). Преобразование Фурье по строкам и по столбцам, если соответствующая размерность задается составным числом, можно в свою очередь упростить, применяя алгоритм БПФ. Таким образом, если длина л преобразования разлагается в произведение простых множителей л

то описанная форма БПФ-алгоритма требует примерно л Е i

умножений и столько же сложений.

Для вычисления преобразования Фурье можно пользоваться как БПФ-алгоритмом Кули-Тьюки, так и БПФ-алгоритмом Гуда-Томаса. Можно даже строить алгоритмы, содержащие БПФ-алгоритм Кули-Тьюки и БПФ-алгоритм Гуда-Томаса одновременно. Например, используя БПФ-алгоритм Гуда-Томаса, можно 63-точечное преобразование Фурье разбить на 7-точечное и 9-точечное; используя далее БПФ-алгоритм Кули- Тьюки, 9-точечное преобразование можно разбить на два 3-точечных преобразования. Вычисления при этом преобразуются в форму, аналогичную трехмерному (ЗхЗх7)-преобразованию