Bailey's FFT algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Bailey's FFT (also known as a 4-step FFT) is a high-performance algorithm for computing the fast Fourier transform (FFT). This variation of the Cooley–Tukey FFT algorithm was originally designed for systems with hierarchical memory, as is common in modern computers, and was the first FFT algorithm in this "out of core" class. The algorithm treats the samples as a two dimensional matrix (thus another name, a matrix FFT algorithm ) and executes short FFT operations on the columns and rows of the matrix, with multiplication by correction "twiddle factors" in between. The algorithm is named after an article by David H. Bailey, FFTs in external or hierarchical memory, published in 19891. In this article, Bailey credits the algorithm to W. M. Gentleman and G. Sande, who published their paper, Fast Fourier Transforms: for fun and profit, in 19661, more than two decades earlier. The algorithm can be considered a radix- \sqrt n FFT decomposition.

Bailey's FFT (also known as a 4-step FFT) is a high-performance algorithm for computing the fast Fourier transform (FFT). This variation of the Cooley–Tukey FFT algorithm was originally designed for systems with hierarchical memory, as is common in modern computers, and was the first FFT algorithm in this "out of core" class. The algorithm treats the samples as a two dimensional matrix (thus another name, a matrix FFT algorithm ) and executes short FFT operations on the columns and rows of the matrix, with multiplication by correction "twiddle factors" in between. The algorithm is named after an article by David H. Bailey, FFTs in external or hierarchical memory, published in 1989. In this article, Bailey credits the algorithm to W. M. Gentleman and G. Sande, who published their paper, Fast Fourier Transforms: for fun and profit, in 1966, more than two decades earlier. The algorithm can be considered a radix- \sqrt n FFT decomposition. Let n=n_1n_2 be the transform size, and let the input data be represented as a n_1\times n_2 matrix. Bailey's four-step FFT consists of the following steps: Perform n_1 independent n_2 point FFTs on the input matrix. Multiply each resulting matrix element A_{jk} by the corresponding twiddle factor e^{\pm 2\pi i jk/n} , where the sign depends on the convention used for the transform. Transpose the resulting n_1\times n_2 matrix to get a n_2\times n_1 matrix. Perform n_2 independent n_1 point FFTs on the transposed matrix. When the component FFTs produce their outputs in natural order, the resulting transform is also in natural order and does not require a separate bit-reversal permutation. Bailey noted that n_1 and n_2 don't need to be equal, although on many systems the algorithm is the most efficient when they are chosen as close as possible to \sqrt n . The algorithm resembles a 2-dimensional FFT; three-dimensional and higher dimensional extensions are known as 5-step FFT, 6-step FFT, etc.

References

Sources

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374298660 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia publication date (×2) · confidence 0.95 https://en.wikipedia.org/w/index.php?oldid=1374298660

Provenance

snapshot enwiki-001374298660 · captured 1789090641.0 · version history

Cite this page as: encyclopegia.org, “Bailey's FFT algorithm”, snapshot enwiki-001374298660. https://encyclopegia.org/a/bailey-s-fft-algorithm

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.