Алгоритм Кулі — Тьюкі — найпоширеніший алгоритм швидкого перетворення Фур'є (ШПФ), запропонований та названий на честь американських математиків Джеймса Кулі та Джона Тьюкі. Пізніше з'ясовано, що алгоритм винайшов Гаусс ще за 160 років до цього. На відміну від дискретного перетворення Фур'є (ДПФ), у якому для обчислення потрібно O(N2) арифметичних операцій, алгоритм дає змогу обчислити той самий результат з невеликою похибкою за O(N log N) операцій, тому й отримав популярність в апаратній та програмній обробці сигналів.
Історія Цей алгоритм, включно з його рекурсивним застосуванням, винайшов німецький математик Карм Фрідріх Гаусс ще 1805 року, який використовував його для інтерполяції астероїдів Паллади та Юнони. ШПФ став популярним після опублікування 1965 року наукової статті Джеймса Кулі (IBM) та Джона Тьюкі (Принстонський університет).
Опис
Алгоритм Radix-2 з прорідженням за часом
Алгоритм Radix-2 з прорідженням за часом може бути здійснений лише тоді, коли кількість точок є степенем двійки (, де — довільне число).
Дискретне перетворення Фур'є (ДПФ) визначається за формулою:
де є цілим числом від 0 до N-1, N — кількість вибірок
Алгоритм спочатку обчислює ДПФ для парних вибірок та непарних , а потім поєднує ці два результати для отримання дискретного перетворення Фур'є всієї послідовності. Обчислення продовжуються рекурсивно, щоб зменшити кількість обчислень до O(N log N).
Алгоритм перебудовує ДПФ функції на дві частини: сума за парними вибірками і сума за непарними вибірками :
Можна враховувати загальний множник з другої суми, як показано в рівнянні нижче. Тоді зрозуміло, що дві суми є ДПФ частини з парними виборками і ДПФ частини з непарними виборками функції . Позначимо DFT вхідних даних парних позицій як і ДПФ даних непарних позицій за , отримаємо:
Завдяки періодичності ДПФ, ми знаємо, що та
Таким чином, все перетворення можна розрахувати так:
Псевдокод X0,...,N−1 ← ditfft2(x, N, s): DFT of (x0, xs, x2s, ..., x(N-1)s): if N = 1 then X0 ← x0 trivial size-1 DFT base case else X0,...,N/2−1 ← ditfft2(x, N/2, 2s) DFT of (x0, x2s, x4s, ...) XN/2,...,N−1 ← ditfft2(x+s, N/2, 2s) DFT of (xs, xs+2s, xs+4s, ...) for k = 0 to N/2−1 combine DFTs of two halves into full DFT: t ← Xk Xk ← t + exp(−2πi k/N) Xk+N/2 Xk+N/2 ← t − exp(−2πi k/N) Xk+N/2 endfor endif
Застосування Які і решту алгоритмів швидкого перетворення Фур'є, алгоритм Кулі-Тьюкі широко застосовують у приладах з цифровою обробкою сигналів (метрологічних, звукових, медичних тощо), комп'ютерній обробці фото та відео, комп'ютерному моделюванні технологічних та природних процесів.
Посилання Проста реалізація алгоритму Radix-2 на C++ Реалізація алгоритму Кулі-Тьюкі на мові C
Джерела James W. Cooley, John W. Tukey: An algorithm for the machine calculation of complex Fourier series. In: Math. Comput. 19, 1965, S. 297—301. Heideman M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform, " IEEE ASSP Magazine, 1, (4), 14-21 (1984)