Швидке перетворення Фур'є

Швидке перетворення Фур'є (часто FFT від англ. Fast Fourier Transform) — швидкий алгоритм обчислення дискретного перетворення Фур'є. Якщо для прямого обчислення дискретного перетворення Фур'є з N точок даних потрібно O(N ²) арифметичних операцій, то FFT дозволяє обчислити такий самий результат використовуючи O(N log N) операцій. Алгоритм FFT часто використовується для цифрової обробки сигналів для перетворення дискретних даних з часового у частотний діапазон.

Алгоритм Кулі-Тьюкі

Найбільш розповсюдженим алгоритмом розрахунку FFT є алгоритм Кулі-Тьюкі, запропонований Джеймсом Кулі та Джоном Тьюкі в 1965 році. Як з'ясувалося згодом, цей алгоритм був винайдений Карлом Гаусом ще в 1805 році.

Алгоритм заснований на рекурсивному розділенні перетворення на кожному кроці на два шматки з розміром $N / 2$. Якщо N не ділиться на два, то робиться факторизація. Для розрахунку використовуються корені з одиниці.

Дискретне перетворення Фур'є величини 2n визначається як:

$f_m = \sum_{k=0}^{2n-1} x_k \;e^{-\frac{2\pi i}{2n} mk } \qquad m = 0,\dots,2n-1.$

Якщо позначити вклади парних індексів як

x'₀ = x₁, x'₁ = x₂, …, x'_n-1 = x_2n-2

та їхні перетворення величини n як

f'₀, …, f'_n-1;

та вклади непарних індексів

x"₀ = x₁, x"₁ = x₃, …, x"_n-1 = x_2n-1

та їхні перетворення величини n як

f"₀, …, f"_n-1.

тоді:

$\begin{align} f_m & = \sum_{k=0}^{n-1} x_{2k } e^{-\frac{2\pi i}{2n} m(2k )} + \sum_{k=0}^{n-1} x_{2k+1} e^{-\frac{2\pi i}{2n} m(2k+1)} \\[0.5em] & = \sum_{k=0}^{n-1} x' _k e^{-\frac{2\pi i}{n} mk} + e^{-\frac{\pi i}{n}m} \sum_{k=0}^{n-1} x''_k e^{-\frac{2\pi i}{n} mk}\\[0.5em] & = \begin{cases} f'_m + e^{-\frac{\pi i}{n} m } f''_m & \text{, } m<n \\[0.5em] f'_{m-n} - e^{-\frac{\pi i}{n}(m-n)} f''_{m-n} & \text{, } m \geq n \end{cases} \end{align}$

Крім алгоритма Кулі-Тьюкі існують також інші.

Див. також

• Перетворення Фур'є
• Дискретне перетворення Фур'є

Джерела

• James W. Cooley, John W. Tukey: An algorithm for the machine calculation of complex Fourier series. In: Math. Comput. 19, 1965, S. 297–301.
• Brigham, E.O. (2002), The Fast Fourier Transform, New York: Prentice-Hall

Посилання

Швидке перетворення Фур’є на базі цифрового сигнального процесору(укр.)