Snabb fouriertransform

En snabb fouriertransform, på engelska 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 Freidrich Gauss sökte samband för 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 fördes J.W. Cooley på IBM och John W. Tukey på Princeton samman av Richard Garvin på IBM då de hade intresse i liknande algoritmer. De publicerade sedan en artikel 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) beräknas 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 tydligen kan beräknas en gång för alla, i övrigt är beräkningsarbetet i det närmaste halverat:

$\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}}$

Algoritmen bygger på att förenklingen drivs vidare så länge antalet termer är jämnt delbart med två. Uppenbarligen är vinsten 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 vi i stället förutsätter att N ä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 som är 4096 mätvärden lång behövs $4096^2 \approx 1,7 \cdot 10^{7}$ komplexa multiplikationer. Med FFT sjunker antalet till $4096 \cdot log_2 4096 = 4096 \cdot 12 \approx 4,9 \cdot 10^4$.

Se även

• Diskret fouriertransform (DFT)