Difference between revisions of "Aufgaben:Exercise 5.5Z: Complexity of the FFT"
m (Text replacement - "Signaldarstellung/Fast-Fouriertransformation (FFT)" to "Signal_Representation/Fast_Fourier_Transform_(FFT)") |
|||
Line 124: | Line 124: | ||
− | [[Category:Exercises for Signal Representation|^5. | + | [[Category:Exercises for Signal Representation|^5.5 Fast Fourier Transform ^]] |
Revision as of 22:00, 29 November 2020
Der FFT–Algorithmus (Fast Fourier Transform) 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 ${\rm log_2} \ N$ Stufen, wobei in jeder Stufe die genau gleiche Anzahl an Rechenoperationen durchzuführen ist.
- 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 $E_1$ und $E_2$ zwei komplexe Ausgänge berechnet:
- $$ A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu}, $$
- $$ A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$
- Hierbei bezeichnet $w = {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$ den komplexen Drehfaktor. Für $N = 8$ ergibt sich der Wert $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}.$
- Der Exponent $\mu$ für diesen komplexen Drehfaktor kann alle ganzzahligen Werte zwischen $0$ und $N/2-1$ annehmen. Für $N = 8$ gilt:
- $$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j} \cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm j},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j} \cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$
Mit dieser Aufgabe sollen die für die FFT erforderliche Anzahl von Rechenoperationen $(\mathcal{O}_{\rm FFT})$ ermittelt und mit dem für die DFT angebbaren Wert $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$ 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.
Hinweis:
- Die Aufgabe gehört zum Kapitel Fast-Fouriertransformation (FFT).
Fragebogen
Musterlösung
- $$(R_1 + {\rm j} \cdot I_1) + (R_2 + {\rm j} \cdot I_2) = (R_1 + R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.3cm}\Rightarrow \hspace{0.3cm} \hspace{0.15 cm}\underline{ A_{\rm A} = 2}\hspace{0.05cm}.$$
(2) Eine jede komplexe Multiplikation benötigt vier reelle Multiplikationen und zwei reelle Additionen:
- $$(R_1 + {\rm j} \cdot I_1) (R_2 + {\rm j} \cdot I_2) = (R_1 \cdot R_2 - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \cdot I_1)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{A_{\rm M} = 2,\hspace{0.3cm}M_{\rm M} = 4} \hspace{0.05cm}.$$
(3) Die Basisoperationen lauten mit den komplexen Eingangsgrößen $E_1$, $E_2$ und $w^{\hspace{0.04cm}\mu}$:
- $$ A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu},\hspace{0.5cm} A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$
- Dies bedeutet eine komplexe Multiplikation und zwei komplexe Additionen: $\hspace{0.15 cm}\underline{a_{\rm B} = 2, \hspace{0.2cm}m_{\rm B} = 1} \hspace{0.05cm}.$
(4) Im Gegensatz zu den ersten Computern nimmt heute eine Multiplikation keine wesentlich größere Rechenzeit in Anspruch als eine Addition bzw. Subtraktion.
- Mit den Ergebnissen der Teilaufgaben (1), (2) und (3) erhält man für die Gesamtzahl der Rechenoperationen:
- $$ \mathcal{O}_{\rm B} = a_{\rm B}\cdot A_{\rm A} + a_{\rm B}\cdot (A_{\rm M} +M_{\rm M} ) = 2 \cdot 2 + 1 \cdot 6\hspace{0.15 cm}\underline{ = 10} \hspace{0.05cm}.$$
(5) Insgesamt gibt es ${\rm log_2} \ N$ Stufen, in denen jeweils $N/2$ Basisoperationen auszuführen sind:
- $$\mathcal{O}_{\rm FFT} = {\rm log_2}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot \mathcal{O}_{\rm B} = 5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N$$
- $$\Rightarrow \hspace{0.3cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=16) = 5\cdot 16 \cdot 4 \hspace{0.15 cm}\underline{= 320}, \hspace{0.5cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=1024) = 5\cdot 1024 \cdot 10 \hspace{0.15 cm}\underline{= 51200} \hspace{0.05cm}.$$
(6) Der Rechenzeitgewinn der FFT gegenüber der herkömmlichen DFT ergibt sich zu:
- $$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm log_2}\hspace{0.1cm}N}$$
- $$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot \frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, \hspace{0.5cm}G_{\rm FFT} \hspace{0.1cm}(N=1024) = 1.6 \cdot\frac{1024}{ 10}\hspace{0.15 cm}\underline{ \approx 164} \hspace{0.05cm}.$$