Signaldarstellung/Fast-Fouriertransformation (FFT) - Versionsgeschichte

Guenter am 21. Mai 2021 um 15:12 Uhr

2021-05-21T15:12:35Z

Guenter am 21. Mai 2021 um 14:50 Uhr

2021-05-21T14:50:58Z

Guenter am 20. Mai 2021 um 15:09 Uhr

2021-05-20T15:09:02Z

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

Guenter am 16. Oktober 2019 um 06:38 Uhr

2019-10-16T06:38:40Z

Änderungen zeigen

Guenter am 29. Juli 2018 um 16:02 Uhr

2018-07-29T16:02:47Z

Guenter am 29. Juli 2018 um 15:50 Uhr

2018-07-29T15:50:00Z

Änderungen zeigen

Guenter am 2. Februar 2018 um 17:37 Uhr

2018-02-02T17:37:51Z

@@ Zeile 158: / Zeile 158: @@
 *Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von&nbsp; ${\rm Re}( \nu)$&nbsp; und&nbsp; ${\rm Im}( \nu)$&nbsp; in die Elemente&nbsp; ${\rm Re}( \kappa)$&nbsp; und&nbsp; ${\rm Im}( \kappa)$&nbsp; eingetragen werden.&nbsp; Das&nbsp; $\text{Beispiel 4}$&nbsp; verdeutlicht die Vorgehensweise.
-<br>
 $\text{Beispiel 4:  Bitumkehroperation}$&nbsp;
 [[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png|center|frame|Radix-2-Algorithmus $($Bitumkehroperation für&nbsp; $N = 8)$]]

@@ Zeile 17: / Zeile 17: @@
   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&nbsp; $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N}$&nbsp; bereits in Real– und Imaginärteilform in einer Lookup–Tabelle vorliegen.&nbsp;
@@ 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}.$$
-Durch&nbsp; '''diese erste Anwendung des Überlagerungssatzes halbiert sich somit in etwa der Rechenaufwand'''.
+'''Durch&nbsp; diese erste Anwendung des Überlagerungssatzes halbiert sich somit in etwa der Rechenaufwand'''.
 {{GraueBox|TEXT=
@@ Zeile 145: / Zeile 145: @@
 *Wie in der&nbsp; [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT|Aufgabe 5.5Z]]&nbsp; gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für&nbsp; $N = 1024$&nbsp; um mehr als den Faktor&nbsp; $150$.
-*Die inverse DFT zur Berechnung der Zeit&ndash; 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=
 $\text{Beispiel 3:}$&nbsp;
-Abschließend wird ein C–Programm <br>
+Abschließend wird das C–Programm&nbsp; $\text{fft(N, Re, Im)}$&nbsp; gemäß dem oben beschriebenen Radix–2–Algorithmus angegeben:
 *Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die jeweils&nbsp; $N$&nbsp; Real– und Imaginärteile der komplexen Zeitkoeffizienten&nbsp; $d(0)$, ... , $d( N - 1)$.
 *In den gleichen Feldern „Re” und „Im” werden am Programmende die komplexen Koeffizienten&nbsp; $D(0)$, ... , $D( N - 1)$&nbsp; an das aufrufende Programm zurückgegeben.
 *Aufgrund der „In–Place”–Programmierung reichen für diesen Algorithmus&nbsp; $N$&nbsp; komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.
-*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von&nbsp; ${\rm Re}( \nu)$&nbsp; und&nbsp; ${\rm Im}( \nu)$&nbsp; in die Elemente&nbsp; ${\rm Re}( \kappa)$&nbsp; und&nbsp; ${\rm Im}( \kappa)$&nbsp; eingetragen werden.&nbsp; Das&nbsp; $\text{Beispiel 4}$&nbsp; verdeutlicht die Vorgehensweise.}}
+*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von&nbsp; ${\rm Re}( \nu)$&nbsp; und&nbsp; ${\rm Im}( \nu)$&nbsp; in die Elemente&nbsp; ${\rm Re}( \kappa)$&nbsp; und&nbsp; ${\rm Im}( \kappa)$&nbsp; eingetragen werden.&nbsp; Das&nbsp; $\text{Beispiel 4}$&nbsp; verdeutlicht die Vorgehensweise.
+<br>
 $\text{Beispiel 4:  Bitumkehroperation}$&nbsp;
 *Der neue Index&nbsp; $\kappa$&nbsp; ergibt sich, wenn man den Index&nbsp; $\nu$&nbsp; als Dualzahl schreibt und anschließend die&nbsp; $\text{log}_2 \hspace{0.05cm} N$&nbsp; Bit in umgekehrter Reihenfolge darstellt.

