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 ) \)
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}}\]
Answer:
\[ 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
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.
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
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
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.