Let the sequence x[n] be of length L and we wish to compute an N-point DFT of x[n] where L « N. Assume that the first L = 2 signal values x[0] and x[1] are nonzero.
(a) Draw a radix-2 N = 16-point DIT-FFT flow-chart in which only those paths originating from the nonzero signal values are retained.
(b) Draw a radix-2 N = 16-point DIF-FFT flow-chart in which only those paths originating from the nonzero signal values are retained.
(c) Determine the total number of complex multiplications in each of the above flow graphs. Which algorithm gives the lesser number of multiplications?
(d) Develop a general rule in terms of L and N for selecting a DIT- or DIF-FFT algorithm in FFT input pruning.