In this problem, we will write the FFT as a sequence of matrix operations. Consider the...

In this problem, we will write the FFT as a sequence of matrix operations. Consider the 8-point decimation-in-time FFT algorithm shown in Figure P9.58. Let a and f denote the input and output vectors, respectively. Assume that the input is in bit-reversed order and that the output is in normal order (compare with Figure 9.11). Let b, c, d, and e denote the intermediate vectors shown on the flow graph.

(a) Determine the matrices F₁, T₁, F₂, T₂, and F₃ such that

b = F₁a,

c = T₁b,

d = F₂c,

e = T₂d,

f = F₃e.

(b) The overall FFT, taking input a and yielding output f can be described in matrix notation as f = Qa, where

Q = F₃T₂F₂T₁F₁

Let Q^H be the complex (Hermitian) transpose of the matrix Q. Draw the flow graph for the sequence of operations described by Q^H. What does this structure compute?

(c) Determine (1/N)Q^H Q.