5 Discrete Fourier Transform
迎着阳光盛大逃亡。
TIP
带 * 内容不在考试范围内。
章节目录
- 章节目录
- 5-1 * 正交变换 Orthogonal Transforms
- 5-2 离散傅里叶变换 Discrete Fourier Transform, DFT
- 5-3 DFT 和 DTFT 的关系
- 5-4 有限序列的运算
- 5-5 * 有限序列的分类
- 5-6 DFT 性质
- 5-7 DFT 定理
- 5-8 * 傅里叶域滤波 Fourier-Domain Filtering
- 5-9 * 实序列计算 DFT
- 5-10 使用 DFT 计算线性卷积
5-1 * 正交变换 Orthogonal Transforms
5-1-1 * 正交变换的一般形式 General Form
1. 正交变换 Orthogonal Transforms
正交变换是一类在信号处理、数据分析和线性代数中至关重要的线性变换。其核心特征是保持向量的内积不变，从而完美保留了数据的几何结构。
对于任意两个向量
其中
正交变换具有以下重要特性：
- 保长度（保范数）：
- 保夹角：变换后任意两个向量的夹角保持不变
- 保正交性：原本正交（垂直）的向量对，变换后依然正交
2. 正交变换的一般形式
一个一般形式的正交变换对可表示为：
分析式 Analysis Equation：
合成式 Synthesis Equation：
TIP
5-1-2 * 离散傅里叶级数 Discrete Fourier Series, DFS
假设有一个周期 DT 信号：
我们选用如下正交函数集对其进行变换：
为了简化表达式，我们定义核函数 Kernel
综上，可得变换对：
即离散傅里叶级数 Discrete Fourier Series, DFS。
其变换可以简单记为：
NOTE
在 DFS 中，基函数
具有以下几个基本性质：
- 时域周期性：对固定的
， 关于 的周期为 。 - 直流与谐波含义：
表示第 个谐波分量。 - 正交性：不同的基函数在一个周期内两两正交，即
这保证了不同频率分量可以被独立分离。 - 频域索引周期性：
也是以 为周期重复的，因此只需考虑 - DFS 变换对：周期序列
与其 DFS 系数 构成一一对应关系： 即可通过 DFS 分析，也可通过 IDFS 重建原序列。
5-1-3 常见 DFS 变换对
| 时域序列 | 频域序列 | 说明与条件 |
|---|---|---|
| 单位采样序列， | ||
| 常数序列， | ||
| 复指数序列， | ||
| 余弦序列 | ||
| 正弦序列 | ||
| 有限长指数序列， | ||
| 斜坡序列 | ||
| 矩形脉冲： | Dirichlet 核形式； |
5-2 离散傅里叶变换 Discrete Fourier Transform, DFT
5-2-1 DFT 的定义
直接给出 DFT 和 IDFT 的计算公式：
TIP
我们注意到一点：DFT 和 DFS 在形式上 完全相同。
也就是说，DFT 的过程暗含了对原始有限序列的周期延拓，这是 DFT 的数学结构所决定的。
同时也不难想到，一段 DFT 序列是无法被区分来自有限序列还是它的周期延拓。
5-2-2 矩阵关系 Matrix Relation
再次观察 DFT 的计算公式：
我们发现该公式的一个特点，即求序列的 DFT 在计算上等效为对
同时等号左右两侧均为序列运算，因此自然地想到将
；同理， IDFT可写为：
。
其中，两矩阵分别为：
和
TIP
这样的形式说明 DFT 是一个 坐标变换 / 基变换。
可以这样理解：
是信号在“时域标准基”下的坐标； 是信号在“傅里叶基”下的坐标； 就是从时域坐标变到频域坐标的变换矩阵。
两矩阵间存在如下运算关系：
NOTE
这一性质很重要，因为它表明：
- DFT 矩阵是可逆的；
- DFT 的逆运算结构非常简单；
- 构成 DFT 的复指数基之间彼此正交。
如果进一步把 DFT 矩阵归一化为
那么
这在线性代数和信号处理中都非常重要。
5-3 DFT 和 DTFT 的关系
5-3-1 从 DTFT 得到 DFT
在 DTFT 的频谱上，以
1. 数学证明
首先，我们有 DTFT 的表达式：
由于 DFT的操作对象是有限长序列，假设其序列分布在区间
然后，对
带入可得
证毕。
2. 在复数坐标上的理解
由于 DTFT 为一个周期为
而 DFT 就是以
5-3-2 插值 DFT 以得到 DTFT
在 Chapter 3 II 中，我们已经证明了一个模拟信号在恰当的采样条件下，其采样所得的离散序列携带着原模拟信号的全部信息，可以通过恰当的方式完美恢复出原始信号。
而上一小节又提及 DFT 可以视作对 DTFT 在频域的等距采样。也就是说，采用类似的方法，在一定条件下，直觉上我们可以通过某些方式从 DFT 序列中恢复出 DTFT 频域信息。
1. 数学证明
对于长度为
由 IDFT 公式
代入上式，可得
交换求和次序，得到
有
于是可写成
定义插值核
则有
基于上述推导，我们证明了 DTFT 可由 DFT 的加权和完全恢复。
5-3-3 DTFT 采样
对一个长度为 M 的离散序列及其 DTFT ，考虑如下操作：
对频域表达式进行 N 点采样：
再对采样后的序列做 IDFT：
这里得到的新序列与原序列的关系为：
把 DTFT 在频域上每隔
NOTE
对于
分两种情况：
当
原序列在按周期折叠时不会发生重叠，因此 即频域采样后再做 IDFT，可以无失真恢复原序列这一段。
当
原序列中相隔的样本会折叠到同一个位置并相加，因此 此时会发生 时域混叠 Time-domain Aliasing，原序列不能由
唯一恢复。
5-3-4 DTFT v.s. DFS v.s. DFT
| Time domain | Transform | Frequency domain |
|---|---|---|
| Continuous Aperiodic | CTFT | Continuous Aperiodic |
| Continuous Periodic | FS | Discrete Aperiodic |
| Discrete Aperiodic | DTFT | Continuous Periodic |
| Discrete Periodic | DFS | Discrete Periodic |
5-4 有限序列的运算
有限序列中主要有三种循环运算：
- Circular Shift：循环移位
- Circular Reversal：循环反转
- Circular Convolution：循环卷积 / 圆卷积
在讲解之前，我们定义如下运算:
即取模运算 Modulo Operation，计算除以
5-4-1 循环移位 Circular Shift
我们定义循环移位操作：
也就是当进行移位时，用另一侧的序列填补移位造成的空白部分。
5-4-2 循环反转 Circular Reversal
循环反转数学定义为
TIP
实际上，循环移位和循环反转都可以用以下步骤进行：
- 将
以序列长度 为周期， 延拓为周期函数 - 进行正常的线性移位 / 反转
- 只取
（假装他是个周期函数）
5-4-3 循环卷积 / 圆卷积 Circular Convolution
1. 定义
假设有两个有限序列
首先看线性卷积：
熟悉地，这个卷积会得到一个长度为
通过与前面类似的定义，有圆卷积：
而这个操作会得到一个长度为
NOTE
对于两个长度不同的序列，不能脱离长度参数直接圆卷积。圆卷积本质上是
设
和
它们的长度分别为
这也是为什么在 DFT/FFT 体系里，频域逐点相乘对应的不是线性卷积，而是圆卷积；因为 DFT 默认把序列看成周期为
2. 圆卷积的矩阵表示
再次观察圆卷积的数学定义：
与 DFS 类似，可以将圆卷积看作一个
简单记为：
其中：
5-5 * 有限序列的分类
5-5-1 * 基于共轭对称 Conjugate Symmetry
1. 循环共轭对称 / 循环共轭反对称
定义：
- 循环共轭对称：
- 循环共轭反对称:
2. 信号的对称表示
一个
其中
一个
其中
5-5-2 * 基于几何对称 Geometric Symmetry
1. 两种常用的几何对称定义
- 对称序列 Symmetric Sequence：关于中点左右两边的样本相等。
- 反对称序列 Antisymmetric Sequence：关于中点左右两边的样本大小相等、符号相反。
因为序列长度
2. 四种几何对称的类型
通常分为以下四类：
- Type 1: Symmetric, odd length
- Type 2: Symmetric, even length
- Type 3: Antisymmetric, odd length
其中中间点必须满足
- Type 4: Antisymmetric, even length
5-6 DFT 性质
| 类别 | 长度为 | |
|---|---|---|
| 复序列 | ||
| 复序列 | ||
| 复序列 | ||
| 复序列 | ||
| 复序列 | ||
| 复序列 | ||
| 复序列 | ||
| 实序列 | 实序列 | |
| 实序列 | ||
| 实序列 | ||
| 实序列的频域对称关系 | ||
| 实序列的频域对称关系 | ||
| 实序列的频域对称关系 | ||
| 实序列的频域对称关系 | ||
| 实序列的频域对称关系 |
NOTE
5-7 DFT 定理
设长度为
则常见性质可写为：
| 性质类型 | 长度为 | |
|---|---|---|
| 线性性 Linearity | ||
| 圆周时移 Circular Time-shifting | ||
| 频移 Frequency-shifting | ||
| 对偶性 Duality | ||
| 圆卷积 Circular Convolution | ||
| 调制 Modulation | ||
| 帕塞瓦尔关系 Parseval's relation |
其中
且
5-8 * 傅里叶域滤波 Fourier-Domain Filtering
频域滤波是指先将离散时间信号变换到频域，在频域中通过乘以滤波器的频率响应来抑制或去除不需要的频率分量，然后再变换回时域得到滤波结果。其理论基础是卷积定理：
实际中常用 DFT/FFT 实现频域滤波，因为频域乘法比时域直接卷积更高效。
若
需要注意的是，基于 DFT 的滤波由于有限长度和离散频域采样，往往会带来一些小波纹；若零填充不足，还可能得到圆卷积而不是线性卷积。
5-9 * 实序列计算 DFT
前面的推导，计算和性质中， DFT 大多是以处理复序列为目的。
然而在实际应用中， DFT 处理的对象一般为实序列 Real Sequence。
对实序列做 DFT 时，注意到其有一非常美丽的性质，即共轭循环对称性：
通过这种性质，我们可以使用一些优雅且巧妙的方式，简化实际计算中的 DFT 。
5-9-1 * 两个实序列共用一次 N 点 DFT
考虑两个长度均为
打包成复序列，做一次 N 点 DFT：
由于
于是可以把它们从
5-9-2 * 用一次 N 点 DFT 求一个 2N 点实序列的 DFT
现设有一个长度为
它的
可以将它拆成两个长度为
其中：
是偶序号样本序列 是奇序号样本序列
则有关系式
其中
这说明，一个
- 偶序列
的 点 DFT - 奇序列
的 点 DFT - 再乘以旋转因子组合起来
这实际上就是将长序列的 DFT 分解成更短 DFT 的基本思想，也是 FFT 偶奇分解的核心形式之一。
5-10 使用 DFT 计算线性卷积
5-10-1 两个有限长序列的线性卷积
有限序列的 DFT 天然对应的是圆卷积，因此如果直接对两个序列做卷积再求和，只会得到圆卷积的结果。因此如果我们想要使用 DFT 计算两个序列的线性卷积，就需要一些特殊的步骤。
考虑如下两个有限序列，其长度分别为
- 将两个序列进行补零，直到二者长度相同且满足：
，通常取等号。
- 分别做
- 对结果做 IDFT ，得到线性卷积结果。
上述计算过程可表示为
TIP
使用这种方法计算线性卷积的原理为：
只要 DFT 长度满足
圆卷积就不会发生混叠，于是圆卷积结果就等于线性卷积。
5-10-2 循环前缀 The Cyclic Prefix
DFT / IDFT 天然对应的是 圆卷积，但真实信道或普通滤波通常产生的是 线性卷积。 循环前缀的目的，就是想办法让“接收端关心的那一段线性卷积结果”看起来像“圆卷积结果”，这样就可以直接用 DFT 在频域里做简单乘法处理。
把一个长度为
经过信道后，时域输出本来是输入序列与信道冲激响应的线性卷积：
若循环前缀长度足够长，通常满足
其中
因此在频域中可写成
这说明循环前缀的关键作用是：把原本复杂的时域线性卷积，转化为频域中的逐点相乘。这样接收端只需要做 DFT、频域乘法和 IDFT，就能高效完成信道作用或均衡处理。这也是循环前缀在 OFDM 等多载波通信中非常重要的原因。
5-10-3 有限长序列和无限长序列卷积
当输入信号
也就是要计算
其中
这种情况下，不能直接把整条
- 重叠相加 Overlap-Add
- 重叠保留 Overlap-Save
1. 重叠相加 Overlap-Add
Overlap-Add 的思想是：将输入序列分成若干个互不重叠的短块，每一块分别与
设每块输入长度为
其中每个子序列
由于
最后总输出写成
相邻两个子输出之间会有
特点：
- 输入分块之间不重叠
- 输出分块之间会重叠
- 重叠部分需要相加
2. 重叠保留 Overlap-Save
Overlap-Save 的思想是：将输入序列分成彼此重叠的块，对每一块做圆卷积，然后保留其中与线性卷积一致的部分，丢弃被混叠污染的部分。
设滤波器长度为
由于圆卷积会产生时域混叠，因此每块输出的前
特点：
- 输入分块之间有重叠
- 输出块不需要相加
- 每块前面的污染部分直接丢弃
- 只保留后面正确的部分