FFTalgoritmen

FFT-algoritmen beskriver en familj av metoder för att beräkna den diskreta Fouriertransformen (DFT) effektivt. En DFT omvandlar en diskret tidsserie till dess frekvensinnehåll och används inom signalbehandling, bildanalys och spektralanalys. Den naiva beräkningen kräver O(N^2) operationer, medan FFT-algoritmer vanligtvis reducerar detta till O(N log N).

Historik och grundidé: algoritmen blev bredt känd efter Cooley–Tukey 1965, även om tidiga insikter går längre tillbaka. Grundprincipen är att dela upp en DFT i mindre DFT:n och återanvända beräkningar genom butterfly-operationer och twiddle-faktorer. Många varianter gör antagandet att N är en potens av två och kallas radix-2 eller radix-k, men det finns även metoder för godtyckliga längder.

Viktigaste varianter och egenskaper: Cooley–Tukey är mest använda; radix-2 och radix-4 är vanliga. Decimation-in-time och decimation-in-frequency beskriver hur data organiseras i beräkningen. Bluestein-algoritmen tillåter DFT:n för godtyckliga längder. FFT kan ofta köras in-place och kan utnyttja realvärden bättre genom optimeringar. Det finns också specialiserade FFT-implementationer och bibliotek för hårdvara och mjukvara (till exempel FFTW, cuFFT).

Användningsområden: FFT används för spektrumanalys, filtrering, konvolution via konvolutionsteoremet och snabb polynom- eller stor tal-multiplikation. Realvärden behandlas ofta med särskilda optimeringar. Inom ljud- och bildteknik samt kommunikationssystem är FFT en grundläggande byggsten.

Begränsningar och överväganden: numerisk precision och rundningsfel uppstår vid stora N, och minneskrav kan vara betydande. Valet av algoritm beror på N, plattform och prestandakrav; vissa N är bättre lämpade för speciella radix-strukturer medan andra kräver Bluestein eller andra tekniker.