Bluestein (1970) showed that ifN = M2, then the chirp transform algorithm has a recursiv...

Bluestein (1970) showed that ifN = M², then the chirp transform algorithm has a recursive implementation.

(a) Show that the DFT can be expressed as the convolution

where ∗ denotes complex conjugation and

(b) Show that the desired values of X[k] (i.e., for k = 0, 1, . . . , N −1) can also be obtained by evaluating the convolution of part (a) for k = N,N + 1, . . . , 2N − 1.

(c) Use the result of part (b) to show that X[k] is also equal to the output of the system shown in Figure P9.48 for k = N,N + 1, . . . , 2N − 1, where ˆh[k] is the finite-duration sequence

(d) Using the fact that N = M2, show that the system function corresponding to the impulse response ˆh[k] is

Hint: Express k as k = r + M.

(e) The expression forHˆ (z) obtained in part (d) suggests a recursive realization of the FIR system. Draw the flow graph of such an implementation.

( f ) Use the result of part (e) to determine the total numbers of complex multiplications and additions required to compute all of the N desired values of X[k]. Compare those numbers with the numbers required for direct computation of X[k]