4.8 HW7, April 14 ,2010

  4.8.1 Problem 1
  4.8.2 Problem 2 (3.18 in text book, page 125)
  4.8.3 Problem 3 (problem 3.25 in textbook, page 130)
  4.8.4 key solution
PDF (letter size)
PDF (legal size)

4.8.1 Problem 1

Given an \(N\) point sequence \(h\left ( n\right ) \), let \(H\left ( z\right ) =Z\left ( h\left ( n\right ) \right ) \) and \(H\left ( k\right ) =DFT\left ( h\left ( n\right ) \right ) \)

1.
Find \(H\left ( z\right ) \) in terms of \(H\left ( k\right ) \)
2.
For \(z\) on the unit circle (\(z=e^{j\omega },\omega \in \left [ 0,2\pi \right ] \)), compute result in (1) using equation (d) in D-5 using \(\beta =1,\Omega =\frac{\omega N}{2\pi }\)

Solution: Part (1)\begin{equation} H\left ( z\right ) ={\sum \limits _{n=0}^{N-1}}h\left ( n\right ) z^{-n}\tag{1} \end{equation} and\begin{align} H\left ( k\right ) & ={\sum \limits _{n=0}^{N-1}}h\left ( n\right ) W_{N}^{nk}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k=0\cdots N-1\nonumber \\ & ={\sum \limits _{n=0}^{N-1}}h\left ( n\right ) e^{-j\frac{2\pi }{N}nk}\tag{2} \end{align}

Compare (1) and (2) we see that\[ H\left ( k\right ) =\left . H\left ( z\right ) \right \vert _{z=e^{j\frac{2\pi }{N}k}}\]

4.8.2 Problem 2 (3.18 in text book, page 125)

   4.8.2.1 First solution
   4.8.2.2 second solution

pict

Answer:

4.8.2.1 First solution

