Bluestein's FFT Algorithm

Algorithm

Recall that the DFT is defined by the formula

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk } \qquad k = 0,\dots,N-1.$

If we replace the product nk in the exponent by the identity nk = –(k–n)2/2 + n2/2 + k2/2, we thus obtain:

$X_k = e^{-\frac{\pi i}{N} k^2 } \sum_{n=0}^{N-1} \left( x_n e^{-\frac{\pi i}{N} n^2 } \right) e^{\frac{\pi i}{N} (k-n)^2 } \qquad k = 0,\dots,N-1.$

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 pre-computed 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 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 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 "zero-padding". 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 zero-padded array mean that –n is equivalent to M–n. Thus, b_n is extended to an array B_n of length M, where B₀ = b₀, 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 zero-padding 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 zero-pads 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).

Read more about this topic: Bluestein's FFT Algorithm

Bluestein's FFT Algorithm - Algorithm