 Bluestein's FFT algorithm

Bluestein's FFT algorithm (1968), commonly called the chirp ztransform algorithm (1969), is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of arbitrary sizes (including prime sizes) by reexpressing 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.)
In fact, Bluestein's algorithm can be used to compute more general transforms than the DFT, based on the (unilateral) ztransform (Rabiner et al., 1969).
Algorithm
Recall that the DFT is defined by the formula
If we replace the product nk in the exponent by the identity nk = –(k–n)^{2}/2 + n^{2}/2 + k^{2}/2, we thus obtain:
This summation is precisely a convolution of the two sequences a_{n} and b_{n} of length N (n = 0,...,N–1) defined by:
with the output of the convolution multiplied by N phase factors b_{k}^{*}. That is:
This convolution, in turn, can be performed with a pair of FFTs (plus the precomputed FFT of b_{n}) via the convolution theorem. The key point is that these FFTs are not of the same length N: such a convolution can be computed exactly from FFTs only by zeropadding 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 primesize DFTs, albeit several times slower than the Cooley–Tukey algorithm for composite sizes.
The use of zeropadding for the convolution in Bluestein's algorithm deserves some additional comment. Suppose we zeropad to a length M ≥ 2N–1. This means that a_{n} is extended to an array A_{n} of length M, where A_{n} = a_{n} for 0 ≤ n < N and A_{n} = 0 otherwise—the usual meaning of "zeropadding". However, because of the b_{k–n} term in the convolution, both positive and negative values of n are required for b_{n} (noting that b_{–n} = b_{n}). The periodic boundaries implied by the DFT of the zeropadded array mean that –n is equivalent to M–n. Thus, b_{n} is extended to an array B_{n} of length M, where B_{0} = b_{0}, B_{n} = B_{M–n} = b_{n} for 0 < n < N, and B_{n} = 0 otherwise. A and B are then FFTed, multiplied pointwise, and inverse FFTed to obtain the convolution of a and b, according to the usual convolution theorem.
Let us also be more precise about what type of convolution is required in Bluestein's algorithm for the DFT. If the sequence b_{n} were periodic in n with period N, then it would be a cyclic convolution of length N, and the zeropadding would be for computational convenience only. However, this is not generally the case:
Therefore, for N even the convolution is cyclic, but in this case N is composite and one would normally use a more efficient FFT algorithm such as Cooley–Tukey. For N odd, however, then b_{n} is antiperiodic and we technically have a negacyclic convolution of length N. Such distinctions disappear when one zeropads a_{n} to a length of at least 2N−1 as described above, however. It is perhaps easiest, therefore, to think of it as a subset of the outputs of a simple linear convolution (i.e. no conceptual "extensions" of the data, periodic or otherwise).
zTransforms
Bluestein's algorithm can also be used to compute a more general transform based on the (unilateral) ztransform (Rabiner et al., 1969). In particular, it can compute any transform of the form:
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 transferfunction analyses, etcetera.
The algorithm was dubbed the chirp ztransform algorithm because, for the Fouriertransform case (z = 1), the sequence b_{n} 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, 218219 (1968).
 Lawrence R. Rabiner, Ronald W. Schafer, and Charles M. Rader, "The chirp ztransform algorithm and its application," Bell Syst. Tech. J. 48, 12491292 (1969). Also published in: Rabiner, Shafer, and Rader, "The chirp ztransform algorithm," IEEE Trans. Audio Electroacoustics 17 (2), 86–92 (1969).
 D. H. Bailey and P. N. Swarztrauber, "The fractional Fourier transform and applications," SIAM Review 33, 389404 (1991). (Note that this terminology for the ztransform is nonstandard: a fractional Fourier transform conventionally refers to an entirely different, continuous transform.)
 Lawrence Rabiner, "The chirp ztransform algorithm—a lesson in serendipity," IEEE Signal Processing Magazine 21, 118119 (March 2004). (Historical commentary.)
Categories: FFT algorithms
Wikimedia Foundation. 2010.
Look at other dictionaries:
Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… … Wikipedia
CooleyTukey FFT algorithm — The Cooley Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 in terms of smaller… … Wikipedia
Rader's FFT algorithm — Rader s algorithm (1968) is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re expressing the DFT as a cyclic convolution. (The other algorithm for FFTs of prime sizes, Bluestein s… … Wikipedia
Bluestein — is a surname and may refer to:* Abe Bluestein * Richard Bluestein * Suzanna Bluestein, see Divergence Eve ee also* Bluestein s FFT algorithm * Blaustein … Wikipedia
Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group … Wikipedia
List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra … Wikipedia
Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… … Wikipedia
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… … Wikipedia