Butterfly diagram

This article is about butterfly diagrams in FFT algorithms; for the sunspot diagrams of the same name, see Solar cycle.

Data-flow diagram connecting the inputs x (left) to the outputs y that depend on them (right) for a "butterfly" step of a radix-2 Cooley-Tukey FFT. This diagram resembles a butterfly (as in the Morpho butterfly shown for comparison), hence the name.

In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms). The name "butterfly" comes from the shape of the data-flow diagram in the radix-2 case, as described below. The same structure can also be found in the Viterbi algorithm, 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=rm$ 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 twiddle factors):

$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 \left({\frac {2\pi i}{n}}\right)$ 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.

The Butterfly DIT FFT scheme

All of DFT's frequency outputs $X_{k}$ can be computed as the sum of the outputs of two length-N/2 DFTs, of the even-indexed $E_{k}$ and odd-indexed $O_{k}$ discrete-time samples, where the odd-indexed short DFT is multiplied by a so-called twiddle factor term $W_{N}^{k}=e^{-{\frac {2\pi i}{N}}k}$. The equation

${\begin{matrix}X_{k}&=&\left\{{\begin{matrix}E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}&{\mbox{if }}k<N/2\\\\E_{k-N/2}-e^{-{\frac {2\pi i}{N}}(k-N/2)}O_{k-N/2}&{\mbox{if }}k\geq N/2.\end{matrix}}\right.\end{matrix}}$

is referred as the FFT butterfly operation and is graphically shown in Fig.1.

Fig.1 The FFT butterfly is the most essential operation of the Fast Fourier Transform.

Figure 2 illustrates how the FFT algorithm works by showing the implementation of the decimation-in-time FFT. The frequency outputs of the length-N/2 DFT of the even-indexed time samples are denoted $E_{k}$ and those of the odd-indexed samples as $O_{k}$.

Fig.2 Decimation in time of a length-N DFT into two length-N/2 DFTs followed by a combining stage.

Because of the periodicity with N/2 frequency samples of these length-N/2 DFTs, $E_{k}$ and $O_{k}$ can be used to compute two of the length-N DFT frequencies, namely $X_{k}$ and $X_{k+N/2}$ but with different twiddle factor $W_{N}^{k}$. Such a reuse of these short-length DFT outputs gives the FFT its computational savings.

See also

• Mathematical diagram
• Zassenhaus lemma

External links

• explanation of the FFT and butterfly diagrams.
• butterfly diagrams of various FFT implementations (Radix-2, Radix-4, Split-Radix).