【DSP笔记 · 第3章】数字世界的“棱镜”：离散傅里叶变换（DFT）完全解析

数字世界的“棱镜”：离散傅里叶变换（DFT）完全解析

在上一章，我们探索了Z变换和离散时间傅里叶变换（DTFT）。我们知道，DTFT是一个无比强大的理论工具，它能将一个时域离散序列的“基因图谱”——也就是它的频谱——完整地揭示出来。理论上，只要我们知道了信号的DTFT，就知道了它包含的所有频率成分。

但这里有一个巨大的“但是”。DTFT是理论上的完美，却在实践中遇到了一个无法逾越的鸿沟：

1. DTFT的定义是针对无限长序列的。而在现实世界中，我们用计算机处理的信号，无论是音频、图像还是一段传感器数据，都必然是有限长度的。
2. DTFT计算出的频谱 $X(e^{j\omega })$ 是一个关于频率 $\omega$ 的连续函数。计算机天生只能处理离散的数据点，它无法存储和计算一个连续函数。

这就好比我们拥有一张描绘了整个地球的、精度无限的完美地图（DTFT），但我们的工具只是一台内存有限的普通电脑。我们不可能把整张地图装进电脑。我们该怎么办？

答案是：对地图进行采样！我们只在有限的区域内（信号的有限长度），选取有限个有代表性的地点（频谱的有限个点）来观察。这个为计算机量身定做的、从理论走向实践的“采样版”傅里叶变换，就是我们今天的主角——离散傅里叶变换（Discrete Fourier Transform, DFT）。

DFT是数字信号处理领域应用最广泛的工具，没有之一。从你的手机音乐播放器里的频谱显示，到通信系统中的调制解调，再到各种高效的滤波算法，背后都有DFT的身影。理解它，是你从理论学习迈向工程实践的决定性一步。

从理想到现实：DFT的诞生

让我们再次明确一下从完美的DTFT到实用的DFT，我们必须解决的两个核心问题：

1. 信号长度问题：我们无法处理无限长的信号 $x(n)$。解决方案：我们只截取信号中一段有限的长度，比如 $N$ 个点，来进行分析。
2. 频谱连续问题：我们无法计算连续的频谱 $X(e^{j\omega })$。解决方案：我们只在频谱的一个周期（通常是 $[0,2\pi )$）内，等间隔地计算 $N$ 个点的频谱值。

这两个解决方案合在一起，就构成了DFT的本质。

DFT的核心定义

对于一个长度为 $N$ 的有限长序列 $x(n)$（其中 $n=0,1,\dots ,N-1$），它的N点DFT定义为：
$$X(k)=\sum _{n=0}^{N-1}x(n)W_N^{kn},k=0,1,\dots ,N-1$$
相应地，从频域序列 $X(k)$ 恢复时域序列 $x(n)$ 的逆变换（IDFT）为：
$$x(n)=\frac{1}{N}\sum _{k=0}^{N-1}X(k)W_N^{-kn},n=0,1,\dots ,N-1$$
这里的 $W_N$ 是一个非常重要的符号，它被称为旋转因子（Twiddle Factor），其定义为：
$$W_N=e^{-j\frac{2\pi }{N}}$$
$W_N^k$ 代表了在复平面单位圆上，从(1, 0)点开始，按顺时针方向转过 $k$ 个 $2\pi /N$ 角度后到达的点。整个DFT的计算，本质上就是将时域信号 $x(n)$ 与这些在单位圆上旋转的点进行内积运算，从而衡量出信号在各个特定频率上的分量大小。

DFT与Z变换/DTFT的血缘关系

DFT并不是一个凭空冒出来的全新概念，它与我们在上一章学习的Z变换和DTFT有着深刻的血缘关系。

一个有限长序列 $x(n)$ 的Z变换为：
$$X(z)=\sum _{n=0}^{N-1}x(n)z^{-n}$$
它的DTFT则是Z变换在单位圆上的取值：
$$X(e^{j\omega })=X(z){|}_{z=e^{j\omega }}=\sum _{n=0}^{N-1}x(n)e^{-j\omega n}$$
现在，让我们在DTFT的频谱上，等间隔地采样N个点。采样点的频率为 ${\omega }_k=\frac{2\pi k}{N}$，其中 $k=0,1,\dots ,N-1$。将这个 ${\omega }_k$ 代入DTFT的公式：
$$X(e^{j{\omega }_k})=\sum _{n=0}^{N-1}x(n)e^{-j(\frac{2\pi k}{N})n}=\sum _{n=0}^{N-1}x(n)(e^{-j\frac{2\pi }{N}}{)}^{kn}=\sum _{n=0}^{N-1}x(n)W_N^{kn}$$
看！这个结果不就是我们定义的DFT $X(k)$ 吗？

所以，我们得出了一个至关重要的结论：
一个N点有限长序列的N点DFT，就是其DTFT（或Z变换）在单位圆上的N个等间隔采样点。

(上图展示了Z平面上的单位圆，DFT的计算就相当于在这个单位圆上等间隔地取N个点，并计算Z变换在这些点上的值。)

这个结论完美地将理论（DTFT/Z变换）与实践（DFT）联系在了一起。DFT通过在频域进行采样，成功地将一个连续的频谱问题转化为了一个计算机可以处理的离散问题。

DFT的“怪癖”：循环的魔咒

将无限和连续的世界强行压缩到有限和离散的世界，必然会带来一些“副作用”。DFT最核心、最独特，也最容易让初学者困惑的特性，就是它的隐含周期性（Implied Periodicity）。

当你对一个长度为N的序列 $x(n)$ 进行N点DFT时，DFT算法“看待”这个序列的方式，并不是一个孤立的、长度为N的片段。它会固执地认为，你给它的这个 $x(n)$，其实是一个周期为N的无限长周期序列中的一个主值周期。

(上隐含周期性：一个有限长序列被DFT看作是首尾相连的圆形序列，并进行周期延拓。)

这个“自作多情”的假设，给DFT的性质带来了深刻的影响，其中最关键的就是循环移位和循环卷积。

线性卷积 vs. 循环卷积：一个不小心就踩的“坑”

在上一章我们知道，LTI系统中信号的传递是通过线性卷积完成的，并且在频域上有一个优美的性质：时域的线性卷积对应频域的乘积。
$x(n)\ast h(n)⟷X(e^{j\omega })H(e^{j\omega })$

我们自然希望DFT也能保持这个美好的性质。但由于隐含周期性的存在，事情发生了变化。在DFT的世界里，时域的运算不再是线性的，而是循环的。

线性卷积的公式是：
$$y_L(n)=\sum _{k=-\infty }^{\infty }x(k)h(n-k)$$
而N点循环卷积的公式是：
$$y_C(n)=x(n)\otimes h(n)=\sum _{m=0}^{N-1}x(m)h((n-m{)}_N)$$
注意那个 $((n-m{)}_N)$，它表示对 $n-m$ 的结果进行模N运算（即取余数）。这就像在一个有N个刻度的时钟上做减法。例如，在8点循环卷积中，从第1个位置后退3个位置，不是到了-2，而是到了第6个位置（ $(1-3{)}_8=-2(\mathrm{mod}8)=6$ ）。

DFT的卷积定理说的是：
N点循环卷积对应N点DFT的乘积。
$$x(n)\otimes h(n)⟷X(k)H(k)$$
这带来了一个巨大的问题。我们通常想计算的是线性卷积，但如果我们直接计算两个序列的DFT，在频域相乘，再做IDFT，我们得到的将是循环卷积的结果。如果两个序列的长度不合适，循环卷积的结果会因为“周期性”的重叠（称为时间混叠）而变得面目全非，根本不是我们想要的线性卷积。

那么，我们还能用DFT来帮助我们计算线性卷积吗？
答案是肯定的，只要我们使用一个绝妙的技巧——补零（Zero-Padding）。

假设我们有两个序列，$x(n)$ 长度为 $M$，$h(n)$ 长度为 $P$。我们知道，它们的线性卷积结果 $y_L(n)$ 的长度将是 $L=M+P-1$。

快速线性卷积的正确步骤：

1. 确定长度: 计算出线性卷积结果的长度 $L=M+P-1$。
2. 补零: 将序列 $x(n)$ 和 $h(n)$ 的尾部都补上若干个零，使它们的长度都达到 至少为L 的新长度 $N$（为了后续FFT算法的效率，通常会选择一个大于等于L的2的幂次方作为N）。
3. DFT: 对补零后的两个序列做N点DFT，得到 $X(k)$ 和 $H(k)$。
4. 频域相乘: 计算 $Y(k)=X(k)\cdot H(k)$。
5. IDFT: 对 $Y(k)$ 做N点IDFT，得到最终的结果 $y(n)$。

