Fourier' kiirteisendus

Fourier' kiirteisenduse algoritmi keerukuse O(N log N (punane kõver) ja diskreetse Fourier' teisenduse keerukuse O(N²) (sinine kõver) võrdlus

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.^[1] Fourier’ kiirteisendus vähendab keerukust O(N log N) peale.^[1]

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.^[1]

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.^[1][2]

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.^[1][3]

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.^[2]

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.^[2]

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.^[2]

Algteguri algoritm

Algteguri algoritm, ühtlasi tuntud ka kui Goodi-Thomase algoritm, on Fourier’ kiirteisendus, mis jaotab teisendatavat signaali pikkusega N = N₁N₂ kahedimensiooniliseks N₁ × N₂ teisenduseks. Selle tingimuseks on, et N₁ ja N₂ 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.^[4][5]

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

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.^[6]

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.^[7]

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.^[8]

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.^[8][9]

Viited

1. Michael T. Heideman, Don H. Johnson, C. Sidney Burrus (oktoober 1984). "Gauss and the History of the Fast Fourier Transform" (PDF). IEEE ASSP Magazine. Vaadatud 30.05.2020.
2. Jack Kisslinger (29. märts 2009). "The Story of the Fast Fourier Transform". Vaadatud 30.05.2020.
3. Jeremy Norman (3. juuni 2012). "The Cooley-Tukey FFT Algorithm". Vaadatud 30.05.2020.
4. Clive Temperton (mai 1992). "A GENERALIZED PRIME FACTOR FFT ALGORITHM FOR ANY N=2'3'5"*" (PDF). Vaadatud 30.05.2020.
5. Julius O. Smith (2007). "Mathematics of the Discrete Fourier Transform (DFT) with Audio Applications, Second Edition". Vaadatud 30.05.2020.
6. Shlomo Engelberg (2017). "Elementary Number Theory and Rader's FFT". Vaadatud 30.05.2020.
7. Thomas H. Cormen, David M. Nicol. "Performing Out􏰀of􏰀Core FFTs on Parallel Disk Systems". Vaadatud 31.05.2020.
8. David K. Maslen, Daniel N. Rockmore (november 2001). "The Cooley-Tukey FFT and Group Theory" (PDF). Vaadatud 31.05.2020.
9. Daan Camps, Roel Van Beeumen, Chao Yang (6. märts 2020). "Quantum Fourier Transform Revisited" (PDF). Vaadatud 31.05.2020.

Välislingid

• The Most Important Algorithm Of All Time Veritasium, YouTube video