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

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

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

Основний алгоритм[ред.ред. код]

Покажемо як виконати дискретне перетворення Фур'є за O(N(p_1+\cdots+p_n)) обчислень при N=p_1p_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\ge2N. Зауважимо, що 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}_jc_{2N-2-i-j}, якщо покласти \bar{a}_i=0 при i\ge 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 N2 відліків, і якщо для початкової задачі потрібно 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'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.

тоді:


\begin{align}

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{align}

Інші алгоритми ШПФ[ред.ред. код]

Крім алгоритму Кулі-Тьюкі існують також інші. Для N = N1N2 з взаємно простими N1 і 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

Посилання[ред.ред. код]

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