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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Історія[ред. | ред. код]

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

Опис[ред. | ред. код]

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

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

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

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

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

Алгоритм спочатку обчислює ДПФ для парних вибірок та непарних , а потім поєднує ці два результати для отримання дискретного перетворення Фур'є усієї послідовності. Обчислення продовжуються рекурсивно, щоб зменшити кількість обчислень до O(N log N).

Алгоритм перебудовує ДПФ функції на дві частини: сума по парних вибірках і сума по непарних вибірках :

Можна враховувати загальний множник з другої суми, як показано в рівнянні нижче. Тоді зрозуміло, що дві суми є ДПФ частини з парними виборками і ДПФ частини з непарними виборками функції . Позначимо DFT вхідних даних парних позицій як і ДПФ даних непарних позицій за , отримаємо:

Завдяки періодичності ДПФ, ми знаємо, що та

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

Псевдокод[ред. | ред. код]

X0,...,N−1ditfft2(x, N, s):             DFT of (x0, xs, x2s, ..., x(N-1)s):
    if N = 1 then
        X0x0                                      trivial size-1 DFT base case
    else
        X0,...,N/2−1ditfft2(x, N/2, 2s)             DFT of (x0, x2s, x4s, ...)
        XN/2,...,N−1ditfft2(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

Застосування[ред. | ред. код]

Які і усі інші алгоритми швидкого перетворення Фур'є, алгоритм Кулі-Тьюкі широко застосовується у приладах з цифровою обробкою сигналів (метрологічних, звукових, медичних тощо), комп'ютерній обробці фото та відео, комп'ютерному моделюванні технологічних та природних процесів.

Посилання[ред. | ред. код]

Джерела[ред. | ред. код]

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