Butterfly-Operation

Der atomare Rechenschritt der FFT, der zwei Werte aus dem vorherigen Schritt kombiniert. Für den $m$ -ten Schritt gilt:

z (j) \leftarrow z (j) + ω \cdot z (k)

z (k) \leftarrow z (j) - ω \cdot z (k)

wobei $ω$ ein entsprechender Drehfaktor (Potenz der Einheitswurzel) ist.