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
[25, 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,

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

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

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

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