Snabb fouriertransform
Från Rilpedia
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.
