# FFT快速傅里叶变换原理

## - 函数理论分析

对于一个多项式，设该多项式为：
$$A(x) = \Sigma_{i=0}^{n-1}a_ix_i = a_0 + a_1x + a_2x^2 + \mathellipsis$$

按A(x)的下标奇偶性分类：
$$A(x) = (a_0 + a_2x^{2} + \mathellipsis + a_{n-2}x^{n-2}) + (a_1 + a_3x^3 + \mathellipsis + a_{n-1}x^{n-1})$$ $$=  (a_0 + a_2x^2 + \mathellipsis + a_{n-2}x^{n-2}) + x(a_1 + a_3x^2 + \mathellipsis + a_{n-1}x^{n-2})$$

观察式子两边发现极为相似，设两个函数$A_e$, $A_o$，令
$$A_e(x) = a_0 + a_2x^{\frac{2}{2}} + \mathellipsis + a_{n-2}x^\frac{n-2}{2} = a_0 + a_2x^{1} + \mathellipsis + a_{n-2}x^{\frac{n}{2}-1} $$ $$A_o(x) = a_1 + a_3x^\frac{2}{2} + \mathellipsis + a_{n-1}x^\frac{n-2}{2} = a_1 + a_3x^1 + \mathellipsis + a_{n-1}x^{\frac{n}{2}-1}$$
显然有
$$A(x) = A_e(x^2) + xA_o(x^2)$$ $$A(-x) = A_e(x^2) - xA_o(x^2)$$

> 请注意上式右侧的平方

带入$x=\omega_n^k$
$$A(\omega_n^k) = A_e(\omega_n^{2k}) + \omega_n^k A_o(\omega_n^{2k})$$ $$=A_e(\omega_\frac{n}{2}^{k}) + \omega_n^k A_o(\omega_\frac{n}{2}^{k})$$ $$A(-\omega_n^k) = A(\omega_n^{k+\frac{n}{2}}) = A_e(\omega_n^{2k+n}) - \omega_n^k A_o(\omega_n^{2k+n})$$ $$=A_e(\omega_n^{2k}) - \omega_n^k A_o(\omega_n^{2k})$$ $$=A_e(\omega_\frac{n}{2}^{k}) - \omega_n^k A_o(\omega_\frac{n}{2}^{k})$$

>利用性质如下
> - $-\omega_n^k = \omega_n^{k+\frac{n}{2}}$ 
> - $\omega_n^{2k} = \omega_\frac{n}{2}^k$

不难发现，如果我们知道了$A_e(\omega_\frac{n}{2}^k), A_o(\omega_\frac{n}{2}^k)$ ，就可以知道$A(\omega_n^k)$

> 这一步叫做Butterfly（蝴蝶操作）
> $$u = A_e(\mathellipsis)$$ $$v=\omega_n^k A_o(\mathellipsis)$$
> 则有
> $$y_k = u + v$$ $$y_{k+\frac{n}{2}} = u - v$$
> 即可以自下而上的，从 $A_{\mathellipsis}(\omega_{\mathellipsis}^k)$ 推导出 $A(x)$
> 同时当我们知道$A(-x)$的时候，我们也可以知道$A(x)$

有下面的树（以$n=4, x = \omega_{16}^k$为例）
> $A(\omega_{16}^k)$
> $Ae(\omega_8^k); Ao(\omega_8^k)$
> $Aee(\omega_4^k), Aeo(\omega_4^k); Aoe(\omega_4^k), Aoo(\omega_4^k)$
> $Aeee(\omega_2^k), Aeeo(\omega_2^k) ,, Aeoe(\omega_2^k), Aeoo(\omega_2^k);$
> $Aoee(\omega_2^k), Aoeo(\omega_2^k) ,, Aeoe(\omega_2^k), Aeoo(\omega_2^k)$
> 最底层为$A...(\omega_1^k) = a_i$（系数 | 常数多项式）

**已知最下层的所有数值（的一半），一次往上带入即可**

---
## - 示例

以下两个式子为例：
$$f_1 = x^3 + x^2 + 8x + 1 $$ $$ f_2 = x^2 - 5x - 2 $$

### 一、确定次数以及补零
- 次数：$2 + 3 = 5$， 需要 $5 + 1 = 6$ 个点值
- 确定n：$2^3=8$，$n = 3$

