The chirp Z-transform (CZT) is a generalization of the discrete Fourier transform (DFT). While the DFT samples the Z plane at uniformly-spaced points along the unit circle, the chirp Z-transform samples along spiral arcs in the Z-plane, corresponding to straight lines in the S plane. The DFT, real DFT, and zoom DFT can be calculated as special cases of the CZT.
Specifically, the chirp Z transform calculates the Z transform at a finite number of points z<sub>k</sub> along a logarithmic spiral contour, defined as:
:<math>X_k = \sum_{n=0}^{N-1} x(n) z_{k}^{-n} </math>
:<math>z_k = A\cdot W^{-k}, k=0,1,\dots,M-1</math>
where A is the complex starting point, W is the complex ratio between points, and M is the number of points to calculate.
Like the DFT, the chirp Z-transform can be computed in O(n log n) operations where <math display=“inline”>n = \max(M, N)</math>.
An O(N log N) algorithm for the inverse chirp Z-transform (ICZT) was described in 2003, and in 2019.
Bluestein's algorithm
Bluestein's algorithm expresses the CZT as a convolution and implements it efficiently using FFT/IFFT.
As the DFT is a special case of the CZT, this allows the efficient calculation of discrete Fourier transform (DFT) of arbitrary sizes, including prime sizes. (The other algorithm for FFTs of prime sizes, Rader's algorithm, also works by rewriting the DFT as a convolution.) It was conceived in 1968 by Leo Bluestein.