傅里叶变换大家族

信息学中经常用到的 “快速傅里叶变换”,其实只是傅里叶大家族的冰山一角。这篇文章将带你了解真实的傅里叶变换家族。

一. 傅里叶变换 (FT)

1. 傅里叶变换的物理意义

简单来说,傅里叶变换是一个从 “时域” 到 “频域” 的变换。

什么意思呢?

它可以将一个有关时间的函数 $f(t)$ 包含的 “频率” 提取出来,用每一种频率的分量构造出一个新的函数 $F(\omega)$ 。如果 $f(t)$ 含有较多的角频率为 $\omega_0$ 的分量,则 $F(\omega_0)$ 的绝对值会很大,反之 $F(\omega_0)$ 的绝对值会很小。

难以理解?

想象这么一个黑盒。黑盒有一个麦克风,可以接受外界的声音,还有一个显示屏,上面画着一个坐标系。横轴为频率,纵轴为大小。这时,你在麦克风附近敲打一个 $440Hz$ 的音叉 (乐队常用的标准音 La),麦克风会接收到标准的 $440Hz$ 的正弦波,此时显示屏上就会在 $440Hz$ 附近出现一个高峰。如果你同时敲打 $440Hz$ 和 $256Hz$ 的音叉,麦克风接受到的将会是两个不同频率正弦波的叠加,这个波形看上去十分混乱,但是显示屏上会出现清晰的两个高峰。敲打的越响,峰就会越高。

这个黑盒就是傅里叶变换。麦克风接收的是函数 $f(t)$ ,而显示屏描绘的是 $F(\omega)$ ;麦克风对应的是函数的时域 (自变量为时间),而显示屏对应的是函数的频域 (自变量为频率)。

2. 如何实现傅里叶变换

为了获得函数 $f$ 中,某一种频率究竟占多大的比重,我们再考虑一个黑盒,这个黑盒可以按照你给定的速率 $\omega$ 把 $f$ 绕到单位圆上,然后输出绕好了的函数的平均值。他的目的是什么呢?等下揭晓。

现在,我们将函数 $f$ 想象成是由一根铁丝弯曲而成的。然后,我们将这个铁丝按 $w$ 的角速率绕到单位圆上。即:

$$
g(t)=f(t)e^{i\omega t}
$$

嗯?什么意思?不难理解,$e^{i\omega t}$ 对应的是终点在单位圆上的一个向量,$\omega$ 决定了这个向量随着 $t$ 绕着圆心转动的角速率。将这个点乘上 $f(t)$ ,意味着把向量按照比例缩放。这样,$g(t)$ 就是这个铁丝被绕在了单位圆上之后的形态。

假设我们只取了 $f$ 中的一段,也就是说这个铁丝是有限长的。那么对应的绕好了的铁丝 $g$ 也不是无限长的。由于铁丝是有确定的质量,我们就可以求出 $g$ 的质心,而质心到原点的距离恰好就反应了 $f$ 中 $w$ 的分量的大小。

也就是说:

$$
F(\omega)=\Big |\frac{1}{L}\int_{0}^{L}f(t)e^{i\omega t}\mathrm dt\Big |
$$

为什么呢?

我们尝试把不等于 $\omega$ 的频率丢进这个黑盒,看输出的结果是什么。假设黑盒的配置是这样的:

  • 黑盒只截取 $f$ 在 $[0,2\pi]$ 这个区间内的片段。
  • 按照 $\omega = 1$ 缠绕铁丝。

如果我们把一个 $\omega=1$ 的函数 $f(t)=\cos t$ 丢进这个黑盒,看看会发生什么:

$$
\begin{aligned}
F(1) &= \frac{1}{2\pi}\int_{0}^{2\pi} e^{i t}\cos t \mathrm dt\\
&= \frac{1}{2\pi}\int_{0}^{2\pi} e^{i t}\frac{e^{it}+e^{-it}}{2} \mathrm dt\\
&= \frac{1}{2\pi}(\frac{1}{2}e^{2it}\Big |_0^{2\pi}+\frac{1}{2}e^{0}\Big|_0^{2\pi})\\
&= \frac{1}{2}
\end{aligned}
$$

如果我们把一个 $\omega\neq 1,\omega \in Z^+$ 的函数 $f(t)=\cos kt$ 丢进这个黑盒,看看会发生什么:

$$
\begin{aligned}
F(1) &= \frac{1}{2\pi}\int_{0}^{2\pi} e^{i t}\cos (kt) \mathrm dt\\
&= \frac{1}{2\pi}\int_{0}^{2\pi} e^{i t}\frac{e^{ikt}+e^{-ikt}}{2} \mathrm dt\\
&= \frac{1}{2\pi}(\frac{1}{2}e^{i(1+k)t}\Big |_0^{2\pi}+\frac{1}{2}e^{i(1-k)t}\Big|_0^{2\pi})\\
&= 0
\end{aligned}
$$

也就是说,只有 $k=1$ 的时候,$\cos kt$ 才使得 $F(1)\neq 0$。这揭示了这个黑盒的有效性。

3. 傅里叶变换的数学公式

$$
F(\omega)=\int_{-\infty}^{+\infty}f(t)e^{i\omega t}\mathrm dt
$$

这就是我们所说的听声音画频率的黑盒。

当然,在实际应用中,我们一般不会涉及到周期无穷长的连续函数,因此我们所应用的方法一般不是 “傅里叶变换”,而是 “傅里叶级数” 或者 “离散傅里叶变换”。

二. 傅里叶级数 (FS)

1. 傅里叶级数的物理意义

假设我们有一个周期为 $2\pi$ 的函数,我们想要对它做傅里叶变换:

$$
F(\omega)=\int_{-\infty}^{+\infty}f(t)e^{i\omega t}\mathrm dt
$$

你会发现这个积分限为无穷的积分基本上没法算。因为但凡 $f$ 含有某个频率,积分会发散,而对于 $f$ 不含有的频率,积分也不会收敛,而是在 $0$ 上下徘徊。

这时,对于周期函数,我们就需要一个更加有效的武器:“傅里叶级数”。

2. 如何实现傅里叶级数

首先我们明确两个事实:

  • 事实一:这是个显而易见的事实:周期是 $2\pi$ 的函数 $f$ ,包含的频率一定都是整数。
  • 事实二:这个事实一点都不显而易见:周期是 $2\pi$ 的连续函数 $f$ ,一定可以被表示成有限个或无穷个正弦函数和余弦函数的和。并且根据第一个事实,这些正余弦函数的角频率一定都是整数。即:

$$
f(t)=\sum_{n=0}^{+\infty}a_n\cos (nt)+b_n\sin (nt)
$$

这两个事实都不予证明。

有了这两个事实,我们就可以尝试计算 $a_n$ 和 $b_n$ 了。

计算 $a_n$ 和 $b_n$ 实际上非常简单,将 “事实二” 表示的等式两边同时乘以我们需要求的 $a_n$ 或 $b_n$ 对应的三角函数,然后在 $f$ 的一个周期内积分:

$$
\int_{-\pi}^{\pi}\cos(nt)f(t)=\sum_{k=0}^{+\infty}a_k\int_{-\pi}^{\pi}\cos(kt)\cos(nt)\mathrm dt+b_k\int_{-\pi}^{\pi}\sin(kt)\cos(nt)\mathrm dt
$$

你会惊讶的发现,等式的右边,除了 $\int_{-\pi}^{\pi}a_n\cos^2(nt)\mathrm dt$ 这一项不是 $0$ 以外,其他的积分全部变成了 $0$ 。至于为什么,大家可以自行证明。

然后,我们通过移项,就可以求得 $a_n$ 和 $b_n$ 的表达式:

$$
\begin{cases}
a_0=\frac{1}{2\pi}\int_{-\pi}^{\pi}f(t)\mathrm dt\\
b_0=0\\
a_n=\frac{1}{\pi}\int_{-\pi}^{\pi}f(t)\cos(nt)\mathrm dt & (n>0)\\
b_n=\frac{1}{\pi}\int_{-\pi}^{\pi}f(t)\sin(nt)\mathrm dt & (n>0)
\end{cases}
$$

$$
f(t)=\sum_{n=0}^{+\infty}a_n\cos (nt)+b_n\sin (nt)
$$

3. 傅里叶级数的数学意义

傅里叶级数是将周期函数分解为若干正余弦函数的和的过程。它使得我们可以一任意精度拟合一个确定的周期函数。

由于正余弦函数非常简单,并且拥有诸多优良的性质,由傅里叶级数表示的函数更方便进行积分、求解微分方程等过程。

三. 离散傅里叶变换 (DFT)

1. 离散傅里叶变换的物理意义

之前讲到,傅里叶变换对应着一个绕铁丝的黑盒。铁丝是一个 “连续” 的 “函数”,但是这样的函数在生产实践中很少能碰得到。我们遇到的一般都是离散的函数。比如,录音机将声波转化为电信号储存起来,它储存的并不是一个连续的函数,而是这个函数上有限个点处的取值。因此再想对这个函数进行 “傅里叶变换” 将会变得十分困难,因为它不是连续的。再说,计算机又如何对一个连续函数进行 “傅里叶变换” 呢?计算机甚至没法真正意义上储存一个连续函数。

这时,离散傅里叶变换诞生了。假设我们知道一个函数的等间距的 $N$ 个点处的取值,我们如何大致知道这个函数进行傅里叶变换之后的函数呢?

假设:

$$
f_n=f(\frac{2\pi n}{N})
$$

那么:

$$
F_n=\sum_{k=0}^{N-1}f_ke^{i\frac{2\pi kn}{N}}
$$

其中:

$$
F_n\approx F(n)
$$

也就是说,离散傅里叶变换是对傅里叶变换的一个近似。

2. 离散傅里叶变换的信息学意义

这个大家比我懂的多。

分类: 文章

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注