## Bluestein's FFT Algorithm

Like Rader's FFT,*Bluestein's FFT algorithm*(also known as the

*chirp -transform algorithm*), can be used to compute prime-length DFTs in operations [24, pp. 213-215].

^{A.6}However, unlike Rader's FFT, Bluestein's algorithm is not restricted to prime lengths, and it can compute other kinds of transforms, as discussed further below.

Beginning with the DFT

^{A.7}we multiply and divide by to obtain

*i.e.*, an instantaneous frequency that increases linearly with time. Such signals are called

*chirp signals*. For this reason, Bluestein's algorithm is also called the chirp -transform algorithm [59]. In summary, Bluestein's FFT algorithm provides complexity for any positive integer DFT-length whatsoever, even when is prime. Other adaptations of the Bluestein FFT algorithm can be used to compute a contiguous subset of DFT frequency samples (any uniformly spaced set of samples along the unit circle), with complexity. It can similarly compute samples of the transform along a sampled spiral of the form , where is any complex number, and , again with complexity [24].

**Next Section:**

Fast Transforms in Audio DSP

**Previous Section:**

Rader's FFT Algorithm for Prime Lengths