a) In many applications (such as evaluating frequency responses and interpolation), it is of interest to compute the DFT of a short sequence that is "zero-padded." In such cases, a specialized "pruned" FFT algorithm can be used to increase the efficiency of computation (Markel, 1971). In this problem, we will consider pruning of the radix-2 decimation-infrequency algorithm when the length of the input sequence is M ≤ 2μ and the length of the DFT is N = 2ν , where μ

b) Assume that the input sequence is of length M = 2; i.e., x[n] = 0 only for N = 0 and N = 1. Draw a new flow graph for N = 16 that shows how the nonzero input samples propagate to the output DFT; i.e., eliminate or prune all branches in the flow graph of part (a) that represent operations on zero-inputs.

(c) In part (b), all of the butterflies in the first three stages of computation should have been effectively replaced by a half-butterfly of the form shown in Figure P9.43, and in the last stage, all the butterflies should have been of the regular form. For the general case where the length of the input sequence is M ≤ 2μ and the length of the DFT is N = 2ν , where μ