Difference between revisions of "Exercise 2.4Z: Repetition to IDFT"

Latest revision as of 19:22, 7 March 2023

Five sample sets for $\rm IDFT$

In the Discrete Fourier Transform $\rm (DFT)$ from the time samples $d(\nu) \hspace{0.15cm} {\rm with} \hspace{0.15cm} \nu = 0$, ... , $N - 1$ the discrete spectral coefficients $D(\mu) \hspace{0.15cm} {\rm with} \hspace{0.15cm} \mu = 0$, ... , $N - 1$ calculated as follows:

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

Here $w$ abbreviates the complex rotation factor, which is defined as follows:

$$w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi /N} = \cos \left( {2 \pi}/{N}\right)-{\rm j} \cdot \sin \left( {2 \pi}/{N}\right) \hspace{0.05cm}.$$

Thus, for the Inverse Discrete Fourier Transform $\rm (IDFT)$ as an inverse function of $\rm DFT$:

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

In this exercise, for different example sequences $D(\mu)$ - which in the above table are denoted by $\boldsymbol{\rm A}$, ... , $\boldsymbol{\rm E}$ - the time coefficients $d(\nu)$ are determined. Thus, it is always $N = 8$.

Hints:

This exercise refers to the theoretical foundations of the chapter "Discrete Fourier Transform" of the book "Signal Representation" and is identical to the one there "Exercise 5.2".
You can check your solution using the interactive applet "Discrete Fourier Transform" .
DFT and IDFT also play a major role in "DSM/DSL" .
In the corresponding chapter, spectral coefficients are denoted by $D_k$ and time samples are denoted by $s_l$. We apologize for this nomenclature discrepancy.
For the two running variables, with the DFT parameter $N = 8$: $0 \le k \le 7, \hspace{0.2cm}0 \le l \le 7 \hspace{0.05cm}.$

Questions

$d(0) \ = \ $

$d(1) \ = \ $

$d(0) \ = \ $

$d(1) \ = \ $

$d(0) \ = \ $

$d(1) \ = \ $

$d(0) \ = \ $

$d(1) \ = \ $

$d(0) \ = \ $

$d(1) \ = \ $

Solution

(1) From the IDFT equation, $D(\mu) = 0$ for $\mu \neq 0$ is obtained for the time coefficients with indices $0 ≤ \nu ≤ 7$:

$$d(\nu) = D(0) \cdot w^0 = D(0) \ = \ 1\hspace{0.3cm} \rightarrow\hspace{0.3cm}\underline{d(0) = d(1) \ = \ 1}.$$

This set of parameters thus describes the discrete form of the Fourier correspondence of the DC signal:

$$x(t) = 1 \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} X(f) = {\delta}(f) \hspace{0.05cm}.$$

(2) Here all spectral coefficients are $0$ except $D_{1} = D_{7} = 0.5$. It follows that for $0 ≤ \nu ≤ 7$:

$$d(\nu) = 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (7\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} \hspace{0.05cm}.$$

However, due to periodicity, the following is also true:

$$d(\nu) \ = \ 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} = \cos \left({\pi}/{4} \cdot \nu \right)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{d(0) = 1, \hspace{0.2cm}d(1) = {1}/{\sqrt{2}} \approx 0.707 \hspace{0.05cm}}.$$

Thus, it is the discrete-time equivalent of

$$x(t) = \cos(2 \pi \cdot f_{\rm A} \cdot t) \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} X(f) = {1}/{2} \cdot {\delta}(f + f_{\rm A}) + {1}/{2} \cdot {\delta}(f - f_{\rm A}) \hspace{0.05cm},$$

where $f_{\rm A}$ denotes the smallest frequency that can be represented in the DFT.

(3) Compared to the subtask (2), the frequency is now twice as large, namely $2 \cdot f_{\rm A}$ instead of $f_{\rm A}$:

$$x(t) = \cos(2 \pi \cdot (2f_{\rm A}) \cdot t) \hspace{0.2cm}\circ\!-\!-\!-\!-\!-\!-\!-\!-\bullet\, \hspace{0.2cm} X(f) = {1}/{2} \cdot {\delta}(f + 2f_{\rm A}) + {1}/{2}\cdot {\delta}(f - 2f_{\rm A}) \hspace{0.05cm},$$

Thus the sequence $〈d(\nu)〉$ describes two periods of the cosine oscillation, and it holds for $0 ≤ \nu ≤ 7$:

$$d(\nu) \ = \ 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /2) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /2) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} = \cos \left({\pi}/{2} \cdot \nu \right)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{d(0) = 1, \hspace{0.2cm}d(1) = 0 }\hspace{0.05cm}.$$

(4) By further doubling the cosine frequency to $4f_{\rm A}$, one finally arrives at the continuous-time Fourier correspondence

$$d(\nu) = 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} = \cos \left(\pi \cdot \nu \right) \hspace{0.05cm}$$

and thus to the time coefficients

$$d(0) = d(2) =d(4) =d(6)= +1, \hspace{0.2cm}d(1) =d(3) =d(5) =d(7) = -1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{d(0) = +1, \hspace{0.2cm}d(1) = -1 }\hspace{0.05cm}.$$

Note that the two Dirac functions coincide in the discrete-time representation due to periodicity.
That is, The coefficients $D(4) = 0.5$ and $D(-4) = 0.5$ add up to $D(4) = 1$.

(5) The Discrete Fourier Transform is also linear. Therefore, the superposition principle is still applicable.

The coefficients $D(\mu)$ from column $\boldsymbol{\rm E}$ are obtained as the sums of columns $\boldsymbol{\rm A}$ and $\boldsymbol{\rm D}$.
Therefore, the alternating sequence $〈d(\nu)〉$ according to subtask (4) becomes the sequence shifted up by 1:

$$d(0) =d(2) =d(4) =d(6)= 2, \hspace{0.2cm}d(1) =d(3) =d(5) =d(7) = 0\hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{d(0) = 2, \hspace{0.2cm}d(1) =0 }\hspace{0.05cm}. $$

@@ Line 1: / Line 1: @@
-{{quiz-Header|Buchseite=Beispiele von Nachrichtensystemen/xDSL als Übertragungstechnik
+{{quiz-Header|Buchseite=Examples_of_Communication_Systems/xDSL_as_Transmission_Technology
 }}
-[[File:P_ID1971__Sig_A_5_2.png|right|frame|Mustersätze zur IDFT]]
+[[File:P_ID1971__Sig_A_5_2.png|right|frame|Five sample sets for&nbsp; $\rm IDFT$]]
-Bei der Diskreten Fouriertransformation (DFT) werden aus den Zeitabtastwerten $d(\nu) \  {\rm mit} \  \nu = 0, ... , N – 1$ die diskreten Spektralkoeffizienten $D(\mu) \ {\rm mit} \  \mu = 0, ... , N – 1$ wie folgt berechnet:
+In the Discrete Fourier Transform&nbsp; $\rm (DFT)$&nbsp; from the time samples&nbsp; $d(\nu) \hspace{0.15cm} {\rm with} \hspace{0.15cm}  \nu = 0$, ... , $N - 1$&nbsp; the discrete spectral coefficients&nbsp; $D(\mu) \hspace{0.15cm} {\rm with} \hspace{0.15cm}  \mu = 0$, ... , $N - 1$&nbsp; calculated as follows:
 :$$D(\mu) = \frac{1}{N} \cdot \sum_{\nu = 0 }^{N-1} d(\nu)\cdot {w}^{\hspace{0.05cm}\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu} \hspace{0.05cm}.$$
-Hierbei ist mit $w$ der komplexe Drehfaktor abgekürzt, der folgendermaßen definiert ist:
+Here&nbsp; $w$&nbsp; abbreviates the complex rotation factor, which is defined as follows:
-:$$w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi /N} = \cos \left( \frac {2 \pi}{N}\right)-{\rm j} \cdot \sin \left( \frac {2 \pi}{N}\right) \hspace{0.05cm}.$$
+:$$w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi /N} = \cos \left( {2 \pi}/{N}\right)-{\rm j} \cdot \sin \left( {2 \pi}/{N}\right) \hspace{0.05cm}.$$
-Somit gilt für die Inverse Diskrete Fouriertransformation (IDFT) als Umkehrfunktion der DFT:
+Thus, for the Inverse Discrete Fourier Transform&nbsp; $\rm (IDFT)$&nbsp; as an inverse function of&nbsp; $\rm DFT$:
 :$$ d(\nu) = \sum_{\mu = 0 }^{N-1} D(\mu) \cdot {w}^{-\nu \hspace{0.03cm} \cdot \hspace{0.05cm}\mu} \hspace{0.05cm}.$$
-In dieser Aufgabe sollen für verschiedene Beispielfolgen $D(\mu)$ – die in obiger Tabelle mit „A”, ... , „E” bezeichnet sind – die Zeitkoeffizienten $d(\nu)$ ermittelt werden. Es gilt somit stets $N = 8$.
+In this exercise, for different example sequences&nbsp; $D(\mu)$ - which in the above table are denoted by&nbsp; $\boldsymbol{\rm A}$, ... , &nbsp;$\boldsymbol{\rm E}$&nbsp; - the time coefficients&nbsp; $d(\nu)$&nbsp; are determined. Thus, it is always&nbsp; $N = 8$.
-''Hinweis:''
-Die Aufgabe bezieht sich auf die theoretischen Grundlagen von Kapitel [[Beispiele_von_Nachrichtensystemen/Verfahren_zur_Senkung_der_Bitfehlerrate_bei_DSL#Gain_Scaling_und_Tone_Ordering|Gain Scaling und Tone Ordering]] des Buches „Signaldarstellung” und ist identisch mit der dortigen Aufgabe A5.2. Sie können sich die Lösung auch mit folgendem Interaktionsmodul verdeutlichen:
-Diskrete Fouriertransformation
-DFT und IDFT spielen auch bei [[Beispiele_von_Nachrichtensystemen/xDSL_als_Übertragungstechnik#DMT.E2.80.93Realisierung_mit_IDFT.2FDFT|DSM/DSL]] eine große Rolle. Im entsprechenden Kapitel werden die Spektralkoeffizienten allerdings mit $D_k$ bezeichnet und die Zeitabtastwerte mit $s_l$. Wir bitten Sie, diese Nomenklaturdiskrepanz zu entschuldigen.
-Für die beiden Laufvariablen gelten mit dem DFT–Parameter $N = 8$:
-:$$0 \le k \le 7, \hspace{0.2cm}0 \le l \le 7 \hspace{0.05cm}.$$
@@ Line 26: / Line 20: @@
-===Fragebogen===
+Hints:
+*This exercise refers to the theoretical foundations of the chapter&nbsp; [[Signal_Representation/Discrete_Fourier_Transform_(DFT)|"Discrete Fourier Transform"]]&nbsp; of the book "Signal Representation" and is identical to the one there&nbsp; [[Aufgaben:Exercise_5.2:_Inverse_Discrete_Fourier_Transform|"Exercise 5.2"]].
+*You can check your solution using the interactive applet&nbsp;  [[Applets:Diskrete_Fouriertransformation_(Applet)|"Discrete Fourier Transform"]]&nbsp;.
+*DFT and IDFT also play a major role in&nbsp; [[Examples_of_Communication_Systems/xDSL_as_Transmission_Technology#DMT_realization_with_IDFT.2FDFT|"DSM/DSL"]]&nbsp;.
+*In the corresponding chapter, spectral coefficients are denoted by&nbsp; $D_k$&nbsp; and time samples are denoted by&nbsp; $s_l$. We apologize for this nomenclature discrepancy.
+*For the two running variables, with the DFT parameter&nbsp; $N = 8$: &nbsp; $0 \le k \le 7, \hspace{0.2cm}0 \le l \le 7 \hspace{0.05cm}.$
+===Questions===
 <quiz display=simple>
+What are the time coefficients&nbsp; $d(\nu)$&nbsp; for&nbsp; $D(\mu)$&nbsp; according to column&nbsp; $\boldsymbol{\rm A}$?
+|type="{}"}
+$d(0) \ = \ ${ 1 }
+$d(1) \ = \ ${ 1 }
+{What are the time coefficients&nbsp; $d(\nu)$&nbsp; for&nbsp; $D(\mu)$&nbsp; according to column&nbsp; $\boldsymbol{\rm B}$?
+|type="{}"}
+$d(0) \ = \ ${ 1 }
+$d(1) \ = \ ${ 0.707 3% }
+{What are the time coefficients&nbsp; $d(\nu)$&nbsp; for&nbsp; $D(\mu)$&nbsp; according to column&nbsp; $\boldsymbol{\rm C}$?
+|type="{}"}
+$d(0) \ = \ ${ 1 }
+$d(1) \ = \ ${ 0. }
+{What are the time coefficients&nbsp; $d(\nu)$&nbsp; for&nbsp; $D(\mu)$&nbsp; according to column&nbsp; $\boldsymbol{\rm D}$?
+|type="{}"}
+$d(0) \ = \ ${ 1 }
+$d(1) \ = \ ${ -1.01--0.99 }
+{What are the time coefficients&nbsp; $d(\nu)$&nbsp; for&nbsp; $D(\mu)$&nbsp; according to column&nbsp; $\boldsymbol{\rm E}$?
+|type="{}"}
+$d(0) \ = \ ${ 2 }
+$d(1) \ = \ ${ 0. }
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp;
+'''(1)'''&nbsp; From the IDFT equation, $D(\mu) = 0$ for $\mu \neq 0$ is obtained for the time coefficients with indices&nbsp; $0 ≤ \nu ≤ 7$:
+:$$d(\nu) = D(0) \cdot w^0 = D(0) \ = \ 1\hspace{0.3cm} \rightarrow\hspace{0.3cm}\underline{d(0) = d(1) \ = \ 1}.$$
+This set of parameters thus describes the discrete form of the Fourier correspondence of the DC signal:
+:$$x(t) = 1 \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} X(f) = {\delta}(f) \hspace{0.05cm}.$$
+'''(2)'''&nbsp; Here all spectral coefficients are $0$ except $D_{1} = D_{7} = 0.5$. It follows that for $0 ≤ \nu ≤ 7$:
+:$$d(\nu) = 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (7\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} \hspace{0.05cm}.$$
+However, due to periodicity, the following is also true:
+:$$d(\nu) \ = \ 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /4) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} = \cos \left({\pi}/{4} \cdot \nu \right)\hspace{0.3cm}
+ \Rightarrow  \hspace{0.3cm}\underline{d(0) = 1, \hspace{0.2cm}d(1) = {1}/{\sqrt{2}} \approx 0.707 \hspace{0.05cm}}.$$
+Thus, it is the discrete-time equivalent of
+:$$x(t) = \cos(2 \pi \cdot f_{\rm A} \cdot t) \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} X(f) = {1}/{2} \cdot {\delta}(f + f_{\rm A}) + {1}/{2} \cdot {\delta}(f - f_{\rm A}) \hspace{0.05cm},$$
+where $f_{\rm A}$ denotes the smallest frequency that can be represented in the DFT.
+'''(3)'''&nbsp; Compared to the subtask '''(2)''', the frequency is now twice as large, namely $2 \cdot f_{\rm A}$ instead of $f_{\rm A}$:
+:$$x(t) = \cos(2 \pi \cdot (2f_{\rm A}) \cdot t) \hspace{0.2cm}\circ\!-\!-\!-\!-\!-\!-\!-\!-\bullet\, \hspace{0.2cm} X(f) = {1}/{2} \cdot {\delta}(f + 2f_{\rm A}) + {1}/{2}\cdot {\delta}(f - 2f_{\rm A}) \hspace{0.05cm},$$
+Thus the sequence $〈d(\nu)〉$ describes two periods of the cosine oscillation, and it holds for $0 ≤ \nu ≤ 7$:
+:$$d(\nu) \ = \ 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /2) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} (\pi /2) \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} = \cos \left({\pi}/{2} \cdot \nu \right)\hspace{0.3cm}
+ \Rightarrow  \hspace{0.3cm}\underline{d(0) = 1, \hspace{0.2cm}d(1) = 0 }\hspace{0.05cm}.$$
+'''(4)'''&nbsp; By further doubling the cosine frequency to $4f_{\rm A}$, one finally arrives at the continuous-time Fourier correspondence
+:$$d(\nu) = 0.5 \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} + 0.5 \cdot {\rm e}^{{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi \hspace{0.05cm}\cdot \hspace{0.05cm} \nu} = \cos \left(\pi \cdot \nu \right) \hspace{0.05cm}$$
+and thus to the time coefficients
+:$$d(0) = d(2) =d(4) =d(6)= +1, \hspace{0.2cm}d(1) =d(3) =d(5) =d(7) = -1 \hspace{0.3cm}
+ \Rightarrow \hspace{0.3cm}\underline{d(0) = +1, \hspace{0.2cm}d(1) = -1 }\hspace{0.05cm}.$$
+*Note that the two Dirac functions coincide in the discrete-time representation due to periodicity.
+*That is, &nbsp; The coefficients $D(4) = 0.5$ and $D(-4) = 0.5$ add up to $D(4) = 1$.
+'''(5)'''&nbsp; The Discrete Fourier Transform is also linear. Therefore, the superposition principle is still applicable.
+*The coefficients $D(\mu)$ from column $\boldsymbol{\rm E}$ are obtained as the sums of columns $\boldsymbol{\rm A}$ and $\boldsymbol{\rm D}$.
+*Therefore, the alternating sequence $〈d(\nu)〉$ according to subtask '''(4)''' becomes the sequence shifted up by 1:
+:$$d(0) =d(2) =d(4) =d(6)= 2, \hspace{0.2cm}d(1) =d(3) =d(5) =d(7) = 0\hspace{0.3cm}
+ \Rightarrow  \hspace{0.3cm}\underline{d(0) = 2, \hspace{0.2cm}d(1) =0 }\hspace{0.05cm}. $$
 {{ML-Fuß}}
@@ Line 43: / Line 116: @@
-[[Category:Aufgaben zu Beispiele von Nachrichtensystemen|^2.3 xDSL als Übertragungstechnik
+[[Category:Examples of Communication Systems: Exercises|^2.3 xDSL Transmission Technology
 ^]]