Aufgaben:Aufgabe 5.5Z: Rechenaufwand für die FFT - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:38:20Z

Add English interlanguage link

← Nächstältere Version		Version vom 16. März 2026, 14:38 Uhr
Zeile 97:		Zeile 97:

	'''(6)'''  Der Rechenzeitgewinn der FFT gegenüber der herkömmlichen DFT ergibt sich zu:		'''(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}{ {\~~rmlog_2~~}\hspace{0.1cm}N}$$		:$$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}.$$		:$$\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}.$$

Zeile 106:		Zeile 106:

	[[Category:Aufgaben zu Signaldarstellung\|^5. Zeit- und frequenzdiskrete Signaldarstellung^]]		[[Category:Aufgaben zu Signaldarstellung\|^5. Zeit- und frequenzdiskrete Signaldarstellung^]]
			[[en:Aufgaben:Exercise_5.5Z:_Complexity_of_the_FFT]]

Maintenance script: Fix MathJax: add space after \cdot before letter

2026-02-25T13:19:26Z

Fix MathJax: add space after \cdot before letter

← Nächstältere Version		Version vom 25. Februar 2026, 15:19 Uhr
Zeile 76:		Zeile 76:

	'''(2)'''  Eine jede komplexe Multiplikation benötigt vier reelle Multiplikationen und zwei reelle Additionen:		'''(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 \~~cdotR_2~~ - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \~~cdotI_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}.$$		:$$(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}.$$