通过补零，我们相当于把循环卷积的“时钟”刻度 N 拉得足够长，使得在一个周期内，翻转后的 $h(n)$ 与 $x(n)$ 进行卷积时，其“尾部”不会“从时钟的另一头绕回来”污染到“头部”。这样，在一个周期内计算出的循环卷积结果，就和线性卷积的结果完全一样了。

这个利用DFT（及其快速算法FFT）来计算线性卷积的方法，被称为快速卷积，是数字信号处理中最高效的卷积计算方法。

DFT的威力：从频谱分析到快速计算

掌握了DFT的定义和核心特性后，我们来看看它在实际工程中的两大应用。

应用一：数字频谱分析

DFT最直接的应用，就是作为一种频谱分析仪。只要我们将一段信号（比如一段录音）送入计算机，对其进行DFT，得到的 $X(k)$ 的幅度 $|X(k)|$ 就告诉了我们，这段信号在各个离散频率点 $f_k=k\cdot f_s/N$ 上的能量强度。这就像一个棱镜，将混合在一起的白光（时域信号）分解成赤橙黄绿青蓝紫的彩色光谱（频域信号）。

然而，我们必须清醒地认识到，这个“数字棱镜”并非完美，它会带来一些由“有限”观测所导致的必然误差：

• 频谱泄漏（Spectral Leakage）: 我们对信号的观测是有限的，这相当于给无限长的原始信号乘上了一个矩形“窗户”。这个操作在频域上会引起卷积，使得原本单一频率的尖锐谱线，“泄漏”成一个主瓣和多个旁瓣。这会导致我们探测到一些本不存在的频率分量，并可能掩盖掉一些微弱的真实信号。选择不同的窗函数（如汉宁窗、哈明窗）可以在主瓣宽度和旁瓣抑制之间进行权衡，以减小泄漏。

(上图展示了频谱泄漏效应。一个理想单频正弦波的频谱（左）应该是一个尖峰，但由于加窗截断，其实际DFT频谱（右）变成了一个有主瓣和多个旁-瓣的形状。)

• 栅栏效应（Picket-Fence Effect）: DFT只在N个离散的频率点上对真实频谱进行采样。如果一个信号的真实频率峰值恰好落在了两个采样点之间，那么我们在两个采样点上观测到的幅度都将低于真实峰值。这就像我们透过一个栅栏看风景，我们只能看到栅栏缝隙里的景象，可能会错过最精彩的部分。增加DFT的点数N（通过补零）可以加密“栅栏”的缝隙，更精确地找到峰值位置和大小。

应用二：快速卷积的基石

如前文所述，利用DFT进行快速卷积是其另一大核心应用。直接计算M点和P点序列的线性卷积，其计算复杂度大约是 $O(M\cdot P)$。而利用DFT（特别是下一章要讲的FFT算法）进行快速卷积，其计算复杂度大约是 $O(N\log N)$，其中 $N$ 是补零后的长度。当序列很长时，FFT方法的效率优势是压倒性的。

想象一下，在图像处理中，一个512x512的模糊核要对一张1920x1080的图像进行卷积滤波，如果用直接法计算，那将是天文数字。而利用2D-FFT进行快速卷积，则可以在几秒钟内完成。这背后全都是DFT的功劳。

DFT的出现，为我们打开了在频域对信号进行处理的大门，也为下一章的快速傅里叶变换（FFT）——这个被誉为20世纪最重要的算法之一——铺平了道路。FFT并不是一种新的变换，它只是实现DFT的一种极其高效的算法。没有DFT的理论基础，FFT就无从谈起。

总结：掌握DFT，掌握实践

今天，我们踏上了一段从理想到现实的旅程。我们理解到：

1. DFT是为计算机而生的傅里叶变换。它通过对信号时域和频域的同时“离散化”，解决了DTFT无法在计算机上实现的问题。
2. DFT是DTFT的采样。N点DFT的本质是在单位圆上对序列的Z变换（或DTFT）进行N点等间隔采样。
3. DFT的核心“怪癖”是隐含周期性。这导致了时域运算的“循环”特性，最典型的就是循环卷积。
4. 补零是关键技巧。通过对序列进行恰当的补零，我们可以利用DFT的循环卷积定理来高效地计算线性卷积，这就是快速卷积的原理。
5. DFT是强大的分析工具。作为数字频谱分析仪，它能揭示信号的频率构成，但我们也需警惕频谱泄漏和栅栏效应等实践中的问题。

