The chirp z-transform algorithm
L. R. Rabiner, Ronald W. Schafer, Charles M. Rader · IEEE Transactions on Audio and Electroacoustics · 1969
A computational algorithm for numerically evaluating thez-transform of a sequence ofNsamples is discussed. This algorithm has been named the chirpz-transform (CZT) algorithm. Using the CZT algorithm one can efficiently evaluate thez-transform atMpoints in thez-plane which lie on circular or spiral contours beginning at any arbitrary point in thez-plane. The angular spacing of the points is an arbitrary constant, andMandNare arbitrary integers. The algorithm is based on the fact that the values of thez-transform on a circular or spiral contour can be expressed as a discrete convolution. Thus one can use well-known high-speed convolution techniques to evaluate the transform efficiently. ForMandNmoderately large, the computation time is roughly proportional to(N+M) \log_{2}(N+M)as opposed to being proportional toN . Mfor direct evaluation of thez-transform atMpoints.