Signal Representation/Fast Fourier Transform (FFT) - Revision history

Guenter at 14:38, 28 June 2023

2023-06-28T14:38:23Z

Guenter at 14:24, 28 June 2023

2023-06-28T14:24:39Z

Guenter at 14:22, 28 June 2023

2023-06-28T14:22:32Z

Guenter at 13:48, 28 June 2023

2023-06-28T13:48:45Z

Guenter at 13:10, 28 June 2023

2023-06-28T13:10:05Z

Show changes

Guenter at 10:52, 28 June 2023

2023-06-28T10:52:26Z

Guenter at 14:07, 13 December 2022

2022-12-13T14:07:16Z

Guenter at 16:39, 12 December 2022

2022-12-12T16:39:07Z

Guenter at 16:38, 12 December 2022

2022-12-12T16:38:31Z

Hwang at 18:28, 8 December 2022

2022-12-08T18:28:44Z

@@ Line 150: / Line 150: @@
 $\text{Conclusion:}$&nbsp;
 The complex spectral coefficients&nbsp; $D(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, D( N - 1)$&nbsp; are obtained at the output of the last stage after division by&nbsp; $N$.
-*As shown in&nbsp; [[Aufgaben:Exercise_5.5Z:_Complexity_of_the_FFT|$\text{Exercise 5.5Z}$]]&nbsp; , this results in a much shorter computation time compared to the DFT,&nbsp; for example for&nbsp; $N = 1024$&nbsp; by more than a factor $150$.
+*As shown in&nbsp; [[Aufgaben:Exercise_5.5Z:_Complexity_of_the_FFT|$\text{Exercise 5.5Z}$]],&nbsp;  this results in a much shorter computation time compared to the DFT,&nbsp; for example for&nbsp; $N = 1024$&nbsp; by more than a factor $150$.
 *The inverse DFT for calculating the time coefficients from the spectral coefficients is done with the same algorithm and only slight modifications.}}

@@ Line 133: / Line 133: @@
 ==Radix-2 algorithm according to Cooley and Tukey==
 <br>
-Like other FFT algorithms,&nbsp; the method &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;   from &nbsp; [https://en.wikipedia.org/wiki/James_Cooley $\text{James W. Cooley}$]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/John_Tukey $\text{John W. Tukey}$]&nbsp; is based on the superposition theorem of the DFT.&nbsp; It only works if the number of interpolation points is a power of two.
+Like other FFT algorithms,&nbsp; the method &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;   from &nbsp; [https://en.wikipedia.org/wiki/James_Cooley &raquo;$\text{James W. Cooley}$&laquo;]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/John_Tukey &raquo;$\text{John W. Tukey}$&laquo;]&nbsp; is based on the superposition theorem of the DFT.&nbsp; It only works if the number of interpolation points is a power of two.
 The diagram illustrates the algorithm for&nbsp; $N = 8$,&nbsp; again showing the transformation from the time to the frequency domain.

@@ Line 161: / Line 161: @@
 *The two float arrays&nbsp; &raquo;Re&laquo;&nbsp; and&nbsp; &raquo;Im&raquo;&nbsp; contain the&nbsp; $N$&nbsp; real and imaginary parts of the complex time coefficients&nbsp; $d(0)$, ... , $d( N - 1)$.
 *In the same fields&nbsp; &raquo;Re&laquo;&nbsp; and&nbsp; &raquo;Im&raquo;&nbsp; the complex coefficients&nbsp; $D(0)$, ... , $D( N - 1)$&nbsp; are returned to the main program.
-*Due to the&nbsp; "in-place"&nbsp; programming, &nbsp; $N$&nbsp; complex memory space is thus sufficient for this algorithm but only if the input values are reordered at the beginning.
+*This is done by the program&nbsp; &raquo;bit-reversal&laquo;,&nbsp; where the contents of&nbsp; ${\rm Re}( \nu)$&nbsp; and&nbsp; ${\rm Im}( \nu)$&nbsp; are entered into the elements&nbsp; ${\rm Re}( \kappa)$&nbsp; and&nbsp; ${\rm Im}( \kappa)$.&nbsp; $\text{Example 4}$&nbsp; illustrates this procedure.}}
-*This is done by the program&nbsp; "bit-reversal", where the contents of&nbsp; ${\rm Re}( \nu)$&nbsp; and&nbsp; ${\rm Im}( \nu)$&nbsp; are entered into the elements&nbsp; ${\rm Re}( \kappa)$&nbsp; and&nbsp; ${\rm Im}( \kappa)$.&nbsp; The&nbsp; $\text{Example 4}$&nbsp; illustrates this procedure.
+<br clear=all>
-*The new index&nbsp; $\kappa$&nbsp; is obtained by writing the index&nbsp; $\nu$&nbsp; as a dual number and then representing the&nbsp; $\text{log}_2 \hspace{0.05cm} N$&nbsp; bits in reverse order.
+#The new index&nbsp; $\kappa$&nbsp; is obtained by writing the index&nbsp; $\nu$&nbsp; as a dual number and then representing the&nbsp; $\text{log}_2 \hspace{0.05cm} N$&nbsp; bits in reverse order.<br><br>
-*For example,&nbsp; $\nu = 3$&nbsp; becomes the new index&nbsp; $\kappa = 6$.}}
+#For example,&nbsp; $\nu = 3$&nbsp; becomes the new index&nbsp; $\kappa = 6$.}}

