30.3 Efficient FFT implementations

30.3-1

Show how $\text{ITERATIVE-FFT}$ computes the $\text{DFT}$ of the input vector $(0, 2, 3, -1, 4, 5, 7, 9)$.

(Omit!)

30.3-2

Show how to implement an $\text{FFT}$ algorithm with the bit-reversal permutation occurring at the end, rather than at the beginning, of the computation. ($\textit{Hint:}$ Consider the inverse $\text{DFT}$.)

(Omit!)

30.3-3

How many times does $\text{ITERATIVE-FFT}$ compute twiddle factors in each stage? Rewrite $\text{ITERATIVE-FFT}$ to compute twiddle factors only $2^{s - 1}$ times in stage $s$.

(Omit!)

30.3-4 $\star$

Suppose that the adders within the butterfly operations of the $\text{FFT}$ circuit sometimes fail in such a manner that they always produce a zero output, independent of their inputs. Suppose that exactly one adder has failed, but that you don't know which one. Describe how you can identify the failed adder by supplying inputs to the overall $\text{FFT}$ circuit and observing the outputs. How efficient is your method?

(Omit!)