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 the figure below. 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. Let b$,$c$,$d and e denote the intermediate vectors as shown on the figure.

$($a$)$ Determine the matrices $F_1,F_2,T_1,T_2$ and $F_3$ such that

$b=F_{1}a.$

$c=T_{1}b.$

$d=F_{2}c.$

$e=T_{2}d$

$f=F_{3}e.$

$($b$)$ The overall FFT$,$ taking input a and yielding output f can be described in matrix notation as $f=Qa$ where $Q=F_3{T}_2{F}_2{T}_1{F}_1.$

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 $(\frac{1}{N})Q^{H}Q.$