@@ Line 133: / Line 133: @@
 ==Radix-2 algorithm according to Cooley and Tukey==
 <br>
-Like other FFT algorithms, the method presented here&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; from &nbsp; [https://en.wikipedia.org/wiki/James_Cooley $\text{James W. Cooley}$]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/John_Tukey $\text{John W. Tukey}$]&nbsp; on the superposition theorem of the DFT.&nbsp; It only works if the number of interpolation points is a power of two.
+Like other FFT algorithms,&nbsp; the method &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;   from &nbsp; [https://en.wikipedia.org/wiki/James_Cooley $\text{James W. Cooley}$]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/John_Tukey $\text{John W. Tukey}$]&nbsp; is based on the superposition theorem of the DFT.&nbsp; It only works if the number of interpolation points is a power of two.
-The diagram illustrates the algorithm for&nbsp; $N = 8$, again showing the transformation from the time to the frequency domain.
+The diagram illustrates the algorithm for&nbsp; $N = 8$,&nbsp; again showing the transformation from the time to the frequency domain.
 [[File:EN_Sig_T_5_5_S3a.png|right|frame|Radix-2 algorithm&nbsp; $($flow diagram$)$;&nbsp; note:&nbsp; "level"&nbsp; and&nbsp; stage" are synonymous terms]]
-*Before the FFT algorithm, the input values&nbsp; $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$&nbsp; have to be reordered in the grey block&nbsp; "Bit Reversal Operation".
+*Before the FFT algorithm,&nbsp; the input values&nbsp; $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$&nbsp; have to be reordered in the grey block&nbsp; &raquo;Bit Reversal Operation&laquo;.
-*The computation is done in&nbsp; $\text{log}_2 N = 3$&nbsp; stages, where in each stage&nbsp; $N/2 = 4$&nbsp; equal computations are performed with different&nbsp; $\mu$&ndash;values as exponent of the complex rotation factor.&nbsp; Such a basic operation is called&nbsp; $\text{butterfly}$.
-*Each butterfly calculates from two&nbsp; (generally complex)&nbsp; input variables&nbsp; $A$&nbsp; and&nbsp; $B$&nbsp; the two output variables&nbsp; $A + B \cdot w^{\mu}$&nbsp; and&nbsp; $A - B \cdot w^{\mu}$&nbsp; according to the following sketch.
+*The computation is done in&nbsp; $\text{log}_2 N = 3$&nbsp; stages,&nbsp; where in each stage&nbsp; $N/2 = 4$&nbsp; equal computations are performed with different&nbsp; $\mu$&ndash;values as exponent of the complex rotation factor.&nbsp; Such a basic operation is called&nbsp; &raquo;'''butterfly'''&laquo;.
@@ Line 148: / Line 150: @@
 $\text{Conclusion:}$&nbsp;
 The complex spectral coefficients&nbsp; $D(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, D( N - 1)$&nbsp; are obtained at the output of the last stage after division by&nbsp; $N$.
-*As shown in&nbsp; [[Aufgaben:Exercise_5.5Z:_Complexity_of_the_FFT|"Exercise 5.5Z"]]&nbsp; compared to the DFT, this results in a much shorter computation time, for example for&nbsp; $N = 1024$&nbsp; by more than a factor&nbsp; $150$.
+*As shown in&nbsp; [[Aufgaben:Exercise_5.5Z:_Complexity_of_the_FFT|$\text{Exercise 5.5Z}$]]&nbsp; , this results in a much shorter computation time compared to the DFT,&nbsp; for example for&nbsp; $N = 1024$&nbsp; by more than a factor $150$.
 *The inverse DFT for calculating the time coefficients from the spectral coefficients is done with the same algorithm and only slight modifications.}}
 {{GraueBox|TEXT=
 $\text{Example 3:}$&nbsp;
-Finally, the C program&nbsp; $\text{fft(N, Re, Im)}$&nbsp; according to the Radix-2 algorithm described above is given:
+Finally,&nbsp; the C program&nbsp; $\text{fft(N, Re, Im)}$&nbsp; according to the Radix-2 algorithm described above is given:
 *Due to the&nbsp; "in-place"&nbsp; programming, &nbsp; $N$&nbsp; complex memory space is thus sufficient for this algorithm but only if the input values are reordered at the beginning.
 *This is done by the program&nbsp; "bit-reversal", where the contents of&nbsp; ${\rm Re}( \nu)$&nbsp; and&nbsp; ${\rm Im}( \nu)$&nbsp; are entered into the elements&nbsp; ${\rm Re}( \kappa)$&nbsp; and&nbsp; ${\rm Im}( \kappa)$.&nbsp; The&nbsp; $\text{Example 4}$&nbsp; illustrates this procedure.
@@ Line 166: / Line 172: @@
 $\text{Example 4: "Bit-reversal" operation}$&nbsp;
-[[File:EN_Sig_T_5_5_S3d_v2.png|100px|left|frame|Radix-2-Algorithm $($"Bit-reversal"&nbsp; operation for&nbsp; $N = 8)$]]
+[[File:EN_Sig_T_5_5_S3d_v2.png|100px|right|frame|Radix-2-Algorithm $($"Bit-reversal"&nbsp; operation for&nbsp; $N = 8)$]]

@@ Line 8: / Line 8: @@
 ==Complexity of DFT and IDFT==
 <br>
-A disadvantage of the direct calculation of the&nbsp; (generally complex) DFT sequences
+A disadvantage of the direct calculation of the&nbsp; $($generally complex$)$&nbsp; DFT sequences
-:$$\langle \hspace{0.1cm}D(\mu)\hspace{0.1cm}\rangle  \hspace{0.2cm}\bullet\!\!-\!\!\!-(N)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm}d(\nu)\hspace{0.1cm} \rangle$$
+:$$\langle \hspace{0.03cm}D(\mu)\hspace{0.03cm}\rangle  \hspace{0.2cm}\bullet\!\!-\!\!\!-(N)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.03cm}d(\nu)\hspace{0.03cm} \rangle$$
-according to the equations given in chapter&nbsp; [[Signal_Representation/Discrete_Fourier_Transform_(DFT)|"Discrete Fourier Transform"]]&nbsp;  $\rm (DFT)$&nbsp; is the large computational cost.
+according to the equations given in chapter&nbsp; [[Signal_Representation/Discrete_Fourier_Transform_(DFT)|&raquo;Discrete Fourier Transform&raquo;]]&nbsp;  $\rm (DFT)$&nbsp; is the large computational cost.
-We consider as an example the DFT, i.e. the calculation of the&nbsp; $D(\mu)$&nbsp; coefficients from the&nbsp; $d(\nu)$&nbsp; coefficients:
+We consider as an example the DFT,&nbsp; i.e. the calculation of the&nbsp; $D(\mu)$&nbsp; coefficients from the&nbsp; $d(\nu)$&nbsp; coefficients:
 :$$N \cdot D(\mu)  =   \sum_{\nu = 0 }^{N-1}
@@ Line 21: / Line 21: @@
    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}.$$
-The computational effort required for this is to be estimated, assuming that the powers of the complex rotation factor&nbsp; $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N}$&nbsp; already exist in real and imaginary part form in a lookup table.&nbsp; To calculate a single coefficient, one then needs&nbsp; $N-1$&nbsp; complex multiplications and as many complex additions, observing:
+The computational effort required for this is to be estimated,&nbsp; assuming that the powers of the complex rotation factor&nbsp; $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm}2 \pi/N}$&nbsp; already exist in real and imaginary part form in a lookup table.&nbsp; To calculate a single coefficient,&nbsp; one then needs&nbsp; $N-1$&nbsp; complex multiplications and as many complex additions,&nbsp; observing:
 *Each complex addition requires two real additions:
 :$$(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}.$$
