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

В соответствии с формулой прямого ДПФ для определения N значений X[k] требуется выполнить примерно N² умножений и N² сложений. С ростом N значительно возрастает время вычисления X[k]. Такая ситуация наблюдается и при вычислении ОДПФ. Для ускорения вычислений ДПФ разработаны алгоритмы быстрого преобразования Фурье (БПФ).

Рассмотрим алгоритмы БПФ с основанием 2, которые применяются к последовательностям длины N=2^k, k – целое.

Основная идея БПФ состоит в следующем. Последовательность x[n] разбивают на две последовательности x₁[n] и x₂[n] длиной N/2 и находят для них X₁[k] и X₂[k]. Затем по значениям X₁[k] и X₂[k] определяют требуемое N – точечное ДПФ X[k]. Если последняя операция будет выполняться просто и не потребует сложных вычислений, то для вычисления N – точечного ДПФ потребуется выполнить (N/2)²+(N/2)²=N²/2 операций. Если продолжить процесс разбиения последовательностей x₁[n] и x₂[n] на две части и находить для каждой из них свои ДПФ, то можно существенно сократить количество операций.

Рассмотрим ДПФ последовательности x[n], полагая, что N равно степени 2:

(23)

Разобьем x[n] на две последовательности x₁[n] и x₂[n], содержащие соответственно четные и нечетные члены x[n]:

x₁[n]=x[2n] , n=0,1,2,…..,(N/2 - 1);

x₂[n]=x[2n+1], n=0,1,2,…..,(N/2 - 1).

Тогда

.