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

Швидке́ перетво́рення Фур'є́ (часто FFT від англ. Fast Fourier Transform) — швидкий алгоритм обчислення дискретного перетворення Фур'є. Якщо для прямого обчислення дискретного перетворення Фур'є з N точок даних потрібно O(N ²) арифметичних операцій, то FFT дозволяє обчислити такий же результат використовуючи O(N log N) операцій. Алгоритм FFT часто використовується для цифрової обробки сигналів для перетворення дискретних даних з часового у частотний діапазон.

Основний алгоритм

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

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

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

Обернене перетворення Фур'є

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

Загальний випадок

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

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

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

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

Висновок перетворення з ДПФ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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.

тоді:

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

Інші алгоритми ШПФ

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

Див. також

• Перетворення Фур'є
• Дискретне перетворення Фур'є
• Алгоритм Шьонхаге — Штрассена

Посилання

• Brigham, E.O. (2002), The Fast Fourier Transform, New York: Prentice-Hall
• Швидке перетворення Фур'є на базі цифрового сигнального процесору. Цифрові сигнальні процесори TMS320C55x фірми Texas Instruments (Курс лабораторних робіт). Архів оригіналу за 8 травня 2013.