Signaldarstellung/Fast-Fouriertransformation (FFT) - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:28:30Z

Add English interlanguage link

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

	{{Display}}		{{Display}}
			[[en:Signal_Representation/Fast_Fourier_Transform_(FFT)]]

Maintenance script: Fix MathJax: add space after \cdot before R_2 and I_1

2026-02-25T13:17:03Z

Fix MathJax: add space after \cdot before R_2 and I_1

← Nächstältere Version		Version vom 25. Februar 2026, 15:17 Uhr
Zeile 22:		Zeile 22:
	:$$(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.05cm}.$$		:$$(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.05cm}.$$
	*Jede komplexe Multiplikation erfordert vier reelle Multiplikationen und zwei reelle Additionen (eine Subtraktion wird wie eine Addition behandelt):		*Jede komplexe Multiplikation erfordert vier reelle Multiplikationen und zwei reelle Additionen (eine Subtraktion wird wie eine Addition behandelt):
	:$$(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.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.05cm}.$$
	*Somit sind zur Berechnung aller  $N$  Koeffizienten insgesamt die folgende Anzahl  $M$  reeller Multiplikationen und die Anzahl  $A$  reeller Additionen erforderlich:		*Somit sind zur Berechnung aller  $N$  Koeffizienten insgesamt die folgende Anzahl  $M$  reeller Multiplikationen und die Anzahl  $A$  reeller Additionen erforderlich:
	:$$M = 4 \cdot N \cdot (N-1),$$		:$$M = 4 \cdot N \cdot (N-1),$$

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

2026-02-24T13:38:03Z

Join multi-line formulas for MW 1.43 parser compat

← Nächstältere Version		Version vom 24. Februar 2026, 15:38 Uhr
Zeile 14:		Zeile 14:
	gemäß den in Kapitel  [[Signaldarstellung/Diskrete_Fouriertransformation_(DFT)\|Diskrete Fouriertransformation]]  angegebenen Gleichungen ist der große Rechenaufwand.  Wir betrachten als Beispiel die  $\rm DFT$, also die Berechnung der Spektralkoeffizienten  $D(\mu)$  aus den Zeitkoeffizienten  $d(\nu)$:		gemäß den in Kapitel  [[Signaldarstellung/Diskrete_Fouriertransformation_(DFT)\|Diskrete Fouriertransformation]]  angegebenen Gleichungen ist der große Rechenaufwand.  Wir betrachten als Beispiel die  $\rm DFT$, also die Berechnung der Spektralkoeffizienten  $D(\mu)$  aus den Zeitkoeffizienten  $d(\nu)$:

	:$$N \cdot D(\mu) = \sum_{\nu = 0 }^{N-1}		:$$N \cdot D(\mu) = \sum_{\nu = 0 }^{N-1}d(\nu) \cdot {w}^{\hspace{0.03cm}\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu}= d(0) \cdot w^{\hspace{0.03cm}0} + d(1) \cdot w^{\hspace{0.03cm}\mu}+ d(2) \cdot w^{\hspace{0.03cm}2\mu}+\hspace{0.05cm}\text{ ...} \hspace{0.05cm}+ d(N-1) \cdot w^{\hspace{0.03cm}(N-1)\cdot \mu}.$$
	d(\nu) \cdot {w}^{\hspace{0.03cm}\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu}
	=
	d(0) \cdot w^{\hspace{0.03cm}0} + d(1) \cdot w^{\hspace{0.03cm}\mu}+ d(2) \cdot w^{\hspace{0.03cm}2\mu}+\hspace{0.05cm}\text{ ...} \hspace{0.05cm}+ d(N-1) \cdot w^{\hspace{0.03cm}(N-1)\cdot \mu}.$$

	Der hierfür erforderliche Rechenaufwand soll abgeschätzt werden, wobei wir davon ausgehen, dass die Potenzen des komplexen Drehfaktors  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N}$  bereits in Real– und Imaginärteilform in einer Lookup–Tabelle vorliegen.		Der hierfür erforderliche Rechenaufwand soll abgeschätzt werden, wobei wir davon ausgehen, dass die Potenzen des komplexen Drehfaktors  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N}$  bereits in Real– und Imaginärteilform in einer Lookup–Tabelle vorliegen.
Zeile 23:		Zeile 20:
	Zur Berechnung eines einzelnen Koeffizienten benötigt man dann  $N-1$  komplexe Multiplikationen und ebenso viele komplexe Additionen, wobei zu beachten ist:		Zur Berechnung eines einzelnen Koeffizienten benötigt man dann  $N-1$  komplexe Multiplikationen und ebenso viele komplexe Additionen, wobei zu beachten ist:
	*Jede komplexe Addition erfordert zwei reelle Additionen:		*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.05cm}.$$
	R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.05cm}.$$
	*Jede komplexe Multiplikation erfordert vier reelle Multiplikationen und zwei reelle Additionen (eine Subtraktion wird wie eine Addition behandelt):		*Jede komplexe Multiplikation erfordert vier reelle Multiplikationen und zwei reelle Additionen (eine Subtraktion wird wie eine Addition behandelt):
	:$$(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.05cm}.$$
	~~R_2~~ - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \~~cdot~~
	~~I_1~~)\hspace{0.05cm}.$$
	*Somit sind zur Berechnung aller  $N$  Koeffizienten insgesamt die folgende Anzahl  $M$  reeller Multiplikationen und die Anzahl  $A$  reeller Additionen erforderlich:		*Somit sind zur Berechnung aller  $N$  Koeffizienten insgesamt die folgende Anzahl  $M$  reeller Multiplikationen und die Anzahl  $A$  reeller Additionen erforderlich:
	:$$M = 4 \cdot N \cdot (N-1),$$		:$$M = 4 \cdot N \cdot (N-1),$$
	:$$A = 2 \cdot N \cdot		:$$A = 2 \cdot N \cdot(N-1)+2 \cdot N \cdot (N-1)=M \hspace{0.05cm}.$$
	(N-1)+2 \cdot N \cdot (N-1)=M \hspace{0.05cm}.$$
	*In heutigen Rechnern benötigen Multiplikationen und Additionen/Subtraktionen etwa die gleiche Rechenzeit.  Es genügt, die Gesamtzahl  $\mathcal{O} = M + A$  aller Operationen zu betrachten:		*In heutigen Rechnern benötigen Multiplikationen und Additionen/Subtraktionen etwa die gleiche Rechenzeit.  Es genügt, die Gesamtzahl  $\mathcal{O} = M + A$  aller Operationen zu betrachten:
	:$$\mathcal{O} = 8 \cdot N \cdot (N-1) \approx 8 \cdot N^2\hspace{0.05cm}.$$		:$$\mathcal{O} = 8 \cdot N \cdot (N-1) \approx 8 \cdot N^2\hspace{0.05cm}.$$
Zeile 53:		Zeile 46:
	*Die Folge  $\langle \hspace{0.1cm}d(\nu)\hspace{0.1cm}\rangle$  der Länge  $N$  wird in zwei Teilfolgen  $\langle \hspace{0.1cm}d_1(\nu)\hspace{0.1cm}\rangle$  und  $\langle \hspace{0.1cm} d_2(\nu)\hspace{0.1cm}\rangle$  jeweils halber Länge separiert (in der Garafik gelb bzw. grün hinterlegt).  Mit  $0 \le \nu \lt N/2$  erhält man so die Folgenelemente		*Die Folge  $\langle \hspace{0.1cm}d(\nu)\hspace{0.1cm}\rangle$  der Länge  $N$  wird in zwei Teilfolgen  $\langle \hspace{0.1cm}d_1(\nu)\hspace{0.1cm}\rangle$  und  $\langle \hspace{0.1cm} d_2(\nu)\hspace{0.1cm}\rangle$  jeweils halber Länge separiert (in der Garafik gelb bzw. grün hinterlegt).  Mit  $0 \le \nu \lt N/2$  erhält man so die Folgenelemente
	:$$d_1(\nu) = d(2\nu), $$		:$$d_1(\nu) = d(2\nu), $$
	:$$d_2(\nu) = d(2\nu+1)		:$$d_2(\nu) = d(2\nu+1)\hspace{0.05cm}.$$
	\hspace{0.05cm}.$$
	*Die Ausgangsfolgen  $\langle \hspace{0.1cm}D_1(\mu )\hspace{0.1cm}\rangle$  und  $\langle \hspace{0.1cm}D_2(\mu )\hspace{0.1cm}\rangle$  der beiden Teilblöcke ergeben sich daraus jeweils durch eine eigene DFT, aber nun nur noch mit halber Länge  $N/2 = 8$:		*Die Ausgangsfolgen  $\langle \hspace{0.1cm}D_1(\mu )\hspace{0.1cm}\rangle$  und  $\langle \hspace{0.1cm}D_2(\mu )\hspace{0.1cm}\rangle$  der beiden Teilblöcke ergeben sich daraus jeweils durch eine eigene DFT, aber nun nur noch mit halber Länge  $N/2 = 8$:
	:$$\langle \hspace{0.1cm}D_1(\mu) \hspace{0.1cm}\rangle \hspace{0.2cm}\bullet\!\!-\!\!\!-(N/2)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm}d_1(\nu) \hspace{0.1cm}\rangle , $$		:$$\langle \hspace{0.1cm}D_1(\mu) \hspace{0.1cm}\rangle \hspace{0.2cm}\bullet\!\!-\!\!\!-(N/2)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm}d_1(\nu) \hspace{0.1cm}\rangle , $$
	:$$ \langle \hspace{0.1cm}D_2(\mu)\hspace{0.1cm} \rangle \hspace{0.2cm}\bullet\!\!-\!\!\!-(N/2)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm}d_2(\nu) \hspace{0.1cm}\rangle \hspace{0.05cm}.$$		:$$ \langle \hspace{0.1cm}D_2(\mu)\hspace{0.1cm} \rangle \hspace{0.2cm}\bullet\!\!-\!\!\!-(N/2)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm}d_2(\nu) \hspace{0.1cm}\rangle \hspace{0.05cm}.$$
	*Die Ausgangswerte  $\langle \hspace{0.1cm} D_2(\mu )\hspace{0.1cm}\rangle$  der unteren, grünen DFT $($mit  $0 \le \mu \lt N/2)$  werden danach im rot umrandeten Block durch komplexe Drehfaktoren hinsichtlich der Phasenlage verändert:		*Die Ausgangswerte  $\langle \hspace{0.1cm} D_2(\mu )\hspace{0.1cm}\rangle$  der unteren, grünen DFT $($mit  $0 \le \mu \lt N/2)$  werden danach im rot umrandeten Block durch komplexe Drehfaktoren hinsichtlich der Phasenlage verändert:
	:$$D_2(\mu) \hspace{0.3cm} \Rightarrow \hspace{0.3cm}D_2(\mu) \cdot w^{\hspace{0.04cm}\mu}, \hspace{0.2cm}{\rm wobei}\hspace{0.1cm}w =		:$$D_2(\mu) \hspace{0.3cm} \Rightarrow \hspace{0.3cm}D_2(\mu) \cdot w^{\hspace{0.04cm}\mu}, \hspace{0.2cm}{\rm wobei}\hspace{0.1cm}w ={\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N} \hspace{0.05cm}.$$
	{\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N} \hspace{0.05cm}.$$
	*Jeder einzelne  $\text{Butterfly}$  im blau umrandeten Block (in der Grafikmitte) liefert durch Addition bzw. Subtraktion zwei Elemente der gesuchten Ausgangsfolge.  Mit  $0 \le \mu \lt N/2$  gilt dabei:		*Jeder einzelne  $\text{Butterfly}$  im blau umrandeten Block (in der Grafikmitte) liefert durch Addition bzw. Subtraktion zwei Elemente der gesuchten Ausgangsfolge.  Mit  $0 \le \mu \lt N/2$  gilt dabei:
	:$$D(\mu) = {1}/{2}\cdot \big[D_1(\mu) + D_2(\mu) \cdot w^{\hspace{0.04cm}\mu}\big],$$		:$$D(\mu) = {1}/{2}\cdot \big[D_1(\mu) + D_2(\mu) \cdot w^{\hspace{0.04cm}\mu}\big],$$
Zeile 105:		Zeile 96:
	:$${D_1}'(\mu) = {1}/{2}\cdot {D_1}(\mu - {N}/{2})\hspace{0.05cm},$$		:$${D_1}'(\mu) = {1}/{2}\cdot {D_1}(\mu - {N}/{2})\hspace{0.05cm},$$
	:$$ {D_2}'(\mu) = {1}/{2}\cdot {D_2}(\mu {-} {N}/{2})\cdot w^{\hspace{0.04cm}\mu}$$		:$$ {D_2}'(\mu) = {1}/{2}\cdot {D_2}(\mu {-} {N}/{2})\cdot w^{\hspace{0.04cm}\mu}$$
	:$$ \Rightarrow \hspace{0.3cm}{D_2}'(\mu) = { - } {1}/{2}\cdot {D_2}(\mu-N/2)\cdot w^{\hspace{0.04cm}\mu {-} N/2}\hspace{0.05cm}.		:$$ \Rightarrow \hspace{0.3cm}{D_2}'(\mu) = { - } {1}/{2}\cdot {D_2}(\mu-N/2)\cdot w^{\hspace{0.04cm}\mu {-} N/2}\hspace{0.05cm}.$$
	$$

	*Zum Beispiel erhält man mit  $N = 16$   ⇒   $w = {\rm e}^{ – {\rm j}\hspace{0.04cm} \cdot \hspace{0.04cm}\pi/8}$  für die Indizes  $\mu = 1$  bzw.  $\mu = 9$:		*Zum Beispiel erhält man mit  $N = 16$   ⇒   $w = {\rm e}^{ – {\rm j}\hspace{0.04cm} \cdot \hspace{0.04cm}\pi/8}$  für die Indizes  $\mu = 1$  bzw.  $\mu = 9$:
	:$${D_1}'(1) = {1.708}/{2} = 0.854,\hspace{0.8cm}		:$${D_1}'(1) = {1.708}/{2} = 0.854,\hspace{0.8cm}{D_2}'(1) ={1}/{2}\cdot (1.456 + {\rm j} 0.603) \cdot {\rm e}^{ - {\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}\pi/8} = 0.788$$
	{D_2}'(1) ={1}/{2}\cdot (1.456 + {\rm j} 0.603) \cdot {\rm e}^{ - {\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}
	\pi/8} = 0.788$$
	:$$\Rightarrow D(1) = {D_1}'(1)+ {D_2}'(1)= 1.642 \hspace{0.05cm}.$$		:$$\Rightarrow D(1) = {D_1}'(1)+ {D_2}'(1)= 1.642 \hspace{0.05cm}.$$
	:$${D_9}'(1) = {1.708}/{2} = 0.854,\hspace{0.8cm}		:$${D_9}'(1) = {1.708}/{2} = 0.854,\hspace{0.8cm}{D_2}'(9) = - {1}/{2}\cdot (1.456 + {\rm j} 0.603) \cdot {\rm e}^{ - {\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}\pi/8} = - 0.788$$
	{D_2}'(9) = - {1}/{2}\cdot (1.456 + {\rm j} 0.603) \cdot {\rm e}^{ - {\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}
	\pi/8} = - 0.788$$
	:$$\Rightarrow D(9) = {D_1}'(9)+ {D_2}'(9)= 0.066 \hspace{0.05cm}.$$}}		:$$\Rightarrow D(9) = {D_1}'(9)+ {D_2}'(9)= 0.066 \hspace{0.05cm}.$$}}

