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
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 [
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 DSPPrevious Section: Rader's FFT Algorithm for Prime Lengths