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

Обратное дискретное преобразование Фурье.

Задача дискретного спектрального анализа может быть поставлена заданы и по-иному. Допустим, что коэффициенты образующие ДПФ. Положим t = kΔ и учтем, что суммируется лишь конечное число членов ряда, которые отвечают гармоникам, содержащимся в спектре исходного сигнала. Тогда:

Формула (9) выражает алгоритм обратного дискретного преобразования Фурье (ОДПФ).

Чтобы вычислить ДПФили ОДПФ последовательности из N элементов, требуется выполнить N² операций с комплексными числами. Выходом из положения явился алгоритм быстрого преобразования Фурье (Б ПФ).

Предположим, что число отсчетов N = 2^Р, где р - целое число. Разобьем входную последовательность на две части с четными и нечетными номерами:

Тогда:

Последовательности коэффициентов, относящихся к четной и нечетной частям входного массива, являются периодическими с периодом N /2:

Множитель при n > N /2 можно преобразовать так:

Тогда:

Формулы (11) и (12) лежат в основе алгоритма БПФ. Далее вычисления строят по итерационному принципу: последовательности отсчетов с четными и нечетными номерами вновь разбивают на две части. Процесс продолжается до тех пор, пока не получится последовательность, состоящая из
единственного элемента. ДПФ этого элемента совпадает с ним самим.

Дата добавления: 2014-01-04