Aufgaben:Exercise 5.5: Fast Fourier Transform - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:56:22Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:56, 16 March 2026
Line 126:		Line 126:
	*Subtask  '''(5)'''  gave the following result:		*Subtask  '''(5)'''  gave the following result:

	:$$d({\rm even}\hspace{0.15cm}\nu) = +1, \hspace{0.2cm}d({\~~rmodd~~}\hspace{0.15cm}\nu)= -1$$		:$$d({\rm even}\hspace{0.15cm}\nu) = +1, \hspace{0.2cm}d({\rm odd}\hspace{0.15cm}\nu)= -1$$
	:$$\Rightarrow\hspace{0.3cm}D(\mu = 4)= 1,\hspace{0.2cm}D(\mu \ne 4)= 0.$$		:$$\Rightarrow\hspace{0.3cm}D(\mu = 4)= 1,\hspace{0.2cm}D(\mu \ne 4)= 0.$$

Line 138:		Line 138:
	__NOEDITSECTION__		__NOEDITSECTION__
	[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]		[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]
	[[de:Aufgaben:5.~~5_Fast~~-Fouriertransformation]]		[[de:Aufgaben:Aufgabe 5.5: Fast-Fouriertransformation]]

Maintenance script: Join split $$ formula lines for correct rendering

2026-03-16T13:31:16Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:31, 16 March 2026
Line 9:		Line 9:
	The associated spectral coefficients  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  are determined from the time coefficients  $d(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}, d(7)$.  The following applies to these with  $0 ≤ μ ≤ 7$:		The associated spectral coefficients  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  are determined from the time coefficients  $d(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}, d(7)$.  The following applies to these with  $0 ≤ μ ≤ 7$:

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

	where the complex rotation factor  $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot		where the complex rotation factor  $w = \text{e}^{-\text{j}\hspace{0.05cm} \cdot
Line 85:		Line 83:
	\hspace{0.05cm}\pi /4}$  taking into account the alternating time coefficients:		\hspace{0.05cm}\pi /4}$  taking into account the alternating time coefficients:

	:$$8 \cdot D(3) = w^0 - w^3 + w^6- w^9+ w^{12}- w^{15}+ w^{18}-		:$$8 \cdot D(3) = w^0 - w^3 + w^6- w^9+ w^{12}- w^{15}+ w^{18}-w^{21} = w^0 - w^3 + w^2- w^1+ w^{4}- w^{7}+ w^{6}-w^{5}\hspace{0.05cm}.$$
	w^{21} = w^0 - w^3 + w^2- w^1+ w^{4}- w^{7}+ w^{6}-
	w^{5}\hspace{0.05cm}.$$

	*Here it is taken into account that due to the periodicity  $w_9 = w_1$,  $w_{12} = w_4$,  $w_{15} = w_7$,  $w_{18} = w_2$  und  $w_{21} = w_5$  ist.		*Here it is taken into account that due to the periodicity  $w_9 = w_1$,  $w_{12} = w_4$,  $w_{15} = w_7$,  $w_{18} = w_2$  und  $w_{21} = w_5$  ist.
Line 99:		Line 95:
	'''(2)'''  In analogy to sub-taske  '''(1)''' , we now get:		'''(2)'''  In analogy to sub-taske  '''(1)''' , we now get:

	:$$ 8 \cdot D(4) = w^0 - w^4 + w^8- w^{12}+ w^{16}- w^{20}+		:$$ 8 \cdot D(4) = w^0 - w^4 + w^8- w^{12}+ w^{16}- w^{20}+w^{24}- w^{28}= 4 \cdot (w^0 - w^4)= 8 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{D(\mu=4) = 1}\hspace{0.05cm}.$$
	w^{24}- w^{28}= 4 \cdot (w^0 - w^4)= 8 \hspace{0.3cm}
	\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{D(\mu=4) = 1}\hspace{0.05cm}.$$


Line 120:		Line 114:
	'''(5)'''  Because of  $Y(5) = Y(6) =Y(7) = 0$, the multiplications with  $w$,  $w^2$  and  $w^3$  do not matter in the third stage either.  All spectral coefficients  $D(\mu)$  therefore result in zero with the exception of		'''(5)'''  Because of  $Y(5) = Y(6) =Y(7) = 0$, the multiplications with  $w$,  $w^2$  and  $w^3$  do not matter in the third stage either.  All spectral coefficients  $D(\mu)$  therefore result in zero with the exception of

	:$$\hspace{0.15 cm}\underline{D(\mu=4)} = {1}/{N}\cdot \left[Y(0) - Y(4) \right ] \hspace{0.15 cm}\underline{= 1}		:$$\hspace{0.15 cm}\underline{D(\mu=4)} = {1}/{N}\cdot \left[Y(0) - Y(4) \right ] \hspace{0.15 cm}\underline{= 1}\hspace{0.05cm},$$
	\hspace{0.05cm},$$		:$$\hspace{0.15 cm}\underline{D(\mu=3)} = D(\mu\ne 4) \hspace{0.15 cm}\underline{= 0}\hspace{0.05cm}.$$
	:$$\hspace{0.15 cm}\underline{D(\mu=3)} = D(\mu\ne 4) \hspace{0.15 cm}\underline{= 0}
	\hspace{0.05cm}.$$

	This result agrees with the results from  '''(1)'''  und  '''(2)'''.		This result agrees with the results from  '''(1)'''  und  '''(2)'''.