-*Each complex multiplication requires four real multiplications and two real additions&nbsp; (a subtraction is treated as an addition):
+*Each complex multiplication requires four real multiplications and two real additions&nbsp; $($a subtraction is treated as an addition$)$:
 :$$(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}.$$
-*Thus, the following number of real multiplications and the number of real additions are required to calculate all $N$ coefficients in total:
+*Thus,&nbsp; the following number of real multiplications and the number of real additions are required to calculate all&nbsp; $N$&nbsp; coefficients in total:
 :$$M = 4 \cdot N \cdot (N-1),$$
 :$$A = 2 \cdot N \cdot
 (N-1)+2 \cdot N \cdot (N-1)=M \hspace{0.05cm}.$$
-*In today's computers, multiplications and additions/subtractions need about the same computing time.&nbsp; It is sufficient to consider the total number&nbsp; $\mathcal{O} = M + A$&nbsp; of all operations:
+*In today's computers,&nbsp; multiplications and additions/subtractions need about the same computing time.&nbsp; It is sufficient to consider the total number&nbsp; $\mathcal{O} = M + A$&nbsp; of all operations:
 :$$\mathcal{O} = 8 \cdot N \cdot (N-1) \approx 8 \cdot N^2\hspace{0.05cm}.$$
 {{BlaueBox|TEXT=
 $\text{Conclusion:}$&nbsp;
-*For a&nbsp; Discrete Fourier Transform&nbsp; (DFT) with&nbsp; $N = 1000$&nbsp; one already needs almost eight million arithmetic operations.&nbsp; The same applies to an IDFT.
+*For a&nbsp; Discrete Fourier Transform&nbsp; $\rm (DFT)$&nbsp; with&nbsp; $N = 1000$&nbsp; one already needs almost eight million arithmetic operations.&nbsp; The same applies to an IDFT.
-*With&nbsp; $N =16$&nbsp; still &nbsp;$1920$&nbsp; computational operations are required.}}
 *With&nbsp; $N =16$&nbsp; still &nbsp;$1920$&nbsp; computational operations are required.
