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
French resistance

... maquis bands and began to plan attacks against the occupation forces. Some groups had also Spanish members who had fought in the Republican side of the Spanish Civil War. ...

 
 
 
This page was created in 36.4 ms