Butterfly (operation)

The two-input, one-multiply, two-output primitive that is the FFT's entire arithmetic content.

The butterfly is the primitive operation $X_{\text{top}}=E+WO$ , $X_{\text{bottom}}=E-WO$ combining one even-indexed and one odd-indexed partial result (scaled by a twiddle factor $W$ ) into two outputs, using only one multiplication. The entire Cooley-Tukey FFT is nothing more than this operation, repeated at every level of the recursion.

Examples

Combining $E=x_0+x_2$ and $O=x_1+x_3$ (with $W=1$ ) via one butterfly gives both $X_0$ and $X_2$ at once.