Guenter am 21. Mai 2021 um 15:12 Uhr

2021-05-21T15:12:35Z

← Nächstältere Version		Version vom 21. Mai 2021, 17:12 Uhr
Zeile 158:		Zeile 158:
	*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von  ${\rm Re}( \nu)$  und  ${\rm Im}( \nu)$  in die Elemente  ${\rm Re}( \kappa)$  und  ${\rm Im}( \kappa)$  eingetragen werden.  Das  $\text{Beispiel 4}$  verdeutlicht die Vorgehensweise.		*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von  ${\rm Re}( \nu)$  und  ${\rm Im}( \nu)$  in die Elemente  ${\rm Re}( \kappa)$  und  ${\rm Im}( \kappa)$  eingetragen werden.  Das  $\text{Beispiel 4}$  verdeutlicht die Vorgehensweise.

	~~<br>~~

	$\text{Beispiel 4: Bitumkehroperation}$		$\text{Beispiel 4: Bitumkehroperation}$
	[[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png\|center\|frame\|Radix-2-Algorithmus $($Bitumkehroperation für  $N = 8)$]]		[[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png\|center\|frame\|Radix-2-Algorithmus $($Bitumkehroperation für  $N = 8)$]]

Guenter am 21. Mai 2021 um 14:50 Uhr

2021-05-21T14:50:58Z

← Nächstältere Version		Version vom 21. Mai 2021, 16:50 Uhr
Zeile 17:		Zeile 17:
	d(\nu) \cdot {w}^{\hspace{0.03cm}\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu}		d(\nu) \cdot {w}^{\hspace{0.03cm}\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu}
	=		=
	d(0) \cdot w^{\hspace{0.03cm}0} + d(1) \cdot w^{\hspace{0.03cm}\mu}+ d(2) \cdot w^{\hspace{0.03cm}2\mu}+\hspace{0.05cm}\text{ ...} \hspace{0.05cm}+ d(N-1) \cdot w^{\hspace{0.03cm}(N-1)\cdot \mu}$$		d(0) \cdot w^{\hspace{0.03cm}0} + d(1) \cdot w^{\hspace{0.03cm}\mu}+ d(2) \cdot w^{\hspace{0.03cm}2\mu}+\hspace{0.05cm}\text{ ...} \hspace{0.05cm}+ d(N-1) \cdot w^{\hspace{0.03cm}(N-1)\cdot \mu}.$$

	Der hierfür erforderliche Rechenaufwand soll abgeschätzt werden, wobei wir davon ausgehen, dass die Potenzen des komplexen Drehfaktors  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N}$  bereits in Real– und Imaginärteilform in einer Lookup–Tabelle vorliegen.		Der hierfür erforderliche Rechenaufwand soll abgeschätzt werden, wobei wir davon ausgehen, dass die Potenzen des komplexen Drehfaktors  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N}$  bereits in Real– und Imaginärteilform in einer Lookup–Tabelle vorliegen.
Zeile 65:		Zeile 65:
	:$$D(\mu +{N}/{2}) = {1}/{2}\cdot \big[D_1(\mu) - D_2(\mu) \cdot w^{\hspace{0.04cm}\mu}\big]\hspace{0.05cm}.$$		:$$D(\mu +{N}/{2}) = {1}/{2}\cdot \big[D_1(\mu) - D_2(\mu) \cdot w^{\hspace{0.04cm}\mu}\big]\hspace{0.05cm}.$$

	Durch  ~~'''~~diese erste Anwendung des Überlagerungssatzes halbiert sich somit in etwa der Rechenaufwand'''.		'''Durch  diese erste Anwendung des Überlagerungssatzes halbiert sich somit in etwa der Rechenaufwand'''.

	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
