Aufgaben:Aufgabe 5.5Z: Rechenaufwand für die FFT: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Signaldarstellung/Fast-Fouriertransformation (FFT) }} [[Datei:|right|]] ===Fragebogen=== <quiz display=simple> {Multiple-Choice Fr…“)
 
 
(16 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:|right|]]
+
[[Datei:P_ID1179__Sig_Z_5_5.png|right|frame|Letzte Stufe der FFT für&nbsp; $N=8$]]
 +
Der FFT–Algorithmus&nbsp; (Fast Fourier Transform)&nbsp; realisiert eine&nbsp; &bdquo;Diskrete Fouriertransformation&rdquo;&nbsp; mit dem kleinstmöglichen Rechenaufwand, wenn der Parameter&nbsp; $N$&nbsp; eine Zweierpotenz ist.
 +
 
 +
Im Einzelnen sind zur Durchführung einer FFT folgende Rechenschritte notwendig:
 +
*Die FFT geschieht in&nbsp; ${\rm log_2} \ N$&nbsp; 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&nbsp; $N = 8$.&nbsp; Man erkennt, dass in dieser und auch den anderen Stufen jeweils&nbsp; $N/2$&nbsp; Basisoperationen durchzuführen sind.
 +
*In jeder Basisoperation, die man häufig auch als&nbsp; '''Butterfly'''&nbsp; bezeichnet, werden aus den beiden komplexen Eingangsgrößen&nbsp; $E_1$&nbsp; und&nbsp; $E_2$&nbsp; 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&nbsp; $w =  {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$&nbsp; den komplexen Drehfaktor.&nbsp; Für&nbsp;  $N = 8$&nbsp; ergibt sich der Wert&nbsp; $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&nbsp; $\mu$&nbsp; für diesen komplexen Drehfaktor kann alle ganzzahligen Werte zwischen&nbsp; $0$&nbsp; und&nbsp; $N/2-1$&nbsp; annehmen.&nbsp; Für&nbsp; $N = 8$&nbsp; 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&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; ermittelt und mit dem für die DFT angebbaren Wert&nbsp; $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$&nbsp; verglichen werden.
 +
 
 +
Zu beachten ist:
 +
*Sinnvollerweise werden die Potenzen von&nbsp; $w$&nbsp; vor dem eigentlichen Algorithmus berechnet und in einer Lookup–Tabelle abgelegt.&nbsp; 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&nbsp; [[Signaldarstellung/Fast-Fouriertransformation_(FFT)|Fast-Fouriertransformation (FFT)]].
 +
 +
 
 +
 
  
  
Zeile 9: Zeile 41:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice Frage
+
{Wieviele reelle Additionen&nbsp; $(A_{\rm A})$&nbsp; erfordert eine komplexe Addition?
|type="[]"}
+
|type="{}"}
- Falsch
+
$A_{\rm A} \hspace{0.3cm} = \ $ { 2 }
+ Richtig
 
  
 +
{Wieviele reelle Additionen&nbsp; $(A_{\rm M})$&nbsp; und Multiplikationen&nbsp; $(M_{\rm M})$&nbsp; sind für eine komplexe Multiplikation erforderlich?
 +
|type="{}"}
 +
$A_{\rm M} \hspace{0.3cm} = \  $ { 2 }
 +
$M_{\rm M} \hspace{0.2cm} = \  $ { 4 }
  
{Input-Box Frage
+
{Wieviele komplexe Additionen/Subtraktionen&nbsp; $(a_{\rm B})$&nbsp; erfordert eine einzige Basisoperation (&bdquo;Butterfly&rdquo;)? 
 +
<br>Wieviele komplexe Multiplikationen&nbsp; $(m_{\rm B})$&nbsp; sind pro Basisoperation notwendig?
 
|type="{}"}
 
|type="{}"}
$\alpha$ = { 0.3 }
+
$a_{\rm B} \hspace{0.32cm} = \ $  { 2 }
 +
