bluestein's fft algorithm

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

f_j = \sum_{k=0}^{n-1} x_k e^{-\frac{2\pi i}{n} jk }

\qquad j = 0,\dots,n-1. If we replace the product jk in the exponent by the identity jk = –(j–k)²/2 + j²/2 + k²/2, we thus obtain:

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. This summation is precisely a linear convolution of the two sequences a_k and b_k of length n (k = 0,...,n–1) defined by:

a_k = x_k e^{-\frac{\pi i}{n} k^2 }

b_k = e^{\frac{\pi i}{n} k^2 },

with the output of the convolution multiplied by n phase factors b_j^*. That is:

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

This convolution, in turn, can be performed with a pair of FFTs (plus the pre-computed FFT of b_k) 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 a_k is extended to an array A_k of length N, where A_k = a_k for 0 ≤ k < n and A_k = 0 otherwise—the usual meaning of "zero-padding". However, because of the b_j–k term in the linear convolution, both positive and negative values of k are required for b_k (noting that b_–k = b_k). The periodic boundaries implied by the DFT of the zero-padded array mean that –k is equivalent to N–k. Thus, b_k is extended to an array B_k of length N, where B₀ = b₀, B_k = B_N–k = b_k for 0 < k < n, and B_k = 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:

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

\qquad j = 0,\dots,m-1, 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 b_k 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.)

<< Previous

Word Browser

Next >>

johann de kalb
rising force
or
feneberg
24 hour clock
alex salmond
sohn kee chung
rosalynn carter
lava lamp
lasalle, ontario
agricultural fencing

livonian language
colubrid
community friendly products
pavement (roads)
don adams
pavement (band)
state of palestine
ghost world
rader's fft algorithm
astroturfing
omniweb

kurt tank
pyromania
avalokitesvara
battle of monmouth
leaving group
richard m. jones
charles taylor
american pie (movie)
pandemonium (movie)
american pie 2
aebutius

pandmonium
pandaemonium (movie)
pandemonium (plane)
mairn bean u dhlaigh
american wedding
flaccus
vincent cianci, jr
san miguel
prime factor fft algorithm
albatros flugzeugwerke
guy smallman