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, W82 is a twiddle factor used in 8-point radix-2 FFT.

References

edit
  • W. M. Gentleman and G. Sande, "Fast Fourier transforms—for fun and profit," Proc. AFIPS 29, 563–578 (1966). doi:10.1145/1464291.1464352
Stub icon

This signal processing–related article is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Twiddle

Look up twiddle in Wiktionary, the free dictionary. Twiddle or twiddling may refer to: Twiddle (band), an American rock band Twiddle factor, used in fast

Cooley–Tukey FFT algorithm

roots of unity (often called the twiddle factors). Perform N2 DFTs of size N1. Typically, either N1 or N2 is a small factor (not necessarily prime), called

Fast Fourier transform

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

Twiddler's syndrome

Twiddler's syndrome is a malfunction of a pacemaker due to manipulation of the device and the consequent dislodging of the leads from their intended location

Prime-factor FFT algorithm

factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called twiddle factors

Butterfly diagram

of the sub-transforms) pre-multiplied by roots of unity (known as twiddle factors). (This is the "decimation in time" case; one can also perform the

Trigonometric table

(FFT) algorithms, where the same trigonometric function values (called twiddle factors) must be evaluated many times in a given transform, especially in the

Split-radix FFT algorithm

_{N}^{k}} and ω N 3 k {\displaystyle \omega _{N}^{3k}} terms, known as twiddle factors. Here, we use the identities: ω N k + N / 4 = − i ω N k {\displaystyle