Other FFT Algorithms
There are other FFT algorithms distinct from Cooley–Tukey. For with coprime and, one can use the Prime-Factor (Good-Thomas) algorithm (PFA), based on the Chinese Remainder Theorem, to factorize the DFT similarly to Cooley–Tukey but without the twiddle factors. The Rader-Brenner algorithm (1976) is a Cooley–Tukey-like factorization but with purely imaginary twiddle factors, reducing multiplications at the cost of increased additions and reduced numerical stability; it was later superseded by the split-radix variant of Cooley–Tukey (which achieves the same multiplication count but with fewer additions and without sacrificing accuracy). Algorithms that recursively factorize the DFT into smaller operations other than DFTs include the Bruun and QFT algorithms. (The Rader-Brenner and QFT algorithms were proposed for power-of-two sizes, but it is possible that they could be adapted to general composite . Bruun's algorithm applies to arbitrary even composite sizes.) Bruun's algorithm, in particular, is based on interpreting the FFT as a recursive factorization of the polynomial, here into real-coefficient polynomials of the form and .
Another polynomial viewpoint is exploited by the Winograd algorithm, which factorizes into cyclotomic polynomials—these often have coefficients of 1, 0, or −1, and therefore require few (if any) multiplications, so Winograd can be used to obtain minimal-multiplication FFTs and is often used to find efficient algorithms for small factors. Indeed, Winograd showed that the DFT can be computed with only irrational multiplications, leading to a proven achievable lower bound on the number of multiplications for power-of-two sizes; unfortunately, this comes at the cost of many more additions, a tradeoff no longer favorable on modern processors with hardware multipliers. In particular, Winograd also makes use of the PFA as well as an algorithm by Rader for FFTs of prime sizes.
Rader's algorithm, exploiting the existence of a generator for the multiplicative group modulo prime, expresses a DFT of prime size as a cyclic convolution of (composite) size, which can then be computed by a pair of ordinary FFTs via the convolution theorem (although Winograd uses other convolution methods). Another prime-size FFT is due to L. I. Bluestein, and is sometimes called the chirp-z algorithm; it also re-expresses a DFT as a convolution, but this time of the same size (which can be zero-padded to a power of two and evaluated by radix-2 Cooley–Tukey FFTs, for example), via the identity .
Read more about this topic: Fast Fourier Transform, Algorithms
Other articles related to "fft, algorithms, fft algorithm":
... A twiddle factor, in fast Fourier transform (FFT) algorithms, is any of the trigonometric constant coefficients that are multiplied by the data in the course ... by Gentleman Sande in 1966, and has since become widespread in thousands of papers of the FFT literature ... root-of-unity complex multiplicative constants in the butterfly operations of the Cooley-Tukey FFT algorithm, used to recursively combine smaller discrete Fourier transforms ...
... When performing FFT-based spectral measurements, traditionally a window function has been used to reduce the effects of discontinuities at the ends of the ... When generating a single frequency test signal for FFT analysis, it is possible to create the frequency such that it aligns perfectly within an FFT bin-centre frequency ... These frequencies are multiples of the frequency resolution of the FFT, given by the sample rate divided by the number of sample points ...
... is slow when compared against the Fast Fourier Transform (FFT) ... However, the FFT can itself be employed, in conjunction with the use of a kernel, to perform the equivalent calculation but much faster ...
... many filters in parallel, then recombine the bands.) Standard filters such as FFT bands are suboptimal for this purpose because they are not designed to isolate bands ... For example, the FFT assumes implicitly that the only frequencies present in the signal are exactly those harmonics present as FFT harmonics ... between these harmonics will typically activate all of the FFT channels, which is not what is wanted in a beamform analysis ...