@@ Zeile 128: / Zeile 128: @@
 ==Radix-2-Algorithmus nach Cooley und Tukey==
 <br>
-Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren&nbsp; [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.:&nbsp; An Algorithm for the Machine Calculation of Complex Fourier Series.&nbsp; In:&nbsp; Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>&nbsp; von&nbsp; [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]&nbsp; und&nbsp; [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]&nbsp; auf dem Überlagerungssatz der DFT auf.&nbsp; Es funktioniert nur dann, wenn die Stützstellenzahl&nbsp; $N$&nbsp; eine Zweierpotenz ist.
+Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren&nbsp; [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.:&nbsp; An Algorithm for the Machine Calculation of Complex Fourier Series.&nbsp; <br>In:&nbsp; Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>&nbsp; von&nbsp; [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]&nbsp; und&nbsp; [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]&nbsp; auf dem Überlagerungssatz der DFT auf.&nbsp; Es funktioniert nur dann, wenn die Stützstellenzahl&nbsp; $N$&nbsp; eine Zweierpotenz ist.
 Die Grafik verdeutlicht den Algorithmus für&nbsp; $N = 8$, wobei wieder die Transformation vom Zeit– in den Frequenzbereich dargestellt ist.

@@ Zeile 128: / Zeile 128: @@
 ==Radix-2-Algorithmus nach Cooley und Tukey==
 <br>
-Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren&nbsp; [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>&nbsp; von&nbsp; [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]&nbsp; und&nbsp; [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]&nbsp; auf dem Überlagerungssatz der DFT auf. Es funktioniert nur dann, wenn die Stützstellenzahl&nbsp; $N$&nbsp; eine Zweierpotenz ist.
+Ebenso wie andere FFT–Algorithmen baut das hier vorgestellte Verfahren&nbsp; [CT65]<ref name ='CT65'>Cooley, J.W.; Tukey, J.W.:&nbsp; An Algorithm for the Machine Calculation of Complex Fourier Series.&nbsp; In:&nbsp; Mathematics of Computation, Vol. 19, No. 90. (Apr., 1965), pp. 297-301.</ref>&nbsp; von&nbsp; [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]&nbsp; und&nbsp; [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]&nbsp; auf dem Überlagerungssatz der DFT auf.&nbsp; Es funktioniert nur dann, wenn die Stützstellenzahl&nbsp; $N$&nbsp; eine Zweierpotenz ist.
 Die Grafik verdeutlicht den Algorithmus für&nbsp; $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&nbsp; $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$&nbsp; im grauen Block &bdquo;Bitumkehroperation&rdquo; umsortiert werden.
-*Die Berechnung erfolgt in&nbsp; $\text{log}_2 N = 3$&nbsp; Stufen, wobei in jeder Stufe&nbsp; $N/2 = 4$&nbsp;  gleiche Berechnungen mit verschiedenen&nbsp; $\mu$&ndash;Werten <br>(= Exponent des komplexen Drehfaktors) ausgeführt werden. Eine solche Basisoperation bezeichnet man auch als&nbsp; '''Butterfly'''.
+*Die Berechnung erfolgt in&nbsp; $\text{log}_2 N = 3$&nbsp; Stufen, wobei in jeder Stufe&nbsp; $N/2 = 4$&nbsp;  gleiche Berechnungen mit verschiedenen&nbsp; $\mu$&ndash;Werten&nbsp; (als Exponent des komplexen Drehfaktors)&nbsp; ausgeführt werden.&nbsp; Eine solche Basisoperation bezeichnet man auch als&nbsp; $\text{Butterfly}$.
-*Jeder Butterfly berechnet aus zwei (im Allgemeinen komplexen) Eingangsgrößen&nbsp; $A$&nbsp; und&nbsp; $B$&nbsp; die beiden Ausgangsgrößen&nbsp; $A + B \cdot w^{\mu}$&nbsp; sowie&nbsp; $A – B \cdot w^{\mu}$&nbsp; entsprechend der folgenden Skizze.
+*Jeder Butterfly berechnet aus zwei&nbsp;  (im Allgemeinen komplexen)&nbsp;  Eingangsgrößen&nbsp; $A$&nbsp; und&nbsp; $B$&nbsp; die beiden Ausgangsgrößen&nbsp; $A + B \cdot w^{\mu}$&nbsp; sowie&nbsp; $A – B \cdot w^{\mu}$&nbsp; entsprechend der folgenden Skizze.
@@ Zeile 145: / Zeile 145: @@
 *Wie in der&nbsp; [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT|Aufgabe 5.5Z]]&nbsp; gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für&nbsp; $N = 1024$&nbsp; um mehr als den Faktor&nbsp; $150$.
-*Die inverse DFT zur Berechnung der Zeit&ndash; aus den Spektralkoeffizienten geschieht mit dem gleichen Algorithmus und nur geringfügigen Modifizierungen.}}
+*Die inverse DFT zur Berechnung der Zeit&ndash; 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:
-*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die&nbsp; $N$&nbsp; Real– und Imaginärteile der komplexen Zeitkoeffizienten&nbsp; $d(0)$, ... , $d( N - 1)$.
+*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die jeweils&nbsp; $N$&nbsp; Real– und Imaginärteile der komplexen Zeitkoeffizienten&nbsp; $d(0)$, ... , $d( N - 1)$.
 *In den gleichen Feldern „Re” und „Im” werden am Programmende die komplexen Koeffizienten&nbsp; $D(0)$, ... , $D( N - 1)$&nbsp; an das aufrufende Programm zurückgegeben.
