Question

How many complex multiplications are need to be performed to calculate chirp z-transform?(M=N+L-1)

(a) log2M

(b) Mlog2M

(c) (M-1)log2M

(d) Mlog2(M-1)

This question was addressed to me at a job interview.

My doubt is from Linear Filtering Approach to Computation of DFT topic in chapter DFT Efficient Computation – Fast Fourier Transform Algorithms of Digital Signal Processing

Answer 1

The correct option is (b) Mlog2M

The explanation is: Since we will compute the convolution via the FFT, let us consider the circular convolution of the N point sequence g(n) with an M point section of h(n) where M>N. In such a case, we know that the first N-1 points contain aliasing and that the remaining M-N+1 points are identical to the result that would be obtained from a linear convolution of h(n) with g(n). In view of this, we should select a DFT of size M=L+N-1. Thus the total number of complex multiplications to be performed are Mlog2M.