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

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

Історія

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

Опис

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

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

Алгоритм 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 ← x0trivial 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/2Xk+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)