快速 Fourier 变换 (FFT)

`ZZ_N` 上的函数空间 对固定的正整数 `N`, 设 `f(k)` 是定义在 `ZZ_N = 0, 1, 2, cdots, N-1` 上的复值函数. 这个函数也可以写成向量形式: `f = (f_0, f_1, cdots, f_(N-1))`. 它的生成函数定义为一个多项式 `F(x) = sum_(0 le k lt N) f_k x^k`. `ZZ_n` 上两个函数 (即向量) 的内积定义为 `(f, g) = sum_(0 le r lt N) f(r) bar(g(r))`.

正交基底 把单位圆周平均分为 `N` 份, 第 `j` 个分点记为 `omega_j = "e"^(2pi"i"j//N)`, 取 `ZZ_N` 上的一组函数 `epsi_j = (1, omega_j, cdots, omega_j^(N-1))`, `quad j in ZZ_N`, 则它们两两正交: `(epsi_j, epsi_k) = { N, if j = k; 0, otherwise :}`

当 `j = k` 时 `(epsi_j, epsi_k) = sum_(0 le r lt N) omega_j^r omega_j^-r = N`.
`j != k` 时, 记 `omega_(j-k) = q`, 有 `q != 1` 和 `q^N = 1`. 于是 `(epsi_j, epsi_k) = sum_(0 le r lt N) omega_j^r omega_k^-r` `= sum_(0 le r lt N) omega_(j-k)^r` `= sum_(0 le r lt N) q^r` `= (1-q^N)/(1-q) = 0`,

离散 Fourier 变换 `f` 在 `ZZ_N` 上的 Fourier 系数定义为 `a_j := a_j^N(f) = 1/N (f, epsi_j) = 1/N sum_(0 le k lt N) f_k omega_j^-k`. 向量 `(a_0, a_1, cdots, a_(N-1))` 称为 `f` 的 Fourier 变换, 记为 `a = hat f`. 如果已知 `a`, 要求 `f`, 只需对 `a_j` 施行 Fourier 逆变换: `f_k = sum_(0 le j lt N) a_j omega_j^k`.

`{epsi_j/sqrt N}_(j=0)^(N-1)` 构成 `ZZ_N` 上函数空间的标准正交基, 因此 `f = sum_(0 le j lt N) (f, epsi_j/sqrt N) epsi_j/sqrt N`, 取第 `k` 个分量得 `f_k = sum_(0 le j lt N) 1/N (f, epsi_j) epsi_j(k)` `= sum_(0 le j lt N) a_j omega_j^k`.

从生成函数的角度看, `f_k` 等于多项式 `A(x) = sum_(0 le j lt N) a_j x^j` 在 `omega_k` 处的值, 而 `a_j` 等于多项式 `F(x) = sum_(0 le k lt N) f_k x^k` 在 `omega_j^-1` 处的值除以 `N`.

已知 `hat f = (4, 3, 2, 1)`, 求 `f`.

由 Fourier 逆变换公式, `f_k = 4 * 1^k + 3 * "i"^k + 2 * (-1)^k + 1 * (-"i")^k`, 代入 `k = 0, 1, 2, 3` 得 `f = (10, 2+2"i", 2, 2-2"i")`.

递推公式 设 `N = 2^n`, 若 `f` 是 `ZZ_(2N)` 上的函数, 则 `f_0(r) = f(2r)`, `f_1(r) = f(2r+1)` 是 `ZZ_N` 上的函数. 有如下递推公式 `a_j^(2N)(f) = (a_j^N(f_0) + a_j^N(f_1) * omega_(2N)^j) // 2`, 这里 `omega_N^j = "e"^(-2pi"i"j//N)`, 和上面稍有不同. 对于逆变换, 也有完全类似的公式, 只需把上式 `f, a` 的地位对调, 再用 `omega` 的共轭代替 `omega`.

由 `a_j^(2N)(f) = 1/(2N) sum_(0 le r lt N) (f(2r) "e"^(-2pi"i"j 2r//2N) + f(2r+1) "e"^(-2pi"i"j(2r+1)//2N))` 即得结论.

从生成函数的角度看, `F(x)` 是 `2N-1` 次多项式, `F_0(x) = f_0 + f_2 x + cdots + f_(2N-2) x^(N-1)`,
`F_1(x) = f_1 + f_3 x + cdots + f_(2N-1) x^(N-1)` 是两个 `N-1` 次多项式, 满足关系 `F(x) = F_0(x^2) + x F_1(x^2)`. 代入 `x = omega_(2N)^j` 有 `F(omega_(2N)^j) = F_0(omega_(2N)^(2j)) + omega_(2N)^j F_1(omega_(2N)^(2j))` `= F_0(omega_N^j) + omega_(2N)^j F_1(omega_N^j)`, 同理 `F(omega_(2N)^(N+j)) = F(-omega_(2N)^(N+j))` `= F_0(omega_N^j) - omega_(2N)^j F_1(omega_N^j)`. 两边同除以 `2N` 就得到结论.