Question

How many multiplications are required to calculate X(k) by chirp-z transform if x(n) is of length N?

(a) N-1

(b) N

(c) N+1

(d) None of the mentioned

I had been asked this question in a job interview.

This intriguing question originated from Linear Filtering Approach to Computation of DFT in division DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

Right answer is (c) N+1

To explain I would say: We know that yk(n)=WN^-kyk(n-1)+x(n).Each iteration requires one multiplication and two additions. Consequently, for a real input sequence x(n), this algorithm requires N+1 real multiplications to yield not only X(k) but also, due to symmetry, the value of X(N-k).