Fourier' kiirteisendus

Fourier' kiirteisendus (FFT) on algoritmide kogum Diskreetse Fourier' teisenduse (DFT) või selle pöördtehte (IDFT) kiireks sooritamiseks. Fourier' teisendus on vajalik mitmetel aladel, et vaadelda signaali sagedusruumis. Selle arvutamine definitsiooni järgi on aga suure keerukuse O(N²), kus N on signaali punktide arv, tõttu aeganõudev ning tihtipeale ebapraktiline.[1]

Fourier' kiirteisenduse algoritmi keerukuse O(N log N) ja diskreetse Fourier' teisenduse keerukuse O(N²) võrdlus.

Fourier’ kiirteisendus vähendab keerukust O(N log N) peale. Algoritmil oli revolutsiooniline mõju digitaalsete signaalide töötlemise meetoditele – see on tänase päevani populaarne inseneriteaduses, muusikatööstuses, matemaatikas jne. Populaarseks sai kiirteisenduse kasutamine 1965. aastal, kuid sarnase sisuga algoritme uurisid matemaatikud juba 19. sajandi alguses.[1]



AjaluguRedigeeri

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


AlgoritmidRedigeeri

Cooley-Tukey algoritmRedigeeri

Populaarseim Fourier’ kiirteisenduse algoritm on Cooley-Tukey algoritm, mis põhineb jaga-ja-valitse printsiibil – tehakse mitmeharuliselt rekursioone. 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 erinevate meetoditega vältida. Lihtsaim viis seda teha, on signaali pikkus sobivaks muuta, lisades signaali lõppu sobiv arv nulle. Lisaks on võimalik muuta sämplitava signaali pikkust nõnda, et selle pikkus oleks 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 algoritmRedigeeri

Algteguri algoritm, ühtlasi tuntud ka kui Good-Thomase algoritm, on Fourier’ kiirteisendus, mis jaotab teisendatavat signaali pikkusega N= N1N2 kahedimensiooniliseks N1 x 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 rekursiivselt uuesti mõnda kiirteisenduse algoritmi kasutada.[4][5]

Algteguri algoritm avalikustati britist matemaatiku Irving John Good’i poolt aastal 1958 ning oli inspiratsiooniks Cooley-Tukey algoritmi arendamisele.[5]

Rader’i algoritmRedigeeri

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

Edasiarendused kiire Fourier’ teisenduse valdkonnasRedigeeri

Suur FFTRedigeeri

Valdkondades nagu seismilised seired ja astronoomia on järjest enam tekkimas vajadus tegemaks suuri Fourier’ kiirteisendusi, kus arvutuspunktide arv ulatub kümnete miljarditeni. Kuna selle arvutuse vajatav mälumaht on tihtipeale suurem kui arvutis on operatiivmälu, siis on vaja meetodeid teisenduste tegemiseks paralleelsel kettasüsteemil.[7]

Grupeeritud FFTRedigeeri

Aktiivselt on uurimise all meetod Fourier’ kiirteisenduse efektiivseks grupeerimiseks. FFT algoritmid jaotavad suure signaali väiksemateks juppideks, et seejärel kõikide juppide peal eraldi Fourier’ teisendus läbi viia. Grupeerimise puhul üritatakse leida meetodeid sarnaste väikeste juppide tuvastamiseks ning suure signaali jaotamine selliselt, et tekiks võimalikult palju sarnaseid väiksemaid juppe. Seeläbi oleks võimalik tehtavate arvutuste arvu vähendada.[8]

Kvantarvutuslik FFTRedigeeri

Üks esimesi õnnestumisi kvantarvutuste valdkonnas oli ameeriklase Peter Shor’i samanimeline Shor’i 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]

ViitedRedigeeri

  1. 1,0 1,1 1,2 1,3 Michael T. Heideman, Don H. Johnson, C. Sidney Burrus. "Gauss and the History of the Fast Fourier Transform". IEEE ASSP Magazine, oktoober 1984. Vaadatud 30.05.2020.
  2. 2,0 2,1 2,2 2,3 Jack Kisslinger. "The Story of the Fast Fourier Transform". 29. märts 2009. Vaadatud 30.05.2020.
  3. Jeremy Norman. "The Cooley-Tukey FFT Algorithm". 3. juuni 2012. Vaadatud 30.05.2020.
  4. Clive Temperton. "A GENERALIZED PRIME FACTOR FFT ALGORITHM FOR ANY N=2’3’5"*". mai 1992. Vaadatud 30.05.2020.
  5. 5,0 5,1 Julius O. Smith. [http://ccrma.stanford.edu/~jos/mdft/"Mathematics of the Discrete Fourier Transform (DFT) with Audio Applications, Second Edition"]. 2007. Vaadatud 30.05.2020.
  6. Shlomo Engelberg. "Elementary Number Theory and Rader’s FFT". 2017. 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. 8,0 8,1 David K. Maslen, Daniel N. Rockmore. "The Cooley-Tukey FFT and Group Theory". november 2001. Vaadatud 31.05.2020.
  9. Daan Camps, Roel Van Beeumen, Chao Yang. "Quantum Fourier Transform Revisited". 6. märts 2020. Vaadatud 31.05.2020.