Zeile 145:		Zeile 145:
	*Wie in der  [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT\|Aufgabe 5.5Z]]  gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für  $N = 1024$  um mehr als den Faktor  $150$.		*Wie in der  [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT\|Aufgabe 5.5Z]]  gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für  $N = 1024$  um mehr als den Faktor  $150$.

	*Die inverse DFT zur Berechnung der ~~Zeit–~~ aus den Spektralkoeffizienten geschieht mit dem gleichen Algorithmus und nur geringfügigen Modifikationen.}}		*Die inverse DFT zur Berechnung der Zeitkoeffizienten aus den Spektralkoeffizienten geschieht mit dem gleichen Algorithmus und nur geringfügigen Modifikationen.}}


Zeile 151:		Zeile 151:
	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Beispiel 3:}$		$\text{Beispiel 3:}$
	Abschließend wird ~~ein~~ C–Programm ~~<br>~~		Abschließend wird das C–Programm  $\text{fft(N, Re, Im)}$  gemäß dem oben beschriebenen Radix–2–Algorithmus angegeben:
	:$$\text{fft(N, Re, Im)}$$
	gemäß dem oben beschriebenen Radix–2–Algorithmus angegeben:

	*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die jeweils  $N$  Real– und Imaginärteile der komplexen Zeitkoeffizienten  $d(0)$, ... , $d( N - 1)$.		*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die jeweils  $N$  Real– und Imaginärteile der komplexen Zeitkoeffizienten  $d(0)$, ... , $d( N - 1)$.
	*In den gleichen Feldern „Re” und „Im” werden am Programmende die komplexen Koeffizienten  $D(0)$, ... , $D( N - 1)$  an das aufrufende Programm zurückgegeben.		*In den gleichen Feldern „Re” und „Im” werden am Programmende die komplexen Koeffizienten  $D(0)$, ... , $D( N - 1)$  an das aufrufende Programm zurückgegeben.
	*Aufgrund der „In–Place”–Programmierung reichen für diesen Algorithmus  $N$  komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.		*Aufgrund der „In–Place”–Programmierung reichen für diesen Algorithmus  $N$  komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.
	*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von  ${\rm Re}( \nu)$  und  ${\rm Im}( \nu)$  in die Elemente  ${\rm Re}( \kappa)$  und  ${\rm Im}( \kappa)$  eingetragen werden.  Das  $\text{Beispiel 4}$  verdeutlicht die Vorgehensweise.}}		*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von  ${\rm Re}( \nu)$  und  ${\rm Im}( \nu)$  in die Elemente  ${\rm Re}( \kappa)$  und  ${\rm Im}( \kappa)$  eingetragen werden.  Das  $\text{Beispiel 4}$  verdeutlicht die Vorgehensweise.

			<br>
	~~[[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png\|right\|frame\|Radix-2-Algorithmus $($Bitumkehroperation für  $N = 8)$]]~~
	~~{{GraueBox\|TEXT=~~
	$\text{Beispiel 4: Bitumkehroperation}$		$\text{Beispiel 4: Bitumkehroperation}$
			[[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png\|center\|frame\|Radix-2-Algorithmus $($Bitumkehroperation für  $N = 8)$]]

	*Der neue Index  $\kappa$  ergibt sich, wenn man den Index  $\nu$  als Dualzahl schreibt und anschließend die  $\text{log}_2 \hspace{0.05cm} N$  Bit in umgekehrter Reihenfolge darstellt.		*Der neue Index  $\kappa$  ergibt sich, wenn man den Index  $\nu$  als Dualzahl schreibt und anschließend die  $\text{log}_2 \hspace{0.05cm} N$  Bit in umgekehrter Reihenfolge darstellt.

Guenter am 20. Mai 2021 um 15:09 Uhr

2021-05-20T15:09:02Z

← Nächstältere Version		Version vom 20. Mai 2021, 17:09 Uhr
Zeile 128:		Zeile 128:
	==Radix-2-Algorithmus nach Cooley und Tukey==		==Radix-2-Algorithmus nach Cooley und Tukey==
	<br>		<br>
	Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren  [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.:  An Algorithm for the Machine Calculation of Complex Fourier Series.  In:  Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>  von  [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]  und  [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]  auf dem Überlagerungssatz der DFT auf.  Es funktioniert nur dann, wenn die Stützstellenzahl  $N$  eine Zweierpotenz ist.		Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren  [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.:  An Algorithm for the Machine Calculation of Complex Fourier Series.  <br>In:  Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>  von  [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]  und  [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]  auf dem Überlagerungssatz der DFT auf.  Es funktioniert nur dann, wenn die Stützstellenzahl  $N$  eine Zweierpotenz ist.

	Die Grafik verdeutlicht den Algorithmus für  $N = 8$, wobei wieder die Transformation vom Zeit– in den Frequenzbereich dargestellt ist.		Die Grafik verdeutlicht den Algorithmus für  $N = 8$, wobei wieder die Transformation vom Zeit– in den Frequenzbereich dargestellt ist.

Guenter am 20. Mai 2021 um 14:53 Uhr

2021-05-20T14:53:14Z

Guenter am 20. Mai 2021 um 14:22 Uhr

2021-05-20T14:22:59Z

Änderungen zeigen

Guenter am 16. Oktober 2019 um 07:03 Uhr

2019-10-16T07:03:08Z

← Nächstältere Version		Version vom 16. Oktober 2019, 09:03 Uhr
Zeile 124:		Zeile 124:
	==Radix-2-Algorithmus nach Cooley und Tukey==		==Radix-2-Algorithmus nach Cooley und Tukey==
	<br>		<br>
	Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.: ''An Algorithm for the Machine Calculation of Complex Fourier Series''. In: Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref> von [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley] und [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey] auf dem Überlagerungssatz der DFT auf. Es funktioniert nur dann, wenn die Stützstellenzahl $N$ eine Zweierpotenz ist.		Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren  [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.: ''An Algorithm for the Machine Calculation of Complex Fourier Series''. In: Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>  von  [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]  und  [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]  auf dem Überlagerungssatz der DFT auf. Es funktioniert nur dann, wenn die Stützstellenzahl  $N$  eine Zweierpotenz ist.

	[[Datei:P_ID1173__Sig_T_5_5_S3a_neu.png\|~~center~~\|frame\|frame\|Radix-2-Algorithmus (Flussdiagramm)]]		Die Grafik verdeutlicht den Algorithmus für  $N = 8$, wobei wieder die Transformation vom Zeit– in den Frequenzbereich dargestellt ist.
			[[Datei:P_ID1173__Sig_T_5_5_S3a_neu.png\|right\|frame\|frame\|Radix-2-Algorithmus (Flussdiagramm)]]

	Die ~~Grafik verdeutlicht den Algorithmus für~~ $N = 8$, wobei ~~wieder~~ die ~~Transformation vom Zeit– in den Frequenzbereich dargestellt ist~~.		*Vor dem eigentlichen FFT-Algorithmus müssen zunächst die Eingangswerte  $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$  im grauen Block &bdquo;Bitumkehroperation” umsortiert werden.
			*Die Berechnung erfolgt in  $\text{log}_2 N = 3$  Stufen, wobei in jeder Stufe  $N/2 = 4$  gleiche Berechnungen mit verschiedenen  $\mu$–Werten <br>(= Exponent des komplexen Drehfaktors) ausgeführt werden. Eine solche Basisoperation bezeichnet man auch als  '''Butterfly'''.
			*Jeder Butterfly berechnet aus zwei (im Allgemeinen komplexen) Eingangsgrößen  $A$  und  $B$  die beiden Ausgangsgrößen  $A + B \cdot w^{\mu}$  sowie  $A – B \cdot w^{\mu}$  entsprechend der folgenden Skizze.

	*Vor dem eigentlichen FFT-Algorithmus müssen zunächst die Eingangswerte $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$ im grauen Block &bdquo;Bitumkehroperation” umsortiert werden.
	*Die Berechnung erfolgt in $\text{log}_2 N = 3$ Stufen, wobei in jeder Stufe genau $N/2 = 4$ prinzipiell gleiche Berechnungen mit verschiedenen $\mu$–Werten (= Exponent des komplexen Drehfaktors) ausgeführt werden. Eine solche Basisoperation bezeichnet man auch als '''Butterfly'''.
	*Jeder Butterfly berechnet aus zwei (im Allgemeinen komplexen) Eingangsgrößen $A$ und $B$ die beiden Ausgangsgrößen $A + B \cdot w^{\mu}$ sowie $A – B \cdot w^{\mu}$ entsprechend der folgenden Skizze.

	[[Datei:P_ID1174__Sig_T_5_5_S3b_neu.png\|center\|frame\|Butterfly des DFT-Algorithmus]]		[[Datei:P_ID1174__Sig_T_5_5_S3b_neu.png\|center\|frame\|Butterfly des DFT-Algorithmus]]
Zeile 138:		Zeile 138:
	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
	$\text{Fazit:}$		$\text{Fazit:}$
	Die komplexen Spektralkoeffizienten $D(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, D( N - 1)$ erhält man am Ausgang der letzten Stufe nach Division durch $N$.		Die komplexen Spektralkoeffizienten  $D(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, D( N - 1)$  erhält man am Ausgang der letzten Stufe nach Division durch  $N$.
	*Wie in der [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT\|Aufgabe 5.5Z]] gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für $N = 1024$ um mehr als den Faktor $150$.		*Wie in der  [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT\|Aufgabe 5.5Z]]  gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für  $N = 1024$  um mehr als den Faktor  $150$.

	*Die inverse DFT zur Berechnung der ~~Zeitkoeffizienten~~ aus den Spektralkoeffizienten ~~lässt sich~~ mit dem gleichen Algorithmus und nur geringfügigen Modifizierungen ~~bewerkstelligen~~.}}		*Die inverse DFT zur Berechnung der Zeit– aus den Spektralkoeffizienten geschieht mit dem gleichen Algorithmus und nur geringfügigen Modifizierungen.}}


Zeile 148:		Zeile 148:
	$\text{Beispiel 3:}$		$\text{Beispiel 3:}$
	Abschließend wird ein C–Programm <br>		Abschließend wird ein C–Programm <br>
	:~~:::'''~~fft(N, Re, Im)~~''' <br>~~		:$$\text{fft(N, Re, Im)}$$
	gemäß dem oben beschriebenen Radix–2–Algorithmus angegeben:		gemäß dem oben beschriebenen Radix–2–Algorithmus angegeben:

	*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die $N$ Real– und Imaginärteile der komplexen Zeitkoeffizienten $d(0)$, ... , $d( N - 1)$.		*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die  $N$  Real– und Imaginärteile der komplexen Zeitkoeffizienten  $d(0)$, ... , $d( N - 1)$.
	*In den gleichen Feldern „Re” und „Im” werden die ~~$N$~~ komplexen ~~Spektralkoeffizienten~~ $D(0)$, ... , $D( N - 1)$ ~~am Programmende~~ an das aufrufende Programm zurückgegeben.		*In den gleichen Feldern „Re” und „Im” werden am Programmende die komplexen Koeffizienten  $D(0)$, ... , $D( N - 1)$  an das aufrufende Programm zurückgegeben.
	*Aufgrund der „In–Place”–Programmierung reichen für diesen Algorithmus $N$ komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.		*Aufgrund der „In–Place”–Programmierung reichen somit für diesen Algorithmus  $N$  komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.
	*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von ${\rm Re}( \nu)$ und ${\rm Im}( \nu)$ in die Elemente ${\rm Re}( \kappa)$ und ${\rm Im}( \kappa)$ eingetragen werden. $\text{Beispiel 4}$ verdeutlicht die Vorgehensweise.}}		*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von  ${\rm Re}( \nu)$  und  ${\rm Im}( \nu)$  in die Elemente  ${\rm Re}( \kappa)$  und  ${\rm Im}( \kappa)$  eingetragen werden. $\text{Beispiel 4}$  verdeutlicht die Vorgehensweise.}}


	[[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png\|right\|frame\|Radix-2-Algorithmus (Bitumkehroperation für $N = 8$)]]		[[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png\|right\|frame\|Radix-2-Algorithmus $($Bitumkehroperation für  $N = 8)$]]
	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Beispiel 4: Bitumkehroperation}$		$\text{Beispiel 4: Bitumkehroperation}$

	*Der neue Index $\kappa$ ergibt sich, wenn man den Index $\nu$ als Dualzahl schreibt und anschließend die $\text{log}_2 \hspace{0.05cm} N$ ~~Bits~~ in umgekehrter Reihenfolge darstellt.		*Der neue Index  $\kappa$  ergibt sich, wenn man den Index  $\nu$  als Dualzahl schreibt und anschließend die  $\text{log}_2 \hspace{0.05cm} N$  Bit in umgekehrter Reihenfolge darstellt.
	*Zum Beispiel wird aus $\nu = 3$ der neue Index $\kappa = 6$.}}		*Zum Beispiel wird aus  $\nu = 3$  der neue Index  $\kappa = 6$.}}

