Butterfly diagram

The butterfly is the small building block of a fast Fourier transform. When an FFT algorithm splits a large discrete Fourier transform into smaller ones, a butterfly is the step that combines the results of the smaller transforms into the larger one, or, run in the other direction, breaks a larger transform up into subtransforms. It gets its name from the data-flow diagram of the radix-2 case, where two inputs and two outputs are joined by crossing lines that resemble the wings of a butterfly. The radix-2 butterfly adds and subtracts its two inputs, with one input first multiplied by a root of unity known as a twiddle factor in the Cooley-Tukey algorithm. The term is thought to appear first in print in a 1969 MIT technical report. The same structure also turns up in the Viterbi algorithm for finding the most likely sequence of hidden states, and it has been used to mix the bits of large arrays of partly random numbers through a hashing algorithm.