FFT input and output pruning in many applications we wish to compute only a few points M of the N-point DFT of a finite-duration sequence of length L (i.e., M << N and L << N).
(a) Draw the flow graph of the radix-2 DIF 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(1), 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.