计算机接收有限个数,而周期函数有无穷多个傅里叶(Fourier)系数。离散傅里叶变换(DFT)是有限列表的精确坐标变换,却不会自动恢复产生该列表的函数的全部系数:相差采样点数整数倍的频率,在网格上无法区分。
我们先固定归一化并证明有限代数,再推导快速分解,并在允许交换采样与无穷级数的假设下证明混叠公式。实线上的带限采样定理属于另一种情形;这里每个频率都是整数,指标按有限采样点数取模。
有限傅里叶坐标
定义 1.11.1
(离散傅里叶变换)
对 ,令 。向量 的离散傅里叶变换是向量 ,其中
超出该范围的指标按模 理解。
关键的有限正交性恒等式是
余数不同时,公比 ,和为 ;余数相同时,每项都为一。求和指标改名为 而非 时,同一恒等式仍成立。
定理 1.11.2
(DFT 反演、帕塞瓦尔(Parseval)公式与循环卷积)
采用上述归一化,
定义循环卷积
它的 DFT 是逐点乘积 。
证明
(正交性与指数的周期性)
代入并重排有限和得 。同理 。因此 DFT 矩阵除以 后为酉矩阵。
对于卷积,令 (模 )并重新排列有限求和:
证明透视
每个恒等式从哪里来
反演与帕塞瓦尔公式各使用一次正交关系 (1),都是对频率指标 求和:反演时指数之差为 ,帕塞瓦尔公式中为 。两种情形都只有对角项留下,每项贡献 ,再由因子 抵消。
卷积恒等式完全不用正交性。它的关键一步是按模 重新编号 ;这之所以合法,只因 只依赖于 模 的值:由 ,即使 ,也有 。卷积必须是循环卷积,正是出于这一点;若用普通卷积,绕回的项会落在错误的指标上。所有求和都是有限的,每次重排都无需论证。下面的混叠证明恰恰在这里不同:把无穷级数代入 DFT 求和需要绝对收敛。
出现在反演和帕塞瓦尔公式中,而不在这里的卷积定义中。若采用酉归一化,即把变换除以 ,这些因子的分配就会不同,卷积恒等式中也会出现 。
概念视角代数
DFT 把循环矩阵对角化
与固定的 作卷积,就是由循环矩阵 给出的线性映射 。对每个 ,令 。按模 代入 ,
因此由 (1) 两两正交的 个向量 是每个循环矩阵的公共特征向量,特征值为 。卷积定理正是说:DFT 是换到这组特征向量的基变换;在新坐标下,卷积变成乘以一个对角矩阵。
二进制分解
令 。把数据分成偶数与奇数指标,计算长度为 的变换
对 ,
事实上,,而 。又 、,但把 换成 会使奇数前因子变号。当 时,递归分解直到长度为一。取 ,并将旋转因子预先计算或计入每层线性工作量,算术运算数满足 ,故为 次复运算;直接计算每个和则需 。这是通常模型下的运算次数,不是舍入误差保证。
例题 1.11.3
(四点变换)
对 、,
例如,偶数子序列 的变换为 ,奇数子序列 的变换为 。由 (2),、,、。帕塞瓦尔公式检验比例:,而 。
例题 1.11.4
(循环卷积与普通卷积)
取 、,循环卷积为 。此例中其支撑没有绕回,因此与普通有限卷积一致。相反, 与 的循环卷积为 :指标 按模四绕回零。
更一般地,长度为 的序列补零到长度 后,循环卷积在指标 与普通线性卷积一致,其后为零:每个非零指标和至多为 ,所以不会绕回。若补零不足,相差 的指标项会相加。
采样周期傅里叶级数
设连续 周期函数 的实际傅里叶系数绝对可和,因此
其傅里叶级数一致收敛,傅里叶唯一性将其和与 等同。取样本 ,令 为 的 DFT 乘以 。有符号频率 与频点 对应;大于 的指标可表示负频率。
定理 1.11.5
(精确混叠公式)
对每个整数 ,
特别地,若 是支撑在 的三角多项式且 ,每个这样的系数可由 恢复,其中 。当 ,两个端点频率 相互重合。
证明
(采样识别余数类)
绝对一致收敛允许把傅里叶级数代入有限 DFT 求和:
由 (1),内层和在 时为一,否则为零,证明 (3)。若 且 ,则非零差 的绝对值小于 ,故两个不同支撑频率不能属于同一余数类。当 ,,该结论失效。
由 (3) 可得一个有用的定量形式。若某个 使 ,则系数绝对可和;对有符号代表 ,有
事实上,对 有 。有限常数依赖于 ,这是绝对误差界。在 附近,混叠系数可能与目标系数同阶;即使远离此处,若没有目标系数的下界,也不能推出相对精度。没有先验假设,它不能从样本中恢复未被区分的频率。
例题 1.11.6
(高频伪装成低频)
在八个等距点采样 。由于 , 的样本与 相同。函数 产生同样数据,尽管它与 在样本之间不同。没有额外频率信息,DFT 无法区分二者。
下面的互动图可选取样本数 与至多四个项,并把精确预测 与直接 DFT 相比,同时显示与之有相同样本的混叠函数。
采样把频率折叠进余数类
选定实三角多项式 f 与样本数 N,在 x_j = 2πj/N 采样。每个频率 n 落在频点 n mod N,因此 d_k 等于所有 n ≡ k(mod N)的 f̂(n) 之和。把精确预测与直接 DFT 相比,并查看与 f 有相同样本的混叠函数 g。
f = cos 5x + (1/2) sin 2x
混叠函数 g = cos 3x + (1/2) sin 2x
下表以数字给出同样数据。实线与虚线在每个样本点相交。
| 频点 k | 预测:n ≡ k 的 f̂(n) 之和 | 计算所得 d_k | 贡献的 n |
|---|---|---|---|
| 0 | 0 | 0.0000 + 0.0000i | — |
| 1 | 0 | 0.0000 + 0.0000i | — |
| 2 | -i/4 | 0.0000 - 0.2500i | 2 |
| 3 | 1/2 | 0.5000 + 0.0000i | -5 |
| 4 | 0 | 0.0000 + 0.0000i | — |
| 5 | 1/2 | 0.5000 + 0.0000i | 5 |
| 6 | i/4 | 0.0000 + 0.2500i | -2 |
| 7 | 0 | 0.0000 + 0.0000i | — |
样本
| j | x_j / 2π | f(x_j) | g(x_j) |
|---|---|---|---|
| 0 | 0 | 1.0000 | 1.0000 |
| 1 | 1/8 | -0.2071 | -0.2071 |
| 2 | 1/4 | 0.0000 | 0.0000 |
| 3 | 3/8 | 0.2071 | 0.2071 |
| 4 | 1/2 | -1.0000 | -1.0000 |
| 5 | 5/8 | 1.2071 | 1.2071 |
| 6 | 3/4 | 0.0000 | 0.0000 |
| 7 | 7/8 | -1.2071 | -1.2071 |
- 样本数 N
- 8
- 最大频率 K
- 5
- 条件 N > 2K
- 否
- 被两个或以上频率落入的频点
- 无
- 对每个 |n| ≤ K 有 d_{n mod N} = f̂(n)
- 否
- 所有样本为零
- 否
- g 作为函数与 f 不同
- 是
- |计算值 − 预测值| 的最大值
- < 10⁻⁹
f = cos 5x + (1/2) sin 2x; N = 8; K = 5; 条件 N > 2K: 否; 被两个或以上频率落入的频点: 无; 对每个 |n| ≤ K 有 d_{n mod N} = f̂(n): 否. 没有频点收到两个频率,但某个 |n| ≤ K 的频点 n mod N 装的是另一个频率的系数,故把 d_{n mod N} 读作 f̂(n) 是错的,g 取代了 f。
表格为何是这个样子
把 f(x) = Σ f̂(n) e^{inx} 代入 d_k = (1/N) Σ_j f(x_j) e^{−2πijk/N},得 Σ_n f̂(n) · (1/N) Σ_j e^{2πij(n−k)/N}。
内层和在 n ≡ k(mod N)时为 1,否则为 0,所以 d_k = Σ_m f̂(k + mN):正是“预测”一列中的和。
若所有频率满足 |n| ≤ K 且 N > 2K,两个不同频率相差小于 N,不会有相同余数。当 N = 2K 时,频率 K 与 −K 的余数相同。
混叠函数 g 把每个频率 n 换成满足 r ≡ n(mod N)且 |r| ≤ N/2 的代表 r。由于 e^{inx_j} = e^{irx_j},g 与 f 有相同的样本。
自我检查
取 N = 8 的 cos 4x:频点 4 收到 f̂(4) + f̂(−4) = 1/2 + 1/2 = 1,而非 1/2。取 N = 8 的 sin 4x:频点 4 收到 −i/2 + i/2 = 0,而且每个样本都是零。
范围:f 是频率为 1 至 12 的三角多项式,故 f̂ 只有有限多项非零,所有和均为有限和。计算值来自双精度 DFT,显示到四位小数;预测值是精确的。
反例模式
边界频率可能在网格上消失
当偶数 ,非零函数 满足
对每个样本都成立。其整个样本向量和 DFT 与零函数相同。模式 与 是不同的连续频率,但按模 属于同一余数。若三角多项式支撑在 ,其奈奎斯特(Nyquist)频点为 。特别地, 的样本为 ,而正弦部分消失。要把这个频点分配给两个端点频率,需要额外约定。恢复定理中的严格不等式 不能换成 。
任意 等价类都不能直接在指定点采样:改变有限网格上的值会改变样本,却不改变傅里叶系数。系数绝对可和是 (3) 的方便充分条件,并非声称所有可能的公式都必须有该条件。
常见错误
常见错误
(把高于 的频点读成高频)
在 个点采样 。由 (3),,其余频点全为零。若把频点 读成频率 ,就会得到 ;由于 ,它的样本确实相同,但在样本之间每个周期振荡七次。一个频点决定的是模 的一个余数类,而不是一个频率。通常约定取 的代表;这是对数据的假设,而在 处,连这个约定也有歧义。
常见错误
(把未归一化的 DFT 与傅里叶系数比较)
混叠公式 (3) 是对 而非 陈述的。对常数函数 ,样本全为一,所以 ,而 。漏掉因子 ,每个恢复出的系数都会大 倍;采用酉归一化时,因子改为 ,同样必须记清。
练习
快速检查
(计算 的四点 DFT 并验证帕塞瓦尔公式。)
解答 · 答案
,故 。帕塞瓦尔公式两边均为二:。
快速检查
(在长度四下,计算 与自身的循环卷积。与把有效长度为三的列表补零到长度五后的普通卷积比较。)
解答 · 答案
普通卷积为 。长度四时指标零与四合并,得到 。将有效长度为三的列表补零到长度五,得到无绕回的 。
快速检查
(对在八个点采样的 ,求 时两个非零的归一化 DFT 系数 。)
解答 · 答案
。模八下这两个频率为 和 ,故 ,其他 为零。
快速检查
(令 。以 使用充分的无碰撞条件 时,最小整数 是多少?为什么这是充分条件,而不是说对这个特定函数每个更小网格都必然失败?)
解答 · 答案
充分条件是 ,最小整数为七。它保证 内每个频率有不同余数。若已知支撑是 , 也给出三个不同余数。当 ,正弦样本全为零,数据与常数 相同。若没有支撑限制,即使这些较小网格的已知频率不碰撞,也没有一般唯一性。