Швидке́ перетво́рення Фур'є́ (часто FFT від англ. Fast Fourier Transform) — швидкий алгоритм обчислення дискретного перетворення Фур'є. Якщо для прямого обчислення дискретного перетворення Фур'є з N точок даних потрібно O(N 2) арифметичних операцій, то FFT дозволяє обчислити такий же результат використовуючи O(N log N) операцій. Алгоритм FFT часто використовується для цифрової обробки сигналів для перетворення дискретних даних з часового у частотний діапазон.
Покажемо як виконати дискретне перетворення Фур'є за
обчислень при
. Зокрема, при
знадобиться
обчислень.
Дискретне перетворення Фур'є перетворює набір чисел
в набір чисел
, такий, що
, де
і
при
. Алгоритм швидкого перетворення Фур'є може бути застосований до будь-яких комутативних асоціативних кілець з одиницею. Найчастіше цей алгоритм застосовують до поля комплексних чисел (з
) і до кілець залишків за модулем n.
Основний крок алгоритму полягає у зведенні задачі для
чисел до задачі для
чисел, де
— дільник
.
Нехай ми вже вміємо вирішувати задачу для
чисел. Застосуємо перетворення Фур'є до наборів
для
.
Тепер покажемо, як за
обчислень розв'язати вихідну задачу. Зауважимо, що
.
Вирази в дужках нам уже відомі — це
-те число після перетворення Фур'є
-тої групи. Таким чином, для обчислення кожного
потрібно
обчислень, а для обчислення всіх
—
обчислень.
Для оберненого перетворення Фур'є можна застосовувати алгоритм прямого перетворення Фур'є — потрібно лише використовувати
замість
(або застосувати операцію комплексного спряження спочатку до вхідних даних, а потім до результату, отриманого після прямого перетворення Фур'є) і остаточний результат поділити на
.
Загальний випадок можна звести до попереднього. Нехай
. Зауважимо, що
. Позначимо
. Тоді
, якщо покласти
при
.
Таким чином, задачу зведено до обчислення згортки, але це можна зробити за допомогою трьох перетворень Фур'є для
елементів. Спочатку виконаємо пряме перетворення Фур'є для
і
, далі перемножимо поелементно результати і виконаємо обернене перетворення Фур'є.
Обчислення всіх
i
потребує
операцій, три перетворення Фур'є виконується за
операцій, перемноження результатів перетворень Фур'є вимагає
операцій; знаючи значення згортки обчислення всіх
вимагає
операцій. Усього для дискретного перетворення Фур'є потрібно
дій для будь-якого
.
Цей алгоритм швидкого перетворення Фур'є може працювати над кільцем тільки коли відомі первісні корені з одиниці ступенів
і
.
Дискретне перетворення Фур'є для вектора
, Що складається з
елементів, має вигляд:
![{\displaystyle {\vec {X}}={\hat {A}}{\vec {x}}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9mY2Q3YzZiODlkNDI1ZDk1Nzk0MjM3YzVjYzliZjE3YTdiMjMyMDEy&__proxy_form=0)
елементи матриці
мають вигляд:
.
Нехай
парне, тоді ДПФ можна переписати таким чином:
![{\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}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82NTE2ZWFjOTc3NmFjZDU4MTk1OGJmOWFmOGQzOGM5ODE3ZTJiZGVh&__proxy_form=0)
Коефіцієнти
і
можна переписати наступним чином
:
![{\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}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9hMmZkNjg3YWNkN2ZhYzY0MWFjOTE3YjkzMjc4N2RjNGVmN2QzNmJj&__proxy_form=0)
![{\displaystyle a_{N}^{(2n+1)m}=\exp \left(-2\pi i{\frac {m}{N}}\right)a_{M}^{nm}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iNDEzZjcwNGU5ODNlN2IyZWQ3MzViYmZlZDg1M2E5M2RjNjgwMjBh&__proxy_form=0)
У результаті отримаємо:
![{\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}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy85OWNlM2Y1MjY2NWUyNWFjODlkZTlmZGExYTRmNzg2MDJhNjkxNjYy&__proxy_form=0)
Тобто дискретне перетворення Фур'є від вектора, що складається з
відліків, звелося до лінійної композиції двох ДПФ від
відліків, і якщо для початкової задачі потрібно
операцій, то для отриманої композиції —
. Якщо
є степенем двійки, то цей поділ можна продовжувати рекурсивно доти, поки не дійдемо до двоточкового перетворення Фур'є, яке обчислюється за такими формулами:
![{\displaystyle {\begin{cases}X_{0}=x_{0}+x_{1}\\X_{1}=x_{0}-x_{1}\end{cases}}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8wNzU4MWQ2NTZjNjMyZjM3N2E0YTk4NWRkYWQ5MjY1YjM4OGZmZDY1&__proxy_form=0)
Найбільш розповсюдженим алгоритмом розрахунку FFT є алгоритм Кулі — Тьюкі, запропонований Джеймсом Кулі та Джоном Тьюкі в 1965 році[1]. Як з'ясувалося згодом, цей алгоритм був винайдений Карлом Гаусом ще в 1805 році.
Алгоритм заснований на рекурсивному розділенні перетворення на кожному кроці на дві частини розміром
. Якщо
не ділиться на два, то робиться факторизація. Для розрахунку застосовують корені з одиниці.
Дискретне перетворення Фур'є величини 2n визначається як:
![{\displaystyle f_{m}=\sum _{k=0}^{2n-1}x_{k}\;e^{-{\frac {2\pi i}{2n}}mk}\qquad m=0,\dots ,2n-1.}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy84OTEyZjRhMmYwOWQ5ZTg1YTQ0ZTc1MWQ2YTM1ODFmMmRlNTA4YTNh&__proxy_form=0)
Якщо позначити вклади парних індексів як
- x'0 = x1, x'1 = x2, …, x'n-1 = x2n-2
та їхні перетворення величини n як
- f'0, …, f'n-1;
та вклади непарних індексів
- x"0 = x1, x"1 = x3, …, x"n-1 = x2n-1
та їхні перетворення величини n як
- f"0, …, 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}}}](./?url=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8yNzY1MjgxMGQwMjExOTJkYjJkYjJkYjg3ZGE0YWQyMDUzMDc2OWFi&__proxy_form=0)
Крім алгоритму Кулі—Тьюкі існують також інші. Для
зі взаємно простими
і
, можна застосувати алгоритм Гуда—Томаса розкладу на прості дільники (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.