第 12 讲：离散傅里叶变换、循环卷积与 FFT

计算机不能保存连续频率函数，因此要把一段有限序列的频谱也离散化。 $N$ 点 DFT 定义为

X[k]=\sum_{n=0}^{N-1} x[n]e^{-j2\pi kn/N}, \qquad k=0,\ldots,N-1,

逆变换

x[n]=\frac1N\sum_{k=0}^{N-1} X[k]e^{j2\pi kn/N}.

令 $W_N=e^{-j2\pi/N}$ ，也可写 $X[k]=\sum_nx[n]W_N^{kn}$ 。

三种等价理解

第二种解释说明了为什么 DFT 的时域移位、卷积都天然是模 $N$ 的循环操作。

有限序列按 N 点周期延拓后的样值排列

X[k+N]=X[k].

若 $x[n]$ 为实序列，

X[N-k]=X^*[k].

因此只需保存约一半频谱。 $X[0]=\sum_nx[n]$ 是直流总量；若 $N$ 为偶数， $X[N/2]$ 对应 Nyquist 频率且为实数。

循环时移：

x[(n-n_0)_N]\longleftrightarrow e^{-j2\pi kn_0/N}X[k].

循环卷积：

x\circledast_Nh \longleftrightarrow X[k]H[k].

Parseval：

\sum_{n=0}^{N-1}|x[n]|^2 =\frac1N\sum_{k=0}^{N-1}|X[k]|^2.

长度为 $L$ 与 $M$ 的序列线性卷积长度为 $L+M-1$ 。先把两者补零到

N\ge L+M-1,

再做 DFT、逐点相乘、IDFT，就不会发生时域折叠。若 $N$ 太小，超出第 $N-1$ 点的卷积尾部会绕回开头，造成时域混叠。

长序列可用 overlap-add 或 overlap-save 分块完成快速卷积。

把 $N$ 点序列补到更长再 DFT，只是在同一个 DTFT 曲线上取更密的频率样本，让图看起来更平滑；它没有增加原始观测时长，也没有提高真正的频率分辨能力。

频率分辨能力主要由观测时长决定。把记录时间延长，才能分开更接近的频率。

DFT 隐含周期延拓。若记录段首尾接不上，边界产生跳变，能量会扩散到多个频点，形成泄漏。给数据乘窗可降低旁瓣，但会加宽主瓣，存在“分辨率—泄漏”权衡。

若正弦恰好在 DFT 栅格频率上并截取整数个周期，能量集中在对应频点；否则发生栅栏效应和泄漏。

直接 DFT 需要 $O(N^2)$ 次复运算。FFT 不是新变换，而是利用

W_N^{2kn}=W_{N/2}^{kn}

把偶数索引和奇数索引分开，递归复用子问题，把复杂度降为 $O(N\log N)$ 。

基 2 FFT 要求 $N$ 为 2 的幂；更一般的混合基算法可处理合数长度。考试手算蝶形图时，先确定采用时间抽取还是频率抽取、输入或输出是否位逆序。