Fourier' kiirteisendus

Fourier' kiirteisendus (lühend FFT inglise keele sõnadest Fast Fourier Transform) on algoritmide kogum diskreetse Fourier' teisenduse (DFT) või selle pöördtehte (IDFT) kiireks sooritamiseks.

Fourier' teisendus on vajalik mitmetel aladel, et käsitleda signaali sagedusruumis. Selle arvutamine on definitsiooni järgi aga tingituna suurest keerukusest O(N²), kus N on signaali punktide arv, aeganõudev ning tihtipeale ebapraktiline. Fourier’ kiirteisendus vähendab keerukust O(N log N) peale.

Algoritmil oli murranguline mõju digitaalsignaalide töötlemise meetoditele – see on tänapäevani kasutusel inseneriteaduses, muusikatööstuses, matemaatikas jne. Populaarseks sai kiirteisenduse kasutamine 1965. aastal, kuid sarnase sisuga algoritme uurisid matemaatikud juba 19. sajandi alguses.

Ajalugu 
Avaldamata jäänud, kuid siiski esimese DFT kiirteisendusega seotud artikli kirjutas tuntud saksa matemaatik Carl Friedrich Gauss aastal 1805. See oli veel enne seda, kui prantsuse matemaatik ja füüsik Joseph Fourier avaldas 1822. aastal artikli Newtoni jahtumisseaduse kohta. Seal kirjutas ta, et iga funktsiooni on võimalik esitada siinuste summana, mis on Fourier’ teisenduste alustalaks.

Gaussi meetod sarnaneb Fourier’ kiirteisenduse 1965. aastal populaarseks teinud ning moodsa FFT leiutajateks loetud ameerika matemaatiku James Cooley ja ameerika statistiku John Tukey loodud Cooley-Tookey algoritmiga.

Algoritmid

Cooley-Tukey algoritm 
Populaarseim Fourier’ kiirteisenduse algoritm on Cooley-Tukey algoritm, mis põhineb jaga-ja-valitse printsiibil – tehakse mitmeharuliselt rekursioone (tagasipöördumisi). Tuntuim viis algoritmi kasutada on iga rekursiooni juures jaotada teisendatav signaal kaheks N/2 pikkusega jupiks. See seab töötlusele aga piirangu, kus signaali pikkus peab võrduma kahe astmega.

Kahe astme piirangut on võimalik küllaltki lihtsalt mitmel viisil vältida. Lihtsaim viis seda teha on signaali pikkus sobivaks muuta, lisades signaali lõppu sobiv arv nulle. Lisaks on võimalik muuta diskreeditava signaali pikkust nii, et selle pikkus oleks kahe aste.

Cooley-Tukey algoritm jaotab ühe suure diskreetse Fourier’ teisenduse mitmeks väiksemaks Fourier’ teisenduseks. Seetõttu on võimalik erinevaid algoritme kombineerida, kasutades suuremate juppide juures Cooley-Tukey algoritmi ning väiksemate juures mõnda allolevatest algoritmidest.

Algteguri algoritm 
Algteguri algoritm, ühtlasi tuntud ka kui Goodi-Thomase algoritm, on Fourier’ kiirteisendus, mis jaotab teisendatavat signaali pikkusega N = N1N2 kahedimensiooniliseks N1 × N2 teisenduseks. Selle tingimuseks on, et N1 ja N2 on omavahel algarvulised – st. ainuke täisarv, millega mõlemad täisarvud jaguvad, on 1. Saadud väiksemate teisenduste peal saab seejärel tagasipöörduvalt uuesti mõnda kiirteisenduse algoritmi kasutada.

Algteguri algoritmi avaldas britist matemaatik Irving John Good 1958. aastal ning see oli inspiratsiooniks Cooley-Tukey algoritmi väljatöötamisele.

Raderi algoritm 
1968. aastal ameeriklase Charles M. Raderi kirjutatud Raderi algoritm on Cooley-Tukey algoritmi edasiarendus. See võimaldab teostada Fourier’ kiirteisendust signaalidel, mille pikkus on võrdne mõne algarvuga. Arvutamisel  muudetakse Fourier’ teisendus ümber ringkonvolutsiooniks suurusega N – 1, kus N on algse signaali pikkus. Ringkonvolutsioonist saab Raderi algoritmi tulemuse kätte, kasutades ära konvolutsiooni teoreemi, mis väidab, et konvolutsioon ajas on võrdne korrutamisega sagedusruumis.

Edasiarendused kiire Fourier’ teisenduse valdkonnas

Suur FFT 
Valdkondades nagu seismilised seired ja astronoomia on järjest enam vaja teha suuri Fourier’ kiirteisendusi, kus arvutuspunktide arv ulatub kümnete miljarditeni. Kuna seejuures vajatav mälumaht on tihtipeale suurem kui arvutis olev operatiivmälu, siis on vaja meetodeid teisenduste tegemiseks paralleelsel kettasüsteemil.

Grupeeritud FFT 
Aktiivselt on uurimise all meetod Fourier’ kiirteisenduse efektiivseks grupeerimiseks. FFT algoritmid jaotavad suuremahulise signaali väiksemateks juppideks, et seejärel igaühe peal eraldi Fourier’ teisendus läbi viia. Grupeerimise puhul üritatakse leida meetodeid sarnaste väikeste juppide tuvastamiseks ning siis jaotada suurt signaali nii, et tekiks võimalikult palju sarnaseid väiksemaid juppe. Sellega oleks võimalik arvutusmahtu vähendada.

Kvantarvutuslik FFT 
Üks esimesi õnnestumisi kvantarvutuste valdkonnas oli ameeriklase Peter Shori nimeline Shori algoritm. Selle algoritmi tuumas arvutab kvantarvuti binaararvulisest vektorist Fourier’ teisenduse. Selline FFT implementatsioon on põhimõttelt Cooley-Tukey algoritm, mis taandab omapäraselt Fourier' maatriksi mitmete maatriksite korrutiseks. Kvantarvutusliku teisenduse kasutusalad on veel uurimisel.

Viited

Välislingid 
 The Most Important Algorithm Of All Time Veritasium, YouTube video

Digitaalne signaalitöötlus
Algoritmid