Слайд 2Быстрое преобразование Фурье
Основной принцип всех этих алгоритмов заключается в разложении операций вычисления
![Быстрое преобразование Фурье Основной принцип всех этих алгоритмов заключается в разложении операций](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-1.jpg)
ДПФ сигнала длины на вычисление преобразований Фурье с меньшим числом точек. Разделив анализируемый набор отсчетов на части, вычисляют их ДПФ и объединяют результаты. Такие процедуры получили название алгоритмов быстрого преобразования Фурье БПФ.
При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления последовательности отсчетов на части (прореживание по времени или по частоте) и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).
Слайд 3Быстрое преобразование Фурье
Рассмотрим алгоритмы БПФ с основанием 2, когда длина последовательности
![Быстрое преобразование Фурье Рассмотрим алгоритмы БПФ с основанием 2, когда длина последовательности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-2.jpg)
, где целое число.
БПФ с прореживанием по времени. Рассмотрим идею БПФ с прореживанием по времени на примере деления набора отсчетов пополам. Введя общепринятое в литературе обозначение для дискретных экспоненциальных функций:
Запишем ДПФ сигнала в виде:
Слайд 4Быстрое преобразование Фурье
Разобьем на две -точечные последовательности, состоящие из отсчетов с четными
![Быстрое преобразование Фурье Разобьем на две -точечные последовательности, состоящие из отсчетов с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-3.jpg)
и нечетными номерами соответственно. В результате получим:
Заменяя индексы суммирования на при четном и на
при нечетном , придем к выражению:
Слайд 5Быстрое преобразование Фурье
Так как , то предыдущее выражение можно записать в виде:
(12.1)
Каждая
![Быстрое преобразование Фурье Так как , то предыдущее выражение можно записать в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-4.jpg)
из сумм (12.1) является точечным ДПФ: первая – для четных отсчетов исходной последовательности, а вторая – для нечетных. Несмотря на то, что индекс в формуле (12.1) распространяется на значений , каждая из сумм требует вычислений только для , так как и
периодичны по с периодом . Объединение же этих сумм приводит к точечному ДПФ .
Слайд 6Быстрое преобразование Фурье
Схема БПФ
![Быстрое преобразование Фурье Схема БПФ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-5.jpg)
Слайд 7Быстрое преобразование Фурье
Далее можно вычислить каждое точечное ДПФ разбиением сумм на два
![Быстрое преобразование Фурье Далее можно вычислить каждое точечное ДПФ разбиением сумм на](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-6.jpg)
точечных ДПФ. Таким образом, и могут быть вычислены в виде:
Слайд 8Быстрое преобразование Фурье
Продолжим описанную процедуру разбиения исходной ДПФ на преобразования меньшей размерности,
![Быстрое преобразование Фурье Продолжим описанную процедуру разбиения исходной ДПФ на преобразования меньшей](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-7.jpg)
пока не останутся только двухточечные преобразования. Двухточечные ДПФ (их число равно ) могут быть вообще вычислены без использования операций умножения. Действительно, для двухточечной последовательности согласно определению ДПФ имеем два спектральных отсчета:
Слайд 9Быстрое преобразование Фурье
Число требуемых при этом пар операций «умножение – сложение» можно
![Быстрое преобразование Фурье Число требуемых при этом пар операций «умножение – сложение»](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-8.jpg)
оценить как . Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы ДПФ уменьшается в раз. При больших это отношение становится весьма велико. Например, при
достигается более чем 100-кратное ускорение, но и это еще не предел. Количество комплексных умножений в алгоритме БПФ с прореживанием по времени может быть сокращено вдвое.
Слайд 10Быстрое преобразование Фурье
Из рассмотренного алгоритма следует, что на каждой ступени вычислений происходит
![Быстрое преобразование Фурье Из рассмотренного алгоритма следует, что на каждой ступени вычислений](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/349487/slide-9.jpg)
преобразование одного множества из комплексных чисел в другое множество из комплексных чисел.
Будем считать входным массивом на ступени вычисления , а – выходным массивом на ступени вычислений.
С учетом введенных обозначений имеем: