采样与离散/快速傅里叶变换

从一条曲线到一串数字

本级到目前为止都活在连续函数的世界里。你把[[fourier-transform-pair|傅里叶变换]]当作傅里叶级数在周期延伸到无穷时的极限来认识：一个对整个 x 的积分把信号 f(t) 变成它的频谱 F(omega)，再一个积分又把它变回去。很美——但计算机算不了一个对全部时间的积分，因为它从未见过每一瞬间的 f(t)。它见到的是一段麦克风电压、或一个传感器读数，在时钟的某一下被测量：t = 0，然后 t = T，再 t = 2T，依此类推。在任何数学开始之前，那条连续曲线就已经被替换成了一串有限的数字。

把每一下时钟之间的间隔叫做采样间隔 T_s，它的倒数 f_s = 1/T_s 叫做采样率——每秒采样多少个点。比如一张光盘以 f_s = 44100 赫兹采样：每个声道每秒四万四千个数字。整篇导览的核心问题问起来朴素得令人放松：当你只留下这些采样点、把连续曲线扔掉时，你丢失了什么吗？两个不同的信号会不会产出完全相同的一串数字？诚实、且起初令人吃惊的答案是：在一个干净的条件下你什么也没丢失——而当那个条件不成立时，你丢失的是某种具体而不可逆的东西。

采样就是乘以一把梳子

要看清采样对频谱做了什么，就得诚实地把它建模。只在时钟刻度处测量 f(t)，等同于把 f(t) 乘以一排无限细的尖峰，每个 T_s 的整数倍处一根——这就是狄拉克梳，对所有整数 n 求和的 delta(t - n T_s)。回想本级前面：单个 delta 的傅里叶变换是一个平直的常数，而一列周期性 delta 串的变换本身又是一列周期性 delta 串——时间中的一把梳子变换成频率中的一把梳子，齿距为 f_s。这一个事实就是采样定理的全部引擎。

现在搬出两篇前的卷积定理：在时间里把两个信号相乘，就在频率里把它们的变换*卷积*起来。我们在时间里把 f 乘了一把梳子，于是在频率里，频谱 F(omega) 就跟一把频率梳子卷积——而任何东西跟一把梳子卷积，无非是在每一根齿上盖下它的一份拷贝。这个画面具体得让人无法抗拒：原本的频谱 F 沿频率轴被一遍又一遍地盖章，一份拷贝以 0 为中心、下一份在 f_s、再下一份在 2 f_s，两个方向都如此。时间上的采样使频谱*周期化*。这一幅图就把「采样何时安全」的一切都告诉了你。

奈奎斯特率，与混叠之罪

假设原信号是带限的：它的频谱 F(omega) 在某个最高频率 B 以上恰好为零——那之外没有能量。那么每一份被盖下的 F 拷贝都是一座宽为 2B 的小岛（从 -B 到 +B），而这些拷贝彼此相距 f_s。若 f_s 足够大，这些岛屿之间留有空隙、清清爽爽地各自分开，原本的 F 仍原封不动地坐在正中央，可被完美还原：乘以一个只留下中央那座岛的方窗、变换回去，你就精确地重建了 f(t)。没有任何信息丢失。这就是奈奎斯特与香农的[[sampling-and-nyquist-criterion|采样定理]]的核心。

多大才算足够大？当间距 f_s 至少是最高频率的两倍时，岛屿恰好不再重叠：f_s >= 2B。这个门槛 2B 就是奈奎斯特率——能保住一个最高频率为 B 的信号所需的最低采样率。等价地说，给定采样率 f_s，你能忠实捕捉的最高频率是奈奎斯特频率 f_s/2。光盘的 44100 赫兹正是这样选的，好让它的奈奎斯特频率 22050 赫兹刚好高过人耳约 20000 赫兹的上限。那个因子 2 不是什么安全余量、也不是工程上的凑数；它直接从那两份盖下的拷贝恰好相触的几何关系里掉出来。

门槛之下出错的方式叫混叠，而它是真正不可逆的。若 f_s < 2B，岛屿挨得太近、它们的裙边互相交叠；一份盖下拷贝的高频尾巴溢进了下一份的频带，而在交叠处的任一频率上，频谱如今是两份贡献之和，你再也分不开了。一个绕回来的高频正戴着伪装——它变成了某个低频的*别名*。教科书里的画面就是老电影里看似倒转的车轮，或者一个 7000 赫兹的音以 8000 赫兹采样后、不可分辨地变成了一个 1000 赫兹的音。一旦两个频率落到了同一批采样点上，事后任何处理都无法把它们区分开，因为采样点本身就是一模一样的。

离散傅里叶变换：一个真能算出来的傅里叶变换

假设我们做对了，如今手里有 N 个采样点 x[0], x[1], ..., x[N-1]，取自一个时间窗口。连续变换对所有 t 积分；我们只能对手里有的采样点求和。于是把积分换成有限和、把连续频率 omega 换成 N 个频率的离散网格，你就得到了[[discrete-and-fast-fourier-transform|离散傅里叶变换]]，即 DFT：X[k] = 对 n 从 0 到 N-1 求和的 x[n] 乘以 e^{-i 2 pi k n / N}。这是那个分析积分的、字面上可计算的表亲，指数里带着同一个负号——它凭正交性一次筛出一个频率分量，正是你在复指数傅里叶级数里见过的把戏，只不过现在是在一个有限网格上、而非一个周期上。

DFT 悄悄假定你的 N 个采样点是某个周期信号的一个周期——它把你的窗口首尾相接地铺满整段时间。这个假定是有牙齿的。若真实信号没有在窗口内走完整数个周期，这种铺排就会在窗口末端与它重复的开头相接处造出一个跳跃，而那个人为的不连续把每一条尖锐的谱线抹成附近若干频点上的一片散布——频谱泄漏，正是当年在傅里叶级数篇里引发吉布斯现象的那些跳跃的离散回声。标准的补救是在变换之前，用一个窗函数（汉宁、汉明及其同类）把采样点在两端平滑地收拢到零，以一点点模糊换取那道假边缘的压制。

快速傅里叶变换：它为何改变了一切

盯紧 DFT 这个和、数一数工作量。N 个输出值 X[k] 中的每一个都是 N 个乘积之和，所以直接计算大约要花 N 乘 N 次乘加。对于一段 N 在 44000 上下的一秒音频，单求一个频谱就约二十亿次运算——而 N^2 增长得如此残暴，以至一小时的音频会变得毫无希望。几十年来，这份代价使 DFT 成了一个美丽却大多贵到无法大规模使用的想法。拯救它的不是另一种变换，而是*算出同一批数字*的一种更快办法：[[discrete-and-fast-fourier-transform|快速傅里叶变换]]，即 FFT。

FFT 的想法——由 Cooley 与 Tukey 在 1965 年发扬光大（后来发现高斯约在 1805 年就瞥见过）——是分而治之。把 N 个采样点拆成偶数下标的一组与奇数下标的一组。一段简短的推算表明，长度为 N 的完整 DFT 可以由 N/2 个偶点的 DFT 加上 N/2 个奇点的 DFT 拼装而成，每一对用一个旋转因子 e^{-i 2 pi k / N} 黏合——这一步叫蝶形运算。每一半再各自被拆成两半，如此一路拆到底。因为你在大约以 2 为底的 log N 个层级上，每一层都把问题对半切，总工作量就从 N^2 坍缩成一个正比于 N log N 的数。

Cost of transforming N samples:

   direct DFT   ~  N * N         operations
   FFT          ~  N * log2(N)   operations

   N = 1,024          DFT ~ 1,000,000     FFT ~ 10,000     ( ~100x )
   N = 1,048,576      DFT ~ 1.1e12        FFT ~ 21,000,000 ( ~50,000x )

Idea (radix-2, Cooley-Tukey):
   X[k]   =  E[k]  +  w^k * O[k]
   X[k+N/2] = E[k] - w^k * O[k]        with  w = e^{-i 2 pi / N}
   where E = DFT of even-indexed samples,
         O = DFT of odd-indexed samples   (each of length N/2)
   recurse until length 1.

同样的 X[k] 值，两种代价。把偶点与奇点拆开并递归，使 N^2 变成 N log N——一种随 N 增大而无止境增长的加速，这正是为什么跑在现代信号处理底下的是 FFT，而非赤裸的 DFT。

别让*快速*这个词把你带偏：FFT 算出的 X[k] 与 DFT 分毫不差、精度相同——它是一种算法，不是一种近似。但代价的这一改变，才是让整套理论得以过日子的关键。正是这个 N log N 的 FFT，让你的手机能解码音乐、画出实时频谱、运行降噪、压缩照片、解调无线信号，而且全程只啜饮一点点电量。它还加速一些看似无关的事：因为一个域里的相乘就是另一个域里的卷积，一次 FFT、一次廉价的逐点相乘、再一次逆 FFT，就能把两个长信号卷积起来——甚至把两个巨大的整数相乘——远快于课本上的笨办法。当人们称 FFT 是有史以来最重要的算法之一时，他们指的就是这个。

把它串起来：从麦克风到频谱

退后一步，整条流水线读起来就是一个干净的故事，每一环都是你如今已经认识的工具。一个连续信号被一个模拟滤波器带限、以高于其奈奎斯特率的速率采样使得各份频谱拷贝不致重叠、被切成一个窗口并加锥以驯服泄漏、然后送进一个 FFT——它廉价而精确地交出连续傅里叶变换一直指向的那个离散频谱。用逆 FFT 与一个重建滤波器把每一支箭头反转过来，你就一路走回声音。前几篇的连续理论是那个梦；这条链子，是一台真实机器如何在那个梦里活着。

抗混叠。让连续信号通过一个低通滤波器，去掉预定奈奎斯特频率以上的一切，使采样定理的带限前提真正成立。
采样。以速率 f_s >= 2B（高于奈奎斯特率）测量，把曲线变成一串 x[0..N-1]，且不丢失信息。
加窗。把这 N 个采样点乘以一个平滑锥（汉宁、汉明），压制窗口接缝处的假跳跃，从而减少频谱泄漏。
变换。运行 FFT 以 N log N 的时间得到 X[0..N-1]；第 k 个频点对应频率 k 乘以 f_s / N，而对实信号而言只有到 N/2 为止的频点携带新信息。
解读（或反变换）。把幅度与相位读作频谱——或者对它们做处理后运行逆 FFT，再经一个重建滤波器，回到一个连续信号。

这就是整级一直在搭建、要通向的那座桥。连续的傅里叶变换告诉你频率内容*意味着什么*；采样定理告诉你*何时*一串有限的数字能把它保住；DFT 使这个想法可计算；而 FFT 使它便宜到一天可以跑十亿次。同一个家族——卷积定理、那把梳子、作为尖峰极限的狄拉克 delta——在每一步都反复现身，这正是为什么一门分析课能撑起一整门工程学科。手握这些，下一篇就推开通向这个变换更广阔亲属的门，它们各自为某种几何或某种对称而调音——那是朴素傅里叶变换没有为之而生的。