ENCYCLOPEDIA 4U .com

 Web Encyclopedia4u.com

# Bluestein's FFT algorithm

Bluestein\'s FFT algorithm (1968), also 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 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

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

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

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, albeit several times slower than the Cooley-Tukey algorithm for composite sizes.

### Chirp z-Transforms

In fact, Bluestein's algorithm can be used to compute more general transforms than the DFT, called chirp z-transforms (Rabiner, 1969); this is any transform of the form:

for an arbitrary complex number α, 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.

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 chirp z-transform is nonstandard: a fractional Fourier transform conventionally refers to an entirely different, continuous transform.]

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.