Page MenuHomec4science
Files F105172902

sol03.tex
No OneTemporary
Actions

File Metadata

Created
Sat, Mar 15, 04:21

sol03.tex
View Options

\documentclass[12pt,a4paper,fleqn]{article}
\usepackage{../styles/defsDSPcourse}
\title{COM-303 - Signal Processing for Communications}
\author{Solutions for Homework \#3}
\date{}
\begin{document}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{DFT in matrix form}
Recall the DFT (analysis) formula:
\begin{align*}
X[k] &= \sum_{n=0}^{N-1} x[n] W_N^{nk}.
\end{align*}
We can define an $N \times N$ square matrix $\textbf{W}$ by stacking the conjugates of the basis vectors $\{\textbf{w}^{(k)}\}_{k = 0,\ldots,N-1}$:
\begin{align*}
\textbf{W} &= \begin{bmatrix}
\textbf{w}^{*(0)}\\
\textbf{w}^{*(1)}\\
\textbf{w}^{*(2)}\\
\ldots\\
\textbf{w}^{*(N-1)}\\
\end{bmatrix}
\end{align*}
and get the analysis formula in matrix - vector multiplication form:
\begin{align*}
\textbf{X} &= \textbf{W} \textbf{x}.
\end{align*}
Then, knowing that:
\begin{align*}
\textbf{W} \textbf{W}^H = \textbf{W}^{H} \textbf{W} = N\textbf{I}
\end{align*}
we obtain the synthesis formula in matrix-vector multiplication form:
\begin{align*}
\textbf{x}&= \frac{1}{N} \textbf{W}^H \textbf{X}.
\end{align*}
A matrix $\textbf{A}$ is hermitian when
\begin{eqnarray*}
\textbf{A} = \textbf{A}^H
\end{eqnarray*}
Therefore, for $\textbf{W}$ to be hermitian, we would need:
\begin{eqnarray*}
\textbf{W}_{nk} = \textbf{W}_{kn}^*
\end{eqnarray*}
for all $n, k \in \{ 0, 1,\ldots N-1 \}$. This translates to having:
\begin{eqnarray*}
e^{-j \frac{2 \pi}{N} nk} = e^{j \frac{2 \pi}{N} kn}.
\end{eqnarray*}
for all $n, k \in \{ 0, 1,\ldots N-1 \}$, which is generally not the case.\\
Consider, for example, the case when $n = k = 1$. We would need to have:
\begin{eqnarray*}
e^{-j \frac{2 \pi}{N}} = e^{j \frac{2 \pi}{N}}
\end{eqnarray*}
which is equivalent to:
\begin{eqnarray*}
e^{j \frac{4 \pi}{N}} = 1.
\end{eqnarray*}
Clearly, this can only happen when $N=2$.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{Derivative in frequency}
\begin{enumerate}
\item There are two ways to solve this problem. You can either replace $X(e^{j\omega})$ by its iDTFT expansion and then take the derivative to obtain:
\[
j\frac{d}{d\omega} X(e^{j\omega})=j\frac{d}{d\omega}[\sum_n x(n)e^{-j\omega n}]=j\sum_n x(n) \frac{d}{d\omega} e^{-j\omega n}=\sum_n nx(n)e^{-j\omega n}
\]
so that $\text{iDTFT}\left\{j\frac{d}{d\omega} X(e^{j\omega})\right\}=nx(n)$.
Alternatively, you can first take the IDTFT and then use integration by part:
\begin{align*}
&
\frac{1}{2\pi} \int_{-\pi}^{\pi} j\frac{d}{d\omega} X(e^{j\omega}) e^{j\omega n}\,d\omega \\
&=\frac{j}{2\pi}X(e^{j\omega})e^{j\omega n} \Big|_{-\pi}^{\pi} - \frac{j}{2\pi}\int_{-\pi}^\pi X(e^{j\omega}) (j n e^{j\omega n})\, d\omega \\
&= n \frac{1}{2\pi}\int_{-\pi}^\pi X(e^{j\omega}) e^{j\omega n}\, d\omega = n x[n]
\end{align*}
where the first equality uses integration by part and the second the periodicity of $X(e^{j\omega})e^{j\omega n}$.
\item Because of linearity, the inverse DTFT will be equal to $\pi/j$ times the result in previous question minus the inverse DTFT of the constant $2$, which easily enough is $2\delta[n]$.
\end{enumerate}
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{DTFT visual inspection}
\begin{enumerate}
\item From the plots one can see that $X(e^{j\omega})$ is 0 at the origin;
\[
X^*(e^{-j \omega})|_{\omega=0} = \sum_{n\in\mathbb Z} x[n] = 0
\]
so $x[n]$ is 0-mean.
\item From the plots one can see that the real part of $X(e^{j\omega})$ is symmetric at the origin, and its imaginary part is antisymmetric. Since
\[
x^*[n] \leftrightarrow X^*(e^{-j \omega})
\]
Then
\[
X^*(e^{-j \omega})=\Re\left(X\left(e^{-j \omega}\right)\right)-j\Im\left(X\left(e^{-j \omega}\right)\right)=\Re\left(X\left(e^{j \omega}\right)\right)+j\Im\left(X\left(e^{j \omega}\right)\right)=X\left(e^{j \omega}\right)
\]
Therefore, $x[n]=x^*[n]$.
\end{enumerate}
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{DTFT properties}
\begin{enumerate}
\item time reversal:
\[
\sum_{n=-\infty}^{\infty} x[-n] e ^{-j \omega n} = \sum_{m=-\infty}^{\infty} x[m] e ^{j \omega m} = \sum_{m=-\infty}^{\infty} x[m] e ^{-j (-\omega) m} = X(e^{-j \omega})
\]
with the change of variable $m = -n$. Therefore the DTFT of the time-reversed sequence $x[-n]$ is $X(e^{-j \omega})$
\item time shift:
\[
\sum_{n=-\infty}^{\infty} x[n - n_0] e ^{-j \omega n} =
\sum_{m=-\infty}^{\infty} x[m] e^{-j \omega (m + n_0)} = e^{-j \omega n_0}
\sum_{m=-\infty}^{\infty} x[m] e^{-j \omega m} = e^{-j \omega n_0} X(e ^ {j
\omega})
\]
with the change of variable $m = n - n_0.$ Therefore the DTFT of the time-shifted sequence $x[n - n_0]$ is $e^{-j \omega n_0} X(e^{j \omega})$
\end{enumerate}
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{Plancherel-Parseval Equality}
\begin{enumerate}
\item The inner product in $l_2(\mathbb{Z})$ is defined as
\[
\langle x[n],y[n]\rangle = \Sigma_n x^*[n]y[n],
\]
and in $L_2([-\pi,\pi])$ as
\[
\langle X(e^{jw}),Y(e^{jw})\rangle = \int_{-\pi}^{\pi}X^*(e^{jw})Y(e^{jw})dw.
\]
Thus,
\begin{align*}
\frac{1}{2\pi}\int_{-\pi}^{\pi}X^*(e^{jw})Y(e^{jw})dw &= \frac{1}{2\pi}\int_{-\pi}^{\pi}\left(\Sigma_n x[n]e^{-jwn}\right)^*\Sigma_m y[m]e^{-jwm}dw \\
&\stackrel{(1)}{=} \frac{1}{2\pi}\int_{-\pi}^{\pi}\Sigma_n x^*[n]e^{jwn}\Sigma_m y[m]e^{-jwm}dw \\
&= \frac{1}{2\pi}\int_{-\pi}^{\pi}\Sigma_n\Sigma_m x^*[n]y[m]e^{jw(n-m)}dw \\
&\stackrel{(2)}{=} \frac{1}{2\pi}\Sigma_n\Sigma_m x^*[n]y[m]\int_{-\pi}^{\pi}e^{jw(n-m)}dw \\
&\stackrel{(3)}{=} \Sigma_n x^*[n]y[n],
\end{align*}
where (1) follows from the properties of the complex conjugate, (2) follows from swapping the integral and the sums and (3) fromthe fact that
\begin{align*}
\frac{1}{2\pi}\int_{-\pi}^{\pi}e^{jw(n-m)}dw &= \left\{
\begin{array}{ll}
1 & \mbox{if $m=n$} \\
0 & \mbox{if $m\neq n$}.
\end{array}
\right.
\end{align*}
\item If $x[n]=y[n]$, then $\langle x[n],x[n]\rangle$ corresponds to the energy of the signal in the time domain and $\langle X(e^{jw}),X(e^{jw})\rangle$ to the energy of the signal in the frequency domain. In this case, the Plancherel-Parseval equality illustrates an energy conservation property from the time domain to the frequency domain. This property is known as the \emph{Parseval theorem}.
\end{enumerate}
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{DTFT,DFT, and numerical computations}
The analytical expression for the DTFT of the signal is
\[
X(e^{j\omega}) = \frac{\sin((M/2)\omega)}{\sin(\omega/2)}e^{j\frac{N-1}{2}\omega}
\]
so that the magnitude can be easily plotted by any numerical package. Here is a Python Notebook code snippet that provides the analysis requested by the exercise:
\small
\begin{verbatim}
%pylab inline
import matplotlib
import matplotlib.pyplot as plt
import numpy as np
M = 20
# plot the analytic DTFT over 10,000 points
w = np.linspace(-np.pi, np.pi, 10000)
X = np.abs(np.sin((M / 2.0) * w) / np.sin(w / 2.0))
plt.plot(w, X);
plt.xlim([-np.pi, np.pi]) # fit the x-axis
plt.show();
# now compute the FFT-based approximations
N = [30, 50, 100, 1000]
for pts in N:
# build the signal
x = np.zeros(pts)
x[0:M] = 1
# compute the DFT and shift it to align it with the DTFT
X_a = np.fft.fftshift(np.fft.fft(x))
plt.plot(np.abs(X_a))
plt.show()
\end{verbatim}
\end{solution}
\end{document}

Event Timeline

c4science · Help