Nederlands
Menu

Wat is Snelle fouriertransformatie (FFT)?

Verzamelnaam voor algoritmen die de discrete fouriertransformatie (DFT) exact berekenen met weinig bewerkingen. De bekendste aanpak (het Cooley-Tukey-algoritme) splitst een DFT van N punten steeds opnieuw in DFT's van half zo grote omvang en deelt de gemeenschappelijke berekeningen, waardoor het aantal bewerkingen daalt van ongeveer N² volgens de definitie tot ongeveer N log₂N. Bij N = 1024 is dat ongeveer 1/100. Het algoritme is het eenvoudigst als het aantal punten een macht van twee is, maar er bestaan ook methoden voor andere groottes. Behalve voor spectrumanalyse wordt het gebruikt voor OFDM-modulatie en -demodulatie en voor de snelle berekening van lange convoluties.

Japanse benaming: 高速フーリエ変換(FFT)

“Snelle fouriertransformatie (FFT)” komt voor in 4 oefenvragen uit 2 onderwerpen, bijv. Basis van digitale signaalverwerking, Basis van draadloze communicatie.

Vakgebied: Basis van digitale signaalverwerking

Waarom het snel is

Door een DFT van N punten te splitsen in twee DFT's van N/2 punten, één van de even en één van de oneven samples, kan het oorspronkelijke resultaat worden samengesteld door alleen te vermenigvuldigen met twiddlefactoren e^(−j2πk/N) en op te tellen en af te trekken. Door dit te herhalen ontstaan log₂N trappen van elk ongeveer N bewerkingen, dus het totaal is van de orde N log₂N. Vanwege de vorm heet dit paar van optellen en aftrekken een vlinder (butterfly).

Hoeveel sneller

De verhouding is N/log₂N: 1024 ÷ 10 = 102,4 voor N = 1024 en 65.536 ÷ 16 = 4096 voor N = 65.536. Hoe groter het aantal punten, hoe groter de winst, waardoor de FFT onmisbaar is voor realtime spectrumweergaven en voor toepassingen zoals communicatieontvangers die veel DFT's na elkaar berekenen.

Convolutie met de FFT

De convolutie van twee reeksen wordt in het frequentiedomein een vermenigvuldiging. Door beide met de FFT te transformeren, ze te vermenigvuldigen en met de inverse FFT terug te transformeren, wordt de convolutie van een lang FIR-filter daarom met minder bewerkingen berekend dan bij directe berekening. Het vermenigvuldigen van DFT's komt echter overeen met een circulaire convolutie, dus de lengtes moeten met zero-padding gelijk worden gemaakt om omloop aan de uiteinden te voorkomen.

Nu oefenen: vragen over Snelle fouriertransformatie (FFT)

Stel dat een DFT van N punten volgens de definitie ongeveer N² bewerkingen kost en met de FFT (snelle fouriertransformatie) ongeveer N log₂N bewerkingen. Welke waarde ligt voor N = 1024 het dichtst bij de vermindering van het aantal bewerkingen door de FFT?

  1. AOngeveer 1/10
  2. BOngeveer 1/100
  3. COngeveer 1/1000
Antwoord en toelichting tonen

Antwoord: B. Ongeveer 1/100

N² = 1024² ≈ 1,05 miljoen en N log₂N = 1024 × 10 = 10.240, dus de verhouding is N/log₂N = 1024 ÷ 10 = 102,4, ongeveer 1/100. Het verschil wordt groter naarmate N groeit; voor N = 65.536 is de vermindering ongeveer 1/4096. De FFT beperkt het werk door een DFT steeds opnieuw te splitsen in DFT's van half zo grote omvang en gemeenschappelijke berekeningen te delen.

Veelgestelde vragen

Moet het aantal punten van een FFT een macht van twee zijn?

Nee. Een macht van twee is vaak het eenvoudigste en snelste geval, maar er bestaan ook mixed-radix-FFT's die de grootte ontbinden in factoren 3, 5 enzovoort, en methoden voor priemgroottes, en gangbare bibliotheken berekenen elke grootte. Als een macht van twee de voorkeur heeft, kan het aantal punten met zero-padding worden verhoogd.

Zijn de resultaten van de FFT dezelfde als die van de DFT?

Ze berekenen dezelfde waarden, dus ze komen op afrondingsfouten na overeen. De FFT is geen benadering, maar een algoritme dat de berekening anders organiseert om hetzelfde resultaat sneller te verkrijgen.

“Snelle fouriertransformatie (FFT)” in de toelichting

Vragen met “Snelle fouriertransformatie (FFT)” (4)

  1. Stel dat een DFT van N punten volgens de definitie ongeveer N² bewerkingen kost en met de FFT (snelle fouriertransformatie) ongeveer N log₂N bewerkingen. Welke waarde ligt voor N = 1024 het dichtst bij de vermindering van het aantal bewerkingen door de FFT?
  2. Achter een signaal van 256 punten worden 768 nullen geplaatst (zero-padding), en er wordt een DFT van 1024 punten berekend. Welke uitspraak is juist, vergeleken met de DFT van de 256 punten zoals ze zijn?
  3. Welke beschrijving van OFDM (orthogonal frequency-division multiplexing) is juist?
  4. Wat is bij OFDM het belangrijkste doel van het cyclisch prefix (CP), dat ontstaat door een deel van het einde van elk symbool te kopiëren en vooraan het symbool toe te voegen?

Verwante termen

OFDM (orthogonal frequency-division multiplexing) Frequentieresolutie Convolutie Decimatie Differentievergelijking Discrete fouriertransformatie FIR-filter Groepsvertraging (group delay) IIR-filter Impulsrespons

Naar de woordenlijst