Chirp Z-transform

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_k along a logarithmic spiral contour, defined as:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}}$

${\displaystyle z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1}$

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 $n=\max(M,N)$. An O(N log N) algorithm for the inverse chirp Z-transform (ICZT) was described in 2003, and in 2019.