-If the parameter&nbsp; $N$&nbsp; is a power to the base&nbsp; $2$, more computationally efficient algorithms can be applied.&nbsp; The multitude of such methods known from the literature are summarized under the collective term&nbsp; $\text{Fast Fourier Transform}$&nbsp; - abbreviated&nbsp; $\text{FFT}$.&nbsp; All these methods are based on the&nbsp; "superposition theorem"&nbsp; of the DFT.
+*If the parameter&nbsp; $N$&nbsp; is a power to the base&nbsp; $2$,&nbsp; more computationally efficient algorithms can be applied.&nbsp; The multitude of such methods known from the literature are summarized under the collective term&nbsp; &raquo;'''Fast Fourier Transform'''&laquo;&nbsp; &ndash; abbreviated&nbsp; $\text{FFT}$.&nbsp; All these methods are based on the&nbsp; &raquo;superposition theorem&laquo;&nbsp; of the DFT.}}
 ==Superposition theorem of the DFT==
 <br>
-The graph illustrates the so-called&nbsp; "superposition theorem"&nbsp; of the DFT using the example of $N = 16$.&nbsp; Shown here is the transition from the time domain to the spectral domain, i.e. the calculation of the spectral domain coefficients from the time domain coefficients: &nbsp;    $\langle \hspace{0.1cm}D(\mu)\hspace{0.1cm}\rangle  \hspace{0.2cm}\bullet\!\!-\!\!\!-(N)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm} d(\nu) \hspace{0.1cm}\rangle.$
+The graph illustrates the so-called&nbsp; &raquo;superposition theorem&laquo;&nbsp; of the DFT using the example of&raquo; $N = 16$.&nbsp; Shown here is the transition from the time domain to the spectral domain,&nbsp; i.e. the calculation of the spectral domain coefficients from the time domain coefficients: &nbsp;    $\langle \hspace{0.1cm}D(\mu)\hspace{0.1cm}\rangle  \hspace{0.2cm}\bullet\!\!-\!\!\!-(N)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm} d(\nu) \hspace{0.1cm}\rangle.$
 [[File:EN_Sig_T_5_5_S2.png|right|frame|Superposition theorem of the DFT]]
 The algorithm described thereby is characterized by the following steps:
