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

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 33: Zeile 33:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice Frage
+
{Wieviele reelle Additionen (<i>A</i><sub>A</sub>) erfordert eine komplexe Addition?
|type="[]"}
+
|type="{}"}
- Falsch
+
$A_A$ = { 2 3% }
+ Richtig
+
 
 +
{Wieviele reelle Additionen (<i>A</i><sub>M</sub>) und Multiplikationen (<i>M</i><sub>M</sub>) sind für eine komplexe Multiplikation erforderlich?
 +
|type="{}"}
 +
$A_M$ = { 2 3% }
 +
 
 +
$M_M$ = { 4 3% }
 +
 
 +
{Wieviele komplexe Additionen/Subtraktionen (<i>a</i><sub>B</sub>) erfordert eine einzige Basisoperation (&bdquo;Butterfly&rdquo;)? 
 +
Wieviele komplexe Multiplikationen (<i>m</i><sub>B</sub>) sind pro Basisoperation notwendig?
 +
|type="{}"}
 +
$a_B$ = { 2 3% }
  
 +
$m_B$ = { 1 3% }
  
{Input-Box Frage
+
{Wieviele Rechenoperationen (Additionen, Subtraktionen, Multiplikationen gleichermaßen) erfordert eine Basisoperation?
 
|type="{}"}
 
|type="{}"}
$\alpha$ = { 0.3 }
+
$O_B$ = { 10 3% }
  
 +
{Wieviele reelle Operationen erfordert der gesamte FFT&ndash;Algorithmus? Welche Zahlenwerte ergeben sich für <i>N</i> = 16 und <i>N</i> = 1024?
 +
|type="{}"}
 +
$O_{FFT} (N = 16 )$ = { 320 3% }
 +
 +
$O_{FFT} (N = 1024 )$ = { 51200 3% }
 +
 +
{Wie groß ist der Zeitgewinn <i>G</i><sub>FFT</sub> = <i>O</i><sub>DFT</sub>/<i>O</i><sub>FFT</sub> für <i>N</i> = 16 und <i>N</i> = 1024?
 +
|type="{}"}
 +
$G_{FFT} (N = 16 )$ = { 6.4 3% }
  
 +
$G_{FFT} (N = 16 )$ = { 164 3% }
  
 
</quiz>
 
</quiz>

Version vom 17. März 2017, 12:45 Uhr

P ID1179 Sig Z 5 5.png

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 $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 = exp(–j · 2π/N) den komplexen Drehfaktor. Für das Beispiel N = 8 hat dieser folgenden 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$ dieses komplexen Drehfaktors kann alle ganzzahligen Werte zwischen 0 und N/2 –1 annehmen. Für N = 8 gilt:

$w^0 = 1,\hspace{0.2cm}w^1 = \frac{1}{\sqrt{2}}- {\rm j} \cdot\frac{1}{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm j},\hspace{0.2cm}w^3 = -\frac{1}{\sqrt{2}}- {\rm j} \cdot\frac{1}{\sqrt{2}} \hspace{0.05cm}.$

Mit dieser Aufgabe sollen die für die FFT erforderliche Anzahl von Rechenoperationen $(O_{FFT})$ ermittelt und mit dem für die DFT angebbaren Wert $O_{DFT}$ ≈ 8N$ ^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.

Fragebogen

1

Wieviele reelle Additionen (AA) erfordert eine komplexe Addition?

$A_A$ =

2

Wieviele reelle Additionen (AM) und Multiplikationen (MM) sind für eine komplexe Multiplikation erforderlich?

$A_M$ =

$M_M$ =

3

Wieviele komplexe Additionen/Subtraktionen (aB) erfordert eine einzige Basisoperation („Butterfly”)? Wieviele komplexe Multiplikationen (mB) sind pro Basisoperation notwendig?

$a_B$ =

$m_B$ =

4

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

$O_B$ =

5

Wieviele reelle Operationen erfordert der gesamte FFT–Algorithmus? Welche Zahlenwerte ergeben sich für N = 16 und N = 1024?

$O_{FFT} (N = 16 )$ =

$O_{FFT} (N = 1024 )$ =

6

Wie groß ist der Zeitgewinn GFFT = ODFT/OFFT für N = 16 und N = 1024?

$G_{FFT} (N = 16 )$ =

$G_{FFT} (N = 16 )$ =


Musterlösung

1. 2. 3. 4. 5. 6. 7.