得到两个系数数组
- $A = [1,8,1,1,0,0,0,0]$
- $B = [-2, -5,1,0,0,0,0,0]$
**（从低次到高次排序，补0至8位）**

### 二、正向FFT
**计算$f_1(\omega_8^k)$，$f_2(\omega_8^k)$，其中$k = 0, 1, \mathellipsis , 7$，单位根$\omega_8^k = e^{i\frac{2\pi k}{8}} = \cos(\frac{2k\pi}{8}) + i\sin(\frac{2k\pi}{8})$**


#### 1. 初始多项式定义
设两个多项式：
$$f_1(x) = x^3 + x^2 + 8x + 1$$
$$f_2(x) = x^2 - 5x - 2$$

为了进行 $n=8$ 的 FFT，补零后的系数向量为：
$$A = [a_0, a_1, a_2, a_3, a_4, a_5, a_6, a_7] = [1, 8, 1, 1, 0, 0, 0, 0]$$
$$B = [b_0, b_1, b_2, b_3, b_4, b_5, b_6, b_7] = [-2, -5, 1, 0, 0, 0, 0, 0]$$

---

#### 2. 递归拆分逻辑 (以 A 为例)

**第一层拆分 ($n=8 \to n=4$)：**
$$A_e(x) = a_0 + a_2x + a_4x^2 + a_6x^3 = 1 + 1x$$
$$A_o(x) = a_1 + a_3x + a_5x^2 + a_7x^3 = 8 + 1x$$

**第二层拆分 ($n=4 \to n=2$)：**
对于 $A_e$：
$$A_{ee}(x) = a_0 + a_4x = 1$$
$$A_{eo}(x) = a_2 + a_6x = 1$$
对于 $A_o$：
$$A_{oe}(x) = a_1 + a_5x = 8$$
$$A_{oo}(x) = a_3 + a_7x = 1$$

**第三层拆分 ($n=2 \to n=1$)：**
这是递归终点，系数即为点值：
$$A_{eee}=1, A_{eeo}=0, A_{eoe}=1, A_{eeo}=0 \dots$$

---

#### 3. 向上回溯（蝴蝶变换公式）
利用核心公式：
$$A(\omega_n^k) = A_e(\omega_{n/2}^k) + \omega_n^k A_o(\omega_{n/2}^k)$$
$$A(\omega_n^{k+n/2}) = A_e(\omega_{n/2}^k) - \omega_n^k A_o(\omega_{n/2}^k)$$

**从 $n=2$ 合并到 $n=4$ 的例子 (计算 $A_e$ 的点值)：**
已知 $A_{ee}$ 的点值在 $\omega_2^0$ 处为 $1$， $A_{eo}$ 的点值也为 $1$。
则在 $n=4$ 层：
$$A_e(\omega_4^0) = A_{ee}(\omega_2^0) + \omega_4^0 A_{eo}(\omega_2^0) = 1 + 1(1) = 2$$
$$A_e(\omega_4^1) = A_{ee}(\omega_2^1) + \omega_4^1 A_{eo}(\omega_2^1) = 1 + i(1) = 1+i$$
$$A_e(\omega_4^2) = A_{ee}(\omega_2^0) - \omega_4^0 A_{eo}(\omega_2^0) = 1 - 1 = 0$$
$$A_e(\omega_4^3) = A_{ee}(\omega_2^1) - \omega_4^1 A_{eo}(\omega_2^1) = 1 - i$$

---

#### 4. 点值乘法与逆变换 (IFFT)
得到 $A(\omega_8^k)$ 和 $B(\omega_8^k)$ 后，进行点值乘法：
$$C(\omega_8^k) = A(\omega_8^k) \cdot B(\omega_8^k)$$

最后进行 IFFT，公式为：
$$c_j = \frac{1}{n} \sum_{k=0}^{n-1} C(\omega_n^k) (\omega_n^{-j})^k$$

---

#### 5. 最终系数结果
$$C(x) = f_1(x) \cdot f_2(x) = x^5 - 4x^4 + x^3 - 41x^2 - 21x - 2$$
系数向量为：
$$[-2, -21, -41, 1, -4, 1, 0, 0]$$