Bluestein's FFT algorithm

The Bluestein FFT algorithm (1968 ), usually referred to as the chirp z-transform (1969, English chirp, dt " chirp " ), is an FFT algorithm, the Discrete Fourier Transform ( DFT ) of data sets of arbitrary size calculated by the reformulation of DFT as a convolution. This is interesting, since the normal fast Fourier transformation requires that the number of the data is a power of two. Another algorithm for FFTs of large amounts of data, which formulates the DFT as a convolution, is Rader's algorithm.

Indeed, the algorithm of Leo Bluestein can be used to carry out more general transformations as DFT, based on the ( unilateral ) z-transform.

Algorithm

The DFT is defined by the formula

If the product is replaced nk in the exponent of the equation yields:

This summation is actually a convolution of the two sequences an and bn with length N (n = 0, ..., N -1) defined by:

With the result of the convolution multiplied by N phase factors. The results:

This folding may be in turn be carried out with a pair of FFT (and the pre-calculated by FFT ) by using the convolution theorem. Key point is that these FFTs are not of the same length N: such a convolution can be computed by FFTs exactly only by padding with zeros to a length greater than or equal to 2N -1. In particular, one can fill up to a power of two, or another composite number for which the FFT can be performed efficiently with respect to the computation time by, for example, the Cooley -Tukey FFT algorithm with O ( N log N). In this way offers Blue stone algorithm a path of order O ( N log N ) for the calculation of DFT of prime size, even if it is slower by several factors as the Cooley -Tukey algorithm for composite numbers.

The zero padding for folding in Blue Stone algorithm needs an additional explanation. Suppose we fill zeros to a length M ≥ 2N -1. This means that is extended to a field of length M, where otherwise for 0 ≤ n < N and is - the original meaning of "zero - padding" ( zero padding ).

However, both positive and negative values ​​of n for the term n in the BK- folding needed (note that ). The periodic boundary conditions that are implied by the DFT of the zero-padded field, mean that n is equivalent to M -n. Consequently, it is extended to a field of length M, where for 0

Let us consider in more detail what type is needed by folding in Blue Stone algorithm for the DFT. If the sequence bn periodic in n with period N, then it would be a cyclic convolution of length N, and zero padding was only the computational convenience. However, this is not generally the case:

Thus, for N just the convolution is cyclic, but in this case N is a composite number and normally you would a more efficient FFT algorithm, for example, choose as the Cooley - Tukey after. However, for odd N the bn an anti- periodic function, and technically we have a negazyklische folding (English negacyclic convolution ) of length N. Such distinctions disappear when you fill up to a length of 2N -1, as described above.

Z-transforms

Blue stone algorithm can also be used to calculate a more general transform that is based on the ( single-sided ), the z-transform. In particular, it can calculate each transformation of the form:

For an arbitrary complex number z and for different numbers N and M of inputs and outputs. Given Blue stone such a transformation algorithm can be used for example to obtain a finer interpolation of a part of the spectrum (although the frequency resolution is still limited by the total measurement time). Also can be any of poles in the analysis of the transfer functions to work out, etc.

The algorithm is referred to as chirp z-transform algorithm as the case of the Fourier transform of | z | = 1, the sequence bn from above a complex sinusoid with linear anwachsender frequency referred to radar systems as a (linear ) chirp will.