Line 134:		Line 126:
	*Subtask  '''(5)'''  gave the following result:		*Subtask  '''(5)'''  gave the following result:

	:$$d({\rm even}\hspace{0.15cm}\nu) = +1, \hspace{0.2cm}d({\rm		:$$d({\rm even}\hspace{0.15cm}\nu) = +1, \hspace{0.2cm}d({\rmodd}\hspace{0.15cm}\nu)= -1$$
	~~odd~~}\hspace{0.15cm}\nu)= -1$$		:$$\Rightarrow\hspace{0.3cm}D(\mu = 4)= 1,\hspace{0.2cm}D(\mu \ne 4)= 0.$$
	:$$\Rightarrow
	\hspace{0.3cm}D(\mu = 4)= 1,\hspace{0.2cm}D(\mu \ne 4)= 0.$$

	*By swapping the input and output values, we arrive at problem  '''(6)''':		*By swapping the input and output values, we arrive at problem  '''(6)''':

	:$$d(\nu = 4)= 1, \hspace{0.2cm}d(\nu \ne 4)= 0 \hspace{0.3cm}		:$$d(\nu = 4)= 1, \hspace{0.2cm}d(\nu \ne 4)= 0 \hspace{0.3cm}\Rightarrow \hspace{0.3cm}D({\rm gerades}\hspace{0.15cm}\mu) = +1,\hspace{0.2cm}D({\rm ungerades}\hspace{0.15cm}\mu)= -1\hspace{0.05cm}.$$
	\Rightarrow \hspace{0.3cm}D({\rm gerades}\hspace{0.15cm}\mu) = +1,
	\hspace{0.2cm}D({\rm ungerades}\hspace{0.15cm}\mu)= -1
	\hspace{0.05cm}.$$

	*In particular, this results in  $D(\mu=3) \; \underline{= -1}$  und  $D(\mu=4) \; \underline{= +1}$.		*In particular, this results in  $D(\mu=3) \; \underline{= -1}$  und  $D(\mu=4) \; \underline{= +1}$.

Maintenance script: Add German interlanguage link

2026-03-16T12:34:11Z

Add German interlanguage link

← Older revision		Revision as of 14:34, 16 March 2026
Line 151:		Line 151:
	__NOEDITSECTION__		__NOEDITSECTION__
	[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]		[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]
			[[de:Aufgaben:5.5_Fast-Fouriertransformation]]

Guenter at 16:08, 21 May 2021

2021-05-21T16:08:54Z

← Older revision		Revision as of 18:08, 21 May 2021
Line 94:		Line 94:
	:$$8 \cdot D(3) = (w^0 + w^4) - (w^1 + w^5)+ (w^2 + w^6) - (w^3 + w^7) = (1 + w + w^2+ w^3) \cdot (w^0 + w^4)\hspace{0.05cm}.$$		:$$8 \cdot D(3) = (w^0 + w^4) - (w^1 + w^5)+ (w^2 + w^6) - (w^3 + w^7) = (1 + w + w^2+ w^3) \cdot (w^0 + w^4)\hspace{0.05cm}.$$

	*Thus, because  $w_0 = 1$  and  $w_4 = \text{e}^{-\text{j}\pi } = \hspace{0.08cm} - \hspace{-0.08cm}1$ , we obtain  $\underline {D(3) = 0}$.		*Thus, because  $w_0 = 1$  and  $w_4 = \text{e}^{-\text{j}\pi } = \hspace{0.08cm} - \hspace{-0.08cm}1$ , we obtain  $\underline {D(\mu=3) = 0}$.


Line 101:		Line 101:
	:$$ 8 \cdot D(4) = w^0 - w^4 + w^8- w^{12}+ w^{16}- w^{20}+		:$$ 8 \cdot D(4) = w^0 - w^4 + w^8- w^{12}+ w^{16}- w^{20}+
	w^{24}- w^{28}= 4 \cdot (w^0 - w^4)= 8 \hspace{0.3cm}		w^{24}- w^{28}= 4 \cdot (w^0 - w^4)= 8 \hspace{0.3cm}
	\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{D(4) = 1}\hspace{0.05cm}.$$		\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{D(\mu=4) = 1}\hspace{0.05cm}.$$


