蝶形運算（butterfly）
在每一個 FFT 內部，同一個微小裝置觸發數百萬次。畫成訊號流程圖時，它兩條交叉的線看起來像蝴蝶的翅膀，名稱由此而來。蝶形是演算法的原子組合步驟：它取兩個複數與一個權重，產生兩個複數。
一個 radix-2 蝶形做的是這件事。取兩個中間值 a 與 b 以及一個旋轉因子 W^k = e^(-2*pi*i*k/N)。算出乘積 t = W^k * b，然後輸出 a + t 與 a - t 這一對。這是一次複數乘法加兩次複數加法，同時產生轉換的兩個值——真正的省力在於那一次乘法 W^k * b 被兩個輸出（加版與減版）共用。把這些堆疊起來：一個 2 的冪的 FFT 不過是 log2(N) 個階段，每個含 N/2 個蝶形，接線使得一階段的輸出餵給下一階段的輸入。數一數工作量就得到 (N/2) * log2(N) 次複數乘法——O(N log N) 的成本正是由這些小零件組成。
理解蝶形能揭開整個 FFT 的神秘面紗：那令人生畏的轉換，不過是一支由相同的加-乘-減單元組成的整齊大軍。它也解釋了為何 FFT 在真實硬體上如此之快——蝶形是規律、可預測的樣式，向量化效果好、塞得進快取、又能原地運作（用輸出覆寫輸入），因此不需額外記憶體。這份規律的代價是資料順序的位元反轉洗牌，演算法必須在蝶形階段之前或之後處理它。
最簡單的蝶形使用 W^0 = 1：由 a = x_0 與 b = x_1 輸出 x_0 + x_1 與 x_0 - x_1。這個「和與差」就是完整的 2 點 DFT——每一個更大的 FFT 都由這塊最小的磚砌成。
一次乘法、兩次加減、兩個輸出——FFT 不可分割的單元。
蝶形對複數做精確算術，但在原地 FFT 中其輸出重用輸入的記憶體，因此資料最後會以位元反轉順序打亂；忘記反洗牌是經典的 FFT 臭蟲。