Exercise 5.5Z: Complexity of the FFT
From LNTwww
Der FFT–Algorithmus realisiert eine Diskrete Fouriertransformation mit dem kleinstmöglichen Rechenaufwand, wenn der Parameter N eine Zweierpotenz ist. Im einzelnen sind zur Durchführung einer FFT folgende Rechenschritte notwendig:
- Die FFT geschieht in ld N Stufen, wobei in jeder Stufe die genau gleiche Anzahl an Rechenoperationen durchzuführen ist. „ld” steht hier als Abkürzung für den Logarithmus zur Basis 2.
- Die Grafik zeigt die dritte und letzte Stufe für das Beispiel N = 8. Man erkennt, dass in dieser und auch den anderen Stufen jeweils N/2 Basisoperationen durchzuführen sind.
- In jeder Basisoperation, die man häufig auch als Butterfly bezeichnet, werden aus den beiden komplexen Eingangsgrößen E1 und E2 zwei komplexe Ausgänge berechnet:
A1=E1+E2⋅wμ, A2=E1−E2⋅wμ.
- Hierbei bezeichnet w = exp(–j · 2π/N) den komplexen Drehfaktor. Für das Beispiel N = 8 hat dieser folgenden Wert:
w=e−j⋅π/4=cos(45∘)−j⋅sin(45∘).
- Der Exponent μ dieses komplexen Drehfaktors kann alle ganzzahligen Werte zwischen 0 und N/2 –1 annehmen. Für N = 8 gilt:
w0=1,w1=1√2−j⋅1√2,w2=−j,w3=−1√2−j⋅1√2.
Mit dieser Aufgabe sollen die für die FFT erforderliche Anzahl von Rechenoperationen (OFFT) ermittelt und mit dem für die DFT angebbaren Wert ODFT ≈ 8N2 verglichen werden.
Zu beachten ist:
- Sinnvollerweise werden die Potenzen von w vor dem eigentlichen Algorithmus berechnet und in einer Lookup–Tabelle abgelegt. Die hierfür notwendigen Operationen sollen deshalb unberücksichtigt bleiben.
- Die Bitumkehroperation – eine Umsortierung, die vor der ersten Stufe durchzuführen ist – soll bei dieser Abschätzung ebenfalls nicht berücksichtigt werden.
Fragebogen
Musterlösung
1.
2.
3.
4.
5.
6.
7.
