7.5. Быстрое преобразование Фурье

Вывод БПФ из ДПФ трактуется для изучающих этот вопрос различными способами [4—7]. Например, ДПФ можно рассматривать как действия с матрицами, и тогда БПФ выводится в результате факторизации матриц. Были также получены короткие рекурсивные уравнения, ценные тем, что дают математическую формулировку принципа БПФ. Они особенно полезны при составлении программ.

Мы используем менее строгий подход, вполне достаточный для объяснения вывода БПФ, его сути и способов программирования. Начнем с того, что запишем соотношение (7.16) в виде

Возьмем последовательность показанную на фиг. 7.10, и разделим ее на две подпоследовательности такие, что

Пусть ДПФ будут соответственно . Тогда можно записать как

Используя принятое ранее более компактное обозначение для экспоненты получим

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

использовать одни те же ячейки памяти для хранения и более коротких . При этом

Тогда вычисление конечного результата выполняется по формуле

Фиг. 7.10. Первое прореживание данных, необходимое для выполнения БПФ.

Естественно, если проводить вычисление таким способом, то нельзя будет найти значения для больших Однако — периодическая функция с периодом обладающая свойством

Поэтому следующие две операции:

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

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

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

Для -точечного преобразования имеем

Следовательно, для -точечных преобразований нужно иметь четыре уравнения:

где всюду

Если — кратно 2, т. е. если

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

Как видно из фиг. 7.12, входные данные которые преобразуются в массив располагаются не в естественном порядке, что является результатом последовательного прореживания данных для уменьшения числа точек преобразования. Порядок перетасовки можно хорошо пояснить следующим образом. Если индексы входных данных записать в двоичной форме [например, (6) в виде (110)], то новое положение числа получается путем инверсии двоичных разрядов индекса. Так, для приведенного примера

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

становится что при преобразовании к десятичному виду дает номер 3. Таким образом, становится третьим, а - шестым. Эта перетасовка носит название двоичной инверсии.

Еще одна интересная особенность направленного графа — возможность проведения вычислений с «замещением». Как было показано, необходимый объем памяти определяется лишь потребностью хранить исходных чисел. По мере выполнения преобразования исходные данные не сохраняются; на их место записываются: сначала промежуточные результаты, а затем отсчеты преобразования в естественном порядке.

Рассмотренный метод преобразования носит название «прореживание по времени», поскольку входная временная последовательность разбивается на две подпоследовательности. Другой, совершенно отличный метод основан на разбиении искомой последовательности. Его называют методом прореживания по частоте. Здесь исходные данные стоят в естественном порядке, а конечные — в двоично-инверсном.

Интересно отметить, что для выполнения вычислений не обязательно, чтобы было кратно 2. В модифицированном виде алгоритм можно использовать и для других Однако эффективность алгоритма уменьшается, особенно когда сомножители, на которые раскладывается велики. В самом деле, если — простое число, алгоритм быстрого преобразования не работает, и необходимо использовать простую схему вычисления ДПФ, показанную на фиг. 7.9.

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