Page 381 - Matrix Analysis & Applied Linear Algebra

5.8 Discrete Fourier Transform 377
1
 
 −i 
5.8.2. (a) Evaluate the discrete Fourier transform of   .
−1
i
 
1

 .
(b) Evaluate the inverse transform of  i 
−1
−i

F 2 D 2 F 2
5.8.3. Verify directly that F 4 = P 4 , where the F 4 , P 4 , and
F 2 −D 2 F 2
D 2 , are as defined in (5.8.15).

5.8.4. Use the following vectors to perform the indicated computations:
   
α 0 β 0

α 0 β 0  α 1   β 1 
ˆ
a = , b = , ˆ a =   , b =   .
α 1 β 1 0 0
0 0
ˆ
(a) Compute a b, F 4 (a b), and (F 4 ˆ a) × (F 4 b).
−1
(b) By using F 4 as given in Example 5.8.1, compute
−1 ˆ
F 4 (F 4 ˆ a) × (F 4 b) .
Compare this with the results guaranteed by the convolution
theorem.

5.8.5. For p(x)=2x − 3 and q(x)=3x − 4, compute the product p(x)q(x)
by using the convolution theorem.

5.8.6. Use convolutions to form the following products.
(a) 43 10 × 21 10 . (b) 123 8 × 601 8 . (c) 1010 2 × 1101 2 .

5.8.7. Let a and b be n × 1vectors, where n is a power of 2.
(a) Show that the number of multiplications required to form a b
2
by using the definition of convolution is n .
Hint: 1+2+ ··· + k = k(k +1)/2.
(b) Show that the number of multiplications required to form a b
by using the FFT in conjunction with the convolution theorem
is 3n log n +7n. Sketch a graph of 3n log n (the 7n factor is
2
2
dropped because it is not significant), and compare it with the
2
graph of n to illustrate why the FFT in conjunction with the
convolution theorem provides such a big advantage.