Guenter am 16. Oktober 2019 um 06:38 Uhr

2019-10-16T06:38:40Z

Änderungen zeigen

← Nächstältere Version		Version vom 20. Mai 2021, 16:53 Uhr
Zeile 128:		Zeile 128:
	==Radix-2-Algorithmus nach Cooley und Tukey==		==Radix-2-Algorithmus nach Cooley und Tukey==
	<br>		<br>
	Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren  [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.: ''An Algorithm for the Machine Calculation of Complex Fourier Series''. In: Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>  von  [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]  und  [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]  auf dem Überlagerungssatz der DFT auf. Es funktioniert nur dann, wenn die Stützstellenzahl  $N$  eine Zweierpotenz ist.		Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren  [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.:  An Algorithm for the Machine Calculation of Complex Fourier Series.  In:  Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>  von  [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]  und  [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]  auf dem Überlagerungssatz der DFT auf.  Es funktioniert nur dann, wenn die Stützstellenzahl  $N$  eine Zweierpotenz ist.

	Die Grafik verdeutlicht den Algorithmus für  $N = 8$, wobei wieder die Transformation vom Zeit– in den Frequenzbereich dargestellt ist.		Die Grafik verdeutlicht den Algorithmus für  $N = 8$, wobei wieder die Transformation vom Zeit– in den Frequenzbereich dargestellt ist.
Zeile 134:		Zeile 134:

	*Vor dem eigentlichen FFT-Algorithmus müssen zunächst die Eingangswerte  $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$  im grauen Block &bdquo;Bitumkehroperation” umsortiert werden.		*Vor dem eigentlichen FFT-Algorithmus müssen zunächst die Eingangswerte  $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$  im grauen Block &bdquo;Bitumkehroperation” umsortiert werden.
	*Die Berechnung erfolgt in  $\text{log}_2 N = 3$  Stufen, wobei in jeder Stufe  $N/2 = 4$  gleiche Berechnungen mit verschiedenen  $\mu$–Werten ~~<br>~~(= Exponent des komplexen Drehfaktors) ausgeführt werden. Eine solche Basisoperation bezeichnet man auch als  ~~'''~~Butterfly~~'''~~.		*Die Berechnung erfolgt in  $\text{log}_2 N = 3$  Stufen, wobei in jeder Stufe  $N/2 = 4$  gleiche Berechnungen mit verschiedenen  $\mu$–Werten  (als Exponent des komplexen Drehfaktors)  ausgeführt werden.  Eine solche Basisoperation bezeichnet man auch als  $\text{Butterfly}$.
	*Jeder Butterfly berechnet aus zwei (im Allgemeinen komplexen) Eingangsgrößen  $A$  und  $B$  die beiden Ausgangsgrößen  $A + B \cdot w^{\mu}$  sowie  $A – B \cdot w^{\mu}$  entsprechend der folgenden Skizze.		*Jeder Butterfly berechnet aus zwei  (im Allgemeinen komplexen)  Eingangsgrößen  $A$  und  $B$  die beiden Ausgangsgrößen  $A + B \cdot w^{\mu}$  sowie  $A – B \cdot w^{\mu}$  entsprechend der folgenden Skizze.


Zeile 145:		Zeile 145:
	*Wie in der  [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT\|Aufgabe 5.5Z]]  gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für  $N = 1024$  um mehr als den Faktor  $150$.		*Wie in der  [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT\|Aufgabe 5.5Z]]  gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für  $N = 1024$  um mehr als den Faktor  $150$.

	*Die inverse DFT zur Berechnung der Zeit– aus den Spektralkoeffizienten geschieht mit dem gleichen Algorithmus und nur geringfügigen ~~Modifizierungen~~.}}		*Die inverse DFT zur Berechnung der Zeit– aus den Spektralkoeffizienten geschieht mit dem gleichen Algorithmus und nur geringfügigen Modifikationen.}}


