Aufgaben:Aufgabe 5.5Z: Rechenaufwand für die FFT: Unterschied zwischen den Versionen
(10 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
Zeile 3: | Zeile 3: | ||
}} | }} | ||
− | [[Datei:P_ID1179__Sig_Z_5_5.png|right| | + | [[Datei:P_ID1179__Sig_Z_5_5.png|right|frame|Letzte Stufe der FFT für $N=8$]] |
− | 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: | + | Der FFT–Algorithmus (Fast Fourier Transform) realisiert eine „Diskrete Fouriertransformation” mit dem kleinstmöglichen Rechenaufwand, wenn der Parameter $N$ eine Zweierpotenz ist. |
− | *Die FFT geschieht in ${\rm | + | |
− | *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. | + | Im Einzelnen sind zur Durchführung einer FFT folgende Rechenschritte notwendig: |
− | *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: | + | *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_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}.$$ | :$$ A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$ | ||
− | *Hierbei bezeichnet $w = {\rm e}^{-{\rm j} 2\pi/N}$ den komplexen Drehfaktor. Für | + | *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$ | + | *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} | :$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j} | ||
\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm | \cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm | ||
Zeile 17: | Zeile 19: | ||
\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$ | \cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$ | ||
− | Mit dieser Aufgabe sollen die für die FFT erforderliche Anzahl von Rechenoperationen $( | + | 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: | 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 | + | *Sinnvollerweise werden die Potenzen von $w$ vor dem eigentlichen Algorithmus berechnet und in einer Lookup–Tabelle abgelegt. Die hierfür notwendigen Operationen sollen hier 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. | *Die Bitumkehroperation – eine Umsortierung, die vor der ersten Stufe durchzuführen ist – soll bei dieser Abschätzung ebenfalls nicht berücksichtigt werden. | ||
− | '' | + | |
− | *Die Aufgabe gehört zum Kapitel [[Signaldarstellung/Fast-Fouriertransformation_(FFT)|Fast-Fouriertransformation (FFT)]]. | + | |
− | + | ||
+ | |||
+ | |||
+ | ''Hinweis:'' | ||
+ | *Die Aufgabe gehört zum Kapitel [[Signaldarstellung/Fast-Fouriertransformation_(FFT)|Fast-Fouriertransformation (FFT)]]. | ||
+ | |||
+ | |||
+ | |||
Zeile 32: | Zeile 41: | ||
<quiz display=simple> | <quiz display=simple> | ||
− | {Wieviele reelle Additionen $(A_{\rm A})$ erfordert eine komplexe Addition? | + | {Wieviele reelle Additionen $(A_{\rm A})$ erfordert eine komplexe Addition? |
|type="{}"} | |type="{}"} | ||
− | $A_{\rm A} \ = $ { 2 } | + | $A_{\rm A} \hspace{0.3cm} = \ $ { 2 } |
− | {Wieviele reelle Additionen ( | + | {Wieviele reelle Additionen $(A_{\rm M})$ und Multiplikationen $(M_{\rm M})$ sind für eine komplexe Multiplikation erforderlich? |
|type="{}"} | |type="{}"} | ||
− | $ | + | $A_{\rm M} \hspace{0.3cm} = \ $ { 2 } |
− | + | $M_{\rm M} \hspace{0.2cm} = \ $ { 4 } | |
− | $ | ||
− | {Wieviele komplexe Additionen/Subtraktionen ( | + | {Wieviele komplexe Additionen/Subtraktionen $(a_{\rm B})$ erfordert eine einzige Basisoperation („Butterfly”)? |
− | Wieviele komplexe Multiplikationen ( | + | <br>Wieviele komplexe Multiplikationen $(m_{\rm B})$ sind pro Basisoperation notwendig? |
|type="{}"} | |type="{}"} | ||
− | $ | + | $a_{\rm B} \hspace{0.32cm} = \ $ { 2 } |
− | + | $m_{\rm B} \hspace{0.2cm} = \ $ { 1 } | |
− | $ | ||
− | {Wieviele Rechenoperationen (Additionen, Subtraktionen, Multiplikationen gleichermaßen) erfordert eine Basisoperation? | + | {Wieviele Rechenoperationen (Additionen, Subtraktionen, Multiplikationen gleichermaßen) erfordert eine Basisoperation? |
|type="{}"} | |type="{}"} | ||
− | $ | + | $\mathcal{O}_{\rm B} \ = \ $ { 10 } |
− | {Wieviele reelle Operationen erfordert der gesamte FFT–Algorithmus? Welche | + | {Wieviele reelle Operationen $(\mathcal{O}_{\rm FFT})$ erfordert der gesamte FFT–Algorithmus? Welche Werte ergeben sich für $N = 16$ und $N = 1024$? |
|type="{}"} | |type="{}"} | ||
− | $ | + | $N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% } |
+ | $N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 3% } | ||
− | + | {Wie groß ist der Zeitgewinn $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$ für $N = 16$ und $N = 1024$? | |
− | |||
− | {Wie groß ist der Zeitgewinn | ||
|type="{}"} | |type="{}"} | ||
− | $G_{FFT} | + | $N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% } |
− | + | $N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $ { 164 3% } | |
− | $G_{FFT} | ||
</quiz> | </quiz> | ||
Zeile 69: | Zeile 74: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | + | '''(1)''' Jede komplexe Addition erfordert zwei reelle Additionen: | |
− | $$(R_1 + {\rm j} \cdot I_1) + (R_2 + {\rm j} \cdot I_2) = (R_1 + | + | :$$(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} | R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.3cm}\Rightarrow \hspace{0.3cm} | ||
\hspace{0.15 cm}\underline{ A_{\rm A} = | \hspace{0.15 cm}\underline{ A_{\rm A} = | ||
2}\hspace{0.05cm}.$$ | 2}\hspace{0.05cm}.$$ | ||
− | + | ||
− | $$(R_1 + {\rm j} \cdot I_1) (R_2 + {\rm j} \cdot I_2) = (R_1 \cdot | + | |
+ | '''(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 | R_2 - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \cdot | ||
− | I_1) | + | 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}.$$ | 4} \hspace{0.05cm}.$$ | ||
− | + | ||
− | $$ A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu}, | + | |
− | + | '''(3)''' Die Basisoperationen lauten mit den komplexen Eingangsgrößen $E_1$, $E_2$ und $w^{\hspace{0.04cm}\mu}$: | |
− | Dies bedeutet eine komplexe Multiplikation und zwei komplexe Additionen: | + | :$$ 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}.$ | + | \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} | +M_{\rm M} ) = 2 \cdot 2 + 1 \cdot 6\hspace{0.15 cm}\underline{ = 10} | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | + | ||
− | $$ | + | |
− | + | '''(5)''' Insgesamt gibt es ${\rm log_2} \ N$ Stufen, in denen jeweils $N/2$ Basisoperationen auszuführen sind: | |
− | $$\Rightarrow \hspace{0.3cm} | + | :$$\mathcal{O}_{\rm FFT} = {\rm log_2}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot |
− | 4 \hspace{0.15 cm}\underline{= 320}, | + | \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} | \cdot 10 \hspace{0.15 cm}\underline{= 51200} | ||
\hspace{0.05cm}.$$ | \hspace{0.05cm}.$$ | ||
− | + | ||
− | $$G_{\rm FFT} = \frac{ | + | |
− | N \cdot {\rm | + | '''(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 | |
− | $$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot | + | N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm |
− | \frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, | + | 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}.$$ | \hspace{0.05cm}.$$ | ||
Aktuelle Version vom 22. Mai 2021, 09:21 Uhr
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 hier 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}.$$