Zeile 97:		Zeile 97:

	'''(6)'''  Der Rechenzeitgewinn der FFT gegenüber der herkömmlichen DFT ergibt sich zu:		'''(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 \~~cdotN~~ \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rmlog_2}\hspace{0.1cm}N}$$		:$$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}{ {\rmlog_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}.$$		:$$\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}.$$

Maintenance script: Join multi-line formulas for MW 1.43 parser compat

2026-02-24T13:40:13Z

Join multi-line formulas for MW 1.43 parser compat

← Nächstältere Version		Version vom 24. Februar 2026, 15:40 Uhr
Zeile 14:		Zeile 14:
	*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}.$		*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:		*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 j},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j}\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$
	\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.		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.
Zeile 75:		Zeile 72:
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Jede komplexe Addition erfordert zwei reelle Additionen:		'''(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}\hspace{0.15 cm}\underline{ A_{\rm A} =2}\hspace{0.05cm}.$$
	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:		'''(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_1 + {\rm j} \cdot I_1) (R_2 + {\rm j} \cdot I_2) = (R_1 \cdotR_2 - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \cdotI_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}.$$
	~~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}.$$


Zeile 98:		Zeile 88:

	*Mit den Ergebnissen der Teilaufgaben  '''(1)''',  '''(2)'''  und  '''(3)'''  erhält man für die Gesamtzahl der Rechenoperationen:		*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}		:$$ \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}.$$
	+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:		'''(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 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$$
	\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 \cdot4 \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}.$$
	:$$\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:		'''(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~~		:$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdotN \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rmlog_2}\hspace{0.1cm}N}$$
	N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm		:$$\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}.$$
	~~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}.$$

Guenter am 22. Mai 2021 um 08:21 Uhr

2021-05-22T08:21:49Z

Guenter am 16. Oktober 2019 um 12:27 Uhr

2019-10-16T12:27:11Z

Guenter am 16. Oktober 2019 um 09:05 Uhr

2019-10-16T09:05:27Z

Guenter am 29. Juli 2018 um 17:30 Uhr

2018-07-29T17:30:39Z

Mwiki-lnt: Textersetzung - „\\sSollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0\.” ein.“ durch „ “

2018-05-29T12:03:56Z

Textersetzung - „\*\s*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0\.” ein.“ durch „ “

← Nächstältere Version		Version vom 29. Mai 2018, 14:03 Uhr
Zeile 30:		Zeile 30:
	''Hinweise:''		''Hinweise:''
	*Die Aufgabe gehört zum Kapitel [[Signaldarstellung/Fast-Fouriertransformation_(FFT)\|Fast-Fouriertransformation (FFT)]].		*Die Aufgabe gehört zum Kapitel [[Signaldarstellung/Fast-Fouriertransformation_(FFT)\|Fast-Fouriertransformation (FFT)]].
	*Sollte die Eingabe des Zahlenwertes &bdquo;0” erforderlich sein, so geben Sie bitte &bdquo;0.” ein.

Guenter am 3. Februar 2018 um 15:56 Uhr

2018-02-03T15:56:19Z

← Nächstältere Version		Version vom 3. Februar 2018, 17:56 Uhr
Zeile 40:		Zeile 40:
	{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 $(A_{\rm M})$ und Multiplikationen $(M_{\rm M})$ sind für eine komplexe Multiplikation erforderlich?		{Wieviele reelle Additionen $(A_{\rm M})$ und Multiplikationen $(M_{\rm M})$ sind für eine komplexe Multiplikation erforderlich?
	\|type="{}"}		\|type="{}"}
	$A_{\rm M} \ = \ $ { 2 }		$A_{\rm M} \hspace{0.3cm} = \ $ { 2 }
	$M_{\rm M} \ = \ $ { 4 }		$M_{\rm M} \hspace{0.2cm} = \ $ { 4 }

	{Wieviele komplexe Additionen/Subtraktionen $(a_{\rm B})$ erfordert eine einzige Basisoperation (&bdquo;Butterfly”)?		{Wieviele komplexe Additionen/Subtraktionen $(a_{\rm B})$ erfordert eine einzige Basisoperation (&bdquo;Butterfly”)?
	<br>Wieviele komplexe Multiplikationen $(m_{\rm B})$ sind pro Basisoperation notwendig?		<br>Wieviele komplexe Multiplikationen $(m_{\rm B})$ sind pro Basisoperation notwendig?
	\|type="{}"}		\|type="{}"}
	$a_{\rm B} \ = \ $ { 2 }		$a_{\rm B} \hspace{0.32cm} = \ $ { 2 }
	$m_{\rm B} \ = \ $ { 1 }		$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="{}"}
	$O_{\rm B} \ = \ $ { 10 }		$\mathcal{O}_{\rm B} \ = \ $ { 10 }

	{Wieviele reelle Operationen $(\mathcal{O}_{\rm FFT})$ erfordert der gesamte FFT–Algorithmus? Welche Werte ergeben sich für $N = 16$ und $N = 1024$?		{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.~~6cm~~} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }		$N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }
	$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 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 $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$ für $N = 16$ und $N = 1024$?
	\|type="{}"}		\|type="{}"}
	$N = 16\text{:} \hspace{0.~~6cm~~} G_{\rm FFT} \ = \ $ { 6.4 3% }		$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }
	$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $ { 164 3% }		$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $ { 164 3% }

Zeile 76:		Zeile 76:
	\hspace{0.15 cm}\underline{ A_{\rm A} =		\hspace{0.15 cm}\underline{ A_{\rm A} =
	2}\hspace{0.05cm}.$$		2}\hspace{0.05cm}.$$


	'''(2)'''  Eine jede komplexe Multiplikation benötigt vier reelle Multiplikationen und zwei reelle Additionen:		'''(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_1 + {\rm j} \cdot I_1) (R_2 + {\rm j} \cdot I_2) = (R_1 \cdot
Zeile 82:		Zeile 84:
	\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{A_{\rm M} = 2,\hspace{0.3cm}M_{\rm M} =		\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}.$$


	'''(3)'''  Die Basisoperationen lauten mit den komplexen Eingangsgrößen $E_1$, $E_2$ und $w^\mu$:		'''(3)'''  Die Basisoperationen lauten mit den komplexen Eingangsgrößen $E_1$, $E_2$ und $w^\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}.$$		:$$ 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}		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 Computern ~~in der Anfangszeit~~ 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:
	:$$ O_{\rm B} = a_{\rm B}\cdot A_{\rm A} + a_{\rm B}\cdot (A_{\rm M}
			'''(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 ld} N$ Stufen, in denen jeweils $N/2$ Basisoperationen auszuführen sind:
	:$$O_{\rm FFT} = {\rm ld}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot
	O_{\rm B} = 5 \cdot N \cdot {\rm ld}\hspace{0.1cm}N$$		'''(5)'''  Insgesamt gibt es ${\rm log_2} \ N$ Stufen, in denen jeweils $N/2$ Basisoperationen auszuführen sind:
	:$$\Rightarrow \hspace{0.3cm}O_{\rm FFT}\hspace{0.1cm}(N=16) = 5\cdot 16 \cdot		:$$\mathcal{O}_{\rm FFT} = {\rm log_2}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot
	4 \hspace{0.15 cm}\underline{= 320}, \hspace{0.5cm}O_{\rm FFT}\hspace{0.1cm}(N=1024) = 5\cdot 1024		\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}.$$


	'''(6)'''  Der Rechenzeitgewinn der FFT gegenüber der herkömmlichen DFT ergibt sich zu:		'''(6)'''  Der Rechenzeitgewinn der FFT gegenüber der herkömmlichen DFT ergibt sich zu:
	:$$G_{\rm FFT} = \frac{O_{\rm DFT}}{O_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdot		:$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdot
	N \cdot {\rm ld}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm		N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm
	ld}\hspace{0.1cm}N}$$		log_2}\hspace{0.1cm}N}$$
	:$$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot		:$$\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}		\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}

Guenter am 3. Februar 2018 um 15:39 Uhr

2018-02-03T15:39:24Z

← Nächstältere Version		Version vom 3. Februar 2018, 17:39 Uhr
Zeile 3:		Zeile 3:
	}}		}}

	[[Datei:P_ID1179__Sig_Z_5_5.png\|right\|~~Zum Rechenaufwand~~ der FFT]]		[[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. Im Einzelnen sind zur Durchführung einer FFT folgende Rechenschritte notwendig:
	*Die FFT geschieht in ${\rm 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 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.		*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:		*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 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}.$		*Hierbei bezeichnet $w = {\rm e}^{-{\rm j} 2\pi/N}$ den komplexen Drehfaktor. Für das Beispiel $N = 8$ hat dieser den 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:		*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 = {1}/{\sqrt{2}}- {\rm j}		:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}
Zeile 17:		Zeile 17:
	\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 $(O_{\rm FFT})$ ermittelt und mit dem für die DFT angebbaren Wert $O_{\rm DFT} ≈ 8\cdot N^2$ verglichen werden.		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 deshalb unberücksichtigt bleiben.		*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.		*Die Bitumkehroperation – eine Umsortierung, die vor der ersten Stufe durchzuführen ist – soll bei dieser Abschätzung ebenfalls nicht berücksichtigt werden.






Zeile 27:		Zeile 31:
	*Die Aufgabe gehört zum Kapitel [[Signaldarstellung/Fast-Fouriertransformation_(FFT)\|Fast-Fouriertransformation (FFT)]].		*Die Aufgabe gehört zum Kapitel [[Signaldarstellung/Fast-Fouriertransformation_(FFT)\|Fast-Fouriertransformation (FFT)]].
	*Sollte die Eingabe des Zahlenwertes &bdquo;0” erforderlich sein, so geben Sie bitte &bdquo;0.” ein.		*Sollte die Eingabe des Zahlenwertes &bdquo;0” erforderlich sein, so geben Sie bitte &bdquo;0.” ein.




Zeile 34:		Zeile 40:
	{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} \ = \ $ { 2 }

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

	{Wieviele komplexe Additionen/Subtraktionen $(a_{\rm B})$ erfordert eine einzige Basisoperation (&bdquo;Butterfly”)?		{Wieviele komplexe Additionen/Subtraktionen $(a_{\rm B})$ erfordert eine einzige Basisoperation (&bdquo;Butterfly”)?
	Wieviele komplexe Multiplikationen $(m_{\rm B})$ sind pro Basisoperation notwendig?		<br>Wieviele komplexe Multiplikationen $(m_{\rm B})$ sind pro Basisoperation notwendig?
	\|type="{}"}		\|type="{}"}
	$a_{\rm B} \ = $ { 2 }		$a_{\rm B} \ = \ $ { 2 }
	$m_{\rm B} \ = $ { 1 }		$m_{\rm B} \ = \ $ { 1 }

	{Wieviele Rechenoperationen (Additionen, Subtraktionen, Multiplikationen gleichermaßen) erfordert eine Basisoperation?		{Wieviele Rechenoperationen (Additionen, Subtraktionen, Multiplikationen gleichermaßen) erfordert eine Basisoperation?
	\|type="{}"}		\|type="{}"}
	$O_{\rm B}$ = { 10 }		$O_{\rm B} \ = \ $ { 10 }

	{Wieviele reelle Operationen $(O_{\rm FFT})$ erfordert der gesamte FFT–Algorithmus? Welche Werte ergeben sich für $N = 16$ und $N = 1024$?		{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.6cm} O_{\rm FFT} \ = $ { 320 3% }		$N = 16\text{:} \hspace{0.6cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }
	$N = 1024\text{:} \hspace{0.2cm} O_{\rm FFT} \ = $ { 51200 3% }		$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 3% }

	{Wie groß ist der Zeitgewinn $G_{\rm FFT} = O_{\rm DFT} - O_{\rm FFT}$ für $N = 16$ und $N = 1024$?		{Wie groß ist der Zeitgewinn $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$ für $N = 16$ und $N = 1024$?
	\|type="{}"}		\|type="{}"}
	$N = 16\text{:} \hspace{0.6cm} G_{\rm FFT} \ = $ { 6.4 3% }		$N = 16\text{:} \hspace{0.6cm} G_{\rm FFT} \ = \ $ { 6.4 3% }
	$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = $ { 164 3% }		$N = 1024\text{:} \hspace{0.2cm} G_{\rm FFT} \ = \ $ { 164 3% }

	</quiz>		</quiz>

← Nächstältere Version		Version vom 22. Mai 2021, 10:21 Uhr
Zeile 3:		Zeile 3:
	}}		}}

	[[Datei:P_ID1179__Sig_Z_5_5.png\|right\|frame\|Letzte Stufe der FFT für $N=8$]]		[[Datei:P_ID1179__Sig_Z_5_5.png\|right\|frame\|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:		Der FFT–Algorithmus  (Fast Fourier Transform)  realisiert eine  &bdquo;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 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.		*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:		*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}\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}.$		*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:		*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 20:		Zeile 22:

	Zu beachten ist:		Zu beachten ist:
	*Sinnvollerweise werden die Potenzen von  $w$  vor dem eigentlichen Algorithmus berechnet und in einer Lookup–Tabelle abgelegt.		*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 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.		*Die Bitumkehroperation – eine Umsortierung, die vor der ersten Stufe durchzuführen ist – soll bei dieser Abschätzung ebenfalls nicht berücksichtigt werden.

Zeile 59:		Zeile 60:
	$\mathcal{O}_{\rm B} \ = \ $ { 10 }		$\mathcal{O}_{\rm B} \ = \ $ { 10 }

	{Wieviele reelle Operationen  $(\mathcal{O}_{\rm FFT})$  erfordert der gesamte FFT–Algorithmus? Welche Werte ergeben sich für  $N = 16$  und  $N = 1024$?		{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 = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }

← Nächstältere Version		Version vom 16. Oktober 2019, 14:27 Uhr
Zeile 88:		Zeile 88:


	'''(3)'''  Die Basisoperationen lauten mit den komplexen Eingangsgrößen $E_1$, $E_2$ und $w^{\hspace{0.04cm}\mu}$:		'''(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}.$$		:$$ 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}		*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}.$

