DSP-8 有限长离散变换(Part+I)

🌟 欢迎来到第8讲：有限长离散变换 (Part I)

#

(对应课本第五章内容)

到目前为止，我们已经学习了多种傅里叶变换，它们分别处理连续/离散、周期/非周期的信号。但它们都有一个共同点：至少在一个域（时域或频域）是连续或无限的，这使得它们无法直接在计算机上进行数值计算。

本讲，我们将学习离散傅里叶变换 (DFT)，这是一种在时域和频域都是离散且有限长的变换。DFT是数字信号处理领域应用最广泛的工具，是连接理论分析与计算机实现的桥梁。我们还将探讨由于这种"双重离散有限"特性而引入的全新运算——圆周卷积。

核心学习目标:

1. 理解DFT：掌握DFT的定义，明白它是如何从DTFT通过频域采样得到的。
2. 掌握DFT与DTFT的关系：深刻理解"频域采样等效于时域周期延拓（混叠）“这一核心对偶关系。
3. 熟悉有限长序列运算：掌握圆周移位和圆周卷积的概念与计算方法。
4. 运用DFT实现线性卷积：学习如何通过补零，利用DFT的快速算法（FFT）来高效计算线性卷积。

📚 本讲知识地图

#

📝 本讲主要内容

#

1. 离散傅里叶变换 (Discrete Fourier Transform, DFT)

#

1.1 ✨ 为什么需要DFT？

#

我们在信号与系统中学到的傅里叶变换，在计算机看来都有"硬伤”： * CTFT：时域和频域都连续，计算机无法处理。 * DTFT：时域离散，但频域是连续的周期函数，计算机仍无法存储和计算。

计算机需要的是在时域和频域上都是离散且有限长的数据。DFT正是为此而生。

1.2 🔧 DFT的定义：从DTFT到DFT

#

• 核心思想：获得DFT最直观的方式，就是对DTFT的频谱进行均匀采样。

• 生动比喻：想象一下DTFT的频谱 $X(e^{j\omega})$ 是一幅平滑、连续的360度全景星空图。我们无法把整幅图都存入电脑，但我们可以用相机对着星空图，等间隔地拍摄N张照片。这N张照片（采样点）的集合，就是DFT。只要照片数量N足够多，我们就能很好地了解整个星空的样貌。

• 数学定义： 对于一个长度为N的有限长序列 $x[n]$ ( $0 \le n \le N-1$ )，其N点DFT定义为： $$ X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}, \quad 0 \le k \le N-1 $$ 其逆变换 (IDFT) 为： $$ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-kn}, \quad 0 \le n \le N-1 $$

  • 关键符号：旋转因子 (Twiddle Factor) $W\_N$ $$ W_N = e^{-j\frac{2\pi}{N}} $$ 它代表了复平面单位圆上的一个基本旋转角度，DFT的计算本质上是序列与不同旋转因子的幂次相乘求和。

• 矩阵形式：DFT和IDFT可以表示为矩阵运算，这在理论推导和硬件实现中很有用。 $$ \mathbf{X} = \mathbf{D}_N \mathbf{x} \quad \text{and} \quad \mathbf{x} = \mathbf{D}_N^{-1} \mathbf{X} = \frac{1}{N}\mathbf{D}_N^* \mathbf{x} $$ 其中 $\mathbf{D}\_N$ 是N×N的DFT矩阵，其元素为 $W\_N^{kn}$。

1.3 💻 DFT的计算与MATLAB实现

#

DFT的直接计算复杂度为 $O(N^2)$。但在实际中，我们几乎总是使用快速傅里叶变换 (FFT) 算法，其复杂度仅为 $O(N\log N)$，这使得大规模DFT计算成为可能。

• MATLAB 函数：

  % 计算序列x的N点FFT (DFT)
  % 如果N > length(x)，则对x补零
  % 如果N < length(x)，则截断x
  X = fft(x, N); 
  
  % 计算频谱X的N点IFFT (IDFT)
  x = ifft(X, N);

• MATLAB 示例代码：

  % Editor - E:\MATLAB701\work\DFTexample.m
  % 计算序列的DFT
  N=input('输入序列的长度=');
  M=input('输入离散傅立叶变换长度=');
  u=[ones(1,N)];
  U=fft(u, M);
  figure();
  t=0:1:N-1;
  stem(t,u);
  title('原始时域序列');
  xlabel('时间序号n');ylabel('振幅');
  figure();
  subplot(2,1,1);
  k=0:1:M-1;
  stem(k, abs(U));
  title('DFT抽样点的幅度');
  xlabel('频率序号k');ylabel('幅度');
  subplot(2,1,2);
  stem(k, angle(U));
  title('DFT抽样点的相位');
  xlabel('频率序号k');ylabel('相位');

  • 代码说明：这段代码首先获取用户定义的序列长度N和DFT长度M，生成一个单位幅度的序列u，然后调用fft函数计算其M点DFT。最后，使用stem函数分别绘制了DFT结果的幅度和相位谱。

2. 核心关系：频域采样与时域周期延拓

#

2.1 ✨ 核心对偶关系

#

• 专业定义：对一个非周期序列 $x[n]$ 的DTFT频谱 $X(e^{j\omega})$ 进行N点均匀采样，得到DFT序列 $Y[k]$。对 $Y[k]$ 进行IDFT得到的时域序列 $y[n]$，并不是原始的 $x[n]$，而是 $x[n]$ 以N为周期的无限周期延拓序列。 $$ y[n] = \sum_{m=-\infty}^{\infty} x[n - mN] $$
• 生动比喻：再次回到全景星空图（DTFT）和N张照片（DFT）的比喻。当你只用这N张照片来"重构"星空时，计算机并不知道这是一个完整的360度全景。它会认为你给它的就是全部信息，并想当然地把这N张照片首尾相连，无限地复制下去，形成一个重复的、周期的"星空壁纸"。这个"壁纸"就是时域的周期延拓序列。

