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!)
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供,附加条款亦可能应用