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

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

Історія

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

Опис

Алгоритм Radix-2 з прорідженням за часом

Алгоритм Radix-2 для 8-ми точок

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

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

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

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

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

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

${\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}}$

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

${\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}}$

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

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

${\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)