\[ y\left ( n\right ) =\left \{ \begin{array} [c]{cc}x\left ( \frac{n}{2}\right ) & n\ even\\ 0 & n\ odd \end{array} \right . \] We are asked to D-5 in handout E. Using equation (c) in the D-5 handout, let \(\beta =2,\) using equation (c) we obtain\[ Y_{N}\left ( k\right ) =X_{M}\left ( k\ \operatorname{mod}\ M\right ) \] In this case \(N=16\) and \(M=8\),  Hence\[ Y_{16}\left ( k\right ) =X_{8}\left ( \left ( k\right ) \right ) _{8}\] Hence based on the above, we select \(Y\left ( k\right ) \) as the one shown in diagram (c) in the book on page 126

4.8.2.2 second solution

This solution is longer, but this is how I first solved the problem, before using the above method. Start by writing \(y\left ( n\right ) \) in terms of \(x\left ( n\right ) \)\begin{align} y_{n} & =\left \{ y_{0},y_{1},y_{2},\cdots ,y_{15}\right \} \nonumber \\ & =\left \{ x_{0},0,x_{1},0,x_{2},0,x_{3},\cdots ,x_{7},0\right \} \tag{1} \end{align}

Now\begin{align*} Y\left ( k\right ) & ={\sum \limits _{n=0}^{15}}y\left ( n\right ) W_{16}^{nk}\hspace{20pt}k=0\cdots 15\\ & =y_{0}+y_{1}W_{16}^{k}+y_{2}W_{16}^{2k}+\cdots +y_{15}W_{16}^{15k} \end{align*}

But odd values of \(y\) are zero, so the above becomes (using (1))\begin{align*} Y\left ( k\right ) & =x_{0}+0+x_{1}W_{16}^{2k}+0+x_{2}W_{16}^{4k}+\cdots +x_{7}W_{16}^{14k}+0\\ & =x_{0}+x_{1}W_{16}^{2k}+x_{2}W_{16}^{4k}+\cdots +x_{7}W_{16}^{14k}\hspace{20pt}k=0\cdots 15 \end{align*}

We can simplify \(W_{16}^{nk}\) above by dividing by 2 to obtain \(W_{8}^{\frac{n}{2}k}\), so the above becomes\begin{equation} Y\left ( k\right ) =x_{0}+x_{1}W_{8}^{k}+x_{2}W_{8}^{2k}+\cdots +x_{7}W_{8}^{7k}\hspace{20pt}k=0\cdots 15\tag{2} \end{equation} But if we compare the above to \(X\left ( k\right ) \), which is\begin{equation} X\left ( k\right ) =x_{0}+x_{1}W_{8}^{k}+x_{2}W_{8}^{2k}+\cdots +x_{7}W_{8}^{7k}\hspace{20pt}k=0\cdots 7\tag{3} \end{equation} We see that \(Y\left ( k\right ) =X\left ( k\right ) \) at least for the range of \(k=0\cdots 7\). So now let us look at the second half of values, i.e. for \(k=8\cdots 15\). If we write down few terms we see\begin{align*} Y(8) & =x_{0}+x_{1}W_{8}^{8}+x_{2}W_{8}^{2\times 8}+\cdots +x_{7}W_{8}^{7\times 8}\\ & =x_{0}+x_{1}W+x_{2}W^{2}+\cdots +x_{7}W^{7}\\ & =x_{0}=X(0) \end{align*}

and \begin{align*} Y(9) & =x_{0}+x_{1}W_{8}^{9}+x_{2}W_{8}^{2\times 9}+\cdots +x_{7}W_{8}^{7\times 9}\\ & =x_{0}+x_{1}W_{8}^{9}+x_{2}W_{8}^{18}+\cdots +x_{7}W_{8}^{63}\\ & =x_{0}+x_{1}W_{8}^{1}+x_{2}W_{8}^{2}+\cdots +x_{7}W_{8}^{7}\\ & =X(1) \end{align*}

and so on. i.e. by taking advantage of the relation that \(W_{N}^{M}=W_{N}^{\left ( \left ( M\right ) \right ) _{N}}\), where \(\left ( \left ( M\right ) \right ) _{N}\) means \(M\) module \(N\), ie. the reminder when \(M\) is divided by \(N\), we see that the second half of \(Y\left ( k\right ) \) also is the same as \(X\left ( k\right ) \). Hence the correct result is the one shown in diagram (c) in the book.

4.8.3 Problem 3 (problem 3.25 in textbook, page 130)

pict

We know that \[ DFT\left ( x\left ( n\right ) \right ) =X_{N}\left ( k\right ) ={\displaystyle \sum \limits _{n=0}^{N-1}} x\left ( n\right ) W_{N}^{nk}=\left . Z\left ( x\left ( n\right ) \right ) \right \vert _{z=W_{N}^{k}}\] So, to find the DFT of \(x\left ( n\right ) \) at some specific \(k\) value, instead of performing the sum above over the length of \(x\left ( n\right ) \), we can just evaluate \(Z\) transform of \(x\left ( n\right ) \) at just one point, \(z=W_{N}^{k}\). So the sum operation is replaced by one evaluation operation (sampling) of the \(Z\) transform. So the idea is to compute the \(Z\) transform once, and then evaluate it at specific locations on the unit circle to obtain specific values of the DFT. I start by ilustrating the relation above on a diagram

pict

Now, each point in the DFT space is found by performin the sum over \(N\) points in the sequence \(x\left ( n\right ) \). (i.e the DFT calculation). Here is another diagram to illustrate

pict

Now, we are asked to find \(M\) samples (equally spaced) in the Z space by using only M samples from \(x\left ( n\right ) \), which is of length \(N\). So we need to pick some values of \(x\) (M of them) and use them to find \(M\) samples in Z space. How to find these \(M\) values of \(x?\) Looking at the DFT sum itself\[ X_{N}\left ( k\right ) ={\sum \limits _{n=0}^{N-1}}x\left ( n\right ) W_{N}^{nk}\] Break this into sums of \(M\) elements at a time (since \(M<N\)). Last segment can be less than \(M\) points if \(M\) do not divide \(N\) exactly.\[ X_{N}\left ( k\right ) ={\sum \limits _{n=0}^{M-1}}x\left ( n\right ) W_{N}^{nk}+{\sum \limits _{n=M}^{2M-1}}x\left ( n\right ) W_{N}^{nk}+{\displaystyle \sum \limits _{n=2M}^{3M-1}} x\left ( n\right ) W_{N}^{nk}\cdots +{\displaystyle \sum \limits _{n=\beta M}^{(\beta +1)M-1}} x\left ( n\right ) W_{N}^{nk}\] Where in the above, we assumed \(N=\beta M\) QED.

4.8.4 key solution

PDF