Fast Fourier Transform: Forskelle mellem versioner
Content deleted Content added
Zorrobot (diskussion | bidrag) m robot Tilføjer: de:Schnelle Fourier-Transformation |
Tilføjelse af reference til Gauss, og betragtninger over beregningstid. |
||
Linje 1:
Fast Fourier Transform (FFT) er en [[algoritme]] til beregning af [[Fouriertransformation]]en af en diskret serie af værdier. Den anvendes til digital signalbehandling.<br />
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.<br />
Ved at fjerne frekvenser fra serien kan signalet komprimeres. Det således komprimerede signal kan overføres over langsomme forbindelser 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.<br />
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.<br />
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.<br />
Den første matematiker, som anvendte FFT, var [[Gauss]] omkring 1805. Pga. af hans store omhyggelighed nåede han, som så meget andet, ikke at plublicere sine resultater. Det medførte, at de gik i glemmebogen, indtil de genopdagedes af [[James Cooley|James W. Cooley]] og [[John W. Tukey]] i 1965.
=== Algoritme ===
De hyppigst anvendte algoritmer bygger på et "del og hersk"-princip. Serien opdeles 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.<br />
Line 32 ⟶ 41:
Serien opdeles på denne måde:<br />
<math> \mathrm{function}\ \operatorname{split}(\operatorname{eo},\vec f): </math>
:<math> \mathrm{
::<math> even : \vec c = [f_0,f_2, \ldots , f_{n-2}]
::<math> odd : \
:<math> \mathrm{return}\ \operatorname{fft}(\vec c) </math>
=== Beregningstid ===
Man kan beregne fouriertransformationen for en diskret serie ved at gå ud fra udtrykket:
<math>F_m = \sum_{k=0}^{n-1} f_k \cdot e^{-i2\pi \cdot m \cdot k/n}</math>
Det vil kræve <math>\ \ n^2</math> beregninger af cosinus og sinus og det dobbelte antal multiplikationer.<br/>
Ved at benytte FFT reduceres antallet af beregninger af cosinus og sinus til <math>\operatorname{log_2}(n)</math> og antallet af multiplikationer til <math>2 \cdot n \cdot \operatorname{log_2}(n)</math>.<br />
Hvis n eksempelvis er 1024, så reduceres antallet af trigonometriske beregninger og multiplikationer fra 2.097.152 til 20 og 20480, hhv. Alt andet lige reducerer det beregningstiden med mindst en faktor 100.<br />
==Se også==
* [[Fouriertransformation]]
* [[Vinduesfunktion]])
[[Kategori:Matematik]]
| |||