Line 108:		Line 108:
	*The term  $w^0 = 1$  does not have to be taken into account.		*The term  $w^0 = 1$  does not have to be taken into account.
	*All output values with odd indices are zero by subtracting two identical input values.		*All output values with odd indices are zero by subtracting two identical input values.
	*The first statement is not true:   ~~Es gilt~~  $X(0) = X(2) = +2$  and  $X(4) = X(6) = - 2$.		*The first statement is not true:   It holds  $X(0) = X(2) = +2$  and  $X(4) = X(6) = - 2$.


Line 118:		Line 118:


	'''(5)'''  Because of  $Y(5) = Y(6) =Y(7) = 0$~~ ~~ , the multiplications with  $w$,  $w^2$  and  $w^3$  do not matter in the third stage either. All spectral coefficients  $D(\mu)$  therefore result in zero with the exception of		'''(5)'''  Because of  $Y(5) = Y(6) =Y(7) = 0$, the multiplications with  $w$,  $w^2$  and  $w^3$  do not matter in the third stage either.  All spectral coefficients  $D(\mu)$  therefore result in zero with the exception of

	:$$\hspace{0.15 cm}\underline{D(4)} = {1}/{N}\cdot \left[Y(0) - Y(4) \right ] \hspace{0.15 cm}\underline{= 1}		:$$\hspace{0.15 cm}\underline{D(\mu=4)} = {1}/{N}\cdot \left[Y(0) - Y(4) \right ] \hspace{0.15 cm}\underline{= 1}
			\hspace{0.05cm},$$
			:$$\hspace{0.15 cm}\underline{D(\mu=3)} = D(\mu\ne 4) \hspace{0.15 cm}\underline{= 0}
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$

	This result agrees with the results from  '''(1)'''  und  '''(2)'''~~ ~~.		This result agrees with the results from  '''(1)'''  und  '''(2)'''.


Line 144:		Line 146:
	\hspace{0.05cm}.$$		\hspace{0.05cm}.$$

	*In particular, this results in  $D(3) \; \underline{= -1}$  und  $D(4) \; \underline{= +1}$.		*In particular, this results in  $D(\mu=3) \; \underline{= -1}$  und  $D(\mu=4) \; \underline{= +1}$.
	{{ML-Fuß}}		{{ML-Fuß}}

	__NOEDITSECTION__		__NOEDITSECTION__
	[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]		[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]

Guenter at 16:00, 21 May 2021

2021-05-21T16:00:10Z

← Older revision		Revision as of 18:00, 21 May 2021
Line 5:		Line 5:
	[[File:EN_Sig_A_5_5.png\|right\|frame\|FFT algorithm for  $N=8$]]		[[File:EN_Sig_A_5_5.png\|right\|frame\|FFT algorithm for  $N=8$]]

	The graph shows the signal flow diagram of the FFT for  $N = 8$. The associated spectral coefficients  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  are determined from the time coefficients  $d(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}, d(7)$ . The following applies to these with  $0 ≤ μ ≤ 7$:		The graph shows the signal flow diagram of the Fast Fourier Transform  $\rm (FFT)$  for  $N = 8$.

			The associated spectral coefficients  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  are determined from the time coefficients  $d(0), \hspace{0.03cm}\text{...} \hspace{0.1cm}, d(7)$.  The following applies to these with  $0 ≤ μ ≤ 7$:

	:$$D(\mu) = \frac{1}{N}\cdot \sum_{\nu = 0 }^{N-1}		:$$D(\mu) = \frac{1}{N}\cdot \sum_{\nu = 0 }^{N-1}
Line 19:		Line 21:


	It holds that  $b(κ) = d(ν)$, if  $ν$  is represented as a dual number and the resulting three bits are written as  $κ$  in reverse order. For example		It holds that  $b(κ) = d(ν)$, if  $ν$  is represented as a dual number and the resulting three bits are written as  $κ$  in reverse order.  For example
	*   $ν = 1$  $($binary  $001)$  is followed by  $κ = 4$  $($binary  $100)$,		*   $ν = 1$  $($binary  $001)$  is followed by  $κ = 4$  $($binary  $100)$,
	*   $d(2)$  remains at the same position  $2$  $($binary  $010)$.		*   $d(2)$  remains at the same position  $2$  $($binary  $010)$.


	The actual FFT algorithm happens for the example  $N = 8$  in  $\log_2 N = 3$  stages, denoted  $L = 1$,  $L =2$  and  $L = 3$ . Further:		The actual FFT algorithm happens for the example  $N = 8$  in  $\log_2 N = 3$  stages, denoted  $L = 1$,  $L =2$  and  $L = 3$.  Further:
	* In each stage, four basic operations - so-called ''butterflies'' - are to be performed.		* In each stage, four basic operations - so-called  '''butterflies'''  - are to be performed.
	* The values at the output of the first stage are designated in this task as  $X(0),\hspace{0.03cm}\text{...} \hspace{0.1cm} , X(7)$~~ ~~ , those of the second as  $Y(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , Y(7)$.		* The values at the output of the first stage are designated in this task as  $X(0),\hspace{0.03cm}\text{...} \hspace{0.1cm} , X(7)$, <br>those of the second as  $Y(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , Y(7)$.
	* After the third and last stage, all values must be divided by  $N$ . The final result  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  is ~~then~~ available here.		* After the third and last stage, all values must be divided by  $N$.  <br>The final result  $D(0), \hspace{0.03cm}\text{...} \hspace{0.1cm} , D(7)$  is available here.


Line 45:		Line 47:
	<quiz display=simple>		<quiz display=simple>

	{Calculate the DFT coefficient  $D(3)$.		{Calculate the DFT coefficient  $D(\mu=3)$.
	\|type="{}"}		\|type="{}"}
	$D(3) \ = \ $ { 0. }		$D(\mu=3) \ = \ $ { 0. }

	{Calculate the DFT coefficient  $D(4)$.		{Calculate the DFT coefficient  $D(\mu=4)$.
	\|type="{}"}		\|type="{}"}
	$D(4) \ = \ $ { 1 3% }		$D(\mu=4) \ = \ $ { 1 3% }

	{Determine the initial values  $X(0)$, ... , $X(7)$  of the first stage. Which of the following statements are true?		{Determine the initial values  $X(0)$, ... , $X(7)$  of the first stage.  Which of the following statements are true?
	\|type="[]"}		\|type="[]"}
	- All  $X$~~–~~values with even indices are equal to  $2$.		- All  $X$ values with even indices are equal to  $2$.
	+ All  $X$~~–~~values with odd indices are equal to  $0$.		+ All  $X$ values with odd indices are equal to  $0$.

	{Determine the initial values  $Y(0)$, ... , $Y(7)$  of the second stage. Enter the values  $Y(0)$  and  $Y(4)$  as a check.		{Determine the initial values  $Y(0)$, ... , $Y(7)$  of the second stage.  Enter the values  $Y(0)$  and  $Y(4)$  as a check.

	\|type="{}"}		\|type="{}"}
Line 66:		Line 68:
	{Calculate all  $N$  spectral values  $D(\mu)$, in particular		{Calculate all  $N$  spectral values  $D(\mu)$, in particular
	\|type="{}"}		\|type="{}"}
			$D(\mu =3) \ = \ $ { 0. }
	$D(\mu = 4) \ = \ $ { 1 3% }		$D(\mu = 4) \ = \ $ { 1 3% }
	~~$D(\mu \neq 4) \ = \ $ { 0. }~~

	{What would be the spectral coefficients for  $d(ν = 4) = 1$  and  $d(ν \neq 4) = 0$ ? <br>Enter the values  $D(3)$  and  $D(4)$  as a check.		{What would be the spectral coefficients for  $d(ν = 4) = 1$  and  $d(ν \neq 4) = 0$ ? <br>Enter the values  $D(\mu =3)$  and  $D(\mu =4)$  as a check.
	\|type="{}"}		\|type="{}"}
	$D(\mu = 3) \ = \ $ { -1.03--0.97 }		$D(\mu = 3) \ = \ $ { -1.03--0.97 }

Noah at 13:36, 23 March 2021

2021-03-23T13:36:46Z

Show changes

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

2021-03-23T12:38:46Z

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

← Older revision		Revision as of 14:38, 23 March 2021
Line 145:		Line 145:

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

Oezdemir: Oezdemir moved page Aufgaben:Aufgabe 5.5: Fast-Fouriertransformation to Aufgaben:Exercise 5.5: Fast Fourier Transform

2020-11-29T21:00:58Z

Oezdemir moved page Aufgaben:Aufgabe 5.5: Fast-Fouriertransformation to Aufgaben:Exercise 5.5: Fast Fourier Transform

← Older revision		Revision as of 23:00, 29 November 2020
(No difference)

Oezdemir at 21:00, 29 November 2020

2020-11-29T21:00:27Z

← Older revision		Revision as of 23:00, 29 November 2020
Line 145:		Line 145:

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

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

2020-09-01T13:36:36Z

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

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

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