FFT input and output pruning In many applications we wish to compute only a few points M of the Appoint DFT of a finite-duration sequence of length L (i.e., M N and L
(a) Draw the flow graph of the radix-2 D IF FFT algorithm for N = 16 and eliminate [i.e., prune] all signal paths that originate from zero inputs assuming that only x(0) and x(1) are nonzero.
(b) Repeat part (a) for the radix-2 DIT algorithm.
(c) Which algorithm is better if we wish to compute all points of the DFT? What happens if we want to compute only the points X
(0), X (l), X (2), and X (3)? Establish a rule to choose between DIT and DIF pruning depending on the values of M and L.
(d) Give an estimate of saving in computations in terms of M, L, and N