专题进阶 · 信号处理推荐总顺序 · 第 116 / 148 课

用复指数基函数表示离散频率,明确正负号、频率索引和归一化约定。

先学会这些,再进入本课 矩阵乘法
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 信号处理

离散傅里叶变换DFT

把长度 N 的序列分解为离散频率分量,直接求和成本 O(N²)。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用复指数基函数表示离散频率,明确正负号、频率索引和归一化约定。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

长度 4 的序列 [1,0,−1,0] 有什么频率成分?怎样从时域样本得到频域系数?

02一步步得到方法

先认识复数旋转

i²=−1,e^(iθ)=cosθ+i sinθ,表示复平面单位圆上的旋转。N=4 时,e^(−2πi/N)=−i,连续幂为 1、−i、−1、i;因此本课可以只用这些简单值手算。

DFT 约定 X[k]=Σₙx[n]e^(−2πikn/N)。固定 k 时,把输入与一组按频率旋转的复数权重相乘求和。k=0 权重全 1,得到直流分量,也就是样本总和。

频率索引不是自动的赫兹

若采样率为 f_s,则第 k 档对应 kf_s/N;高于一半的索引通常表示负频率。实信号满足共轭对称 X[N−k]=conj(X[k]),不是说后一半数据没有任何数学意义。

本约定正变换不除 N,逆变换用正号并除 N。不同库可将归一化分配在不同方向,比较结果前要对齐约定。有限观察窗口与采样还会影响谱泄漏和混叠,DFT 本身不恢复被采样丢失的信息。

频域系数是投影,不是另一批时间点

固定 k 的复指数权重在样本上旋转,求和衡量输入与这种离散振荡的关联。不同 k 的基向量在完整长度上正交,这使输入能被所有频率系数完整表示。

当实际信号的周期不能整齐落入观察窗口时,能量可能分散到多个频率格,称为谱泄漏;提高采样率与延长观察时间解决的也不是同一种分辨率问题。先说明采样和窗口,再解释频谱。

03把一个小例子完全算清楚

x=[1,0,−1,0],N=4。

步骤计算与状态为什么这样做
k=01+0−1+0=0无直流偏置
k=11+(−1)×(−1)=2旋转权重使两项同向
k=21+(−1)×1=0相互抵消
k=32与 k=1 共轭对称

窄屏可左右滑动表格,阅读完整计算与理由。

X=[0,2,0,2];幅值解释要考虑长度与是否采用单边频谱。

04为什么这个方法成立

  1. 离散复指数在 N 个样本上相互正交:不同频率的几何级数和为零。
  2. 与各基函数作加权和提取对应频率系数。
  3. 正交性也给出逆变换,表明在有限序列模型内变换可逆(忽略舍入)。

05把推导翻译成代码

Python · 可独立运行的教学实现

import cmath
from math import pi
def dft(x):
    n = len(x)
    if n == 0:
        return []
    return [sum(x[t]*cmath.exp(-2j*pi*k*t/n) for t in range(n))
            for k in range(n)]

逐个理解关键决定

-2j*pi*k*t/n
负号约定正变换,j 是 Python 的虚数单位写法。
for k in range(n)
计算全部 N 个频率,不是只取实部或只计算前一半。

06时间、空间与实现范围

N 个输出各累加 N 项,直接 DFT 时间 O(N²),输出 O(N),本实现不显式保存 N×N 变换矩阵。

小的虚部如 1e−15 常来自浮点舍入,应使用容差比较而非严格复数相等。

07改变条件,检查哪里会出错

把 |X[k]| 直接当作原正弦振幅

还需考虑 N、实信号正负频率分摊与归一化方式。

把最大频率索引直接当作最高正频率

常规输出后半段通常对应负频率,要结合采样率和索引约定转换。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

常数序列 [2,2,2,2] 的 X?

需要一点提示

除直流外旋转项相消。

查看解析与答案

约 [8,0,0,0]。

练习 2 · 边界与辨析

采样率 800Hz、N=8,k=2 对应多少?

需要一点提示

k f_s/N。

查看解析与答案

200Hz。

练习 3 · 变式与迁移

DFT 与 FFT 是不同变换吗?

需要一点提示

一个是数学定义,一个是计算方法。

查看解析与答案

不是,FFT 是快速计算同一 DFT 的算法家族。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 科学计算与 FFT 代码

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。