$m_{\rm B} \hspace{0.2cm} = \ $  { 1 }
  
 +
{Wieviele Rechenoperationen&nbsp; (Additionen, Subtraktionen, Multiplikationen gleichermaßen)&nbsp; erfordert eine Basisoperation?
 +
|type="{}"}
 +
$\mathcal{O}_{\rm B} \ = \ $  { 10 }
  
 +
{Wieviele reelle Operationen&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; erfordert der gesamte FFT&ndash;Algorithmus?&nbsp; Welche Werte ergeben sich für&nbsp; $N = 16$&nbsp; und&nbsp; $N = 1024$?
 +
|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&nbsp; $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$&nbsp; für&nbsp; $N = 16$&nbsp; und&nbsp; $N = 1024$?
 +
|type="{}"}
 +
$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }
 +
$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $ { 164 3% }
  
 
</quiz>
 
</quiz>
Zeile 25: Zeile 74:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.'''
+
'''(1)'''&nbsp; Jede komplexe Addition erfordert zwei reelle Additionen:
'''2.'''
+
:$$(R_1 + {\rm j} \cdot I_1) + (R_2 + {\rm j} \cdot I_2) = (R_1 +
'''3.'''
+
R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.3cm}\Rightarrow \hspace{0.3cm}
'''4.'''
+
\hspace{0.15 cm}\underline{ A_{\rm A} =
'''5.'''
+
2}\hspace{0.05cm}.$$
'''6.'''
+
 
'''7.'''
+
 
 +
'''(2)'''&nbsp; 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)'''&nbsp; Die Basisoperationen lauten mit den komplexen Eingangsgrößen&nbsp; $E_1$,&nbsp; $E_2$&nbsp; und&nbsp; $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: &nbsp; $\hspace{0.15 cm}\underline{a_{\rm B} = 2, \hspace{0.2cm}m_{\rm B} = 1}
 +
\hspace{0.05cm}.$
 +
 
 +
 
 +
'''(4)'''&nbsp; 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&nbsp; '''(1)''',&nbsp; '''(2)'''&nbsp; und&nbsp; '''(3)'''&nbsp; 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)'''&nbsp; Insgesamt gibt es&nbsp; ${\rm log_2} \ N$ Stufen, in denen jeweils&nbsp; $N/2$&nbsp; 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)'''&nbsp; 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}.$$
 +
 
 +
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 22. Mai 2021, 09:21 Uhr

Letzte Stufe der FFT für  $N=8$

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:



Fragebogen

1

Wieviele reelle Additionen  $(A_{\rm A})$  erfordert eine komplexe Addition?

$A_{\rm A} \hspace{0.3cm} = \ $

2

Wieviele reelle Additionen  $(A_{\rm M})$  und Multiplikationen  $(M_{\rm M})$  sind für eine komplexe Multiplikation erforderlich?

$A_{\rm M} \hspace{0.3cm} = \ $

$M_{\rm M} \hspace{0.2cm} = \ $

3

Wieviele komplexe Additionen/Subtraktionen  $(a_{\rm B})$  erfordert eine einzige Basisoperation („Butterfly”)?
Wieviele komplexe Multiplikationen  $(m_{\rm B})$  sind pro Basisoperation notwendig?

$a_{\rm B} \hspace{0.32cm} = \ $

$m_{\rm B} \hspace{0.2cm} = \ $

4

Wieviele Rechenoperationen  (Additionen, Subtraktionen, Multiplikationen gleichermaßen)  erfordert eine Basisoperation?

$\mathcal{O}_{\rm B} \ = \ $

5

Wieviele reelle Operationen  $(\mathcal{O}_{\rm FFT})$  erfordert der gesamte FFT–Algorithmus?  Welche Werte ergeben sich für  $N = 16$  und  $N = 1024$?

$N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $

$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $

6

Wie groß ist der Zeitgewinn  $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$  für  $N = 16$  und  $N = 1024$?

$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $

$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $


Musterlösung

(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_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}.$$