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

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

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

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

[ред. | ред. код]

Покажемо як виконати дискретне перетворення Фур'є за обчислень при . Зокрема, при знадобиться обчислень.

Дискретне перетворення Фур'є перетворює набір чисел в набір чисел , такий, що , де і при . Алгоритм швидкого перетворення Фур'є може бути застосований до будь-яких комутативних асоціативних кілець з одиницею. Найчастіше цей алгоритм застосовують до поля комплексних чисел) і до кілець залишків за модулем n.

Основний крок алгоритму полягає у зведенні задачі для чисел до задачі для чисел, де  — дільник . Нехай ми вже вміємо вирішувати задачу для чисел. Застосуємо перетворення Фур'є до наборів для . Тепер покажемо, як за обчислень розв'язати вихідну задачу. Зауважимо, що . Вирази в дужках нам уже відомі — це -те число після перетворення Фур'є -тої групи. Таким чином, для обчислення кожного потрібно обчислень, а для обчислення всіх  — обчислень.

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

[ред. | ред. код]

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

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

[ред. | ред. код]

Загальний випадок можна звести до попереднього. Нехай . Зауважимо, що . Позначимо . Тоді , якщо покласти при .

Таким чином, задачу зведено до обчислення згортки, але це можна зробити за допомогою трьох перетворень Фур'є для елементів. Спочатку виконаємо пряме перетворення Фур'є для і , далі перемножимо поелементно результати і виконаємо обернене перетворення Фур'є.

Обчислення всіх i потребує операцій, три перетворення Фур'є виконується за операцій, перемноження результатів перетворень Фур'є вимагає операцій; знаючи значення згортки обчислення всіх вимагає операцій. Усього для дискретного перетворення Фур'є потрібно дій для будь-якого .

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

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

[ред. | ред. код]

Дискретне перетворення Фур'є для вектора , Що складається з елементів, має вигляд:

елементи матриці мають вигляд: .

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

Коефіцієнти і можна переписати наступним чином :

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

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

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

[ред. | ред. код]

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

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

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

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

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.

тоді:

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

[ред. | ред. код]

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

Див. також

[ред. | ред. код]

Джерела

[ред. | ред. код]
  1. 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
  • Швидке перетворення Фур'є на базі цифрового сигнального процесору. Цифрові сигнальні процесори TMS320C55x фірми Texas Instruments (Курс лабораторних робіт). Архів оригіналу за 8 травня 2013.