Twiddle factor
≈ 3 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.
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 of the algorithm. This term was apparently coined by Gentleman & Sande in 1966, and has since become widespread in thousands of papers of the FFT literature. More specifically, "twiddle factors" originally referred to the root-of-unity complex multiplicative constants in the butterfly operations of the Cooley–Tukey FFT algorithm, used to recursively combine smaller discrete Fourier transforms. This remains the term's most common meaning, but it may also be used for any data-independent multiplicative constant in an FFT. The prime-factor FFT algorithm is one unusual case in which an FFT can be performed without twiddle factors, albeit only for restricted factorizations of the transform size. For example, W 8 2 is a twiddle factor used in 8-point radix-2 FFT.
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 of the algorithm. This term was apparently coined by Gentleman & Sande in 1966, and has since become widespread in thousands of papers of the FFT literature. More specifically, "twiddle factors" originally referred to the root-of-unity complex multiplicative constants in the butterfly operations of the Cooley–Tukey FFT algorithm, used to recursively combine smaller discrete Fourier transforms. This remains the term's most common meaning, but it may also be used for any data-independent multiplicative constant in an FFT. The prime-factor FFT algorithm is one unusual case in which an FFT can be performed without twiddle factors, albeit only for restricted factorizations of the transform size. For example, W 8 2 is a twiddle factor used in 8-point radix-2 FFT.
References
W. M. Gentleman and G. Sande, "Fast Fourier transforms—for fun and profit," Proc. AFIPS 29, 563–578 (1966).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1320745112 under CC BY-SA 4.0; modifications have been made.