高等代数选讲笔记(4)——傅里叶变换

高等代数选讲笔记(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$ 写成二进制,然后前后顺序颠倒,再写回十进制,即可得到蝴蝶图表的左侧下标。

 

点赞 0

No Comments

Add your comment