-*The sequence&nbsp; $\langle \hspace{0.1cm}d(\nu)\hspace{0.1cm}\rangle$&nbsp; of length&nbsp; $N$&nbsp; is divided into two subsequences$\langle \hspace{0.1cm} d_1(\nu)\hspace{0.1cm}\rangle$&nbsp;  and&nbsp; $\langle \hspace{0.1cm} d_2(\nu)\hspace{0.1cm}\rangle$&nbsp; each of half length&nbsp; (highlighted in yellow and green respectively in the graphic).&nbsp; With&nbsp; $0 \le \nu \lt N/2$&nbsp; one thus obtains the sequence elements
+*The sequence&nbsp; $\langle \hspace{0.1cm}d(\nu)\hspace{0.1cm}\rangle$&nbsp; of length&nbsp; $N$&nbsp; is divided into two subsequences&nbsp; $\langle \hspace{0.1cm} d_1(\nu)\hspace{0.1cm}\rangle$&nbsp;  and&nbsp; $\langle \hspace{0.1cm} d_2(\nu)\hspace{0.1cm}\rangle$&nbsp; each of half length&nbsp; $($highlighted in yellow and green respectively in the graphic$)$.&nbsp; With&nbsp; $0 \le \nu \lt N/2$&nbsp; one thus obtains the sequence elements
 :$$d_1(\nu) = d(2\nu), $$
 :$$d_2(\nu) = d(2\nu+1)

