\documentstyle{article}

\pagestyle{empty}
\thispagestyle{empty}
\begin{document}


\begin{center}
{\bf EECS 225d: Audio Signal Processing by Humans and Machines} \\
\vspace{0.6cm}

\begin{Large}
{\bf Problem Set 2} \\
{\bf Due in class Fri Feb 14, 1997} \\
\end{Large}

\end{center}

\vspace {0.1cm}

{\sc Reading:} Chapters 6-7

\hspace{0.2in} (Oppenheim and Schafer provide an alternate discussion of the 
FFT.)

\vspace {0.2cm}

\begin{enumerate}
\item
Consider the following equation which defines the output $y[n]$ of a 
linear-time invariant system in terms of its input $x[n]$:

$y[n] = y[n-1] + x[n] - x[n-N]$ \hspace{1cm} with \hspace{2ex} $y[-1] = 0$

\begin{enumerate}
\item
Is the equation recursive or non-recursive?

\item
Is the LTI system defined by the equation FIR or IIR?

\item
If the input $x[n] = \delta [n]$, plot $y[n]$ from $n = 0 .. \infty$. \\
($\delta[n]$ is the unit impulse function:
$\delta[0] = 1$ and $\delta[n \neq 0] = 0$)
\end{enumerate}

\item
Find the z-transform of the sequence $x[n-2]$ in terms of $X(z)$, the
z-transform of $x[n]$, where $x[-1]=A$ and $x[-2]=B$.

\item
Given the mapping $s = \frac{z-1}{z+1}$:
\begin{enumerate}
\item What region of the z-plane corresponds to the left half of the s-plane?  
\item What region corresponds to the right half of the s-plane?  
\item What region corresponds to the y axis of the s-plane?  
\end{enumerate}

\item Chapter 6, Exercise 3

\item Chapter 6, Exercise 4

\item Chapter 6, Exercise 5

\item Chapter 6, Exercise 8

\item
Convolve the sequence $\{6, 5\}$ with the sequence $\{7, 2, -4\}$:  
\begin{enumerate}
\item First, do a straightforward linear convolution.  
\item Next, obtain the same result by suitable zero augmentation, then
	computing the DFT of both sequences, and finally computing the IDFT
	of the product.
\end{enumerate}

\item Why might radix-2 and radix-4 transforms be efficient but other radix
transforms such as 3, 5, or 8 be less efficient?  (This will help in 
subsequent problems.  The {\it radix} of an fixed radix FFT can be thought of 
as the lowest level of recursion in the transform definition.)

\item Chapter 7, Exercise 4

{\it Notes:} In the text's explanation, the number of rows, L, is the radix
of the transform (2 in our case).  Thus since the number of elements in the 
original transform is $N$, the number of columns, M, would be $\frac{N}{2}$.

Additionally, most trivial multiplications are not counted.  (Strictly 
speaking, fewer than $\frac{N}{2}(\log_2{N}-1)$ non-trivial complex multiplies
are required.  Why is that?)  

Lastly, figure 7.12 does not exactly reflect
the text's algorithm in that it shows some terms being the sum of one term
multiplied by $W^{SomeNumber}$ and another term multiplied by 
$-W^{SameNumber}$, thus involving two multiplies.  The algorithm on pages
121-122 instead subtracts one term from the other (via DFT$_2$) and multiplies
the difference by $W^{TheNumber}$, requiring only 1 complex multiply.  This 
will yield the correct result as well as the correct number of multiplies for
this problem.  

\item Chapter 7, Exercise 5

Again, don't count trivial multiplications.  

\item What is the most efficient way to compute a 30 point FFT?
What is the most efficient way to compute the FFT of a 32-point sequence using
a mixed radix transform?  How about using a constant radix transform? 

\item Chapter 7, Exercise 8

\end{enumerate}
\end{document}

