A twiddle factor, in
fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
(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
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
multiplicative constants in the
butterfly
Butterflies are winged insects from the lepidopteran superfamily Papilionoidea, characterized by large, often brightly coloured wings that often fold together when at rest, and a conspicuous, fluttering flight. The oldest butterfly fossi ...
operations of the
Cooley–Tukey FFT algorithm, used to
recursively combine smaller
discrete Fourier transform
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...
s. 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
82 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).
FFT algorithms
{{signal-processing-stub