库利 – 图基快速傅里叶变换（Cooley-Tukey FFT）

感觉非重点，因为没有例题

核心思想：将一个大规模 DFT 的计算任务通过索引变换，分解成多个小规模的 DFT，从而减少计算量

回顾离散傅里叶变换公式为\(\hat{x}_k = \sum_{j = 0}^{N – 1} x_j W_N^{jk}\)

通过将一维离散傅里叶变换（DFT）方程重写为二维方程，N分解为 N = N₁N₂ 可以让整个变换操作更快，效率更高：

把索引 j 和 k 分别表示为： j = aN₁ + b，k = cN₂ + d，这样每个 j 只出现一次；

可改写为：

\(\begin{align*} \hat{x}_k&=\hat{x}_{c,d}=\sum_{a = 0}^{N_2 – 1} \sum_{b = 0}^{N_1 – 1} x_{a,b} W_N^{(aN_1 + b)(cN_2 + d)}\\ &=\sum_{b = 0}^{N_1 – 1} W_N^{b(cN_2 + d)} \sum_{a = 0}^{N_2 – 1} x_{a,b} W_N^{aN_1(cN_2 + d)}\\ &=\sum_{b = 0}^{N_1 – 1} W_N^{b(cN_2 + d)} \sum_{a = 0}^{N_2 – 1} x_{a,b} \underbrace{W_N^{acN_1N_2}}_{= 1} W_N^{adN_1}\\ &=\sum_{b = 0}^{N_1 – 1} W_N^{b(cN_2 + d)} \sum_{a = 0}^{N_2 – 1} x_{a,b} W_{N_2}^{ad} \end{align*}\)

(注：\(W_N = e^{-2\pi i / N}\)为旋转因子，利用\(N_1N_2 = N\)化简指数项)

为1的原因：\( W_N^{acN_1N_2} = e^{-2\pi i\cdot acN_1N_2/(N_1N_2)} = e^{-2\pi i\cdot ac} \)

