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.
In fact, Bluestein's algorithm can be used to compute more general transforms than the DFT: any transform of the form:
for an arbitrary complex number α. This is called a chirp-z transform or, for real α, a fractional Fourier transform. This 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).
Search Encyclopedia
|
Featured Article
|