A FFT "butterfly" is the name for an algorithmic structure inside the FFT. It
- has two complex inputs
- two complex outputs
- one complex multiply
- sum and difference of two complex numbers
There are two basic types. The decimation-in-time butterfly does the multiply first
$$y_0 = x_0 + x_1 \cdot W$$
$$ y_1 = x_0 - x_1 \cdot W $$
Decimation-in-Frequency computes the sum/difference operation first
$$ y_0 = (x_0 + x_1) $$
$$ y_1 = (x_0 - x_1) \cdot W $$
It's useful to write this in matrix notation. Decimation-in-time:
$$ \begin{pmatrix}
y_0 \\ y_1
\end{pmatrix} = \begin{pmatrix}
1 & W \\ 1 & -W
\end{pmatrix} \cdot
\begin{pmatrix}
x_0 \\ x_1
\end{pmatrix} $$
and decimation-in-frequency:
$$\begin{pmatrix}
y_0 \\ y_1
\end{pmatrix} = \begin{pmatrix}
1 & 1 \\ W & -W
\end{pmatrix} \cdot
\begin{pmatrix}
x_0 \\ x_1
\end{pmatrix} $$
So the matrices are transposed of each other.
Update:
The twiddle factor $W$ is a function of which stage you are in and which butterfly inside the stage. For decimation-in-time, $W$ simply alternates between $+1$ and $-1$, i.e. $W = [+1,-1,+1,-1 ...]$ so there is no need for an actual multiplication. Similarly for the second stage we have $W=[1, -j, -1, j, 1, -j, ...]$ which also doesn't require multiplication. This property can be used to further optimize the implementation and so in many Implementation these stages are hand-coded