<<Up     Contents

Bluestein's FFT algorithm

Bluestein's FFT algorithm, also called the chirp-z algorithm, is a Fast Fourier Transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of arbitrary sizes (including prime sizes) by re-expressing the DFT as a convolution. (The other algorithm for FFTs of prime sizes, Rader's algorithm, also works by rewriting the DFT as a convolution.)

Recall that the DFT is defined by the formula

<math> f_j = \sum_{k=0}^{n-1} x_k e^{-\frac{2\pi i}{n} jk }
\qquad j = 0,\dots,n-1. </math>

If we replace the product jk in the exponent by the identity jk = -(j-k)2/2 + j2/2 + k2/2, we thus obtain:

<math> f_j = e^{-\frac{\pi i}{n} j^2 } \sum_{k=0}^{n-1} \left( x_k e^{-\frac{\pi i}{n} k^2 } \right) e^{\frac{\pi i}{n} (j-k)^2 }
\qquad j = 0,\dots,n-1. </math>

This summation is precisely a convolution of the two sequences ak and bk of length n (k = 0,...,n-1) defined by:

<math>a_k = x_k e^{-\frac{\pi i}{n} k^2 }</math>
<math>b_k = e^{\frac{\pi i}{n} k^2 },</math>

with the output of the convolution multiplied by n phase factors bj*.

This convolution, in turn, can be performed with a pair of FFTs (plus the pre-computed FFT of bk) via the convolution theorem. Although this may seem circular, the key point is that these FFTs need not be of the same length n. Rather, a convolution can always be computed exactly by zero-padding it to any size greater than or equal to 2n-1. In particular, one can pad to a power of two or some other highly composite size, for which the FFT can be efficiently computed by e.g. the Cooley-Tukey algorithm in O(n log n) time. Thus, Bluestein's algorithm provides an O(n log n) way to compute prime-size DFTs.

In fact, Bluestein's algorithm can be used to compute more general transforms than the DFT: any transform of the form:

<math> f_j = \sum_{k=0}^{n-1} x_k e^{i \alpha jk }
\qquad j = 0,\dots,n-1, </math>

for an arbitrary complex number α. This is called a chirp-z transform or, for real α, a fractional Fourier transform. This can be used, for example, to obtain a more finely spaced interpolation of some portion of the spectrum (although the frequency resolution is still limited by the total sampling time).

References:

wikipedia.org dumped 2003-03-17 with terodump