===================================== The Discrete Time Fourier Transform ===================================== We now make the switch to discrete time signals $x[n]$ where $n$ is an integer $n\in\setZ$. The name discrete *time* signals is a bit of a misnomer, essentially there is no time involved. Fourier analysis of discrete signals can be done entirely without the notion of time. It will be only later that we will make the connection between CT and DT signals. DTFT and IDTFT ============== The synthesis equation should look familiar: .. math:: x[n] = \frac{1}{2\pi} \int_{\langle 2\pi\rangle} X(\Omega)e^{j\Omega n} d\Omega A DT signal is constructed from DT complex exponentials. Note that a *discrete* complex exponential $e^{j\Omega n}$ is periodic in $\Omega$ with period $2\pi$, i.e. $e^{j(\Omega+2\pi) n}=e^{j\Omega n}$. That is why the integral over $\Omega$ is restricted to one period of $2\pi$. Please note (see the section on basic signals) that a complex exponential is only periodic in $n$ in case $\Omega/\pi$ is a fractional number. The analysis equation is .. math:: X(\Omega) = \sum_{n=-\infty}^{\infty} x[n]e^{-j \Omega n} For a DT signal $x[n]$ and its DT Fourier transform we write: .. math:: x[n] \FTright X(\Omega) .. todo:: proof? It is important to note that the Fourier transform of a DT signal $x[n]$ is a signal $X(\W)$ that is defined for $\W\in\setR$. As usual the signal for frequency $\Omega=0$ corresponds with a constant signal. For increasingly larger values of $\Omega$ up to $\Omega=\pi$ the frequency of the signal increases. The maximal frequency signal is .. math:: e^{-j\pi n} = \begin{cases} 1 &: n \text{ is even}\\ -1 &: n \text{ is odd} \end{cases} which of course is the fastest varying DT signal. For values starting at $\W=\pi$ and increasing to $\W=2\pi$ the frequency of the complex exponential $e^{j\W n}$ again decreases. .. exec_python:: freqsymmetryDTNP DTNP :linenumbers: :code: shutter :code_label: Show code for figure :results: hide import numpy as np import matplotlib.pyplot as plt plt.clf() NW = 8 fig, axs = plt.subplots(NW, 2, figsize=(5,9)) Ws = np.linspace(0, np.pi, NW) Ns = 8 n = np.arange(Ns) t = np.linspace(0, Ns-1, 1000) for i, W in enumerate(Ws): Wdivpi = W / np.pi axs[i, 0].plot(t, np.cos(W * t), color='gray') axs[i, 0].stem(n, np.cos(W * n)) axs[i, 0].get_yaxis().set_ticks([]) axs[i, 0].set_ylabel('${W:1.2f}\\,\\pi$'.format(W=Wdivpi)) axs[i, 1].plot(t, np.cos((2 * np.pi - W) * t), color='gray') axs[i, 1].stem(n, np.cos((2 * np.pi - W) * n)) axs[i, 1].get_yaxis().set_ticks([]) axs[i, 1].set_ylabel('${W:1.2f}\\,\\pi$'.format(W=2-Wdivpi)) print(i, W/np.pi) print(np.cos(W * n)) plt.savefig('source/figures/freqsymmetryDTNP.png') .. figure:: /figures/freqsymmetryDTNP.png :width: 100% **Frequency symmetry in the discrete time complex exponentials.** In the left column the frequency $\W$ runs from $0$ to $\pi$ going top to bottom. In the right column the frequency is $2\pi-\W$ where $\W$ is the frequency in the same row in the left column (so for both plots on the bottom row the frequency is $\W=\pi$. In blue the DT signal $x[n]=\cos(\W n)$ is shown, in gray the CT signal $x(t)=\cos(\W t)$ is shown (assuming the sampling time is 1 s). As an example of the DT Fourier transform consider a discrete block function of 5 samples: .. math:: b_2[n] = \begin{cases} 1 &: |n|\leq 2\\ 0 &: |n|>2 \end{cases} Its Fourier transform can be calculated as: .. math:: B(\W) &= e^{-2j\W} + e^{-j\W} + 1 + e^{j\W} + e^{2j\W}\\ &= 1 + 2 \cos(\W) + 2 \cos(\W n) .. exec_python:: blockDTNP DTNP :linenumbers: :code: shutter :code_label: Show code for figure :results: hide import numpy as np import matplotlib.pyplot as plt from matplotlib.ticker import FuncFormatter, MultipleLocator plt.close('all') def b2(n): return 1.0 * np.logical_and(n>=-2, n<=2) def B2(W): return 1 + 2 * np.cos(W) + 2 * np.cos(2*W) fig, axs = plt.subplots(2) n = np.arange(-7,8) W = np.linspace(0, 2*np.pi, 1000) axs[0].stem(n, b2(n)) axs[0].set_xlabel("n") axs[0].set_ylabel('$b_2(n)$') axs[1].plot(W, B2(W)) axs[1].axhline(0) axs[1].set_xlabel("$\\Omega$") axs[1].set_ylabel('$B_2(\Omega)$') axs[1].xaxis.set_major_formatter(FuncFormatter(lambda val,pos: '{:.1f}$\pi$'.format(float(val)/np.pi) if val !=0 else '0')) axs[1].xaxis.set_major_locator(MultipleLocator(base=np.pi/2)) plt.savefig('source/figures/blockDTNP.png') .. figure:: /figures/blockDTNP.png **A DT block function and its DT Fourier Transform.** Observe that the DT Fourier transform has a period of $2\pi$. Furthermore observe that the interval $\W\in[0,\pi]$ characterizes the entire function (for real signals...). These properties are proven in the next subsection. Properties of the DTFT ====================== .. list-table:: :widths: 10 10 :header-rows: 1 :class: tablefullwidth * - Time Domain - Frequency Domain * - Synthesis (Inverse Fourier Transform) .. math:: x[n] = \frac{1}{2\pi} \int_{\langle 2\pi \rangle} X(\Omega) e^{j\Omega n} d\Omega - Analysis (Fourier Transform) .. math:: X(\Omega) = \sum_{n=-\infty}^{\infty} x[n] e^{-j \Omega n} * - Real Signals .. math:: x[n] \in\setR - Symmetry in Fourier transform .. math:: X(-\Omega) = X^\star(\Omega) * - Even Signals .. math:: x[-n] = x[n] - Real Fourier transform .. math:: X(\Omega) \text{ is real} * - Odd Signals .. math:: x[-n] = -x[n] - Imaginary Fourier transform .. math:: X(\Omega) \text{ is imaginary} * - Time Shift .. math:: x[n-n_0] - Phase factor .. math:: e^{-j \W n_0} X(\W) * - Difference .. math:: x[n] - x[n-1] - .. math:: (1-e^{-j \Omega})X(\Omega) * - Convolution .. math:: x[n] \ast y[n] - Multiplication .. math:: X(\Omega) Y(\Omega) * - Multiplication .. math:: x[n] y[n] - Convolution .. math:: \frac{1}{2\pi} X(\w)\ast_{\langle 2\pi\rangle} Y(\Omega) .. rubric:: Real Signals Let $x(t)$ be a real signal then $X(-\Omega)=X^\star(\Omega)$. The proof immediately follows from the definition. .. rubric:: Symmetry Consider the frequency in the range from $\pi$ to $2\pi$. The value of $X(\Omega)$ for these frequencies for real signals is not really neaded due to summetry (periodicity) .. math:: X(2\pi-\Omega) &= \sum_{n=-\infty}^{\infty} x[n]e^{-j (2\pi - \Omega) n}\\ &= \sum_{n=-\infty}^{\infty} x[n]e^{-j 2\pi n}e^{ j\Omega n}\\ Note that $e^{-j2\pi n}=1$ for all $n$. So for a real valued signal $x[n]$ we have: .. math:: X(2\pi-\Omega) &= \sum_{n=-\infty}^{\infty} x[n] e^{j\Omega n}\\ &= X(-\Omega)\\ &= X^\star(\Omega) In summary we only need to consider the $X(\Omega)$ values for $0\leq\Omega<\pi$. .. rubric:: Shift in Time Domain A shift in the time domain corresponds with a phase shift in the frequency domain: .. math:: x[n-n_0] \FTright e^{-j\Omega n_0} X(\Omega) The proof is simple. Take $x[n-n_0]$ into the definition of DTFT: .. math:: \FT(x[n-n_0]) = \sum_{n=-\infty}^{\infty} x[n-n_0] e^{-j\Omega n} substituting $n'=n-n_9$ we get: .. math:: \FT(x[n-n_0]) &= \sum_{n'=-\infty}^{\infty} x[n'] e^{-j\Omega (n'+n_0)}\\ &= \sum_{n'=-\infty}^{\infty} x[n'] e^{-j\Omega n'} e^{-j \Omega n_0}\\ &= e^{-j \Omega n_0} \sum_{n'=-\infty}^{\infty} x[n'] e^{-j\Omega n'}\\ &= e^{-j \Omega n_0} X(\Omega) .. rubric:: Shift in Frequency Domain The dual property of the shift in time domain is the shift in the frequency domain: .. math:: e^{j\Omega_0 n} x[n] \FTright X(\Omega-\Omega_0) The proof is simple, just calculate the Fourier transform of $e^{j\W_0 n}x[n]$ following the definiion. .. rubric:: Convolution in Time Domain Convolution in the time domain corresponds with multiplication in the frequency domain. .. math:: x[n]*y[n] \FTright X(\Omega)Y(\Omega) The proof is straightforward. We have: .. math:: \FT\{x[n]\ast y[n]\} &= \FT\left\{ \sum_{k=-\infty}^{\infty} x[n-k] y[k] \right\}\\ &= \sum_{k=-\infty}^{\infty} \FT\{x[n-k]\} y[k]\\ &= \sum_{k=-\infty}^{\infty} e^{-j\W k} X(\W) y[k]\\ &= X(\W) \sum_{k=-\infty}^{\infty} y[k] e^{-j\W k}\\ &= X(\W) Y(\W) .. rubric:: Multiplication in Time Domain .. math:: x[n] y[n] \FTright \frac{1}{2\pi} X(\Omega)\ast_{\langle 2\pi\rangle} Y(\Omega) .. rubric:: Difference in Time Domain In the discrete time domain we cannot calculate the derivative of a signal $x[n]$ (it can be done only in approximation). De difference operator $y[n]=x[n]-x[n-1]$ is the best we can locally do to estimate the derivative. For the Fourier Transform we have: .. math:: x[n]-x[n-1] \FTright (1-e^{-j\Omega})X(\Omega) Straigtforward use of the linearity of the Fourier transform and one of its properties we get: .. math:: \FT\{x[n]-x[n-1]\} &= \FT\{x[n]\} - \FT\{x[n-1]\}\\ &= X(\W) - e^{-j\W} X(\W)\\ &= (1 - e^{-j\W}) X(\W) Fourier Transform Pairs ======================= As with all Fourier transforms we list some of the important Fourier transform pairs. .. list-table:: :widths: 10 10 :header-rows: 1 :class: tablefullwidth * - Time Domain - Frequency Domain * - Synthesis (Inverse Fourier Transform) .. math:: x[n] = \frac{1}{2\pi} \int_{\langle 2\pi \rangle} X(\Omega) e^{j\Omega n} d\Omega - Analysis (Fourier Transform) .. math:: X(\Omega) = \sum_{n=-\infty}^{\infty} x[n] e^{-j \Omega n} * - Pulse .. math:: x[n]=\delta[n] - Constant .. math:: X(\W) = 1 * - Step .. math:: u[n] = \begin{cases}1 &: n\geq 0\\ 0 &: n<0\end{cases} - .. math:: \frac{1}{1-e^{-j\W}} + \pi\sum_{k=-\infty}^{+\infty} \delta(\W-2k\pi) * - Block .. math:: b_N[n] = \begin{cases}\frac{1}{N} &: 0\leq n < N\\ 0 &:\text{elsewhere}\end{cases} - .. math:: B_N(\W) = \frac{1}{N}\frac{1-e^{-j\W N}}{1-e^{-j\W}} * - Complex Exponential .. math:: e^{j\W_0 n} - .. math:: 2\pi \sum_{k=-\infty}^{\infty} \delta(\W - \W_0 + k 2\pi) .. * - Cosine .. math:: x[n] = \cos(\W n) - .. math:: \unicode{1064} .. rubric:: Step Function The proof for the Fourier transform of the step function is not trivial. There are many video's to be found explaining the proof (where the step function is written as the sum of a constant and a sign function). The constant then gives rise to the pulse function in the Fourier transform. .. rubric:: Block Function The block function $b_N[n]$ as defined in the table above, can be written as the difference of two shifted step functions: .. math:: b_N[n] = \frac{1}{N}\left(u[n] - u[n-N]\right) For the discrete Fourier transform of $b_N$ we can use the transform of the step function and the shifted step function. Another way of calculating the discrete Fourier transform if by writing $b_N$ as the finite sum of shifted pulses and using the sum formula for a geometric sequence (see the chapter on :ref:`Geometric Sequences`). .. rubric:: Complex Exponential The proof for the complex exponential is relatively simple when we substite $X(\W)$ into the synthesis equation and derive the complex exponential function. .. math:: x[n] = \frac{1}{2\pi} \int_{\langle 2\pi\rangle} X(\W)e^{j\W n}d\W Substituting .. math:: X(\W) = 2\pi\sum_{k=-\infty}^{\infty} \delta(\W-\W_0-k2\pi) leads to .. math:: x[n] = \frac{1}{2\pi} \int_{\langle 2\pi\rangle} \left(2\pi\sum_{k=-\infty}^{\infty} \delta(\W-\W_0-k2\pi)\right)e^{j\W n}d\W Due to the integration over only a period of $2\pi$ we can reduce the summation to just the term for $k=0$ and get: .. math:: x[n] &= \int_{\langle 2\pi\rangle} \delta(\W-\W_0) e^{j\W n}d\W\\ &= e^{j\W_0 n} Introducing Time ================ Thusfar we have not used time, a discrete signal $x[n]$ doesn't refer to time. But now let us introduce time in the following way: .. math:: x[n] = x(nT_s) i.e. each value $x[n]$ is the value of the CT signal $x(t)$ at time $t=nT_s$ where $T_s$ is the **sample period**. We have allready seen that the highest frequency corresponding with $\Omega = \pi$ corresponds with a block wave (square wave) with period $2T_s$ and thus with frequency $1/(2T_s)$. So we can link the radial frequency $\Omega$ with the time domain frequency $f$: .. math:: f = \frac{\Omega}{2\pi T_s} The radial frequency we know from CT systems is $\w = 2\pi f$ and thus .. math:: \w = \frac{\Omega}{T_s} Note that you should only use these for $0\leq\Omega\leq\pi$. Exercises ========= #. Fourier Transform Given the signal: .. math:: x[n] = \begin{cases} 1 &: n=-1\\ -1 &: n=0\\ 1 &: n=1\\ 0 &: \text{elsewhere} \end{cases} #. Calculate the Fourier transform $X(\Omega)$ #. Plot the frequency spectrum $X(\Omega)$ #. Convolution Given two Fourier transforms: .. math:: X_1(\Omega) &= 1 + 2 e^{-j\Omega} + 4 e^{-j 2\Omega}\\ X_2(\Omega) &= 2 + e^{-j\Omega} #. Give $x_1[n]$ and $x_2[n]$ #. Calculate the convolution of $y[n] = x_1[n] \ast x_2[n]$ #. Calculate $Y(\Omega)$ from the result above (i.e. using $y[n]$). #. Calculate $Y(\Omega)$ using the convolution property. #. Zero Response Consider the discrete convolution kernel function .. math:: h[n] = \frac{1}{7} \begin{cases} 1 &: |n|\leq 3\\ 0 &: \text{elsewhere} \end{cases} and the signal $x[n]$: .. math:: x[n] = \sin(\W_0 n) #. Calculate the DTFT $H(\W)$ of $h[n]$. #. Calculate the DTFT $X(\W)$ of $x[n]$. #. For which values of $\W_0$ is the response zero, i.e. $\forall n:\; x[n]\ast h[n] = 0$.