DFT是连接理论与工程的坚固桥梁。掌握了它，你就不再仅仅是看着数学公式，而是真正拥有了用计算机分析和处理信号的利器。在下一章，我们将为这把利器装上一个强力马达——FFT算法，让它的威力发挥到极致。

---

习题

第1题 (概念题)

一位工程师说：“我用计算机直接计算了一个信号的DTFT频谱，发现它是一个连续的平滑曲线。” 这句话在严格意义上正确吗？为什么？

第2题 (计算题)

有两个长度为4的序列， x ( n ) = { 1 , 2 , 2 , 1 } x(n)=\{1, 2, 2, 1\} x(n)={1,2,2,1} 和 h ( n ) = { 1 , − 1 , 0 , 0 } h(n)=\{1, -1, 0, 0\} h(n)={1,−1,0,0}。请计算它们的4点循环卷积 $y_C(n)=x(n)\otimes h(n)$。

第3题 (应用题)

你希望使用DFT（以及未来的FFT）来计算两个有限长序列的线性卷积。第一个序列 $x_1(n)$ 的长度为30个点，第二个序列 $x_2(n)$ 的长度为20个点。为了得到正确的结果，你需要对这两个序列进行补零，然后进行DFT。请问，你选择的DFT点数N最小应该是多少？

---

答案

第1题答案:

这句话在严格意义上不正确。

原因: 计算机无法直接计算或存储一个真正的连续函数。DTFT的频谱 $X(e^{j\omega })$ 是一个关于连续变量 $\omega$ 的函数。这位工程师看到的“连续平滑曲线”实际上是计算了大量点的DFT（例如，对原信号大量补零后做DFT），然后在绘图时将这些密集的离散点用直线连接起来，从而在视觉上产生了连续的效果。其本质仍然是离散点，而不是真正的连续函数。

第2题答案:

我们可以使用定义法计算。循环卷积 $y_C(n)={\sum }_{m=0}^{3}x(m)h((n-m{)}_4)$。

• $y_C(0)=x(0)h(0)+x(1)h(-1{)}_4+x(2)h(-2{)}_4+x(3)h(-3{)}_4$
  $=x(0)h(0)+x(1)h(3)+x(2)h(2)+x(3)h(1)$
  $=(1)(1)+(2)(0)+(2)(0)+(1)(-1)=1-1=0$

• $y_C(1)=x(0)h(1)+x(1)h(0)+x(2)h(-1{)}_4+x(3)h(-2{)}_4$
  $=x(0)h(1)+x(1)h(0)+x(2)h(3)+x(3)h(2)$
  $=(1)(-1)+(2)(1)+(2)(0)+(1)(0)=-1+2=1$

• $y_C(2)=x(0)h(2)+x(1)h(1)+x(2)h(0)+x(3)h(-1{)}_4$
  $=x(0)h(2)+x(1)h(1)+x(2)h(0)+x(3)h(3)$
  $=(1)(0)+(2)(-1)+(2)(1)+(1)(0)=-2+2=0$

• $y_C(3)=x(0)h(3)+x(1)h(2)+x(2)h(1)+x(3)h(0)$
  $=(1)(0)+(2)(0)+(2)(-1)+(1)(1)=-2+1=-1$

所以，4点循环卷积的结果是 y C ( n ) = { 0 , 1 , 0 , − 1 } y_C(n) = \{0, 1, 0, -1\} yC​(n)={0,1,0,−1}。

第3题答案:

线性卷积结果的长度为 $L=M+P-1$。
在这里，$M=30$, $P=20$。
所以，线性卷积结果的长度 $L=30+20-1=49$。

为了使用DFT/FFT计算线性卷积而不产生时间混叠，补零后的长度（即DFT的点数N）必须大于或等于线性卷积结果的长度L。
所以，DFT点数N的最小值是 49。

（在实际应用中，为了利用FFT算法的高效性，通常会选择大于等于49的第一个2的幂次方，即 $N=64$。）