Ero sivun ”Fourier-muunnos” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Rivi 62:
FFT (Fast Fourier Transform) eli nopea Fourier'n muunnos tarkoittaa tehokasta algoritmia DFT:n ja sen käänteismuunnoksen laskemiseksi. Yleisin FFT on Cooley-Tukey algoritmi, jonka tunsi jo C.F Gauss (1805) ja käytti sitä Pallas ja Juno asteroidien ratojen laskentaan. Työ ei ollut kovin tunnettu Erilaisia rajoitettuja versioita kehitettiin 1800-luvulla ja 1900-luvun alkupuolella. Maineensa FFT saavutti v.1965 Cooley IBM:stä ja Tukey Princetonista osoittivat työssään algoritmin soveltuvuuden tietokoneohjelmointiin.
Jos DFT laskettaisiin suoraan määritelmästä, tarvittavien laskentaoperaatioiden määrä olisi verrannollinen näytepisteiden määrän neliöön <math>N^2\,</math>.
FFT:n nopeusero verrattuna suoraan DFT:n määritelmästä laskemiseen on hyvin merkittävä kun näytepisteiden määrä on suuri. Käytännön sovelluksissa Fourier'n muunnos lasketaan aina [[numeerinen laskenta|numeerisesti]] FFT:n avulla.
|