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
![$\displaystyle X(k) = \sum_{n=0}^{N-1} x(n) W^{-kn}, \quad k=0,1,2,\ldots,N-1,
$](http://www.dsprelated.com/josimages_new/mdft/img1650.png)
![$ W \isdeftext \exp(j2\pi/N)$](http://www.dsprelated.com/josimages_new/mdft/img1651.png)
![$ N$](http://www.dsprelated.com/josimages_new/mdft/img35.png)
![$ W^{(n^2+k^2)/2}$](http://www.dsprelated.com/josimages_new/mdft/img1652.png)
![\begin{eqnarray*}
X(k)
&=&
\sum_{n=0}^{N-1}x(n)W^{-kn}W^{\frac{1}{2}(n^2+k^2)}...
...frac{1}{2}(k-n)^2} \\
&=& W^{-\frac{1}{2}k^2} (x_q \ast w_q)_k,
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1653.png)
where `' denotes convolution (§7.2.4), and
the sequences
and
are defined by
![\begin{eqnarray*}
x_q(n) & \isdef & x(n)W^{-\frac{1}{2}n^2}, \quad n=0,1,2,\ldot...
...{\frac{1}{2}n^2}, \quad n=-N+1,-N+2,\ldots,-1,0,1,2,\ldots, N-1,
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1657.png)
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