In many applications (such as evaluating frequency responses and interpolation), it is o...

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 isM ≤ 2^μ and the length of the DFT is N = 2^v , where μ < ν.

(a) Draw the complete flow graph of a decimation-in-frequency radix-2 FFT algorithm for N = 16. Label all branches appropriately

(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 isM ≤ 2μ and the length of the DFT is N = 2ν , where μ < ν, determine the number of stages in which the pruned butterflies can be used. Also, determine the number of complex multiplications required to compute the N-point DFT of an M-point sequence using the pruned FFT algorithm. Express your answers in terms of ν and μ.