4.8 KiB
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 + vy_{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]