CHIRP Z-TRANSFORM ALGORITHM

A computational algorithm for numerically evaluating the z-transform of a sequence of ? samples is discussed. This algorithm has been named the chirp z-transform (CZT) algorithm. Using the CZT algorithm one can efficiently evaluate the z-transform at M points in the z-plane which lie on circular or spiral contours beginning at any arbitrary point in the z-plane. The angular spacing of the points is an arbitrary constant, and M and ? are arbitrary integers. The algorithm is based on the fact that the values of the z-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. For M and N moderately large, the computation time is roughly proportional to (N+M) log2(N+M) as opposed to being proportional to N.M for direct evaluation of the z-transform at M points. Copyright © 1969 by The Institute of Electrical and Electronics Engineers, Inc.