Bluestein's FFT Algorithm

Z-Transforms

Bluestein's algorithm can also be used to compute a more general transform based on the (unilateral) z-transform (Rabiner et al., 1969). In particular, it can compute any transform of the form:

$X_k = \sum_{n=0}^{N-1} x_n z^{nk} \qquad k = 0,\dots,M-1,$

for an arbitrary complex number z and for differing numbers N and M of inputs and outputs. Given Bluestein's algorithm, such a transform can be used, for example, to obtain a more finely spaced interpolation of some portion of the spectrum (although the frequency resolution is still limited by the total sampling time), enhance arbitrary poles in transfer-function analyses, etcetera.

The algorithm was dubbed the chirp z-transform algorithm because, for the Fourier-transform case (|z| = 1), the sequence b_n from above is a complex sinusoid of linearly increasing frequency, which is called a (linear) chirp in radar systems.

Read more about this topic: Bluestein's FFT Algorithm

Bluestein's FFT Algorithm - Z-Transforms