2.2.2 Konkrete Realisierung

s. a. Numerical Receipes in C: 12.2 Fast Fourier Transform (FFT)

• Definition:
  

  $$W = e^{2 \pi {i \over N}}$$ (2.34)

  
  

• jede Transformation läßt sich in gerade und ungerade Punkte teilen (Danielson-Lanczos Lemma):
  

  $$\sum_{j=0}^{N-1} e^{2 \pi i k {j \over N}} f_j$$ F_k = (2.35)

  $$\sum_{j=0}^{\halbe{N}-1} e^{2 \pi i k {2j \over N}} f_{2j} + \sum_{j=0}^{\halbe{N}-1} e^{2 \pi i k {2j+1 \over N}} f_{2j+1}$$ = (2.36)

  $$\sum_{j=0}^{\halbe{N}-1} e^{2 \pi i k {j \over {N \over 2}}} f_{2j} + W^k\sum_{j=0}^{\halbe{N}-1} e^{2 \pi i k {j \over {N \over 2}}} f_{2j+1}$$ = (2.37)

  = F_k^e + W^k F_k^o (2.38)

  
  

• Rekursive Anwendung des Danielson-Lanczos Lemma führt auf eine Einpunkt-Transformation
  

  $$F_k^{eeeoeoeooo\cdots eoo} = f_n$$ (2.39)

  
  
  d. h. einer der Koeffizienten ist gleich dem Eingabewert der Transformation. Problem: Bestimmung desjenigen n für das das gilt

• Betrachtung des Teilungsalgorithmus liefert
  
  
• Anzahl der nötigen Operationen: $\log_2(N)$ aufteilungen, N Multiplikationen $N \log_2(N)$ Operationen insgesamt

  Beachte: Ausgangsvektor muß eine 2^N Eingangswerte haben, damit die Teilung auf einer Punkttransformation endet

• Laufindizes der Summen: $N-1 \rightarrow \halbe{N}-1 \rightarrow \cdots \rightarrow 1$, d.h. Punkttransformation ist erreicht, wenn die Summe nur noch über einen Wert läuft ( Abbruchbedinung)

• Bitreversal: Entspricht dem tauschen von zwei Arrayeinträgen, d.h. es wird kein zusätzlicher Speicherplatz benötigt. (Wenn die erste Zahl das bitinvertierte der zweiten ist, ist die zweite das Bitinvertierte der ersten, z. B. $1011011 \leftrightarrow 1101101$)

• Beschleunigung der Berechnung: je weniger Sinus- und Cosinusfunktionen berechnet werden müssen, umso schneller der Algorithmus. Berechnung von Sinus und Cosinus höherer Winkelwerte über Additionstheoreme wie $\sin(2\alpha) = 2 \sin(\alpha) \cos(\alpha)$ etc.