-*Aufgrund der „In–Place”–Programmierung reichen somit für diesen Algorithmus&nbsp; $N$&nbsp; komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.
+*Aufgrund der „In–Place”–Programmierung reichen für diesen Algorithmus&nbsp; $N$&nbsp; komplexe Speicherplätze aus, allerdings nur, wenn zu Beginn die Eingangswerte umsortiert werden.
-*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von&nbsp; ${\rm Re}( \nu)$&nbsp; und&nbsp; ${\rm Im}( \nu)$&nbsp; in die Elemente&nbsp; ${\rm Re}( \kappa)$&nbsp; und&nbsp; ${\rm Im}( \kappa)$&nbsp; eingetragen werden. $\text{Beispiel 4}$&nbsp; verdeutlicht die Vorgehensweise.}}
+*Dies geschieht durch das Programm „bitumkehr”, wobei die Inhalte von&nbsp; ${\rm Re}( \nu)$&nbsp; und&nbsp; ${\rm Im}( \nu)$&nbsp; in die Elemente&nbsp; ${\rm Re}( \kappa)$&nbsp; und&nbsp; ${\rm Im}( \kappa)$&nbsp; eingetragen werden.&nbsp; Das&nbsp; $\text{Beispiel 4}$&nbsp; verdeutlicht die Vorgehensweise.}}

@@ Zeile 124: / Zeile 124: @@
 ==Radix-2-Algorithmus nach Cooley und Tukey==
 <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&nbsp; [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>&nbsp; von&nbsp; [https://de.wikipedia.org/wiki/James_Cooley James W. Cooley]&nbsp; und&nbsp; [https://en.wikipedia.org/wiki/John_Tukey John W. Tukey]&nbsp; auf dem Überlagerungssatz der DFT auf. Es funktioniert nur dann, wenn die Stützstellenzahl&nbsp; $N$&nbsp; 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&nbsp; $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.
+*Vor dem eigentlichen FFT-Algorithmus müssen zunächst die Eingangswerte&nbsp; $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$&nbsp; im grauen Block &bdquo;Bitumkehroperation&rdquo; umsortiert werden.
 [[Datei:P_ID1174__Sig_T_5_5_S3b_neu.png|center|frame|Butterfly des DFT-Algorithmus]]
@@ Zeile 138: / Zeile 138: @@
 {{BlaueBox|TEXT=
 $\text{Fazit:}$&nbsp;
-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&nbsp; $D(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, D( N - 1)$&nbsp; erhält man am Ausgang der letzten Stufe nach Division durch&nbsp; $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&nbsp; [[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT|Aufgabe 5.5Z]]&nbsp; gezeigt wird, ergibt sich gegenüber der DFT eine deutlich kürzere Rechenzeit, zum Beispiel für&nbsp; $N = 1024$&nbsp; um mehr als den Faktor&nbsp; $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&ndash; aus den Spektralkoeffizienten geschieht mit dem gleichen Algorithmus und nur geringfügigen Modifizierungen.}}
@@ Zeile 148: / Zeile 148: @@
 $\text{Beispiel 3:}$&nbsp;
 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:
-*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&nbsp; $N$&nbsp; Real– und Imaginärteile der komplexen Zeitkoeffizienten&nbsp; $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&nbsp; $D(0)$, ... , $D( N - 1)$&nbsp; 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&nbsp; $N$&nbsp; 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&nbsp; ${\rm Re}( \nu)$&nbsp; und&nbsp; ${\rm Im}( \nu)$&nbsp; in die Elemente&nbsp; ${\rm Re}( \kappa)$&nbsp; und&nbsp; ${\rm Im}( \kappa)$&nbsp; eingetragen werden. $\text{Beispiel 4}$&nbsp; 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&nbsp; $N = 8)$]]
 {{GraueBox|TEXT=
-$\text{Beispiel 4: Bitumkehroperation}$&nbsp;
+$\text{Beispiel 4:  Bitumkehroperation}$&nbsp;
-*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&nbsp; $\kappa$&nbsp; ergibt sich, wenn man den Index&nbsp; $\nu$&nbsp; als Dualzahl schreibt und anschließend die&nbsp; $\text{log}_2 \hspace{0.05cm} N$&nbsp; Bit in umgekehrter Reihenfolge darstellt.
-*Zum Beispiel wird aus $\nu = 3$ der neue Index $\kappa = 6$.}}
+*Zum Beispiel wird aus&nbsp; $\nu = 3$&nbsp; der neue Index&nbsp; $\kappa = 6$.}}

