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 as twiddle factors). (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)] .