CHIRP Z-TRANSFORM ALGORITHM AND ITS APPLICATION

We discuss a computational algorithm for numerically evaluating the z‐transform of a sequence of N samples. This algorithm has been named the chirp z‐transform algorithm. Using this 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; M and N 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. Applications discussed include: enhancement of poles in spectral analysis, high resolution narrow‐band frequency analysis, interpolation of band‐limited waveforms, and the conversion of a base 2 fast Fourier transform program into an arbitrary radix fast Fourier transform program. © 1969 The Bell System Technical Journal