【图片：DTFT和DFT的关系示意图，展示频域采样和时域周期延拓的对应关系 (参考PPT P18)】

2.2 ⚠️ 时域混叠 (Time-Domain Aliasing)

#

从上述关系可以看出，如果原始序列 $x[n]$ 的长度 $L$ 大于DFT的点数 $N$，那么在周期延拓求和时，序列的"尾部"会和下一个周期的"头部"发生重叠，这就是时域混叠。 * 无混叠条件：为了能从IDFT的结果 $y[n]$ 中无失真地恢复出原始序列 $x[n]$，必须保证DFT点数 $N$ 不小于 原始序列的长度 $L$，即 $N \ge L$。

3. 有限长序列的周期运算

#

由于DFT内在的周期性，它引出了一套与线性运算不同的"圆周"或"周期"运算。

3.1 🔄 序列的圆周移位 (Circular Shift)

#

• 定义：对一个N点序列 $x[n]$ 进行的移位，其结果仍然被限制在 $[0, N-1]$ 的范围内。移出边界的部分会从另一端"卷回来"。
• 生动比喻：想象这N个点均匀地分布在一个钟表的表盘上。圆周移位就像是转动这个表盘，点永远不会离开表盘，只是位置发生了周期性的变化。
• 公式：$x((n-n\_0))\_N$ 表示将 $x[n]$ 圆周右移 $n\_0$ 位。

【图片：圆周移位示意图，展示序列点在圆环上的移动 (参考PPT P29)】

3.2 ⚙️ 序列的圆周卷积 (Circular Convolution)

#

• 定义：这是由DFT的乘积性质自然导出的卷积形式。 $$ \text{DFT}\{x_1[n]\} \cdot \text{DFT}\{x_2[n]\} = \text{DFT}\{x_1[n] \text{ N } x_2[n]\} $$ 其中 $\text{ N }$ 表示N点圆周卷积。
• 生动比喻：
  • 线性卷积：像是在一条无限长的传送带上，一个模板（$h[n]$）滑过一个物件（$x[n]$），计算每时每刻的重叠面积。结果的长度是 $L+M-1$。
  • 圆周卷积：像是一个有N个齿的旋转齿轮（$h[n]$的反转序列）与另一个有N个齿的固定齿轮（$x[n]$）啮合。每旋转一格，就计算一次啮合齿对应值的乘积和。结果的长度仍然是N。
• 与线性卷积的关系：
  • 通常情况下，圆周卷积 ≠ 线性卷积。圆周卷积的结果是线性卷积结果发生时域混叠后的产物。
  • 关键应用：如果对两个长度分别为L和M的序列，在进行DFT前先补零至长度 $N \ge L+M-1$，那么它们N点圆周卷积的结果将与线性卷积完全相同！

【图片：线性卷积与圆周卷积的关系图，对比补零前后的结果 (参考PPT P33)】

🔗 知识关联与应用

#

• 承上启下：DFT是我们整个傅里叶变换理论体系的终点，也是通往实际应用的起点。它将我们之前学习的连续、无限的理论，转化为了计算机可以执行的有限、离散的算法。圆周卷积的概念，正是理解DFT内在周期性的关键。

• 现实应用：

  1. 快速卷积：直接计算两个长序列的线性卷积非常耗时（复杂度 $O(L \cdot M)$）。但我们可以利用DFT：先将序列补零到 $N \ge L+M-1$，然后做N点FFT，在频域相乘，再做IFFT。整个过程利用FFT的效率，复杂度仅为 $O(N\log N)$。这在音频处理、图像滤波等领域是标准操作。
  2. OFDM通信：现代通信系统（如Wi-Fi, 4G/5G）广泛使用OFDM技术。其核心就是利用IFFT和FFT来高效地实现多路信号的调制和解调。系统巧妙地利用了圆周卷积的特性，通过添加循环前缀（Cyclic Prefix）来对抗信道延迟带来的符号间干扰。

🤔 引导式提问

#

1. 为什么说"频域采样"和"时域周期延拓"是同一枚硬币的两面？ 请尝试从DFT和IDFT的求和公式中寻找线索。
2. 既然DFT的乘积对应的是圆周卷积，而我们工程中通常需要的是线性卷积，这是否意味着DFT的卷积定理"用处不大"？ 我们是如何"欺骗"DFT来为我们计算线性卷积的？
3. 计算一个1024点序列的DFT，直接计算和使用FFT算法，在计算量（复数乘法次数）上大约会相差多少倍？ （提示：对比 $N^2$ 和 $N\log\_2 N$）

💡 本讲总结

#

今天，我们踏入了数字信号处理的实践核心——DFT。 * DFT是为计算机而生的：它在时域和频域都是离散且有限的，是所有傅里叶分析工具中唯一可以直接进行数值计算的。 * DFT是DTFT的采样版本：这个关系是理解DFT所有特性的基石。 * 周期性是DFT的灵魂（也是"诅咒"）：频域采样不可避免地导致了时域的周期性，这引入了圆周移位和圆周卷积等新概念。 * 圆周卷积不等于线性卷积：除非进行了充分的补零。这个技巧是利用DFT（通过FFT算法）实现高效线性滤波和卷积的关键。

🔍 相关缩写

#