FFT“蝴蝶”是 FFT 内部算法结构的名称。它

• 有两个复数输入
• 两个复杂的输出
• 一复数乘法
• 两个复数的和与差

有两种基本类型。时间抽取蝶式先进行乘法运算

$$y_0 = x_0 + x_1 \cdot W$$ $$y_1 = x_0 - x_1 \cdot W$$

频率抽取首先计算和/差运算

$$y_0 = (x_0 + x_1)$$ $$y_1 = (x_0 - x_1) \cdot W$$

用矩阵表示法写这个很有用。及时抽取：

$$\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}$$

和抽取频率：

$$\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}$$

所以矩阵是相互转置的。

更新：

旋转因素$W$是您处于哪个阶段以及阶段内哪个蝴蝶的函数。对于及时抽取，$W$只是在之间交替$+1$和$-1$， IE$W = [+1,-1,+1,-1 ...]$所以不需要实际的乘法。同样对于第二阶段，我们有$W=[1, -j, -1, j, 1, -j, ...]$这也不需要乘法。此属性可用于进一步优化实现，因此在许多实现中，这些阶段是手动编码的