Fast Fourier Transform

FFT (eng. Fast Fourier Transform) er en algoritme til beregning af Fouriertransformationen af en diskret serie af værdier. Den anvendes til digital signalbehandling.

Et signal kan være en optagelse af lyd. Når lyden er digitaliseret, som den er på en musik-CD, kan den Fouriertransformeres med FFT. I den transformerede serie kan udvalgte frekvenser forstærkes eller dæmpes. Derefter kan serien transformeres tilbage og afspilles som lyd, hvor f.eks. diskant eller bas er hævet eller sænket.

Ved at fjerne frekvenser fra serien kan signalet komprimeres. Det således komprimerede signal kan overføres over langsomme dataforbindelser og efter modtagelsen transformeres tilbage. Det signal, som høres i den anden ende, er ikke identisk med det oprindelige signal, men hvis frekvenserne vælges rigtigt vil man kun kunne høre en mindre forskel.

Metoden anvendes også videnskabeligt. Det er muligt ved hjælp af FFT at sammenligne to signaler og identificere komponenter, som med en relativ tidsforskydning indgår i begge signaler. Det anvendes indenfor seismologi til at analysere seismiske signaler, som er registreret på forskellige geografiske positioner. De komponenter i signalerne, som stammer fra samme jordskælv, kan udskilles fordi de ligner hinanden. Tidsforskellen bruges til at fastslå hvor skælvet fandt sted.

Et digitalt foto kan opfattes som en todimensional serie af diskrete værdier. FFT kan også anvendes på todimensionale serier, og anvendes således til komprimering af billedet ved at fjerne frekvenser, som ikke indeholder væsentlig billedinformation.

Den første matematiker, som anvendte FFT, var Gauss omkring 1805. Pga. af hans store grundighed nåede han, som så meget andet, ikke at publicere sine resultater. Det medførte, at de gik i glemmebogen, indtil de genopdagedes af James W. Cooley og John W. Tukey i 1965.

Algoritme redigér

De hyppigst anvendte algoritmer bygger på et "del og hersk"-princip. I den såkaldte radix 2-FFT opdeles Serien i to mindre serier, som derefter hver især opdeles igen ved rekursion, indtil man når frem til så små serier, at de nemt kan transformeres. Metoden beskrives her ved pseudo-kode.

Serien udtrykkes ved en vektor af komplekse værdier:

${\vec {f}}=[a_{0}+i\cdot b_{0},a_{1}+i\cdot b_{1},a_{2}+i\cdot b_{2},\ldots ,a_{n-1}+i\cdot b_{n-1}]=[f_{0},f_{1},f_{2},\ldots ,f_{n-1}]$

$\ \ i$ er det imaginære grundtal, og de indicerede værdier af $\ \ a$ og $\ \ b$ er målte serier. Det kunne være venstre og højre kanal i et stereosignal. Tidsforskellen mellem de målte værdier bestemmes af den ønskede øvre frekvens, og længden af serien bestemmes af den ønskede nedre frekvens; disse to størrelser bestemmer værdien af $\ \ n$ , som i dette eksempel er en potens af 2:

$\ n=2^{k}$

hvor $\ \ k$ er et naturligt tal.

FFT udføres ved hjælp af funktionen $\ \operatorname {fft}$ :

$\mathrm {function} \ \operatorname {fft} ({\vec {f}}):$

\ \ n=\operatorname {length} ({\vec {f}})

\mathrm {if} \ (n==1):

{\vec {c}}\ ={\vec {f}}

\ \ \mathrm {else} :

{\vec {g}}=\operatorname {split} (even,{\vec {f}}))

{\vec {u}}=\operatorname {split} (odd,{\vec {f}}))

\ \ \kappa =e^{-2\pi \cdot i/n}

\mathrm {for} \ k=0\ \mathrm {to} \ n-1:

\ \ c_{k}=g_{k}+u_{k}

\ \ c_{k+n/2}=g_{k}+u_{k}\cdot \kappa ^{k}

\mathrm {return} \ {\vec {c}}

Serien opdeles på denne måde:

$\mathrm {function} \ \operatorname {split} (\operatorname {eo} ,{\vec {f}}):$

\mathrm {switch} \ (eo)

even:{\vec {c}}=[f_{0},f_{2},\ldots ,f_{n-2}]

odd:{\vec {c}}=[f_{1},f_{3},\ldots ,f_{n-1}]

\mathrm {return} \ \operatorname {fft} ({\vec {c}})

Beregningstid redigér

Man kan beregne fouriertransformationen for en diskret serie ved at gå ud fra udtrykket:

$F_{m}=\sum _{k=0}^{n-1}f_{k}\cdot e^{-2\pi \cdot i\cdot m\cdot k/n}\ \ ;m=0,1,2,\ldots ,n-1$

Det vil kræve $\ \ n^{2}$ beregninger af den komplekse exponentialfunktion og det samme antal komplekse multiplikationer.
Ved at benytte FFT reduceres antallet af beregninger af exponentialfuktionen til $\operatorname {log_{2}} (n)$ og antallet af multiplikationer til $n\cdot \operatorname {log_{2}} (n)$ .
Hvis n eksempelvis er 1024, så reduceres antallet af trigonometriske beregninger og multiplikationer fra 1.048.576 til 10 og 10240, hhv. Alt andet lige reducerer det beregningstiden med mindst en faktor 100.

Et enkelt eksempel redigér

For at vise hvordan metoden virker er her et eksempel med en serie med længden 8.

I eksemplet benyttes størrelsen:

$\kappa =e^{-2\pi \cdot i/8}$

I beregningerne udnyttes at:

$\kappa ^{8}=e^{-2\pi \cdot i}=1$

