wzf2000 高等代数选讲笔记（4）——傅里叶变换
Contents
第四讲：傅里叶变换
傅里叶变换
信号传输
常见的如正弦波，余弦波。
如 $\cos (2 \pi t) = \Re e^{2\pi \mathrm{i} t}$。
其乘上复数 $c = r e^{-\mathrm{i} \theta}$ 得：
$$
\Re \left (r e^{2\pi \mathrm{i} \left (t - \frac{\theta}{2 \pi} \right )} \right )
$$
其图像，$r$ 对应振幅，$\frac{\theta}{2 \pi}$ 对应相位偏移。
信号的集合
$$
c_1 e^{2 \pi \mathrm{i} t} + c_2 e^{4 \pi \mathrm{i} t} + \cdots +c_n e^{2n \pi \mathrm{i} t} + \cdots
$$
输入一个信号，可以逼近：
$$
c_0 + c_1 e^{2 \pi \mathrm{i} t} + \cdots + c_n e^{2 n \pi \mathrm{i} t}
$$
傅里叶变换
将物理空间中的信号波 $f : [0, 1] \to \mathbb{C}, f = c_0 + c_1 e^{2 \pi \mathrm{i} t} + \cdots$ 映射到了频率空间 $\widehat{f} : \mathbb{Z} \to \mathbb{C}, \widehat{f} = (\cdots, c_{-1}, c_0, c_1, \cdots)$。
特殊情况：$f = e^{2 k \pi \mathrm{i} t}$：
$$
\widehat{f}(n) = \delta_k(n) =
\begin{cases}
1 & n = k \\
0 & n \not = k
\end{cases}
$$
离散傅里叶变换
单位根
记 $\omega_n = \omega = e^{\frac{2 \pi \mathrm{i}}{n}}$，称为 $n$ 次单位根。
离散傅里叶变换
考虑前 $m$ 个余弦函数：
$$
\begin{bmatrix}
f(0) \\
f(\frac{1}{n}) \\
\vdots \\
f(\frac{n - 1}{n})
\end{bmatrix} =
\begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & \omega & \omega^2 & \cdots & \omega^{m - 1} \\
1 & \omega^2 & \omega^4 & \cdots & \omega^{2(m - 1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \omega^{n - 1} & \omega^{2(n - 1)} & \cdots & \omega^{(m - 1)(n - 1)}
\end{bmatrix}
\begin{bmatrix}
c_0 \\
c_1 \\
\vdots \\
c_{m - 1}
\end{bmatrix} \\
y = A_{m, n} C
$$
取 $m = n$，$F_n = A_{m, n}$ 称为离散傅里叶矩阵，则 $y = F_n C$。
注意 $F_n$ 是可逆的（$\frac{1}{\sqrt{n}} F_n$ 是酉矩阵）。
如果要计算 $y = F_n C$ 需要用到 $n^2$ 次乘法，如何减少运算量？
快速傅里叶变换
基本想法
找到 $F_n$ 与 $F_m$ 的关系，当 $n = 2m$ 时。
快速傅里叶变换
一般来说，我们有：
$$
F_n =
\begin{bmatrix}
I_{\frac{n}{2}} & D_{\frac{n}{2}} \\
I_{\frac{n}{2}} & -D_{\frac{n}{2}}
\end{bmatrix}
\begin{bmatrix}
F_{\frac{n}{2}} & 0 \\
0 & F_{\frac{n}{2}}
\end{bmatrix}
P \\
D_{n} =
\begin{bmatrix}
1 & 0& \cdots & 0 \\
0 & \omega & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \omega^{n - 1}
\end{bmatrix}
$$
其中 $P$ 为一个置换阵。
需要迭代 $l = \log_2 n$ 次。
总共约需要乘法次数：$\frac{n}{2} \cdot l = \frac{n}{2} \log_2 n << n^2$。
蝴蝶图表
略。
bit-reverse order
把 $0 \sim 2^n - 1$ 写成二进制，然后前后顺序颠倒，再写回十进制，即可得到蝴蝶图表的左侧下标。
No Comments