- Butterfly diagram
, used for finding the most likely sequence of hidden states.
Most commonly, the term "butterfly" appears in the context of the
Cooley-Tukey FFT algorithm , which recursively breaks down a DFT of composite size n = r m into r smaller transforms of size m where r is the "radix" of the transform. These smaller DFTs are then combined with size-r butterflies, which themselves are DFTs of size r (performed m times on corresponding outputs of the sub-transforms) pre-multiplied by roots of unity (known astwiddle factor s). (This is the "decimation in time" case; one can also perform the steps in reverse, known as "decimation in frequency", where the butterflies come first and are post-multiplied by twiddle factors. See also the Cooley-Tukey FFT article.)Radix-2 butterfly diagram
In the case of the radix-2 Cooley-Tukey algorithm, the butterfly is simply a DFT of size 2 that takes two inputs x_0, x_1) (corresponding outputs of the two sub-transforms) and gives two outputs y_0, y_1) by the formula (not including twiddlefactors):
:y_0 = x_0 + x_1:y_1 = x_0 - x_1.
If one draws the data-flow diagram for this pair of operations, the x_0, x_1) to y_0, y_1) lines cross and resemble the wings of a
butterfly , hence the name. (See also the illustration at right.)More specifically, a decimation-in-time FFT algorithm on n=2^p inputs with respect to a primitive n-th root of unity omega= exp(frac{2 pi i}{n}) relies on O(n log n) butterflies of the form:
:y_0 = x_0 + x_1 omega^k:y_1 = x_0 - x_1 omega^k,
where "k" is an integer depending on the part of the transform being computed. Whereas the corresponding inverse transform can mathematically be performed by replacing omega with omega^{-1} (and possibly multiplying by an overall scale factor, depending on the normalization convention), one may also directly invert the butterflies:
:x_0 = frac{1}{2} (y_0 + y_1):x_1 = frac{omega^{-k{2} (y_0 - y_1),
corresponding to a decimation-in-frequency FFT algorithm.
See also
*
Mathematical diagram
*Zassenhaus lemma References
External links
* [http://www.relisoft.com/Science/Physics/fft.html explanation of the FFT and butterfly diagrams] .
* [http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html butterfly diagrams of various FFT implementations (Radix-2, Radix-4, Split-Radix)] .
Wikimedia Foundation. 2010.