Bluestein's FFT algorithm

The Chirp Z-transform (CZT) is a generalization of the discrete Fourier transform. 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:

where A is the complex starting point, W is the complex ratio between points, and M is the number of points to calculate.

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. Bluestein's algorithm can be used to compute more general transforms than the DFT, based on the (unilateral) z-transform (Rabiner et al., 1969).

Recall that the DFT is defined by the formula

If we replace the product nk in the exponent by the identity

we thus obtain:

This summation is precisely a convolution of the two sequences a_n and b_n defined by:

with the output of the convolution multiplied by N phase factors b_k^*. That is:

This convolution, in turn, can be performed with a pair of FFTs (plus the pre-computed FFT of complex chirp b_n) via the convolution theorem. The key point is that these FFTs are not of the same length N: such a convolution can be computed exactly from FFTs only by zero-padding it to a length greater than or equal to 2N–1. In particular, one can pad to a power of two or some other highly composite size, for which the FFT can be efficiently performed by e.g. the Cooley–Tukey algorithm in O(N log N) time. Thus, Bluestein's algorithm provides an O(N log N) way to compute prime-size DFTs, albeit several times slower than the Cooley–Tukey algorithm for composite sizes.

...
Wikipedia