Zeile 96:		Zeile 96:
	'''(4)'''  Im Gegensatz zu den ersten Computern nimmt heute eine Multiplikation keine wesentlich größere Rechenzeit in Anspruch als eine Addition bzw. Subtraktion.		'''(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:		*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}		:$$ \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}
Zeile 102:		Zeile 102:


	'''(5)'''  Insgesamt gibt es ${\rm log_2} \ N$ Stufen, in denen jeweils $N/2$ Basisoperationen auszuführen sind:		'''(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 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$$		\mathcal{O}_{\rm B} = 5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N$$

← Nächstältere Version		Version vom 16. Oktober 2019, 11:05 Uhr
Zeile 4:		Zeile 4:

	[[Datei:P_ID1179__Sig_Z_5_5.png\|right\|frame\|Letzte Stufe der FFT für $N=8$]]		[[Datei:P_ID1179__Sig_Z_5_5.png\|right\|frame\|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:		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 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.		*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:		*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}\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}.$		*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$ ~~dieses~~ komplexen ~~Drehfaktors~~ kann alle ganzzahligen Werte zwischen $0$ und $N/2-1$ annehmen. Für $N = 8$ gilt:		*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 17:
	\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 $(\mathcal{O}_{\rm FFT})$ ermittelt und mit dem für die DFT angebbaren Wert $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$ verglichen werden.		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.		*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 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.		*Die Bitumkehroperation – eine Umsortierung, die vor der ersten Stufe durchzuführen ist – soll bei dieser Abschätzung ebenfalls nicht berücksichtigt werden.
Zeile 29:		Zeile 29:


	''~~Hinweise~~:''
	*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 39:		Zeile 40:

	<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} \hspace{0.3cm} = \ $ { 2 }		$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?		{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 }		$A_{\rm M} \hspace{0.3cm} = \ $ { 2 }
	$M_{\rm M} \hspace{0.2cm} = \ $ { 4 }		$M_{\rm M} \hspace{0.2cm} = \ $ { 4 }

	{Wieviele komplexe Additionen/Subtraktionen $(a_{\rm B})$ erfordert eine einzige Basisoperation (&bdquo;Butterfly”)?		{Wieviele komplexe Additionen/Subtraktionen  $(a_{\rm B})$  erfordert eine einzige Basisoperation (&bdquo;Butterfly”)?
	<br>Wieviele komplexe Multiplikationen $(m_{\rm B})$ sind pro Basisoperation notwendig?		<br>Wieviele komplexe Multiplikationen  $(m_{\rm B})$  sind pro Basisoperation notwendig?
	\|type="{}"}		\|type="{}"}
	$a_{\rm B} \hspace{0.32cm} = \ $ { 2 }		$a_{\rm B} \hspace{0.32cm} = \ $ { 2 }
	$m_{\rm B} \hspace{0.2cm} = \ $ { 1 }		$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 }		$\mathcal{O}_{\rm B} \ = \ $ { 10 }

	{Wieviele reelle Operationen $(\mathcal{O}_{\rm FFT})$ erfordert der gesamte FFT–Algorithmus? Welche Werte ergeben sich für $N = 16$ und $N = 1024$?		{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 = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }
	$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 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  $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$  für  $N = 16$  und  $N = 1024$?
	\|type="{}"}		\|type="{}"}
	$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }		$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }

← Nächstältere Version		Version vom 29. Juli 2018, 19:30 Uhr
Zeile 10:		Zeile 10:
	:$$ 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 ~~das Beispiel~~ $N = 8$ ~~hat dieser den~~ 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}.$		*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$ dieses komplexen Drehfaktors kann alle ganzzahligen Werte zwischen $0$ und $N/2-1$ annehmen. Für $N = 8$ gilt:		*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 = {1}/{\sqrt{2}}- {\rm j}		:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}
Zeile 20:		Zeile 20:

	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 deshalb unberücksichtigt bleiben.		*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.		*Die Bitumkehroperation – eine Umsortierung, die vor der ersten Stufe durchzuführen ist – soll bei dieser Abschätzung ebenfalls nicht berücksichtigt werden.

Zeile 86:		Zeile 87:


	'''(3)'''  Die Basisoperationen lauten mit den komplexen Eingangsgrößen $E_1$, $E_2$ und $w^\mu$:		'''(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}.$$		:$$ 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}		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}
Zeile 94:		Zeile 95:
	'''(4)'''  Im Gegensatz zu den ersten Computern nimmt heute eine Multiplikation keine wesentlich größere Rechenzeit in Anspruch als eine Addition bzw. Subtraktion.		'''(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:		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}		:$$ \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}