## 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

where denotes a primitive th root of unity,A.7 we multiply and divide by to obtain

where ' denotes convolution7.2.4), and the sequences and are defined by

where the ranges of given are those actually required by the convolution sum above. Beyond these required minimum ranges for , the sequences may be extended by zeros. As a result, we may implement this convolution (which is cyclic for even and `negacyclic'' for odd ) using zero-padding and a larger cyclic convolution, as mentioned in §7.2.4. In particular, the larger cyclic convolution size may be chosen a power of 2, which need not be larger than . Within this larger cyclic convolution, the negative- indexes map to in the usual way.

Note that the sequence above consists of the original data sequence multiplied by a signal which can be interpreted as a sampled complex sinusoid with instantaneous normalized radian frequency , 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