Bluestein FFT algorithm
The Bluestein FFT algorithm (1968), usually referred to as the Chirp-z-Transformation (1969, English chirp , dt. »Chirp«), is an FFT algorithm that the Discrete Fourier Transformation (DFT) of data sets of any size calculated by reformulating the DFT as a convolution . This is interesting because the normal fast Fourier transform requires the number of data to be a power of two. Another algorithm for FFTs of large amounts of data that formulates the DFT as a convolution is Rader's algorithm .
Indeed, Leo Bluestein's algorithm can be used to perform more general transformations than DFT, based on the (unilateral) z-transformation .
algorithm
The DFT is defined by the formula
If the product in the exponent is substituted by and taken into account, the result is:
Strictly speaking, this summation is a convolution of the two sequences and its length is defined by:
with the result of the convolution multiplied by phase factors . That makes:
This convolution can in turn be performed with a pair of FFTs (and the precomputed FFT of ) using the convolution theorem . The key point is that these FFTs are not of the same length : such a convolution can only be calculated by FFTs exactly by padding with zeros to a length greater than or equal to . In particular, one can pad to a power of two or some other composite number for which the FFT can be efficiently performed by e.g. B. the Cooley-Tukey FFT algorithm with order with respect to the computing time. In this way, Bluestein's algorithm provides a way of ordering the computation of prime-sized DFTs, even if it is several factors slower than the Cooley-Tukey algorithm for composite numbers.
Padding with zeros for the convolution in Bluestone's algorithm needs additional explanation. Suppose we fill in zeros up to a length . This means that it is expanded to a field of length , otherwise for and - the original meaning of "zero-padding" (padding with zeros).
However, because of the term in the convolution, both positive and negative values of are required for (note that ). The periodic constraints implied by the DFT of the field padded with zeros mean that is equivalent to . Hence it is expanded to a field of length , where , for , and otherwise.
So let's take a closer look at what type of convolution is needed in Bluestone's algorithm for DFT. If the sequence were periodic in with period , then it would be a cyclic convolution of the length , and padding with zeros was only for computational convenience. However, this is not generally the case:
Hence for just the convolution is cyclic, but in this case is a composite number and normally one would use a more efficient FFT algorithm such as B. choose the one after Cooley-Tukey . For however odd the anti-periodic function, and technically we have a negazyklische folding (Engl. Negacyclic convolution ) of length . Such distinctions disappear when padding to a length of , as described above.
z transformations
Bluestone's algorithm can also be used to compute a more general transformation based on the (one-sided) z-transformation . In particular, it can compute any transformation of the form:
for any complex number and for different numbers and for inputs and outputs. Given Bluestein's algorithm, such a transformation can be used, for example, to obtain a finer interpolation of part of the spectrum (although the frequency resolution is still limited by the total measurement time). You can also work out any poles when analyzing transfer functions , etc.
The algorithm is called the chirp z-transformation algorithm because in the case of the Fourier transformation with the sequence from above is a complex sinusoid with a linearly increasing frequency, which is called (linear) chirp in radar systems .
literature
- Leo I. Bluestein: A linear filtering approach to the computation of the discrete Fourier transform. In: Northeast Electronics Research and Engineering Meeting Record 10, 1968, pp. 218-219.
- Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform Algorithmus and its applicatio. In: Bell Syst. Tech. J. 48, 1969, pp. 1249-1292. Also published in: Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform algorithm. In: IEEE Trans. Audio Electroacoustics. 17, No. 2, 1969, pp. 86-92.
- DH Bailey, PN Swarztitzel: The fractional Fourier transform and applications. In: SIAM Review. 33, 1991, pp. 389-404 (Note that this terminology is not standard for the z-transform: a fractional Fourier transform usually refers to an entirely different continuous transform.).
- Lawrence Rabiner: The chirp z-transform algorithm — a lesson in serendipity. In: IEEE Signal Processing Magazine. 24, 2004, pp. 118–119 (historical commentary).
Individual evidence
- ^ A b Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform algorithm and its application. In: Bell Syst. Tech. J. 48, 1969, pp. 1249-1292. Also published in: Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader: The chirp z-transform algorithm. In: IEEE Trans. Audio Electroacoustics. 17, No. 2, 1969, pp. 86-92.
- ↑ see " fractional Fourier transform " in the English Wikipedia