EECS 225d: Audio Signal Processing by Humans and Machines
Problem Set 2
Due in class Fri Feb 14, 1997

READING: Chapters 6-7

(Oppenheim and Schafer provide an alternate discussion of the FFT.)

  1. 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] with y[-1] = 0

    1. Is the equation recursive or non-recursive?
    2. Is the LTI system defined by the equation FIR or IIR?
    3. If the input tex2html_wrap_inline48 , plot y[n] from tex2html_wrap_inline52 .
      ( tex2html_wrap_inline54 is the unit impulse function: tex2html_wrap_inline56 and tex2html_wrap_inline58 )
  2. 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.
  3. Given the mapping tex2html_wrap_inline70 :
    1. What region of the z-plane corresponds to the left half of the s-plane?
    2. What region corresponds to the right half of the s-plane?
    3. What region corresponds to the y axis of the s-plane?
  4. Chapter 6, Exercise 3
  5. Chapter 6, Exercise 4
  6. Chapter 6, Exercise 5
  7. Chapter 6, Exercise 8
  8. Convolve the sequence tex2html_wrap_inline72 with the sequence tex2html_wrap_inline74 :
    1. First, do a straightforward linear convolution.
    2. Next, obtain the same result by suitable zero augmentation, then computing the DFT of both sequences, and finally computing the IDFT of the product.
  9. 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 radix of an fixed radix FFT can be thought of as the lowest level of recursion in the transform definition.)
  10. Chapter 7, Exercise 4

    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 tex2html_wrap_inline78 .

    Additionally, most trivial multiplications are not counted. (Strictly speaking, fewer than tex2html_wrap_inline80 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 tex2html_wrap_inline82 and another term multiplied by tex2html_wrap_inline84 , thus involving two multiplies. The algorithm on pages 121-122 instead subtracts one term from the other (via DFT tex2html_wrap_inline86 ) and multiplies the difference by tex2html_wrap_inline88 , requiring only 1 complex multiply. This will yield the correct result as well as the correct number of multiplies for this problem.

  11. Chapter 7, Exercise 5

    Again, don't count trivial multiplications.

  12. 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?
  13. Chapter 7, Exercise 8


Jeff Gilbert (homepage), gilbertj@eecs.berkeley.edu (mail me)