ЧАСТЬ IV. ПРИЛОЖЕНИЯ

А. ПОДПРОГРАММЫ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Комплексное периодическое дискретное преобразование Фурье. Требуется вычислить дискретное преобразование Фурье (ДПФ)

для где Последовательности комплексны. Если предположить, что комплексное экспоненты уже вычислены, то для непосредственного вычисления при каждом требуется комплексных умножений (по 6 арифметических операций) и комплексное сложение (по 2 арифметические операции). Итого для непосредственной обработки всей последовательности требуется операций. Очевидные усовершенствования заключаются в использовании специальных значений, симметрий и периодичности экспоненты. Изобретательность и техника, быть может, позволят вам вычислить так же быстро, как и хорошая программа БПФ, но опыт показывает, то из этого вряд ли что-нибудь получится. Если же вам все-таки это удалось, то скорее всего вы вновь изобрели алгоритм БПФ или какую-либо его часть.

Следуя обозначениям работы [Gentleman, Sande, 1966], мы обсудим форму БПФ, принадлежащую Сэнду и Тьюки, вместо формы Кули и Тьюки. Ограничимся также для начала простым случаем, когда является, степенью 2.

Для четных и нечетных сумма вычисляется по-разному.

Для четных

Для нечетных

Заметим, что каждое из выражений и представляет собой прямое преобразование Фурье (ППФ) длиной Поскольку на вычисление ППФ длиной уходит примерно операций, мы получили примерно двойной выигрыш (для больших заменив операций на формирование двух последовательностей в квадратных скобках и на что уходит операций, плюс два ППФ длиной на что уходит операций, или всего

Групповыми свойствами экспоненты, которые позволяют осуществить эту редукцию, являются

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

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

Прежде чем написать хорошую программу БПФ, остается решить некоторые проблемы. Одна из них генерация комплексных экспонент в квадратных скобках в Простой и быстрый путь заключается в запоминании большой таблицы синусов и косинусов. На это уходит большой объем памяти, чего можно избежать. Благодаря тому что в БПФ типа Сэнда аргументы у экспонент возникают в определенном порядке, существуют простые и эффективные способы вычисления, хотя их используют немногие. Синглтон [Singleton, 1967, 1969] генерировал все экспоненты при помощи многоуглового

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

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

В табл. записаны шаги БПФ длиной 8 и содержание памяти в каждый момент времени. Величины вычисляются из и записываются в те же места; с остальными величинами поступают аналогично. В соответствии с и теперь следует вычислить БПФ последовательностей Это делается при помощи расщепления на 4 последовательности которые записываются на месте последовательностей и обычно вычисления осуществляются параллельно. БПФ этих последовательностей равны ( Величины 5 являются элементами х, но записаны они в другом порядке. Для приведения последовательности в порядок следует переставить местами пары -дополнительные массивы для этого не нужны.

Таблица А.1. (см. скан) Организация БПФ Сэнда и Тьюкн

Преобразование сразу двух действительных последовательностей. В процессе моделирования обычно приходится преобразовывать действительные величины. Если при помощи подпрограммы CPFT комплексного БПФ преобразуется действительная последовательность, то сначала массив заполнен нулями. Аналогично из-за эрмитовой симметрии

которая следует из массивы преобразованных величин содержат излишнюю информацию. Можно осуществить БПФ действительной последовательности, затратив примерно вдвое меньше памяти, чем при непосредственном применении CPFT [Cooley, Lewis, Welch, 1970], но этот алгоритм намного сложнее приводимой ниже подпрограммы Если нужно выполнить много преобразований, например при обработке строк или столбцов двухмерного массива, то время преобразования играет существенную роль, и их можно выполнять парами.

Пусть где действительные величины. Тогда преобразованные величины a и b можно выделить из при помощи соотношений

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

Синус-преобразование сразу двух действительных последовательностей. Синус-преобразование имеет вид

где Его можно выполнить, определив последовательность длиной при помощи симметрии

и совершив периодическое преобразование длиной Вместо этого мы приспособим алгоритм ] и при помощи только одного комплексного периодического преобразования длиной выполним синус-преобразование пары последовательностей

Сначала при помощи перепишем в виде

(см. задачу причем эти преобразования являются периодическими. Теперь можно определить комплексную периодическую последовательность

при которая преобразуется при помощи Синус-преобразование а выделяется из т. е.

Точно так же из выделяется 6.

Этот алгоритм применялся для двухмерного преобразования периодических по у величин, имеющих синус-симметрию по х и возникающих при вычислении потенциалов между двумя плоскими проводящими поверхностями.

Задачи

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)