Zeile 155:		Zeile 155:
	gemäß dem oben beschriebenen Radix–2–Algorithmus angegeben:		gemäß dem oben beschriebenen Radix–2–Algorithmus angegeben:

	*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die  $N$  Real– und Imaginärteile der komplexen Zeitkoeffizienten  $d(0)$, ... , $d( N - 1)$.		*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die jeweils  $N$  Real– und Imaginärteile der komplexen Zeitkoeffizienten  $d(0)$, ... , $d( N - 1)$.
	*In den gleichen Feldern „Re” und „Im” werden am Programmende die komplexen Koeffizienten  $D(0)$, ... , $D( N - 1)$  an das aufrufende Programm zurückgegeben.		*In den gleichen Feldern „Re” und „Im” werden am Programmende die komplexen Koeffizienten  $D(0)$, ... , $D( N - 1)$  an das aufrufende Programm zurückgegeben.
	*Aufgrund der „In–Place”–Programmierung reichen ~~somit~~ für diesen Algorithmus  $N$  komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.		*Aufgrund der „In–Place”–Programmierung reichen für diesen Algorithmus  $N$  komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.
	*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von  ${\rm Re}( \nu)$  und  ${\rm Im}( \nu)$  in die Elemente  ${\rm Re}( \kappa)$  und  ${\rm Im}( \kappa)$  eingetragen werden. $\text{Beispiel 4}$  verdeutlicht die Vorgehensweise.}}		*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von  ${\rm Re}( \nu)$  und  ${\rm Im}( \nu)$  in die Elemente  ${\rm Re}( \kappa)$  und  ${\rm Im}( \kappa)$  eingetragen werden.  Das  $\text{Beispiel 4}$  verdeutlicht die Vorgehensweise.}}