Aufgaben:Exercise 5.5Z: Complexity of the FFT - Revision history

Guenter at 14:48, 24 May 2021

2021-05-24T14:48:25Z

Guenter at 09:43, 22 May 2021

2021-05-22T09:43:35Z

Guenter at 08:34, 22 May 2021

2021-05-22T08:34:00Z

Guenter at 08:33, 22 May 2021

2021-05-22T08:33:16Z

Guenter: Guenter moved page Aufgaben:Exercise 5.5Z: Complexity of The FFT to Aufgaben:Exercise 5.5Z: Complexity of the FFT

2021-05-21T15:17:22Z

Guenter moved page Exercise 5.5Z: Complexity of The FFT to Exercise 5.5Z: Complexity of the FFT

Noah at 14:02, 23 March 2021

2021-03-23T14:02:03Z

Show changes

Javier: Text replacement - "Category:Exercises for Signal Representation" to "Category:Signal Representation: Exercises"

2021-03-23T12:38:57Z

Text replacement - "Category:Exercises for Signal Representation" to "Category:Signal Representation: Exercises"

Oezdemir: Oezdemir moved page Aufgaben:Aufgabe 5.5Z: Rechenaufwand für die FFT to Aufgaben:Exercise 5.5Z: Complexity of The FFT

2020-11-29T21:01:50Z

Oezdemir moved page Aufgabe 5.5Z: Rechenaufwand für die FFT to Exercise 5.5Z: Complexity of The FFT

Oezdemir at 21:00, 29 November 2020

2020-11-29T21:00:33Z

Javier: Text replacement - "Signaldarstellung/Fast-Fouriertransformation (FFT)" to "Signal_Representation/Fast_Fourier_Transform_(FFT)"

2020-09-01T13:36:42Z

Text replacement - "Signaldarstellung/Fast-Fouriertransformation (FFT)" to "Signal_Representation/Fast_Fourier_Transform_(FFT)"

@@ Line 7: / Line 7: @@
 *The FFT occurs in&nbsp; ${\rm log_2} \ N$&nbsp; stages, whereby the exact same number of arithmetic operations must be carried out in each stage.
 *The diagram shows the third and last stage for the example&nbsp; $N = 8$.&nbsp; It can be seen that&nbsp; $N/2$&nbsp; basic operations have to be carried out in this and the other stages.
-*In each basic operation called &nbsp; '''butterfly''',&nbsp; two complex outputs are calculated from the two complex input variables&nbsp; $E_1$&nbsp; and&nbsp; $E_2$&nbsp;:
+*In each basic operation called&nbsp; '''butterfly''',&nbsp; two complex outputs are calculated from the two complex input variables&nbsp; $E_1$&nbsp; and&nbsp; $E_2$&nbsp;:
 :$$ 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}.$$

@@ Line 44: / Line 44: @@
 $M_{\rm M} \hspace{0.2cm} = \  $ { 4 }
-{How many complex additions/subtractions&nbsp; $(a_{\rm B})$&nbsp; does a single basic operationn (&bdquo;butterfly&rdquo;) require?
+{How many complex additions/subtractions&nbsp; $(a_{\rm B})$&nbsp; does a single basic operationn&nbsp; ("butterfly")&nbsp; require?
 <br>How many complex multiplications&nbsp; $(m_{\rm B})$&nbsp; are required per basic operation?
 |type="{}"}
@@ Line 54: / Line 54: @@
 $\mathcal{O}_{\rm B} \ = \ $  { 10 }
-{How many real operations&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; does the entire FFT&ndash;algorithm require? What are the values for&nbsp; $N = 16$&nbsp; und&nbsp; $N = 1024$?
+{How many real operations&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; does the entire FFT&ndash;algorithm require?&nbsp; What are the values for&nbsp; $N = 16$&nbsp; und&nbsp; $N = 1024$?
 |type="{}"}
 $N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }
 $N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 3% }
-{What is the time gain&nbsp; $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$&nbsp; für&nbsp; $N = 16$&nbsp; and&nbsp; $N = 1024$?
+{What is the time gain&nbsp; $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$&nbsp; for&nbsp; $N = 16$&nbsp; and&nbsp; $N = 1024$?
 |type="{}"}
 $N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }

@@ Line 26: / Line 26: @@
 *This task belongs to the chapter&nbsp; [[Signal_Representation/Fast_Fourier_Transform_(FFT)|Fast Fourier Transform (FFT)]].
 *It makes sense to calculate the powers of&nbsp; $w$&nbsp; before the actual algorithm and store them in a lookup table.&nbsp; The operations necessary for this are to be disregarded.
