Bluestein's FFT algorithm

From Academic Kids

Bluestein's FFT algorithm (1968), commonly called the chirp-z algorithm (1969), 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 linear convolution. (The other algorithm for FFTs of prime sizes, Rader's algorithm, also works by rewriting the DFT as a convolution.)

In fact, Bluestein's algorithm can be used to compute more general transforms than the DFT, based on the (unilateral) z-transform (Rabiner et al., 1969).

Algorithm

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 = –(jk)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 linear 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*. That is:

<math> f_j = b_j^* \sum_{k=0}^{n-1} a_k b_{j-k} \qquad j = 0,\dots,n-1. <math>

This convolution, in turn, can be performed with a pair of FFTs (plus the pre-computed FFT of bk) via the convolution theorem. The key point is that these FFTs are not of the same length n: such a linear convolution can be computed exactly from FFTs only by zero-padding it to a length 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 performed 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, albeit several times slower than the Cooley-Tukey algorithm for composite sizes.

The use of zero-padding for the convolution in Bluestein's algorithm deserves some additional comment. Suppose we zero-pad to a length N ≥ 2n–1. This means that ak is extended to an array Ak of length N, where Ak = ak for 0 ≤ k < n and Ak = 0 otherwise—the usual meaning of "zero-padding". However, because of the bjk term in the linear convolution, both positive and negative values of k are required for bk (noting that bk = bk). The periodic boundaries implied by the DFT of the zero-padded array mean that –k is equivalent to Nk. Thus, bk is extended to an array Bk of length N, where B0 = b0, Bk = BNk = bk for 0 < k < n, and Bk = 0 otherwise. A and B are then FFTed, multiplied pointwise, and inverse FFTed to obtain the linear convolution of a and b, according to the usual convolution theorem.

z-Transforms

Bluestein's algorithm can also be used to compute a more general transform based on the (unilateral) z-transform (Rabiner et al., 1969). In particular, it can compute any transform of the form:

<math> f_j = \sum_{k=0}^{n-1} x_k z^{jk}

\qquad j = 0,\dots,m-1, <math>

for an arbitrary complex number z and for differing numbers n and m of inputs and outputs. Given Bluestein's algorithm, such a transform 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), enhance arbitrary poles in transfer-function analyses, etcetera.

The algorithm was dubbed the chirp z-transform algorithm because, for the Fourier-transform case (|z| = 1), the sequence bk from above is a complex sinusoid of linearly increasing frequency, which is called a (linear) chirp in radar systems.

References

  • Leo I. Bluestein, "A linear filtering approach to the computation of the discrete Fourier transform," Northeast Electronics Research and Engineering Meeting Record 10, 218-219 (1968).
  • Lawrence R. Rabiner, Ronald W. Schafer, and Charles M. Rader, "The chirp z-transform algorithm and its application," Bell Syst. Tech. J. 48, 1249-1292 (1969).
  • D. H. Bailey and P. N. Swarztrauber, "The fractional Fourier transform and applications," SIAM Review 33, 389-404 (1991). (Note that this terminology for the z-transform is nonstandard: a fractional Fourier transform conventionally refers to an entirely different, continuous transform.)
Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools