Snabb fouriertransform

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 $N$ sampelpunkter $N^{2}$ multiplikationer, men med hjälp av FFT sjunker denna siffra till i storleksordningen $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.

Historia

Cooley–Tukey-algoritmens historia börjar kring år 1805 då Carl Friedrich Gauss sökte samband för 2 Pallas och Junos asteroidbanor. Eftersom Gauss artikel kring detta endast publicerades postumt och dessutom på latin blev detta inte vida uppmärksammat. I mitten på 1960-talet sammanfördes J. W. Cooley^(en) på IBM och John W. Tukey på Princeton University av Richard Garvin på IBM då de hade intresse för liknande algoritmer. De publicerade sedan 1965 en artikel^[1] där de återuppfann FFT och visade på hur deras algoritmer kunde användas i datorberäkningar.

Algoritmer

En komplex vektor $x=(x_{0},x_{1},x_{2},\ldots ,x_{N-1})$ har diskret fouriertransform ${\hat {x}}={\mathcal {F}}(x)$ , båda med $N$ element, enligt definition:

${\hat {x}}_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{\frac {-i2\pi nk}{N}}$ (1)

Det har visat sig att beräkningen kan förenklas långt om antalet element $N$ är en tvåpotens av ett naturligt tal, dvs $N$ $=2^{j},j\in \mathbb {N}$ .

Radix-2-algoritmen

Redan om antalet element $N$ är jämnt delbart med två kan summan i (1) skrivas om som två hälften så långa summor med udda respektive jämna element vilket är samma som en enda hälften så lång summa med två termer i taget enligt följande:

${\hat {x}}_{k}=\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m}e^{\frac {-i2\pi 2mk}{N}}+\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m+1}e^{\frac {-i2\pi (2m+1)k}{N}}$

Exponentialuttrycket i båda summorna är lika sånär som på faktorn $e^{\frac {-i2\pi k}{N}}$ som för ett stort antal element kan beräknas en gång för alla:

${\hat {x}}_{k}=\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m}e^{\frac {-i2\pi 2mk}{N}}+e^{\frac {-i2\pi k}{N}}\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m+1}e^{\frac {-i2\pi 2mk}{N}}$

Så här långt har ingenting vunnits med dessa omskrivningar, då varje element av ${\hat {x}}_{k}$ måste fortfarande räknas ut med lika många multiplikationer och additioner som tidigare. Vinsten från dessa omskrivningar kommer av att den övre halvan av elementen använder samma delsummor som den undre halvan, vilket kan visas genom att utnyttja att $e^{i\pi }=-1$ och bryta ut detta:

${\begin{alignedat}{2}{\hat {x}}_{k+N/2}&=\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m}e^{\frac {-i2\pi 2m(k+N/2)}{N}}+e^{\frac {-i2\pi (k+N/2)}{N}}\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m+1}e^{\frac {-i2\pi 2m(k+N/2)}{N}}\\&=\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m}e^{\frac {-i2\pi 2mk}{N}}-e^{\frac {-i2\pi k}{N}}\sum _{m=0}^{{\frac {N}{2}}-1}x_{2m+1}e^{\frac {-i2\pi 2mk}{N}}\\\end{alignedat}}$

Det framgår att summorna för ${\hat {x}}_{k+N/2}$ är identiska med summorna för ${\hat {x}}_{k}$ bortsett från tecknet på den andra summan, vilket innebär att algoritmen räknar ut båda element på en gång.

Algoritmen bygger sedan på att förenklingen drivs vidare så länge antalet termer är jämnt delbart med två, och vinsten är allra störst när totala antalet element ${\hat {x}}_{k}$ respektive ${x}_{m}$ är en tvåpotens av ett naturligt tal.

Effektivitet

Om ${\hat {x}}$ beräknas med (1) kommer antalet multiplikationer vara av storleksordningen $N^{2}$ . Om N istället är en tvåpotens kan antalet multiplikationer reduceras till $2N(\log _{2}N)$ .

Exempel

För att beräkna den diskreta fouriertransformen för en samplad signal med 4096 mätvärden behövs $4096^{2}\approx 1,7\cdot 10^{7}$ komplexa multiplikationer. Med FFT sjunker antalet till $2\cdot 4096\cdot \log _{2}4096=8192\cdot 12\approx 9,8\cdot 10^{4}$ vilket typiskt går flera hundra gånger snabbare att utföra.