-*The bit reversal operation – a rearrangement that has to be carried out before the first stage – is also not to be taken into account in this estimation.
+*The&nbsp; "bit reversal operation"&nbsp; – a rearrangement that has to be carried out before the first stage – is also not to be taken into account in this estimation.

@@ Line 4: / Line 4: @@
 [[File:P_ID1179__Sig_Z_5_5.png|right|frame|Final step of the FFT for $N=8$]]
-The FFT algorithm&nbsp; (''Fast Fourier Transform'')&nbsp; realises a&nbsp; ''Discrete Fourier Transform''&nbsp; with the smallest possible computational effort if the parameter&nbsp; $N$&nbsp; is a power of two. In detail, the following calculation steps are necessary to carry out an FFT:
+The&nbsp; $\rm FFT$&nbsp; algorithm&nbsp; ("Fast Fourier Transform")&nbsp; realises a&nbsp; "Discrete Fourier Transform"&nbsp; $\rm (DFT)$&nbsp; with the smallest possible computational effort if the parameter&nbsp; $N$&nbsp; is a power of two.&nbsp; In detail, the following calculation steps are necessary to carry out an FFT:
 *The FFT occurs in&nbsp; ${\rm log_2} \ N$&nbsp; stages, whereby the exact same number of arithmetic operations must be carried out in each stage.
-*The diagram shows the third and last stage for the example&nbsp; $N = 8$. It can be seen that&nbsp; $N/2$&nbsp; basic operations have to be carried out in this and the other stages.
+*The diagram shows the third and last stage for the example&nbsp; $N = 8$.&nbsp; It can be seen that&nbsp; $N/2$&nbsp; basic operations have to be carried out in this and the other stages.
-*In each basic operation, which is often called a &nbsp; '''butterfly'''&nbsp;, two complex outputs are calculated from the two complex input variables&nbsp; $E_1$&nbsp; and&nbsp; $E_2$&nbsp;:
+*In each basic operation called &nbsp; '''butterfly''',&nbsp; two complex outputs are calculated from the two complex input variables&nbsp; $E_1$&nbsp; and&nbsp; $E_2$&nbsp;:
 :$$ 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}.$$
-*Here&nbsp; $w =  {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$&nbsp; denotes the complex rotation factor. For&nbsp;  $N = 8$&nbsp; the value&nbsp; $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}$ is obtained.
+*Here&nbsp; $w =  {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$&nbsp; denotes the complex rotation factor.&nbsp; For&nbsp;  $N = 8$&nbsp; the value&nbsp; $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}$ is obtained.
-*The exponent&nbsp; $\mu$&nbsp; for this complex rotation factor can take all integer values between&nbsp; $0$&nbsp; and&nbsp; $N/2-1$&nbsp;. For&nbsp; $N = 8$&nbsp; it is:
+*The exponent&nbsp; $\mu$&nbsp; for this complex rotation factor can take all integer values between&nbsp; $0$&nbsp; and&nbsp; $N/2-1$.&nbsp; For&nbsp; $N = 8$&nbsp; it is:
 :$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}
 \cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm
@@ Line 17: / Line 17: @@
 \cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$
-The purpose of this task is to determine the number of arithmetic operations&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; required for the FFT and compare it with the value&nbsp; $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$&nbsp; that can be specified for the DFT
+The purpose of this task is to determine the number of arithmetic operations&nbsp; $(\mathcal{O}_{\rm FFT})$&nbsp; required for the FFT and compare it with the value&nbsp; $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$&nbsp; that can be specified for the DFT.
@@ Line 29: / Line 23: @@
-''Hint:''
+''Hints:''
 *This task belongs to the chapter&nbsp; [[Signal_Representation/Fast_Fourier_Transform_(FFT)|Fast Fourier Transform (FFT)]].

← Older revision		Revision as of 12:38, 23 March 2021
Line 124:		Line 124:


−	[[Category:~~Exercises for~~ Signal Representation\|^5.5 Fast Fourier Transform ^]]	+	[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]

← Older revision	Revision as of 15:17, 21 May 2021
(No difference)

← Older revision	Revision as of 21:01, 29 November 2020
(No difference)

← Older revision		Revision as of 21:00, 29 November 2020
Line 124:		Line 124:


−	[[Category:Exercises for Signal Representation\|^5. ~~Zeit- und frequenzdiskrete Signaldarstellung~~^]]	+	[[Category:Exercises for Signal Representation\|^5.5 Fast Fourier Transform ^]]

← Older revision		Revision as of 13:36, 1 September 2020
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Signaldarstellung~~/~~Fast-Fouriertransformation~~ (FFT)	+	{{quiz-Header\|Buchseite=Signal_Representation/Fast_Fourier_Transform_(FFT)
	}}		}}