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

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}=\sum _{n=0}^{N-1}x_{n}e^{{\mathbf {-2nk} }{\frac {\pi i}{N}}}\qquad k=0,\dots ,N-1.}$

If the product in the exponent is substituted by and taken into account, the result is: ${\displaystyle \mathbf {-2nk} }$ ${\displaystyle \mathbf {-2nk} =\mathbf {-k^{2}} +\mathbf {-n^{2}} +\mathbf {(k-n)^{2}} }$ ${\displaystyle e^{a+b}=e^{a}e^{b}}$

${\displaystyle X_{k}=e^{\mathbf {-k^{2}} {\frac {\pi i}{N}}}\sum _{n=0}^{N-1}\left(x_{n}e^{\mathbf {-n^{2}} {\frac {\pi i}{N}}}\right)e^{\mathbf {+(k-n)^{2}} {\frac {\pi i}{N}}}\qquad k=0,\dots ,N-1.}$

Strictly speaking, this summation is a convolution of the two sequences and its length is defined by: ${\displaystyle a_{n}}$ ${\displaystyle b_{n}}$ ${\displaystyle N}$ ${\displaystyle (n=0,\ldots ,N-1)}$

${\displaystyle a_{n}=x_{n}e^{-n^{2}{\frac {\pi i}{N}}}}$

${\displaystyle b_{k-n}=e^{+(k-n)^{2}{\frac {\pi i}{N}}},}$

with the result of the convolution multiplied by phase factors . That makes: ${\displaystyle N}$ ${\displaystyle b_{k}^{*}}$

${\displaystyle X_{k}=b_{k}^{*}\sum _{n=0}^{N-1}a_{n}b_{k-n}\qquad k=0,\dots ,N-1.}$

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. ${\displaystyle b_{n}}$ ${\displaystyle N}$ ${\displaystyle 2N-1}$ ${\displaystyle O(N\log N)}$ ${\displaystyle O(N\log N)}$

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). ${\displaystyle M\geq 2N-1}$ ${\displaystyle a_{n}}$ ${\displaystyle A_{n}}$ ${\displaystyle M}$ ${\displaystyle A_{n}=a_{n}}$ ${\displaystyle 0\leq n<N}$ ${\displaystyle A_{n}=0}$

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. ${\displaystyle b_{k-n}}$ ${\displaystyle n}$ ${\displaystyle b_{n}}$ ${\displaystyle b_{-n}=b_{n}}$ ${\displaystyle -n}$ ${\displaystyle M-n}$ ${\displaystyle b_{n}}$ ${\displaystyle B_{n}}$ ${\displaystyle M}$ ${\displaystyle B_{0}=b_{0}}$ ${\displaystyle B_{n}=B_{M-n}=b_{n}}$ ${\displaystyle 1\leq n<N}$ ${\displaystyle B_{n}=0}$

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: ${\displaystyle b_{n}}$ ${\displaystyle n}$ ${\displaystyle N}$ ${\displaystyle N}$

${\displaystyle b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}e^{{\frac {\pi i}{N}}(2Nn+N^{2})}=(-1)^{N}b_{n}.}$

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. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle b_{n}}$ ${\displaystyle N}$ ${\displaystyle a_{n}}$ ${\displaystyle 2N-1}$

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:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,}$

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. ${\displaystyle z}$ ${\displaystyle N}$ ${\displaystyle M}$

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 . ${\displaystyle \left\|z\right\|=1}$ ${\displaystyle b_{n}}$

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

1. ^ ^{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.
2. ↑ see " fractional Fourier transform " in the English Wikipedia