Швидке перетворення Фур'є

Покажемо як виконати дискретне перетворення Фур'є за ${\displaystyle O(N(p_{1}+\cdots +p_{n}))}$ обчислень при ${\displaystyle N=p_{1}p_{2}\cdots p_{n}}$. Зокрема, при ${\displaystyle N=2^{n}}$ знадобиться ${\displaystyle O(N\log(N))}$ обчислень.

Дискретне перетворення Фур'є перетворює набір чисел ${\displaystyle a_{0},\dots ,a_{n-1}}$ в набір чисел ${\displaystyle b_{0},\dots ,b_{n-1}}$, такий, що ${\displaystyle b_{i}=\sum _{j=0}^{n-1}a_{j}\varepsilon ^{ij}}$, де ${\displaystyle \varepsilon ^{n}=1}$ і ${\displaystyle \varepsilon ^{k}\neq 1}$ при ${\displaystyle 0<k<n}$. Алгоритм швидкого перетворення Фур'є може бути застосований до будь-яких комутативних асоціативних кілець з одиницею. Найчастіше цей алгоритм застосовують до поля комплексних чисел (з ${\displaystyle \varepsilon =e^{2\pi i/n}}$) і до кілець залишків за модулем n.

Основний крок алгоритму полягає у зведенні задачі для ${\displaystyle N}$ чисел до задачі для ${\displaystyle p=N/q}$ чисел, де ${\displaystyle q}$ — дільник ${\displaystyle N}$. Нехай ми вже вміємо вирішувати задачу для ${\displaystyle N/q}$ чисел. Застосуємо перетворення Фур'є до наборів ${\displaystyle a_{i},a_{q+i},\dots ,a_{q(p-1)+i}}$ для ${\displaystyle i=0,1,\dots ,q-1}$. Тепер покажемо, як за ${\displaystyle O(Np)}$ обчислень розв'язати вихідну задачу. Зауважимо, що ${\displaystyle b_{i}=\sum _{j=0}^{q-1}\varepsilon ^{ij}(\sum _{k=0}^{p-1}a_{kq+j}\varepsilon ^{kiq})}$. Вирази в дужках нам уже відомі — це ${\displaystyle i{\pmod {p}}}$-те число після перетворення Фур'є ${\displaystyle j}$-тої групи. Таким чином, для обчислення кожного ${\displaystyle b_{i}}$ потрібно ${\displaystyle O(q)}$ обчислень, а для обчислення всіх ${\displaystyle b_{i}}$ — ${\displaystyle O(Nq)}$ обчислень.

