FFT
Iz E-študij, proste zakladnice študentskega znanja
FFT (Fast Fourier Tranformation) je algoritem za hitro računanje diskretne Fourierjeve transformacije. Medtem, ko je število kompleksnih množenj običajnega algoritma (DFT) N2, je število kompleksnih množenj FFT samo 
.
Obstaja veliko inačic tega algoritma. Najhitrejša je Winogradova, a je prezapletena za uporabo pri digitalnem procesiranju signalu, kjer se uporablja radix 2 decimacija v času.
Vsebina |
Radix 2 decimacija v času
DFT je definirana kot:
... N-ti primitivni koren
- Za N-ti primitivni koren mora veljati;
Velja:
in
,
- pri čemer je
in
Če razdelimo x na sode in na lihe indekse, dobimo par enačb:
Z delitvijo na sode in na lihe indekse nadaljujemo vse dokler ne dobimo DFT dolžine 1.
Prednost tega postopka je visoka stopnja paralelnosti in možnost inplace računanja. Inverzna FFT deluje po istem principu, le da za N-ti pritivni koren vzamem funkcijo 
Vprašanja na ustnem izpitu
Metuljčki pri FFT
Metuljček je naslednji par enačb:
Izhaja iz naslednjih enačb:
Pri računanju FFT naredimo log2N korakov. V vsakem koraku uporabimo 
metuljčov.
Bitreverzno mešanje
Vsak indeks se preslika v vrednost, ki je enaka reverzni zapisani v binarni obliki.
Zakaj pride do bitreverznega mešanja pri radix 2?
Z delitvijo zaporedja na sode in na lihe indekse, se nam indeksi med seboj premešajo. Pri zaporedju dolžine 8 pridemo na koncu do zaporedja indeksov: 0,4,2,6,1,5,3,7. Če hočemo, da imamo na izhodu transformirano zaporedje v pravem vrstnem redu, moramo vhodno zaporedje premešati. Če uporabljamo decimacijo v frekvenci, imamo premešane izhode.
Kje dobimo na hitrosti pri radix 4 in radix 8?
Namesto deljenja zaporedja na dva dela, ga v vsakem koraku razdelimo na 4 ali 8 delov. Pogoj da to lahko naredimo je, da je dolžina zaporeja potenca števila 4 oziroma 8. S tem pridemo do 
oziroma 
kompleksnih množenj. Metuljčki v teh primerih izgubijo obliko metulja (sestavljeni so iz štirih/osmih vhodov in štirih/osmih izhodov). Izboljšava ni zadostna v primerjavi s kompleksnostjo radix 4 oziroma radix 8 algoritma.
Hitro računanje konvolucije
Periodična zaporedja
Izračunati želimo izhodno zaporedje sistema: 
.
Postopek:
- izračunamo DFT od xp in hp s pomočjo FFT algoritma
- pomnožimo transforma
- izračunamo inverzno DFT produkta transformov s pomočjo FFT algoritma
Neperiodična zaporedja
x(n) je zaporedje dolžine N1, h(n) pa dolžine N2. Če računamo po definiciji konvolucije, dobimo izhodno zaporednje y(n) dolžine N1 + N2 − 1. Lahko rečemo, da sta zaporedji x(n) in h(n) periodični s periodo N1 + N2 − 1. Vrednosti, ki v prvotnih zaporedjih niso definirane postavimo na 0. Če ta dolžina ni potenca števila dva, na koncu dodamo še več ničel saj (zaradi uporabe FFT algoritma?) želimo da je dolžina potenca števila dva. Ker so sedaj vsa zaporedja iste dolžine lahko uporabimo postopek za periodična zaporedja. Tega ne moremo narediti le, če je x(n) neskončno dolgo zaporedje. V tem primeru računamo hitro konvolucijo po odsekih.
Hitra konvolucija po odsekih
Imamo prenosno funkcijo sistema h(n) dolžine N2 in vhodno zaporedje x(n) dolžine 
. Izberemo število N3 in definiramo xk(n), ki je definiran kot:
Dolžina izhodnega zaporedja y(n) je tako N3 + N2 − 1. N3 mora biti izbran tako, da je ta dolžina potenca števila 2. Do te dolžine dopolnimo tudi h(n) in vsak odsek xk(n). Tako lahko izračunamo y(n) za vsak odsek posebej po postopku za periodična zaporedja.
Hitro računanje korelacije
Križna korelacija je definirana kot:
Križna korelacija ni komutativna operacija tako kot konvolucija. S pomočjo križne korelacije lahko detektiramo signale, ki so vsebovani v šumu. Avtokorelacijo lahko uporabljamo za ugotavljanje periodičnosti signala. Avtokorelacija je soda funkcija.
Hitro računanje križne korelacije periodičnih zaporedij
Za realna zaporedja velja:
Xp( − k) = Xp(N − k) = X * (k)
Postopek:
- izračunam DFT od xp in yp po FFT algoritmu
- izračunam Rpxy(k)
- izračunam rpxy(n) s pomočjo inverzne DFT za n = 0,1,...,N − 1
V praksi se uporablja enostavnejša formula za računanje križne korelacije:
Prednosti:
- končno dolg odcep
- deljenje s k omogoča primerjavo rezultatov, ki jih dobimo za različne vrednosti k
Hitro računanje križne korelacije neperiodičnih zaporedij
Če imamo zaporedje x(n) dolžine N1 in zaporedje y(n) dolžine N2, bo imelo izhodno zaporedje rxy(n) dolžino N1 + N2 − 1. Torej podaljšam vhodni zaporedji do dolžine, ki je potenca števila 2 in je večja od N1 + N2 − 1 z dodajanjem 0. Postopek za samo računanje je enak kot pri periodičnih zaporedjih.
