Encyclopedia > Bluestein's FFT algorithm

  Article Content

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:
  • L. I. Bluestein, Northeast Electronics Res. and Eng. Meeting Record 10, 218-219 (1968).
  • D. H. Bailey and P. N. Swarztrauber, "The fractional Fourier transform and applications," SIAM Review 33, 389-404 (1991).



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Grateful Dead

... of the shows and did not sell terribly well. The 1970s live album Live Dead did capture more of their essence, but commercial success did not come until the country ...

 
 
 
This page was created in 37.2 ms