Det medfører yderligere at:

$\kappa ^{8\cdot n+k}=\kappa ^{k}$

Her benyttes regnereglerne:

$\kappa ^{n}\cdot \kappa ^{m}=\kappa ^{n+m}$

og:

$\kappa ^{n\cdot m}=(\kappa ^{n})^{m}$

Skemaet illustrerer hvordan beregningerne udføres:

	f₀	f₁	f₂	f₃	f₄	f₅	f₆	f₇	beregning
F₀	f₀•κ⁰=f₀	f₁•κ⁰=f₁	f₂•κ⁰=f₂	f₃•κ⁰=f₃	f₄•κ⁰=f₄	f₅•κ⁰=f₅	f₆•κ⁰=f₆	f₇•κ⁰=f₇	((f₀+f₄)+(f₂+f₆))+((f₁+f₅)+(f₃+f₇))
F₁	f₀•κ⁰=f₀	f₁•κ	f₂•κ²	f₃•κ³	f₄•κ⁴	f₅•κ⁵	f₆•κ⁶	f₇•κ⁷	((f₀+f₄•κ⁴)+(f₂+f₆•κ⁴)•κ²)+((f₁+f₅•κ⁴)+(f₃+f₇•κ⁴)•κ²)•κ
F₂	f₀•κ⁰=f₀	f₁•κ²	f₂•κ⁴	f₃•κ⁶	f₄•κ⁸=f₄	f₅•κ¹⁰=f₅•κ²	f₆•κ¹²=f₆•κ⁴	f₇•κ¹⁴=f₇•κ⁶	((f₀+f₄)+(f₂+f₆)•κ⁴)+((f₁+f₅)+(f₃+f₇)•κ⁴)•κ²
F₃	f₀•κ⁰=f₀	f₁•κ³	f₂•κ⁶	f₃•κ⁹=f₃•κ	f₄•κ¹²=f₄•κ⁴	f₅•κ¹⁵=f₅•κ⁷	f₆•κ¹⁸=f₆•κ²	f₇•κ²¹=f₇•κ⁵	((f₀+f₄•κ⁴)+(f₂+f₆•κ⁴)•κ⁶)+((f₁+f₅•κ⁴)+(f₃+f₇•κ⁴)•κ⁶)•κ³
F₄	f₀•κ⁰=f₀	f₁•κ⁴	f₂•κ⁸=f₂	f₃•κ¹²=f₃•κ⁴	f₄•κ¹⁶=f₄	f₅•κ²⁰=f₅•κ⁴	f₆•κ²⁴=f₆	f₇•κ²⁸=f₇•κ⁴	((f₀+f₄)+(f₂+f₆))+((f₁+f₅)+(f₃+f₇))•κ⁴
F₅	f₀•κ⁰=f₀	f₁•κ⁵	f₂•κ¹⁰=f₂•κ²	f₃•κ¹⁵=f₃•κ⁷	f₄•κ²⁰=f₄•κ⁴	f₅•κ²⁵=f₅•κ	f₆•κ³⁰=f₆•κ⁶	f₇•κ³⁵=f₇•κ³	((f₀+f₄•κ⁴)+(f₂+f₆•κ⁴)•κ²)+((f₁+f₅•κ⁴)+(f₃+f₇•κ⁴)•κ²)•κ⁵
F₆	f₀•κ⁰=f₀	f₁•κ⁶	f₂•κ¹²=f₂•κ⁴	f₃•κ¹⁸=f₃•κ²	f₄•κ²⁴=f₄	f₅•κ³⁰=f₅•κ⁶	f₆•κ³⁶=f₆•κ⁴	f₇•κ⁴²=f₇•κ²	((f₀+f₄)+(f₂+f₆)•κ⁴)+((f₁+f₅)+(f₃+f₇)•κ⁴)•κ⁶
F₇	f₀•κ⁰=f₀	f₁•κ⁷	f₂•κ¹⁴=f₂•κ⁶	f₃•κ²¹=f₃•κ⁵	f₄•κ²⁸=f₄•κ⁴	f₅•κ³⁵= f₅•κ³	f₆•κ⁴²=f₆•κ²	f₇•κ⁴⁹=f₇•κ	((f₀+f₄•κ⁴)+(f₂+f₆•κ⁴)•κ⁶)+((f₁+f₅•κ⁴)+(f₃+f₇•κ⁴)•κ⁶)•κ⁷

Som det ses, er der mange udregninger, som kan genbruges. Eksempelvis indgår $(f_{0}+f_{4}\cdot \kappa ^{4})$ flere steder. I algoritmen udregnes denne størrelse kun én gang, og derved spares en del regnetid.

I dette eksempel, hvor serien af hensyn til overskueligheden er ganske lille, er besparelsen også lille. Når serien bliver stor, bliver besparelsen større.

Alternative metoder redigér

Den her viste radix 2 FFT er den mest udbredte algoritme i DSP-kode. Den bygger på, at længden af serien reduceres ved at dele den lige over i to halvdele. Heraf kommer kravet om, at n skal være en potens af 2. Deles serien op i fire dele, kaldes algoritmen for en radix 4 FFT, og på en processor med mange dataregistre kan den være markant hurtigere end radix 2 FFT-algoritmen.

Der er senere udviklet metoder, hvor man udnytter primfaktoropløsning af n. Når m indgår som primfaktor i n, så kan serien opdeles i m mindre serier, som hver har længden n / m. Disse kan så igen opdeles, indtil længden af serierne selv bliver et primtal.

Fast Fourier Transform

Indholdsfortegnelse

Algoritme redigér

Beregningstid redigér

Et enkelt eksempel redigér

Alternative metoder redigér

Se også redigér