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
[22, pp. 213-215].^{A.7} 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 convolution (§7.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 [58].

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 [22].

[How to cite this work] [Order a printed hardcopy]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University

[Automatic-links disclaimer]