Брза Фуријеова трансформација

Брза Фуријеова трансформација (Шаблон:Јез-ен; често се означава као -{FFT}-) је алгоритам за „брзо“ израчунавање вредности дискретне Фуријеове трансформације. Убрзање у односу на уобичајен поступак израчунавања дискретне Фуријеове трансформације постиже се избегавањем поновног израчунавања израза који се међусобно негирају. Алгоритам се приписује Џејмсу В. Кулију (-{James W. Cooley}-) и Џону В. Тукију (-{John W. Tukey}-) који су га објавили 1965. године. Међутим, Карл Фридрих Гаус га је развио већ 1805. да би израчунао путању астероида Палас и Јуно. Притом су многе верзије развијене и пре Кулијеве и Тукијеве варијанте. После су се појавила многа побољшања и варијације.

За брзу Фуријеову трансформацију постоји и алгоритам у супротном смеру - инверзна брза Фуријеова трансформација.

Неформалан опис Кули-Туки алгоритма

Кули-Туки алгоритам се базира на идеји подели-па-владај (divide-and-conquer, енг.). Предуслов за његово извршавање је да број тачака (тачке измерене за неки сигнал, на пример) на којима се врши трансформација буде степен двојке. Како често можемо сами да изаберемо колико тачака хоћемо да узмемо, ово и не представља велику препреку.

ДФТ израчунавамо тако што наше тачке (вектор) прво поделимо на два вектора, један који одговара компонентама изворног вектора са парним индексима, а други са непарним. Онда израчунамо ДФТ оба вектора и спојимо резултате. Притом користимо особине јединичног корена Фуријеове матрице. После понављамо рекурзивно поступак. Тиме можемо да ДФТ на крају израчунамо према сложености $O(n\log (n))$ у времену.

Формалан опис Кули-Туки алгоритма

Присетимо се дефиниције дискретне Фуријеове трансформације:

${\hat{c}}_k=\sum _{j=0}^{N-1}{e}^{-2\pi \mathrm{i}\cdot \frac{jk}{N}}\cdot c_j$ за $k=0,\dots ,N-1$

где је $c=(c_0,\dots ,c_{N-1})$ вектор који желимо да трансформишемо, а $\hat{c}$ тај вектор Фурије трансформисан.

Дефинишимо $N^{\prime }=N^{″}=\frac{N}{2}$.

Потом дефинишемо вектор са парним индексима:

$c{\text{'}}_0=c_0,c{\text{'}}_1=c_2,\dots ,c{\text{'}}_{N^{\prime }-1}=c_{N-2}$

и означимо његову ДФТ као:

$\hat{c}{\text{'}}_0,\hat{c}{\text{'}}_1,\dots ,\hat{c}{\text{'}}_{N^{\prime }-1}$

те вектор са непарним индексима:

$c^{\prime }{\text{'}}_0=c_1,c^{\prime }{\text{'}}_2=c_3,\dots ,c^{\prime }{\text{'}}_{N^{″}-1}=c_{N-1}$

и његову ДФТ:

${\hat{c}}^{\prime }{\text{'}}_0,{\hat{c}}^{\prime }{\text{'}}_1,\dots ,{\hat{c}}^{\prime }{\text{'}}_{N^{″}-1}$

Следи спајање:

$\begin{array}{ccc}{\hat{c}}_k& =& \sum _{j=0}^{N-1}{e}^{-2\pi \mathrm{i}\cdot \frac{jk}{N}}\cdot c_j\\ \\ & =& \sum _{j=0}^{N-1}{e}^{-2\pi \mathrm{i}\frac{(2j)k}{N}}\cdot c_{2j}+\sum _{j=0}^{\frac{N}{2}-1}{e}^{-2\pi \mathrm{i}\frac{(2j+1)k}{N}}\cdot c_{2j+1}\\ \\ & =& \sum _{j=0}^{N^{\prime }-1}{e}^{-2\pi \mathrm{i}\cdot \frac{jk}{N^{\prime }}}\cdot c{\text{'}}_j+\sum _{j=0}^{N^{″}-1}{e}^{-2\pi \mathrm{i}\cdot \frac{jk}{N^{″}}}\cdot c^{\prime }{\text{'}}_j\\ \\ & =& \{\begin{array}{cc}\hat{c}{\text{'}}_k+e^{-2\pi \mathrm{i}\frac{k}{N}}\cdot {\hat{c}}^{\prime }{\text{'}}_k& \text{kada }k<n^{\prime }\\ \hat{c}{\text{'}}_{k-N^{\prime }}-e^{-2\pi \mathrm{i}\frac{k-N^{″}}{N}}\cdot {\hat{c}}^{\prime }{\text{'}}_{k-N^{″}}& \text{kada }k\ge n^{\prime }\end{array}\end{array}$

Напомена: $N^{\prime }=N^{″}=\frac{N}{2}$, али се ради лакшег разумевања наводи различито!

Често смо у пракси заинтересовани за конкретне фреквенције. Уводимо нотацију:

${\omega }_n:=2\pi \frac{n}{NT},n=1-K,...,N-K$, $K$ је негде у близини $\frac{N}{2}$, а $T$ периода нашег мерења.

Онда је брза фуријеова трансформација за одређену фреквенцију:

$\hat{c}({\omega }_k)=\{\begin{array}{cc}{\hat{c}}^{\prime }({\omega }_k)+e^{-\mathrm{i}{\omega }_{k}T}\cdot {\hat{c}}^{″}({\omega }_k)& \text{kada }k<0\\ {\hat{c}}^{\prime }({\omega }_{-k})-e^{-\mathrm{i}{\omega }_k(1-\frac{NT}{2})}\cdot {\hat{c}}^{″}({\omega }_{-k})& \text{kada }k\ge 0\end{array}$

Литература

• Шаблон:Cite journal
• Шаблон:Cite journal
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, . Introduction to Algorithms, 2nd. ed. MIT Press and McGraw-Hill. Шаблон:Cite book. Especially chapter 30, "Polynomials and the FFT."
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite journal, Proc. 27th ACM Symposium on the Theory of Computing: 407–416.}-
• Шаблон:Cite journalШаблон:Мртва веза.}-
• -{Carl Friedrich Gauss, 1866. "Nachlass: Theoria interpolationis methodo nova tractata," Werke band 3, 265–327. Göttingen: Königliche Gesellschaft der Wissenschaften.}-
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite journal. ).}-
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal.
• Шаблон:Cite book. Cites Strang, G. (1994)/May–June). Wavelets. American Scientist, 82, 250-255.}-
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal.
• Шаблон:Cite journal. .}-
• -{D. Potts, G. Steidl, and M. Tasche, 2001. "Fast Fourier transforms for nonequispaced data: A tutorial", in: J.J. Benedetto and P. Ferreira (Eds.), Modern Sampling Theory: Mathematics and Applications (Birkhauser).}-
• Шаблон:Cite book
• Шаблон:Cite journal
• -{James C. Schatzman, 1996, Шаблон:Cite journal.}-
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal