Page MenuHomec4science
Files F104911038

sol02.tex
No OneTemporary
Actions

File Metadata

Created
Thu, Mar 13, 07:37

sol02.tex
View Options

\documentclass[12pt,a4paper,fleqn]{article}
\usepackage{../styles/defsDSPcourse}
\title{COM-303 - Signal Processing for Communications}
\author{Solutions for Homework \#2}
\date{}
\begin{document}
\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{Bases}
Suppose by contradiction that the vector $\mathbf{z}\in S$ admits two distinct representations in the basis $\{\mathbf{x}^{(k)}\}_{k=0,\ldots,N-1}$. In other words, suppose that there exist two set of scalars $\alpha_0,\ldots,\alpha_{N-1}$ and $\beta_0,\ldots,\beta_{N-1}$, with $\alpha_i \neq \beta_i$ for all $i$, such that
\[
\mathbf{z}=\sum_{k=0}^{N-1}\alpha_k\mathbf{x}^{(k)}
\]
and
\[
\mathbf{z}=\sum_{k=0}^{N-1}\beta_k\mathbf{x}^{(k)}.
\]
In this case we can write
\[
\sum_{k=0}^{N-1}\alpha_k\mathbf{x}^{(k)}=\sum_{k=0}^{N-1}\beta_k\mathbf{x}^{(k)}
\]
or, equivalently,
\[
\sum_{k=0}^{N-1}(\alpha_k-\beta_k)\mathbf{x}^{(k)}=0.
\]
The above expression is a linear combination of basis vectors that is equal to zero. Because of the linear independence of a set of basis vector, the only set of coefficients that satisfies the above equation is a set of null coefficients so that it must be $\alpha_i \neq \beta_i$ for all $i$, in contradiction with the hypothesis.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{Plancherel-Parseval Equality}
\begin{enumerate}
\item We expand the sum of the multiplication of DFTs $X[k]$ and $Y[k]$, that is,
\begin{align*}
\sum_{k=0}^{N-1} (X[k] Y^*[k]) & = \sum_{k=0}^{N-1} \left(\sum_{n=0}^{N-1} x[n] e^{-j2\pi n k/N} \right) \left(\sum_{m=0}^{N-1} y[m] e^{-j2\pi m k/N} \right)^*\\
&= \sum_{n=0}^{N-1} \sum_{m=0}^{N-1} x[n] y^*[m] \sum_{k=0}^{N-1} e^{-j2\pi (n-m) k/N}.
\end{align*}
Since
\[
\sum_{k=0}^{N-1} e^{-j2\pi (n-m) k/N} = \begin{cases}
0 & m\neq n\\
N & m= n,
\end{cases}
\]
the result is proved.
\item Note that, if we consider signals as vectors in $\mathbb{C}^N$, the formula is just the inner product between the vectors. If $x[n]=y[n]$, then $\langle x[n], x[n]\rangle$ corresponds to the energy of the signal in the time domain while $\langle X[k], X[k]\rangle /N$ corresponds to the energy of the signal in the frequency domain. In this case, the Plancherel-Parseval equality illustrates the energy conservation property from the time domain to the frequency domain. This property is also known as the \emph{Parseval theorem}. Note that, because we choose not to normalize the Fourier basis vectors, the energy is conserved up to a scaling factor $N$.
\end{enumerate}
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{DFT of elementary functions}
We have:
\begin{eqnarray*}
x[n] & = & \frac{e^{j\phi}}{2}e^{j(2\pi/N)Ln} + \frac{e^{-j\phi}}{2}e^{-j(2\pi/N)Ln} \\
& = & \frac{e^{j\phi}}{2}e^{j(2\pi/N)Ln} + \frac{e^{-j\phi}}{2}e^{-j(2\pi/N)Ln}e^{j(2\pi/N)Nn} \\
& = & \frac{e^{j\phi}}{2}e^{j(2\pi/N)Ln} +
\frac{e^{-j\phi}}{2}e^{j(2\pi/N)(N-L)n}.
\end{eqnarray*}
Therefore, we can write in vector notation:
\[
\mathbf{x} = \frac{e^{j\phi}}{2} \mathbf{w}^{(L)} + \frac{e^{-j\phi}}{2}
\mathbf{w}^{(N-L)},
\]
and the result follows from the linearity of the expansion formula:
\begin{eqnarray*}
X[k] & = & \langle \mathbf{w}^{(k)},\; \mathbf{x} \rangle \\
& = & \left\langle \mathbf{w}^{(k)},\; \frac{e^{j\phi}}{2}\mathbf{w}^{(L)} + \frac{e^{-j\phi}}{2}\mathbf{w}^{(N-L)} \right\rangle
= \frac{e^{j\phi}}{2} \langle \mathbf{w}^{(k)},\; \mathbf{w}^{(L)}
\rangle + \frac{e^{-j\phi}}{2} \langle \mathbf{w}^{(k)},\; \mathbf{w}^{(N-L)}
\rangle
\end{eqnarray*}
Now, if $L \neq N - L$, we have:
\begin{eqnarray*}
X[k] & = & \left\{ \begin{array}{ll} \frac{N}{2}e^{j\phi} & \textrm{if } k=L\\
\frac{N}{2}e^{-j\phi} & \textrm{if } k=N-L
\\ 0 & \textrm{otherwise.} \end{array}\right.
\end{eqnarray*}
Otherwise, if $L = N - L$, we have:
\begin{eqnarray*}
X[k] & = & \left\{ \begin{array}{ll} \frac{N}{2}e^{j\phi} +
\frac{N}{2}e^{-j\phi} & \textrm{if } k=L = N - L\\
0 & \textrm{otherwise.} \end{array}\right.
\end{eqnarray*}
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{DFT Example}
By simple visual inspection we can determine that
\begin{eqnarray*}
a[n] & = & 2 \\
b[n] & = & 3\cos(3(2\pi/64)n) \\
c[n] & = & \sin(7(2\pi/64)n) = - \cos(7(2\pi/64)n+\pi/2).
\end{eqnarray*}
The DFT coefficients are $X[k] = A[k] + B[k] + C[k]$, with
\begin{eqnarray*}
A[k] & = & 2N\delta[k] \\
B[k] & = & (3N/2)\delta[k-3] + (3N/2)\delta[k-61] \\
C[k] & = & -(jN/2)\delta[k-7] + (jN/2)\delta[k-57]
\end{eqnarray*}
and $N = 64$, so that in the end we have
\begin{eqnarray*}
X[0] & = & 128 \\
X[3] & = & 96 \\
X[7] & = & -32j \\
X[57] & = & 32j \\
X[61] & = & 96
\end{eqnarray*}
and $X[k] = 0$ for all the other values of $k$.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{DFT computation}
There are many ways to solve this problem. A simple method is to observe that we can write $\mathbf{x = a + b}$ with
\begin{align*}
\mathbf{a} &= \begin{bmatrix} -1 & 0 & 1 & 0 & -1 & 0 & 1 & 0 \end{bmatrix}^T \\
\mathbf{b} &= \begin{bmatrix} 0 & -1 & 0 & 1 & 0 & -1 & 0 & 1 \end{bmatrix}^T
\end{align*}
which, in signal notation, corresponds to
\begin{align*}
a[n] &= \sin((2\pi/8)2n - \pi/2)\\
b[n] &= \cos((2\pi/8)2n + \pi/2)
\end{align*}
Using the result from the previous exercise we have
\[
A[k] = \begin{cases}
-4j e^{j\pi/2} = -4 & k=2 \\
4j e^{-j\pi/2} = -4 & k=6
\end{cases}
\]
and
\[
B[k] = \begin{cases}
4 e^{j\pi/2} = 4j & k=2 \\
4 e^{-j\pi/2} = -4j & k=6
\end{cases}
\]
so that
\[
\mathbf{X} = \begin{bmatrix} 0 & 4(-1+j) & 0 & 0 & 0 & 0 & 4(-1-j) & 0 \end{bmatrix}^T
\]
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{Structure of DFT formulas}
Let $f[n] = \mbox{DFT}\{x[n]\}$. We have:
\begin{eqnarray*}
y[n] & = & \sum_{k=0}^{N-1} f[k]e^{-j\frac{2\pi}{N}nk} \\
& = & \sum_{k=0}^{N-1} \biggr\{ \sum_{i=0}^{N-1} x[i]e^{-j\frac{2\pi}{N}ik} \biggl\} e^{-j\frac{2\pi}{N}nk} \\
& = & \sum_{i=0}^{N-1} x[i] \sum_{k=0}^{N-1} e^{-j\frac{2\pi}{N}(i+n)k}.
\end{eqnarray*}
Now,
\[
\sum_{k=0}^{N-1} e^{-j\frac{2\pi}{N}(i+n)k} = \left\{
\begin{array}{ll}
N & \mbox{for } (i+n) = 0, N, 2N, 3N, \ldots \\
0 & \mbox{otherwise}
\end{array}
\right. = N\delta[(i+n) \mod N]
\]
so that
\begin{eqnarray*}
y[n] & = & \sum_{i=0}^{N-1}x[i]N\delta[(i+n) \mod N]\\
& = & \left\{
\begin{array}{ll}
Nx[0] & \mbox{for } n = 0\\
Nx[N-n] & \mbox{otherwise}.
\end{array}
\right.
\end{eqnarray*}
In other words, if $\mathbf{x}=[1\; 2\; 3\; 4\; 5]^T$ then $\mbox{DFT}\{\mbox{DFT}\{\mathbf{x}\}\} = 5[1\; 5\; 4\; 3\; 2]^T = [5\; 25\; 20\; 15\; 10]^T$.
\end{solution}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{solution}{Signal repetitions}
Consider the auxiliary signal
\[
\mathbf{y} = [x[0] \quad 0 \quad x[1] \quad 0 \quad x[2] \quad 0 \quad \ldots \quad x[N-1] \quad 0]^T
\]
whose DFT coefficients are (for $k = 0, 1, \ldots, 2N-1$):
\begin{align*}
Y[k] &= \sum_{n=0}^{2N-1} y[n]e^{-j\frac{2\pi}{2N}nk} \\
&= \sum_{n=0}^{N-1} x[n]e^{-j\frac{2\pi}{2N}2nk} \\
&= X[k]
\end{align*}
The signal $\mathbf{x_2}$ is the sum of $\mathbf{y}$ and of $\mathbf{y}$ circularly shifted by one. Since the circular shift in time corresponds to multiplication by a phase term $e^{-j\frac{2\pi}{2N}k}$ in frequency, we have
\[
X_2[k] = (1+e^{-j\frac{2\pi}{2N}k})X[k]
\]
\end{solution}
%\begin{solution}{DFT \& Matlab}
%\begin{enumerate}
%
%\item The signal after DFT should only have two peaks, which corresponds the $21$-st DFT coefficient and the $107$-th DFT coefficient.
%
%\item
%The spectrum of the signal $x[n]$, for both frequencies, is given
%in the following figure that is obtained using the Matlab commands
%given below.
%\begin{verbatim}
% >> N=128;fo1=21/128;fo2=21/127;
% >> n=0:N-1;
% >> x1=cos(2*pi*fo1*n);x2=cos(2*pi*fo2*n);
% >> X1=fft(x1);X2=fft(x2);
% >> subplot(223),stem(n-N/2,fftshift(abs(X1)))
% >> subplot(224),stem(n-N/2,fftshift(abs(X2)))
%\end{verbatim}
%\begin{center}
%\includegraphics[width=12cm,height=4cm]{ex5.eps}
%\end{center}
%Since we take the cosine wave example, we expect to see just one
%sample at the frequency of the signal. This is the case in the
%left figure, where we have the DFT signal spectrum for the signal
%with $f_0=21/128$, and the $21$st DFT coefficient represents the
%exact signal frequency. However, in the right figure, the
%frequency of the signal $f_0=21/127$ does not coincide with any
%DFT frequency component. The signal energy is spread over each of
%the DFT components. This is called frequency leakage. Therefore,
%we can conclude that if the signal period exactly fits the
%measurement time (number of samples), the frequency spectrum is
%correct, while if the period does not match the measurement time,
%the frequency spectrum is incorrect - it is broadened.
%
%\item
%We can achieve the same results using the \textit{dftmtx} function instead, as
%illustrated below.
%\begin{verbatim}
% >> W=dftmtx(N);
% >> X3=W*x1;X4=W*x2;
% >> norm(X1-X3)
% >> norm(X2-X4)
% >> subplot(223),stem(n-N/2,fftshift(abs(X3)))
% >> subplot(224),stem(n-N/2,fftshift(abs(X4)))
%\end{verbatim}
%In practice, however, the discrete Fourier transform is computed more
%efficiently and uses less memory with an FFT algorithm than by using the Fourier transform matrix.
%\end{enumerate}
%\end{solution}
\end{document}

Event Timeline

c4science · Help