Алгоритм Кулі — Тьюкі — найбільш поширений алгоритм швидкого перетворення Фур'є (ШПФ), запропонований та названий на честь американських математиків Джеймса Кулі та Джона Тьюкі. Пізніше було з'ясовано, що алгоритм було винайдено Гаусом ще 160 років до цього. На відміну від дискретного перетворення Фур'є (ДПФ), у якому для обчислення потрібно O(N²) арифметичних операцій, алгоритм дозволяє обчислити той самий результат з невеликою похибкою за O(N log N) операцій, тому й отримав популярність в апаратній та програмній обробці сигналів.

Цей алгоритм, в тому числі і його рекурсивне застосування був винайдений німецьким математиком Карлом Фрідріхом Гаусом ще у 1805 році, який використовував його для інтерполяції астероїдів Паллади та Юнони. ШПФ став популярним після публікації наукової статті Джеймса Кулі (IBM) та Джона Тьюкі (Принстонський університет) у 1965 році.

Алгоритм Radix-2 з прорідженням за часом може бути здійснений лише тоді, коли кількість точок ${\displaystyle N}$ є степенем двійки (${\displaystyle N=2^{m}}$, де ${\displaystyle m}$ — довільне число).

Дискретне перетворення Фур'є (ДПФ) визначається за формулою:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk},}$

де ${\displaystyle k}$ є цілим числом від 0 до N-1, N — кількість вибірок

Алгоритм спочатку обчислює ДПФ для парних вибірок ${\displaystyle (x_{2m}=x_{0},x_{2},\ldots ,x_{N-2})}$та непарних ${\displaystyle (x_{2m+1}=x_{1},x_{3},\ldots ,x_{N-1})}$, а потім поєднує ці два результати для отримання дискретного перетворення Фур'є усієї послідовності. Обчислення продовжуються рекурсивно, щоб зменшити кількість обчислень до O(N log N).

Алгоритм перебудовує ДПФ функції ${\displaystyle x_{n}}$ на дві частини: сума по парних вибірках ${\displaystyle n={2m}}$ і сума по непарних вибірках ${\displaystyle n={2m+1}}$:

${\displaystyle {\begin{matrix}X_{k}&=&\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N}}(2m)k}+\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N}}(2m+1)k}\end{matrix}}}$

Можна враховувати загальний множник ${\displaystyle e^{-{\frac {2\pi i}{N}}k}}$ з другої суми, як показано в рівнянні нижче. Тоді зрозуміло, що дві суми є ДПФ частини з парними виборками ${\displaystyle x_{2m}}$ і ДПФ частини з непарними виборками ${\displaystyle x_{2m+1}}$ функції ${\displaystyle x_{n}}$. Позначимо DFT вхідних даних парних позицій ${\displaystyle x_{2m}}$ як ${\displaystyle E_{k}}$ і ДПФ даних непарних позицій ${\displaystyle x_{2m+1}}$ за ${\displaystyle O_{k}}$, отримаємо:

${\displaystyle {\begin{matrix}X_{k}=\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;even-indexed\;part\;of\;} x_{m}}{}+e^{-{\frac {2\pi i}{N}}k}\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;odd-indexed\;part\;of\;} x_{m}}=E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}.\end{matrix}}}$

Завдяки періодичності ДПФ, ми знаємо, що ${\displaystyle E_{k+N/2}=E_{k}}$ та ${\displaystyle O_{k+N/2}=O_{k}}$

Таким чином, все перетворення можна розрахувати наступним чином:

${\displaystyle {\begin{matrix}X_{k}&=&\left\{{\begin{matrix}E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}&{\mbox{for }}0\leq k<N/2\\\\E_{k-N/2}+e^{-{\frac {2\pi i}{N}}k}O_{k-N/2}&{\mbox{for }}N/2\leq k<N.\\\end{matrix}}\right.\end{matrix}}}$

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++ [Архівовано 8 липня 2020 у Wayback Machine.]
• Реалізація алгоритму Кулі-Тьюкі на мові C [Архівовано 23 лютого 2015 у Wayback Machine.]

• 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)