Snabb fouriertransform

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

En snabb Fouriertransform, på engelska Fast Fourier Transform (FFT), är en effektiv algoritm för att beräkna en diskret, begränsad Fourier-transform. Vanligtvis kräver en diskret fouriertransform av en signal med N sampelpunkter N2 multiplikationer, men med hjälp av FFT sjunker denna siffra till i storleksordningen NlogN multiplikationer.

Den första matematikern som använde FFT, 160 år före sina kollegor, var Carl Friedrich Gauss omkring 1805, men som så mycket annat p g a sin stora noggrannhet så publicerade han inte sina resultat, vilket medförde att den föll i glömska tills den återupptäcktes av J W Cooley och John W Tukey 1965.

Idéen som gör att den snabba fouriertransformen snabb är att välja N som en tvåpotens, vilket gör att mycket räknearbete blir överflödigt på grund av exponentialfunktionens periodiska egenskap.


Personliga verktyg