傅里叶变换大家族

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

一. 傅里叶变换 (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. 离散傅里叶变换的信息学意义

这个大家比我懂的多。