Для оберненого перетворення Фур'є можна застосовувати алгоритм прямого перетворення Фур'є — потрібно лише використовувати ${\displaystyle \varepsilon ^{-1}}$ замість ${\displaystyle \varepsilon }$ (або застосувати операцію комплексного спряження спочатку до вхідних даних, а потім до результату, отриманого після прямого перетворення Фур'є) і остаточний результат поділити на ${\displaystyle N}$.

Загальний випадок можна звести до попереднього. Нехай ${\displaystyle 4N>2^{k}\geq 2N}$. Зауважимо, що ${\displaystyle b_{i}=\varepsilon ^{-i^{2}/2}\sum _{j=0}^{N-1}\varepsilon ^{(i+j)^{2}/2}\varepsilon ^{-j^{2}/2}a_{j}}$. Позначимо ${\displaystyle {\bar {a}}_{i}=\varepsilon ^{-i^{2}/2}a_{i},{\bar {b}}_{i}=\varepsilon ^{i^{2}/2}b_{i},c_{i}=\varepsilon ^{(2N-2-i)^{2}/2}}$. Тоді ${\displaystyle {\bar {b}}_{i}=\sum _{j=0}^{2N-2-i}{\bar {a}}_{j}c_{2N-2-i-j}}$, якщо покласти ${\displaystyle {\bar {a}}_{i}=0}$ при ${\displaystyle i\geq N}$.

Таким чином, задачу зведено до обчислення згортки, але це можна зробити за допомогою трьох перетворень Фур'є для ${\displaystyle 2^{k}}$ елементів. Спочатку виконаємо пряме перетворення Фур'є для ${\displaystyle \{{\bar {a}}_{i}\}_{i=0}^{i=2^{k}-1}}$ і ${\displaystyle \{c_{i}\}_{i=0}^{i=2^{k}-1}}$, далі перемножимо поелементно результати і виконаємо обернене перетворення Фур'є.

Обчислення всіх ${\displaystyle {\bar {a}}_{i}}$ i ${\displaystyle c_{i}}$ потребує ${\displaystyle O(N)}$ операцій, три перетворення Фур'є виконується за ${\displaystyle O(N\log(N))}$ операцій, перемноження результатів перетворень Фур'є вимагає ${\displaystyle O(N)}$ операцій; знаючи значення згортки обчислення всіх ${\displaystyle b_{i}}$ вимагає ${\displaystyle O(N)}$ операцій. Усього для дискретного перетворення Фур'є потрібно ${\displaystyle O(N\log(N))}$ дій для будь-якого ${\displaystyle N}$.

Цей алгоритм швидкого перетворення Фур'є може працювати над кільцем тільки коли відомі первісні корені з одиниці ступенів ${\displaystyle 2N}$ і ${\displaystyle 2^{k}}$.

Дискретне перетворення Фур'є для вектора ${\displaystyle {\vec {x}}}$, Що складається з ${\displaystyle N}$ елементів, має вигляд:

${\displaystyle {\vec {X}}={\hat {A}}{\vec {x}}}$

елементи матриці ${\displaystyle {\hat {A}}}$ мають вигляд: ${\displaystyle a_{N}^{mn}=\exp \left(-2\pi i{\frac {mn}{N}}\right)}$.

Нехай ${\displaystyle N}$ парне, тоді ДПФ можна переписати таким чином:

${\displaystyle X_{m}=\sum _{n=0}^{N-1}x_{n}a_{N}^{mn}=\sum _{n=0}^{N/2-1}x_{2n}a_{N}^{2nm}+\sum _{n=0}^{N/2-1}x_{2n+1}a_{N}^{(2n+1)m}}$

Коефіцієнти ${\displaystyle a_{N}^{2nm}}$ і ${\displaystyle a_{N}^{(2n+1)m}}$ можна переписати наступним чином ${\displaystyle (M=N/2)}$:

${\displaystyle a_{N}^{2nm}=\exp \left(-2\pi i{\frac {2mn}{N}}\right)=\exp \left(-2\pi i{\frac {mn}{N/2}}\right)=a_{M}^{nm}}$

${\displaystyle a_{N}^{(2n+1)m}=\exp \left(-2\pi i{\frac {m}{N}}\right)a_{M}^{nm}}$

В результаті отримаємо:

${\displaystyle X_{m}=\sum _{n=0}^{M-1}x_{2n}a_{M}^{nm}+\exp \left(-2\pi i{\frac {m}{N}}\right)\sum _{n=0}^{M-1}x_{2n+1}a_{M}^{nm}}$

Тобто дискретне перетворення Фур'є від вектора, що складається з ${\displaystyle N}$ відліків, звелося до лінійної композиції двох ДПФ від ${\displaystyle {\frac {N}{2}}}$ відліків, і якщо для початкової задачі потрібно ${\displaystyle N^{2}}$ операцій, то для отриманої композиції — ${\displaystyle {\frac {N^{2}}{2}}}$. Якщо ${\displaystyle M}$ є степенем двійки, то цей поділ можна продовжувати рекурсивно до тих пір, поки не дійдемо до двоточкового перетворення Фур'є, яке обчислюється за такими формулами:

${\displaystyle {\begin{cases}X_{0}=x_{0}+x_{1}\\X_{1}=x_{0}-x_{1}\end{cases}}}$

Найбільш розповсюдженим алгоритмом розрахунку FFT є алгоритм Кулі — Тьюкі, запропонований Джеймсом Кулі та Джоном Тьюкі в 1965 році. Як з'ясувалося згодом, цей алгоритм був винайдений Карлом Гаусом ще в 1805 році.

Алгоритм заснований на рекурсивному розділенні перетворення на кожному кроці на два шматки з розміром ${\displaystyle N/2}$. Якщо ${\displaystyle N}$ не ділиться на два, то робиться факторизація. Для розрахунку використовуються корені з одиниці.

Дискретне перетворення Фур'є величини 2n визначається як:

${\displaystyle f_{m}=\sum _{k=0}^{2n-1}x_{k}\;e^{-{\frac {2\pi i}{2n}}mk}\qquad m=0,\dots ,2n-1.}$

Якщо позначити вклади парних індексів як

x'₀ = x₁, x'₁ = x₂, …, x'_n-1 = x_2n-2

та їхні перетворення величини n як

f'₀, …, f'_n-1;

та вклади непарних індексів

x"₀ = x₁, x"₁ = x₃, …, x"_n-1 = x_2n-1

та їхні перетворення величини n як

f"₀, …, f"_n-1.

тоді:

${\displaystyle {\begin{aligned}f_{m}&=\sum _{k=0}^{n-1}x_{2k}e^{-{\frac {2\pi i}{2n}}m(2k)}+\sum _{k=0}^{n-1}x_{2k+1}e^{-{\frac {2\pi i}{2n}}m(2k+1)}\\[0.5em]&=\sum _{k=0}^{n-1}x'_{k}e^{-{\frac {2\pi i}{n}}mk}+e^{-{\frac {\pi i}{n}}m}\sum _{k=0}^{n-1}x''_{k}e^{-{\frac {2\pi i}{n}}mk}\\[0.5em]&={\begin{cases}f'_{m}+e^{-{\frac {\pi i}{n}}m}f''_{m}&{\text{, }}m<n\\[0.5em]f'_{m-n}-e^{-{\frac {\pi i}{n}}(m-n)}f''_{m-n}&{\text{, }}m\geq n\end{cases}}\end{aligned}}}$

Крім алгоритму Кулі-Тьюкі існують також інші. Для ${\displaystyle N=N1N2}$ з взаємно простими ${\displaystyle N1}$ і ${\displaystyle N2}$, можна застосувати алгоритм Гуда-Томаса розкладу на прості дільники (Prime-Factor Algorithm), заснований на китайській теоремі про залишки, щоб факторизувати ДПФ аналогічно Кулі-Тьюкі але без коефіцієнтів повороту.

• Перетворення Фур'є
• Дискретне перетворення Фур'є

• James W. Cooley, John W. Tukey: An algorithm for the machine calculation of complex Fourier series. In: Math. Comput. 19, 1965, S. 297—301.
• Brigham, E.O. (2002), The Fast Fourier Transform, New York: Prentice-Hall

Швидке перетворення Фур'є на базі цифрового сигнального процесору(укр.)