设有两个次数分别为 n 和 m 的多项式：
\(A(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n = \sum_{j=0}^n a_jx^j\)\(B(x) = b_0 + b_1x + b_2x^2 + \dots + b_mx^m = \sum_{k=0}^m b_kx^k\)

其乘积\(C(x) = A(x)B(x)\)为次数 n+m 的多项式：
\(C(x) = c_0 + c_1x + c_2x^2 + \dots + c_{m+n}x^{m+n} = \sum_{l=0}^{m+n} c_lx^l\)

展开乘积可得：
\(\begin{align*} C(x) &= A(x)B(x) \\ &= \left( \sum_{j=0}^n a_jx^j \right) \left( \sum_{k=0}^m b_kx^k \right) \\ &= \sum_{j=0}^n \sum_{k=0}^m a_jb_kx^{j+k} \\ &= \sum_{l=0}^{n+m} \left( \sum_{\substack{j+k=l}} a_jb_k \right) x^l = \sum_{l=0}^{n+m} \left( \sum_{r=0}^l a_rb_{l-r} \right) x^l \end{align*}\)

因此，系数为：
\(c_l = \sum_{r=0}^l a_rb_{l-r}, \quad l = 0, \dots, n + m\)

例：

假设我们有两个简单的多项式： $$A(x)=1 + 2x + 3x^2 \quad (\text{系数} \ a_0 = 1, a_1 = 2, a_2 = 3)$$ $$B(x)=4 + 5x \quad (\text{系数} \ b_0 = 4, b_1 = 5)$$ 直接乘法展开就是： $$C(x) = (1 + 2x + 3x^2)(4 + 5x)$$ 把这些结果按次幂合并起来： $$C(x) = 4 + (5 + 8)x + (10 + 12)x^2 + 15x^3 = 4 + 13x + 22x^2 + 15x^3$$ 公式中说： $$c_l = \sum_{r = 0}^{l} a_r \cdot b_{l – r}$$ 我们来看看是不是成立的，比如计算 \(c_2\)： $$c_2 = a_0 \cdot b_2 + a_1 \cdot b_1 + a_2 \cdot b_0$$ 注意：因为 \(B(x)\) 中 \(b_2 = 0\)，所以： $$c_2 = 1 \cdot 0 + 2 \cdot 5 + 3 \cdot 4 = 0 + 10 + 12 = 22$$ 正好和展开结果对上！

多项式乘法本质就是卷积（一个数列 “反过来捎过去” 的点乘和 ）。
每一项 \(c_l\) 的计算方式是：“所有满足 \(i + j = l\) 的 \(a_i \cdot b_j\) 的和” 。

循环卷积（回顾）

循环卷积的定义为：
\((x * y)_j = \sum_{l=0}^{N-1} x_l y_{j-l}, \quad j = 0, \dots, N-1\)

其中索引 j−l 需对 N 取模（因此称为 “循环”，如\(y_{-m} = y_{N-m}\)）。

问题：如何利用循环卷积进行多项式乘法？ 关键：多项式乘法无 “取模” 操作，因此本质上不是循环卷积。需通过补零等方法将线性卷积转换为循环卷积后，再利用 FFT 加速计算。

Discrete Cosine Transformation(DFT)

\(\hat{x}_k = \sum_{n=0}^{N-1} x_n \cos\left( \frac{\pi}{N} \left(n + \frac{1}{2}\right) k \right), \quad k = 0, \ldots, N – 1.\)

The inverse Discrete Cosine Transformation for \(\hat{x} \in \mathbb{R}^N\) is given by

\(x_k = \frac{2}{N} \left( \frac{1}{2} \hat{x}_0 + \sum_{n=1}^{N-1} \hat{x}_n \cos\left( \frac{\pi}{N} \left(k + \frac{1}{2}\right) n \right) \right), \quad k = 0, \ldots, N – 1.\)

Remember DFT (\(x \in \mathbb{C}^N, \hat{x} \in \mathbb{C}^N\))

\(\hat{x}_k = \sum_{j=0}^{N-1} x_j w_N^{jk}, \quad k = 0, \ldots, N – 1.\)

where \(w_N = e^{-2\pi i / N}\), i.e. \(w_N^{jk} = \cos\left(-2\pi \frac{kj}{N}\right) + i \sin\left(-2\pi \frac{kj}{N}\right)\)

例题：Compute the DCT of (1,1)

For \(N = 2\) we have

\(\hat{x}_0 = x_0 \cos\left( \frac{\pi}{2}(0 + 0.5) \cdot 0 \right) + x_1 \cos\left( \frac{\pi}{2}(1 + 0.5) \cdot 0 \right)\)

\(\hat{x}_1 = x_0 \cos\left( \frac{\pi}{2}(0 + 0.5) \cdot 1 \right) + x_1 \cos\left( \frac{\pi}{2}(1 + 0.5) \cdot 1 \right)\)

leading to (after simplification)

\(\hat{x}_0 = x_0 + x_1\)

\(\hat{x}_1 = x_0 \cos\left( \frac{\pi}{2} \cdot 0.5 \right) + x_1 \cos\left( \frac{\pi}{2} \cdot 1.5 \right)\)

For \(x_0 = 1, x_1 = 1\) we have then

\(\hat{x}_0 = 1 + 1 = 2\)

\(\hat{x}_1 = 1 \cdot \cos\left( \frac{\pi}{4} \right) + 1 \cdot \cos\left( \frac{3\pi}{4} \right) = \frac{1}{\sqrt{2}} – \frac{1}{\sqrt{2}} = 0\)

如何把 DCT（离散余弦变换）用 DFT（离散傅里叶变换）来实现？

DCT 只用余弦，但 DFT 包含余弦 + 正弦（即复数）。所以我们用一种“巧妙构造”的方式，把实数 DCT 转换为复数 DFT 来计算。

需要对一个实数向量：\(x \in \mathbb{R}^N\)：原始信号，长度为 N。构造一个复数向量 \(y \in \mathbb{C}^{4N}\)，规则如下：

1. \(y_{2n} = 0\) for \(0 \leq n < N\) 偶数下标填 0➡️ 所以 \(y_0, y_2, y_4, \dots, y_{2N-2}\) 都是 0。 这是为了后续频率成分整齐排列（让信号不混叠）。
2. \(y_{2n+1} = x_n\) for \(0 \leq n < N\) 奇数下标填入原始数据 ➡️ 所以 \(y_1, y_3, y_5, \dots, y_{2N-1}\) 就放入了原始信号 \(x_n\)。
3. \(y_{4N-n} = y_n\) for \(0 < n < 2N\) 后半部分做镜像翻转➡️ 从 \(y_{2N+1}\) 到 \(y_{4N-1}\) 是对前面那一半的镜像拷贝（即对称）。 这使得整个向量是偶对称结构

对这个新的长度为 4N 的向量 y 做 DFT，再乘以 2，就得到了 DCT：\(\hat{x}_k = 2 \cdot \mathcal{F}[y]_k\)