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

Швидке́ перетво́рення Фур'є́ (часто FFT від Шаблон:Lang-en) — швидкий алгоритм обчислення дискретного перетворення Фур'є. Якщо для прямого обчислення дискретного перетворення Фур'є з 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{\epsilon }^{ij}$, де ${\epsilon }^n=1$ і ${\epsilon }^k\ne 1$ при $0<k<n$. Алгоритм швидкого перетворення Фур'є може бути застосований до будь-яких комутативних асоціативних кілець з одиницею. Найчастіше цей алгоритм застосовують до поля комплексних чисел (з $\epsilon =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}{\epsilon }^{ij}(\sum _{k=0}^{p-1}{a}_{kq+j}{\epsilon }^{kiq})$. Вирази в дужках нам уже відомі — це $i(\mathrm{mod}p)$-те число після перетворення Фур'є $j$-тої групи. Таким чином, для обчислення кожного $b_i$ потрібно $O(q)$ обчислень, а для обчислення всіх $b_i$ — $O(Nq)$ обчислень.

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

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

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

Загальний випадок можна звести до попереднього. Нехай $4N>2^k\ge 2N$. Зауважимо, що $b_i={\epsilon }^{-i^2/2}\sum _{j=0}^{N-1}{\epsilon }^{(i+j{)}^2/2}{\epsilon }^{-j^2/2}{a}_j$. Позначимо ${\overline{a}}_i={\epsilon }^{-i^2/2}{a}_i,{\overline{b}}_i={\epsilon }^{i^2/2}{b}_i,c_i={\epsilon }^{(2N-2-i{)}^2/2}$. Тоді ${\overline{b}}_i=\sum _{j=0}^{2N-2-i}{\overline{a}}_j{c}_{2N-2-i-j}$, якщо покласти ${\overline{a}}_i=0$ при $i\ge N$.

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

Обчислення всіх ${\overline{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$.

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

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

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

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

Нехай $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 (-2\pi i\frac{2mn}{N})=\exp (-2\pi i\frac{mn}{N/2})=a_M^{nm}$

$a_N^{(2n+1)m}=\exp (-2\pi i\frac{m}{N})a_M^{nm}$

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

$X_m=\sum _{n=0}^{M-1}{x}_{2n}{a}_M^{nm}+\exp (-2\pi i\frac{m}{N})\sum _{n=0}^{M-1}{x}_{2n+1}{a}_M^{nm}$

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

$\{\begin{array}{c}{X}_0=x_0+x_1\\ X_1=x_0-x_1\end{array}$

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

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

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

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

$f_m=\sum _{k=0}^{2n-1}{x}_k{e}^{-\frac{2\pi i}{2n}mk}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{array}{cc}{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)}\\ & =\sum _{k=0}^{n-1}x{\text{'}}_k{e}^{-\frac{2\pi i}{n}mk}+e^{-\frac{\pi i}{n}m}\sum _{k=0}^{n-1}{x}^{\prime }{\text{'}}_k{e}^{-\frac{2\pi i}{n}mk}\\ & =\{\begin{array}{cc}f{\text{'}}_m+e^{-\frac{\pi i}{n}m}{f}^{\prime }{\text{'}}_m& \text{, }m<n\\ f{\text{'}}_{m-n}-e^{-\frac{\pi i}{n}(m-n)}{f}^{\prime }{\text{'}}_{m-n}& \text{, }m\ge n\end{array}\end{array}$

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

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

Див. також

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

Посилання

• Brigham, E.O. (2002), The Fast Fourier Transform, New York: Prentice-Hall
• Шаблон:Cite web