Brza furijeova transformacija

Izvor: testwiki
Prijeđi na navigaciju Prijeđi na pretragu

Brza Furijeova transformacija (Šablon:Jez-en; često se označava kao FFT) je algoritam za „brzo“ izračunavanje vrednosti diskretne Furijeove transformacije. Ubrzanje u odnosu na uobičajen postupak izračunavanja diskretne Furijeove transformacije postiže se izbegavanjem ponovnog izračunavanja izraza koji se međusobno negiraju. Algoritam se pripisuje Džejmsu V. Kuliju (James W. Cooley) i Džonu V. Tukiju (John W. Tukey) koji su ga objavili 1965. godine. Međutim, Karl Fridrih Gaus ga je razvio već 1805. da bi izračunao putanju asteroida Palas i Juno. Pritom su mnoge verzije razvijene i pre Kulijeve i Tukijeve varijante. Posle su se pojavila mnoga poboljšanja i varijacije.

Za brzu Furijeovu transformaciju postoji i algoritam u suprotnom smeru - inverzna brza Furijeova transformacija.

Neformalan opis Kuli-Tuki algoritma

Kuli-Tuki algoritam se bazira na ideji podeli-pa-vladaj (divide-and-conquer, eng.). Preduslov za njegovo izvršavanje je da broj tačaka (tačke izmerene za neki signal, na primer) na kojima se vrši transformacija bude stepen dvojke. Kako često možemo sami da izaberemo koliko tačaka hoćemo da uzmemo, ovo i ne predstavlja veliku prepreku.

DFT izračunavamo tako što naše tačke (vektor) prvo podelimo na dva vektora, jedan koji odgovara komponentama izvornog vektora sa parnim indeksima, a drugi sa neparnim. Onda izračunamo DFT oba vektora i spojimo rezultate. Pritom koristimo osobine jediničnog korena Furijeove matrice. Posle ponavljamo rekurzivno postupak. Time možemo da DFT na kraju izračunamo prema složenosti O(log⁡(n)) u vremenu.

Formalan opis Kuli-Tuki algoritma

Prisetimo se definicije diskretne Furijeove transformacije:

c^k=∑j=0N−1e−2πi⋅jkN⋅cj za k=0,…,N−1

gde je c=(c0,…,cN−1) vektor koji želimo da transformišemo, a c^ taj vektor Furije transformisan.

Definišimo N′=N″=N2.

Potom definišemo vektor sa parnim indeksima:

c'0=c0,c'1=c2,…,c'N′−1=cN−2

i označimo njegovu DFT kao:

c^'0,c^'1,…,c^'N′−1

te vektor sa neparnim indeksima:

c′'0=c1,c′'2=c3,…,c′'N″−1=cN−1

i njegovu DFT:

c^′'0,c^′'1,…,c^′'N″−1

Sledi spajanje:

c^k=∑j=0N−1e−2πi⋅jkN⋅cj                 =∑j=0N−1e−2πi(2j)kN⋅c2j+∑j=0N2−1e−2πi(2j+1)kN⋅c2j+1=∑j=0N′−1e−2πi⋅jkN′⋅c'j+∑j=0N″−1e−2πi⋅jkN″⋅c′'j={c^'k+e−2πikN⋅c^′'kkada k<n′c^'k−N′−e−2πik−N″N⋅c^′'k−N″kada k≥n′

Napomena: N′=N″=N2, ali se radi lakšeg razumevanja navodi različito!

Često smo u praksi zainteresovani za konkretne frekvencije. Uvodimo notaciju:

ωn:=2πnNT,n=1−K,...,N−K, K je negde u blizini N2, a T perioda našeg merenja.

Onda je brza furijeova transformacija za određenu frekvenciju:

c^(ωk)={c^′(ωk)+e−iωkT⋅c^″(ωk)kada k<0c^′(ω−k)−e−iωk(1−NT2)⋅c^″(ω−k)kada k≥0

Literatura

Šablon:Refbegin

Šablon:Refend

Izvor: https://sh.wiki.beta.math.wmflabs.org/w/index.php?title=Brza_furijeova_transformacija&oldid=5316