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. 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). 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^NQ.

Transcribed Image Text:

b(0] d[0] e[0] c(이 a [0] f(0) b(1] c[1] e[1] a[1) li]p b(2] wg c[2] d[2] e[2] a[2] S12] -1 c[3] e[3] d[3] f(3] a[3] - -1 [b]P w: e4) b[4] c[4] f141 a[4] c[S] b[5] e[5] d[5] a[5] SIS) w: c[6] b16] e[6] f(6) a[6] [9]p -1 c[7) e(7] f17) a[7) -1 -1