@@ Zeile 135: / Zeile 135: @@
 *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&rdquo; 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$&ndash;Werten (= Exponent des komplexen Drehfaktors) ausgeführt werden. Eine solche Basisoperation bezeichnet man auch als '''Butterfly'''.
-[[Datei:P_ID1174__Sig_T_5_5_S3b_neu.png|right|frame|Butterfly des DFT-Algorithmus]]
+*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 nebenstehenden Skizze.
-<br clear=all>
+[[Datei:P_ID1174__Sig_T_5_5_S3b_neu.png|center|frame|Butterfly des DFT-Algorithmus]]
 {{BlaueBox|TEXT=
 $\text{Fazit:}$&nbsp;
-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 [[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 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 inverse DFT zur Berechnung der Zeitkoeffizienten aus den Spektralkoeffizienten lässt sich mit dem gleichen Algorithmus und nur geringfügigen Modifizierungen bewerkstelligen.}}

@@ Zeile 129: / Zeile 129: @@
 *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&rdquo; 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$&ndash;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|right|frame|Butterfly des DFT-Algorithmus]]
-:[[Datei:P_ID1174__Sig_T_5_5_S3b_neu.png|right|frame|Butterfly des DFT-Algorithmus]]
+*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 nebenstehenden Skizze.
-*Die komplexen Spektralkoeffizienten $D(0), \hspace{0.1cm}... \hspace{0.1cm}, D( N - 1)$ erhält man am Ausgang der letzten Stufe nach Division durch $N$. Wie in [[Aufgabe Z5.5]] 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.
+[[Datei:P_ID1175__Sig_T_5_5_S3c_neu.png|right|frame|Radix-2-Algorithmus (C-Programm)]]
-*Die inverse DFT zur Berechnung der Zeitkoeffizienten aus den Spektralkoeffizienten lässt sich mit dem gleichen Algorithmus und nur geringfügigen Modifizierungen bewerkstelligen.
+{{GraueBox|TEXT=
-[[Datei:P_ID1175__Sig_T_5_5_S3c_neu.png|center|frame|Radix-2-Algorithmus (C-Programm)]]
+[[Datei:P_ID1176__Sig_T_5_5_S3d_neu.png|right|frame|Radix-2-Algorithmus (Bitumkehroperation für $N = 8$)]]
-*Beim Aufruf beinhalten die beiden Float–Arrays „Re” und „Im” die jeweils $N$ Real– und Imaginärteile der komplexen Zeitkoeffizienten $d(0), \hspace{0.1cm}... \hspace{0.1cm}, d( N - 1)$.
+*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.
-*In den gleichen Feldern „Re” und „Im” werden die $N$ komplexen Spektralkoeffizienten $D(0), \hspace{0.1cm}... \hspace{0.1cm}, D( N - 1)$ am Programmende an das aufrufende Programm zurückgegeben.
+*Zum Beispiel wird aus $\nu = 3$ der neue Index $\kappa = 6$.}}
 ==Aufgaben zum Kapitel==
-[[Aufgaben:5.5 Fast-Fouriertransformation|Aufgabe 5.5: &nbsp; Fast-Fouriertransformation]]
+[[Aufgaben:Aufgabe_5.5:_Fast-Fouriertransformation|Aufgabe 5.5: Fast-Fouriertransformation]]
-[[Aufgaben:5.5Z_Rechenaufwand_für_die_FFT|Zusatzaufgabe 5.5Z:&nbsp; 5.5Z Rechenaufwand für die FFT]]
+[[Aufgaben:Aufgabe_5.5Z:_Rechenaufwand_für_die_FFT|Aufgabe 5.5Z: Rechenaufwand für die FFT]]
 ==Quellenverzeichnis==