Snabb fouriertransform

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-11) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

En snabb fouriertransform (en: Fast Fourier Transform FFT) är en effektiv algoritm för att beräkna en diskret, begränsad fouriertransform. Vanligtvis kräver en diskret fouriertransform av en signal med ${\displaystyle N}$ sampelpunkter ${\displaystyle N^{2}}$ multiplikationer, men med hjälp av FFT sjunker denna siffra till i storleksordningen ${\displaystyle N\log N}$ multiplikationer.

Det finns olika FFT-algoritmer med egenskaper som passar för olika definitionsmängder. En av de vanligaste algoritmerna är Cooley–Tukey-algoritmen där radix-2 DIT är det vanligaste fallet.