@@ Line 147: / Line 147: @@
-[[File:EN_Sig_Programm.png|right|frame|Radix-2 algorithm (C program) '''KORREKTUR: von, transfer parameters, ""''']]
+[[File:EN_Sig_Programm.png|right|frame|Radix-2 algorithm (C program)]]
 {{GraueBox|TEXT=
 $\text{Example 3:}$&nbsp;

@@ Line 73: / Line 73: @@
 Applying the DFT algorithm with&nbsp; $N = 16$&nbsp; one obtains the spectral coefficients&nbsp; $D(\mu )$&nbsp; given in&nbsp; '''line 3'''&nbsp; which would be equal&nbsp; $D(\mu ) = 4 \cdot \text{sinc}^2(\mu/2)$&nbsp; if the aliasing error were neglected.&nbsp; We can see that the aliasing error only affects the odd coefficients (shaded boxes). For example, $D(1) = 16/ \pi^2 \approx 1.621\neq 1.642$&nbsp; should be.
-[[File:Sig_T_5_5_S2b_Version2.png|right|frame|Result table for &nbsp;$\text{Example 1}$&nbsp; for the superposition theorem of the DFT '''KORREKTUR: Zeile, btw.''']]
+[[File:Sig_T_5_5_S2b_Version2.png|right|frame|Result table for &nbsp;$\text{Example 1}$&nbsp; for the superposition theorem of the DFT&nbsp; $($Note: "Zeile" &nbsp; &rArr;&nbsp; "row"$)$]]
 If we split the total sequence&nbsp; $\langle \hspace{0.1cm}d(\nu)\hspace{0.1cm}\rangle$&nbsp; into two subsequences  such that the first subsequence&nbsp; $\langle \hspace{0.1cm}{d_1}'(\nu)\hspace{0.1cm}\rangle$ &nbsp; &rArr; &nbsp; yellow marked has only even coefficients&nbsp; $(\nu = 0, 2, \hspace{0.03cm}\text{ ...} \hspace{0.1cm}, N–2)$&nbsp;  and the second subsequence&nbsp; $\langle \hspace{0.1cm}{d_2}'(\nu)\hspace{0.1cm}\rangle$&nbsp; &rArr; &nbsp; green marked contains only odd coefficients&nbsp; $(\nu = 1, 3, \hspace{0.03cm}\text{ ...} \hspace{0.1cm} , N-1)$&nbsp; and all others are set to zero.&nbsp; The corresponding sequences in the spectral domain are obtained:
@@ Line 95: / Line 95: @@
 To continue the first example, the previous table is now extended by the rows &nbsp;$8$&nbsp; to &nbsp;$12$&nbsp;.
-[[File:Sig_T_5_5_S2c_Version2.png|right|frame|Result table for &nbsp;$\text{Example 2}$&nbsp; for the superposition theorem of the DFT '''KORREKTUR: Zeile, bzw.''']]
+[[File:EN_Sig_T_5_5_S2c.png|right|frame|Result table for &nbsp;$\text{Example 2}$&nbsp; for the superposition theorem of the DFT]]
 Omitting the coefficients&nbsp; ${d_1}'(\nu) = 0$&nbsp; with odd indices and&nbsp; ${d_2}'(\nu) = 0$&nbsp; with even indices, we arrive at the subsequences&nbsp; $\langle \hspace{0.1cm}d_1(\nu)\hspace{0.1cm}\rangle$&nbsp; and&nbsp; $\langle \hspace{0.1cm}d_2(\nu)\hspace{0.1cm}\rangle$&nbsp; corresponding to lines &nbsp;$9$&nbsp; and &nbsp;$11$&nbsp;. You can see:
@@ Line 130: / Line 130: @@
 The diagram illustrates the algorithm for&nbsp; $N = 8$, again showing the transformation from the time to the frequency domain.
-[[File:EN_Sig_T_5_5_S3a_v2.png|right|frame|Radix-2 algorithm (flow diagram) '''KORREKTUR: Stufe''']]
+[[File:EN_Sig_T_5_5_S3a.png|right|frame|Radix-2 algorithm (flow diagram)]]
 *Before the FFT algorithm, the input values&nbsp; $d(0), \hspace{0.05cm}\text{...} \hspace{0.1cm}, d( N - 1)$&nbsp; have to be reordered in the grey block&nbsp; "Bit Reversal Operation".