返回课程主线
第 7 条主线 · 12 个考点

DTFT、DFS、DFT 与 FFT

区分 DTFT、DFS、DFT 的对象和周期性,掌握圆周卷积、线性卷积和谱分析参数。

完成后应当能做到

  • 能从序列类型选择 DTFT、DFS 或 DFT
  • 能完成 DFT、圆周卷积和补零线性卷积
  • 理解频率采样、谱泄漏和 FFT 的参数关系

DTFT、DFS、DFT 与 FFT

先分清三个对象:非周期序列的DTFT是连续而周期的频谱;周期序列的DFS是有限个独立谐波系数;有限记录的DFT是一组频率采样。FFT只是算DFT的算法。原基2、混合基、分裂基的完整蝶形与例题保留。

7.1 DTFT 的周期性、收敛和有限门序列

对照 S015 手写笔记 PDF 15、16、17、18、19、102、108 页。以下用统一记号重建推导;未注明“原页例题”的数值例题为本讲教学例题。

定义与逆变换为

X(ejΩ)=∑n=−∞∞x[n]e−jΩn,x[n]=12π∫−ππX(ejΩ)ejΩndΩ.X(e^{j\Omega})=\sum_{n=-\infty}^{\infty}x[n]e^{-j\Omega n},\quad x[n]=\frac1{2\pi}\int_{-\pi}^{\pi}X(e^{j\Omega})e^{j\Omega n}d\Omega.

由于整数 nn 使 e−j2πn=1e^{-j2\pi n}=1,频谱以 2π2\pi 为周期。Ω\Omega 单位 rad/sample,连续频率经采样对应 Ω=ωTs\Omega=\omega T_s。绝对可和是普通DTFT存在的充分条件,但周期序列等也可以按广义函数处理。

δ[n]↔1\delta[n]\leftrightarrow1,anu[n]↔(1−ae−jΩ)−1a^nu[n]\leftrightarrow(1-ae^{-j\Omega})^{-1} 要求 ∣a∣<1|a|<1。Z变换取 z=ejΩz=e^{j\Omega} 之前必须确认单位圆在ROC内,不能给发散序列硬代入一个有理式。

长度 NN 的门序列 w[n]=u[n]−u[n−N]w[n]=u[n]-u[n-N] 的有限几何和为

W(ejΩ)=e−jΩ(N−1)/2sin⁡(NΩ/2)sin⁡(Ω/2).W(e^{j\Omega})=e^{-j\Omega(N-1)/2}\frac{\sin(N\Omega/2)}{\sin(\Omega/2)}.

Ω=2πm\Omega=2\pi m 取极限为 NN;它不是连续Sa,分母和 2π2\pi 周期性不可丢。线性相位记录门的中心 (N−1)/2(N-1)/2。

7.2 离散性质与差分方程的频率响应

对照 S015 手写笔记 PDF 16、17、18、19、102、108、109、110 页。以下用统一记号重建推导;未注明“原页例题”的数值例题为本讲教学例题。

时移 x[n−n0]x[n-n_0] 乘 e−jΩn0e^{-j\Omega n_0};乘 ejΩ0ne^{j\Omega_0n} 搬移频谱并作 2π2\pi 周期理解。卷积和对应频域乘积;逐点乘积对应一周期频域卷积并乘 1/(2π)1/(2\pi)。

对零状态差分方程 ∑kaky[n−k]=∑mbmx[n−m]\sum_ka_ky[n-k]=\sum_mb_mx[n-m],在频率响应存在时,

H(ejΩ)=∑mbme−jΩm∑kake−jΩk.H(e^{j\Omega})=\frac{\sum_mb_me^{-j\Omega m}}{\sum_ka_ke^{-j\Omega k}}.

S015第108页的两点平均器 y[n]=(x[n]+x[n−1])/2y[n]=(x[n]+x[n-1])/2 给出 H=e−jΩ/2cos⁡(Ω/2)H=e^{-j\Omega/2}\cos(\Omega/2)。在 (−π,π)(-\pi,\pi),幅度为 cos⁡(Ω/2)\cos(\Omega/2),直流通过、π\pi 被抑制、群时延半个样本;端点响应为0,相位无定义。不能因时延非整数就认定系统不因果,它仍只用当前和过去样值。

7.3 DFS、DFT 与正交性

对照 S015 手写笔记 PDF 20、21、22、23 页。以下用统一记号重建推导;未注明“原页例题”的数值例题为本讲教学例题。

对周期 NN 的序列,DFS写为 x[n]=∑k=0N−1Ckej2πkn/Nx[n]=\sum_{k=0}^{N-1}C_ke^{j2\pi kn/N},Ck=N−1∑n=0N−1x[n]e−j2πkn/NC_k=N^{-1}\sum_{n=0}^{N-1}x[n]e^{-j2\pi kn/N}。下标 k,nk,n 都按 NN 周期延拓。

对一个有限记录,本课DFT约定为

X[k]=∑n=0N−1x[n]WNkn,x[n]=1N∑k=0N−1X[k]WN−kn,WN=e−j2π/N.X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn},\quad x[n]=\frac1N\sum_{k=0}^{N-1}X[k]W_N^{-kn},\quad W_N=e^{-j2\pi/N}.

原理仍是复指数正交性:∑n=0N−1WN(k−m)n\sum_{n=0}^{N-1}W_N^{(k-m)n} 在模 NN 同余时为 NN,否则为0。同一周期段有 Ck=X[k]/NC_k=X[k]/N;有限记录的DFT也等于该记录DTFT在 Ωk=2πk/N\Omega_k=2\pi k/N 的样值。

例:四点常数记录 [1,1,1,1][1,1,1,1] 的DFT为 [4,0,0,0][4,0,0,0],DFS直流系数为1。两者差4倍是定义,不是算法误差。

7.4 圆周卷积与补零后的线性卷积

对照 S015 手写笔记 PDF 20、21、22、23 页。以下用统一记号重建推导;未注明“原页例题”的数值例题为本讲教学例题。

DFT乘法隐含周期延拓,因此IDFT得到

yN[n]=∑m=0N−1x[m]h[(n−m) mod N].y_N[n]=\sum_{m=0}^{N-1}x[m]h[(n-m)\bmod N].

这是N点圆周卷积,长结果会绕回开头。若想得到长度 Lx+Lh−1L_x+L_h-1 的普通线性卷积,两个序列都补零到同一 N≥Lx+Lh−1N\ge L_x+L_h-1,再DFT相乘和IDFT。

教学例:[1,1]∗[1,1]=[1,2,1][1,1]*[1,1]=[1,2,1];两点圆周卷积却是 [2,2][2,2],最后的1绕回0号位置。补成三点或四点后即可无混叠地读出原线性卷积。频域采样间隔变粗会导致时域周期副本重叠,与第8讲时域采样引发频域重叠互为对应。

7.5 FFT 与谱分析:保留算法而不混淆结论

本节是原课程保留的扩展,S015 未提供可确证的对应推导页。

基2FFT将偶、奇样本的 N/2N/2 点DFT记为 E[k],O[k]E[k],O[k],然后

X[k]=E[k]+WNkO[k],X[k+N/2]=E[k]−WNkO[k].X[k]=E[k]+W_N^kO[k],\quad X[k+N/2]=E[k]-W_N^kO[k].

蝶形只计算一次旋转乘积,下支路必须减去同一项。标准复数基2算法约需 (N/2)log⁡2N(N/2)\log_2N 次复乘、Nlog⁡2NN\log_2N 次复加,实际可消去部分平凡因子。混合基按 N=N1N2N=N_1N_2 分解,并处理旋转因子和输出重排;六点DFT不是补零八点DFT。分裂基拆为偶序列 N/2N/2 与 4n+1,4n+34n+1,4n+3 两个 N/4N/4 子序列,正变换因子分别为 WNk,WN3kW_N^k,W_N^{3k},四组输出的差项含 −j,+j-j,+j,完整推导在本讲保留的专节。

谱分析时先写采样率 fsf_s、实际记录长度 LL、DFT长度 NN。频点间隔 fs/Nf_s/N 可以靠补零减小,但真实记录时长仍是 L/fsL/f_s,近频可分辨能力由记录长度与窗主瓣决定。有限截断相当于乘窗,会与窗频谱卷积产生泄漏;频点未落在谱峰上产生栅栏效应。例:固定100点记录补到1024点,图更密,不能声称观测时间增长了10倍。

14. DFT、DFS、圆周卷积

DFT 适合有限长序列、频谱采样、FFT 和线性卷积的快速计算;DFS 适合离散周期序列。

14.1 DFT 定义

令

WN=e−j2πNW_N=e^{-j\frac{2\pi}{N}}

则

X[k]=∑n=0N−1x[n]WNknX[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn} x[n]=1N∑k=0N−1X[k]WN−knx[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]W_N^{-kn}

其中 x[n]x[n] 和 X[k]X[k] 都按 NN 周期延拓。

14.2 正交性证明

∑n=0N−1WN(k−m)n={N,k−m=rN0,k−m≠rN\sum_{n=0}^{N-1}W_N^{(k-m)n} = \begin{cases} N,&k-m=rN\\ 0,&k-m\ne rN \end{cases}

当 k≠m(modN)k\ne m \pmod N 时,这是等比数列:

1−WN(k−m)N1−WNk−m=1−e−j2π(k−m)1−WNk−m=0\frac{1-W_N^{(k-m)N}}{1-W_N^{k-m}} =\frac{1-e^{-j2\pi(k-m)}}{1-W_N^{k-m}}=0

当 k=m(modN)k=m\pmod N 时,每一项都是 11,和为 NN。反变换公式由这个正交性直接得到。

14.3 DFT 常用表

x[n]x[n],0≤n<N0\le n<NX[k]X[k]
δ[n]\delta[n]11
δ[n−n0]\delta[n-n_0]e−j2πkn0/Ne^{-j2\pi kn_0/N}
11NδN[k]N\delta_N[k]
ej2πk0n/Ne^{j2\pi k_0n/N}NδN[k−k0]N\delta_N[k-k_0]
cos⁡(2πk0n/N)\cos(2\pi k_0n/N)N2{δN[k−k0]+δN[k+k0]}\frac{N}{2}\{\delta_N[k-k_0]+\delta_N[k+k_0]\}
sin⁡(2πk0n/N)\sin(2\pi k_0n/N)N2j{δN[k−k0]−δN[k+k0]}\frac{N}{2j}\{\delta_N[k-k_0]-\delta_N[k+k_0]\}
ana^n1−aN1−ae−j2πk/N\frac{1-a^N}{1-ae^{-j2\pi k/N}},ae−j2πk/N≠1ae^{-j2\pi k/N}\ne1
1, 0≤n≤M−11,\ 0\le n\le M-1e−jπk(M−1)/Nsin⁡(πkM/N)sin⁡(πk/N)e^{-j\pi k(M-1)/N}\frac{\sin(\pi kM/N)}{\sin(\pi k/N)}

最后一行在 k=0k=0 时取极限,结果为 MM。

证明有限矩形序列:

X[k]=∑n=0M−1e−j2πkn/N=1−e−j2πkM/N1−e−j2πk/NX[k]=\sum_{n=0}^{M-1}e^{-j2\pi kn/N} =\frac{1-e^{-j2\pi kM/N}}{1-e^{-j2\pi k/N}}

分子分母各提取半角相位:

X[k]=e−jπk(M−1)/Nsin⁡(πkM/N)sin⁡(πk/N)X[k]=e^{-j\pi k(M-1)/N} \frac{\sin(\pi kM/N)}{\sin(\pi k/N)}

14.4 DFT 性质

性质结论
圆周时移x[(n−n0)N]↔X[k]e−j2πkn0/Nx[(n-n_0)_N]\leftrightarrow X[k]e^{-j2\pi kn_0/N}
圆周频移x[n]ej2πk0n/N↔X[(k−k0)N]x[n]e^{j2\pi k_0n/N}\leftrightarrow X[(k-k_0)_N]
圆周反转x[(−n)N]↔X[(−k)N]x[(-n)_N]\leftrightarrow X[(-k)_N]
圆周卷积x[n]⊛Nh[n]↔X[k]H[k]x[n]\circledast_N h[n]\leftrightarrow X[k]H[k]
时域相乘x[n]h[n]↔1NX[k]⊛NH[k]x[n]h[n]\leftrightarrow \frac{1}{N}X[k]\circledast_N H[k]
Parseval∑n=0N−1∣x[n]∣2=1N∑k=0N−1∣X[k]∣2\sum_{n=0}^{N-1}\lvert x[n]\rvert^2=\frac{1}{N}\sum_{k=0}^{N-1}\lvert X[k]\rvert^2

14.5 圆周卷积

定义:

y[n]=∑m=0N−1x[m]h[(n−m)N]y[n]=\sum_{m=0}^{N-1}x[m]h[(n-m)_N]

则

Y[k]=X[k]H[k]Y[k]=X[k]H[k]

证明:

Y[k]=∑n=0N−1∑m=0N−1x[m]h[(n−m)N]WNknY[k]=\sum_{n=0}^{N-1}\sum_{m=0}^{N-1}x[m]h[(n-m)_N]W_N^{kn}

令 r=(n−m)Nr=(n-m)_N,即 n=(r+m)Nn=(r+m)_N:

Y[k]=∑mx[m]WNkm∑rh[r]WNkr=X[k]H[k]Y[k]=\sum_m x[m]W_N^{km}\sum_r h[r]W_N^{kr} =X[k]H[k]

14.6 用 DFT 做线性卷积

若 x[n]x[n] 长度为 LxL_x,h[n]h[n] 长度为 LhL_h,线性卷积长度为:

Ly=Lx+Lh−1L_y=L_x+L_h-1

只要选择

N≥Lx+Lh−1N\ge L_x+L_h-1

把两个序列补零到 NN 点,再做 NN 点圆周卷积,就等于线性卷积。若 NN 太小,尾部会折回,发生时域混叠。

14.7 DFS:离散周期序列

若 x[n]x[n] 周期为 NN:

x[n]=∑k=0N−1akej2πkn/Nx[n]=\sum_{k=0}^{N-1}a_k e^{j2\pi kn/N} ak=1N∑n=0N−1x[n]e−j2πkn/Na_k=\frac{1}{N}\sum_{n=0}^{N-1}x[n]e^{-j2\pi kn/N}

DFT 与 DFS 的关系:

X[k]=NakX[k]=Na_k

DFT 是一段有限数据的频谱采样;DFS 是周期序列的傅里叶级数系数。形式相似,但物理意义不同。

来源:主讲义第 2987-3133 行

28.5 DTFT、DFS、DFT 三者关系

这三个名字最容易混,但对象不同。

名称对象频域特点考场关键词
DTFT非周期离散序列连续频率,周期为 2π2\pi无限序列、频率响应
DFS离散周期序列离散谱线,系数周期周期序列、一个周期
DFT有限长序列有限个频率采样点NN 点、FFT、圆周卷积

DTFT 定义:

X(ejΩ)=∑n=−∞∞x[n]e−jΩnX(e^{j\Omega})=\sum_{n=-\infty}^{\infty}x[n]e^{-j\Omega n}

它一定关于 Ω\Omega 以 2π2\pi 为周期:

X(ej(Ω+2π))=X(ejΩ)X(e^{j(\Omega+2\pi)})=X(e^{j\Omega})

DFT 可以看作有限长序列 DTFT 在 NN 个等间隔频点上的采样:

X[k]=X(ejΩ)∣Ω=2πk/NX[k]=X(e^{j\Omega})\bigg|_{\Omega=2\pi k/N}

DFS 可以看作离散周期序列在一个周期内的傅里叶级数。若序列周期为 NN:

x[n]=∑k=0N−1Ckej2πkn/Nx[n]=\sum_{k=0}^{N-1}C_k e^{j2\pi kn/N}

系数:

Ck=1N∑n=0N−1x[n]e−j2πkn/NC_k=\frac{1}{N}\sum_{n=0}^{N-1}x[n]e^{-j2\pi kn/N}

二级结论:DTFT 看“连续频率曲线”,DFT 看“取了 NN 个点”,DFS 看“周期序列的谱线”。

来源:主讲义第 7390-7431 行

29.7 DFT、FFT 和谱分析的考场参数

用 DFT 分析连续信号频谱时,一定有三个环节:

DFT 谱分析中的泄漏分辨率和栅栏效应

  1. 采样:连续时间变成离散序列。
  2. 截断:只取有限长数据。
  3. DFT:只在有限个频点上看频谱。

频率间隔:

Δf=fsN\Delta f=\frac{f_s}{N}

频率采样点:

fk=kfsNf_k=\frac{k f_s}{N}

矩形窗截断会导致频谱泄漏。若信号频率不落在 DFT 栅格点上,会出现栅栏效应。

常见改善方法:

  1. 加窗:降低旁瓣,但主瓣通常变宽。
  2. 补零:让频谱曲线看起来更密,不真正提高物理分辨率。
  3. 增加记录长度:真正提高分辨率,因为 Δf=fs/N\Delta f=f_s/N 变小。

FFT 只是快速计算 DFT 的算法,不改变 DFT 的定义。基 2 FFT 常要求:

N=2mN=2^m

二级结论:谱分析题先算 Δf\Delta f,再判断泄漏、栅栏效应和窗函数影响。

继续加深:DFT 谱分析题一般不是考“会不会按定义求和”,而是考你是否知道 DFT 图像为什么和真实频谱不完全一样。

四个参数必须先算:

参数公式含义
采样间隔Ts=1/fsT_s=1/f_s时域离散化步长
记录长度T0=NTsT_0=NT_s实际观察了多长时间
频率间隔Δf=fs/N=1/T0\Delta f=f_s/N=1/T_0DFT 相邻频点间距
第 kk 点频率fk=kfs/Nf_k=kf_s/N第 kk 个栅格位置

泄漏、栅栏效应和补零的区别:

  1. 泄漏来自截断,相当于时域乘窗、频域卷积。
  2. 栅栏效应来自只在有限个频点采样,真实峰值可能落在两个栅格之间。
  3. 补零增加 DFT 点数,让频谱曲线显示更密,但原始记录长度不变,所以不真正提高物理分辨率。
  4. 增加实际采样时长可缩窄同类窗的主瓣,改善分开近频谱线的能力;增加补零点数只减小 DFT 显示频点间隔。

小例题模板:fs=1000 Hzf_s=1000\text{ Hz},采 N=500N=500 点,则 Δf=2 Hz\Delta f=2\text{ Hz}。若信号频率为 123 Hz123\text{ Hz},它不落在 2 Hz2\text{ Hz} 的整数栅格上,会泄漏;补零到 2000 点后显示间隔变成 0.5 Hz0.5\text{ Hz},但原始记录时间仍是 0.5 s0.5\text{ s},物理分辨率本质仍由原记录决定。

来源:主讲义第 7936-7993 行

基 2 FFT:从奇偶拆分到蝶形

FFT 是计算 DFT 的算法。下面以时间抽取的基 2 算法说明为什么能少算;按频率抽取的分组顺序不同,不能把两种流程图的输入、输出排序直接混用。

令 N=2mN=2^m,WN=e−j2π/NW_N=e^{-j2\pi/N}。把输入的偶数下标与奇数下标分开:

X[k]=∑r=0N/2−1x[2r]WN/2kr+WNk∑r=0N/2−1x[2r+1]WN/2kr=E[k]+WNkO[k].X[k]=\sum_{r=0}^{N/2-1}x[2r]W_{N/2}^{kr}+W_N^k\sum_{r=0}^{N/2-1}x[2r+1]W_{N/2}^{kr}=E[k]+W_N^kO[k].

其中 E[k]E[k]、O[k]O[k] 分别是偶数样本组和奇数样本组的 N/2N/2 点 DFT。因为 WNk+N/2=−WNkW_N^{k+N/2}=-W_N^k,同一对小变换结果还可以得到

X[k+N/2]=E[k]−WNkO[k],0≤k<N/2.X[k+N/2]=E[k]-W_N^kO[k],\qquad 0\le k<N/2.

一次乘法 WNkO[k]W_N^kO[k] 配一次加法和一次减法,生成两个输出,这就是蝶形。继续对小变换作奇偶拆分,最终变成 2 点 DFT。常见迭代时间抽取流程采用输入倒位序、输出自然序;其他实现可以重新排列,不能仅凭“FFT”三个字确定排序。

算一个 4 点例子。 对 x=[1,2,3,4]x=[1,2,3,4],偶数组为 [1,3][1,3]、奇数组为 [2,4][2,4],各自的 2 点 DFT 是 E=[4,−2]E=[4,-2]、O=[6,−2]O=[6,-2]。W40=1W_4^0=1、W41=−jW_4^1=-j,故 X=[10,−2+2j,−2,−2−2j]X=[10,-2+2j,-2,-2-2j]。直流值 10 等于输入样本和,其余点符合实序列的共轭对称,可检查计算。

一般计数约定下,每级有 N/2N/2 个蝶形、共 log⁡2N\log_2N 级,因而需要 (N/2)log⁡2N(N/2)\log_2N 次复乘、Nlog⁡2NN\log_2N 次复加。若把 ±1,±j\pm1,\pm j 旋转因子视作符号和实虚交换,实际乘法还能减少;答运算量题时先声明计数口径。

补零到 2m2^m 可使用基 2 FFT。补零会增加频谱采样点,但不会增加原始观察时长,因此不能据此宣称分开两条近频率谱线的能力变强。

来源:主讲义第 139-157 行

混合基 FFT:把六点 DFT 拆成二点和三点

本节为原创补充讲义。基 2 FFT 每一步都拆成两组,所以要求长度是 2 的幂。混合基 FFT 允许按 NN 的因子组合拆分,例如 N=6=2×3N=6=2\times3、N=12=3×4N=12=3\times4。输出仍是同一个 NN 点 DFT;它并不是给序列补零后计算另一种长度的变换。

从定义推一次分解。 设 N=abN=ab,令 WN=e−j2π/NW_N=e^{-j2\pi/N}。把输入下标写成 n=ar+sn=ar+s,其中 0≤r<b0\le r<b、0≤s<a0\le s<a;把输出下标写成 k=q+bpk=q+bp,其中 0≤q<b0\le q<b、0≤p<a0\le p<a。每个合法下标恰好出现一次,因此

X[q+bp]=∑s=0a−1∑r=0b−1x[ar+s]WN(ar+s)(q+bp).X[q+bp]=\sum_{s=0}^{a-1}\sum_{r=0}^{b-1}x[ar+s]W_N^{(ar+s)(q+bp)}.

指数展开后,含有 abpr=Nprabpr=Npr 的因子为 1,其他因子分别给出

X[q+bp]=∑s=0a−1[∑r=0b−1x[ar+s]Wbrq]WNsqWasp.X[q+bp]=\sum_{s=0}^{a-1}\left[\sum_{r=0}^{b-1}x[ar+s]W_b^{rq}\right]W_N^{sq}W_a^{sp}.

令括号内为 Gs[q]G_s[q],实际算法变成三步:先对每个 ss 的输入子序列做 bb 点 DFT;再乘跨两级连接的旋转因子 WNsqW_N^{sq};最后对每个 qq 做 aa 点 DFT,并按 k=q+bpk=q+bp 放回输出位置。旋转因子与输出重排都是公式的一部分,不能省略。

完整算例:N=6N=6、a=2a=2、b=3b=3。 取 x=[1,2,3,4,5,6]x=[1,2,3,4,5,6]。两组输入为偶下标 [1,3,5][1,3,5] 和奇下标 [2,4,6][2,4,6]。利用 W3=−1/2−j3/2W_3=-1/2-j\sqrt3/2,分别计算三点 DFT:

G0=[9,−3+j3,−3−j3],G1=[12,−3+j3,−3−j3].G_0=[9,-3+j\sqrt3,-3-j\sqrt3],\qquad G_1=[12,-3+j\sqrt3,-3-j\sqrt3].

每个 q=0,1,2q=0,1,2 再做一次二点组合:

X[q]=G0[q]+W6qG1[q],X[q+3]=G0[q]−W6qG1[q].X[q]=G_0[q]+W_6^qG_1[q],\qquad X[q+3]=G_0[q]-W_6^qG_1[q].

在 q=0q=0,得到 X[0]=21X[0]=21、X[3]=−3X[3]=-3。在 q=1q=1,W6=1/2−j3/2W_6=1/2-j\sqrt3/2,乘积 W6G1[1]=2j3W_6G_1[1]=2j\sqrt3,因此 X[1]=−3+3j3X[1]=-3+3j\sqrt3、X[4]=−3−j3X[4]=-3-j\sqrt3。在 q=2q=2,W62G1[2]=2j3W_6^2G_1[2]=2j\sqrt3,得到 X[2]=−3+j3X[2]=-3+j\sqrt3、X[5]=−3−3j3X[5]=-3-3j\sqrt3。按自然下标排列:

X=[21,−3+3j3,−3+j3,−3,−3−j3,−3−3j3].X=[21,-3+3j\sqrt3,-3+j\sqrt3,-3,-3-j\sqrt3,-3-3j\sqrt3].

直流值 21 等于六个样本的和;X[5]=X∗[1]X[5]=X^*[1]、X[4]=X∗[2]X[4]=X^*[2],符合实序列的共轭对称。这两项可以及时发现旋转因子符号或输出排列错误。

什么时候继续分解? 若 aa 或 bb 仍可分解,就递归计算小 DFT;含有小素因子的长度通常有高效实现。素数长度不能直接按非平凡的 abab 分解,但仍有 Rader、Bluestein 等算法,本节不把它们与混合基分解混为一谈。

不同基数和实现方式的乘法数量不同,不能把基 2 的 (N/2)log⁡2N(N/2)\log_2N 次复乘直接套到任何混合基流程。题目指定六点 DFT 时,补零到八点会改变频率栅格,八点结果不是原六点结果;只有任务允许更改变换长度时才能选择这种做法。

来源:主讲义第 1-31 行

分裂基 FFT:一组二分,另外两组四分

本节为原创补充讲义。FFT 计算的仍是 DFT,只是复用小变换来减少重复运算。分裂基 FFT(split-radix FFT)把长度为 NN 的输入拆成一组长度为 N/2N/2 的偶下标序列和两组长度为 N/4N/4 的奇下标序列。本节采用按时间抽取的分解,标准递归长度为 N=2mN=2^m,其中 mm 是非负整数。先理解输入分组,再推导输出位置,就不必死记一张蝶形图。

先把符号和前提对齐。 采用正变换约定

X[k]=∑n=0N−1x[n]WNnk,WN=e−j2π/N,0≤k<N.X[k]=\sum_{n=0}^{N-1}x[n]W_N^{nk},\qquad W_N=e^{-j2\pi/N},\qquad 0\le k<N.

这里 nn 是输入下标,kk 是频率下标,j2=−1j^2=-1。WNW_N 是旋转因子;它的指数负号决定后面四组输出中的 jj 的符号。推导当前这一层时先假设 N≥4N\ge4,并记 Q=N/4Q=N/4。长度为 11 或 22 时直接计算,不再四分。

第一步:为什么是三个子序列? 每个整数下标或者是偶数 2r2r,或者是奇数;奇数又恰好分为除以四余一的 4r+14r+1 和除以四余三的 4r+34r+3。三组没有重复,也没有遗漏,总长度为 N/2+N/4+N/4=NN/2+N/4+N/4=N。

子序列取样方式长度八点输入时取出的下标
偶下标组e[r]=x[2r]e[r]=x[2r]N/2N/20,2,4,60,2,4,6
第一奇下标组u[r]=x[4r+1]u[r]=x[4r+1]N/4N/41,51,5
第二奇下标组v[r]=x[4r+3]v[r]=x[4r+3]N/4N/43,73,7

偶下标组的范围为 0≤r<N/20\le r<N/2,两个奇下标组为 0≤r<Q0\le r<Q。分别计算它们的小 DFT,记为

E[k]=∑r=0N/2−1x[2r]WN/2rk,E[k]=\sum_{r=0}^{N/2-1}x[2r]W_{N/2}^{rk}, U[k]=∑r=0Q−1x[4r+1]WQrk,V[k]=∑r=0Q−1x[4r+3]WQrk.U[k]=\sum_{r=0}^{Q-1}x[4r+1]W_Q^{rk},\qquad V[k]=\sum_{r=0}^{Q-1}x[4r+3]W_Q^{rk}.

这些下标可以按各自长度周期延拓:E[k+N/2]=E[k]E[k+N/2]=E[k],U[k+Q]=U[k]U[k+Q]=U[k],V[k+Q]=V[k]V[k+Q]=V[k]。这是有限 DFT 随频率下标的周期性,不是把原始输入补零或增加新样本。

第二步:把原始求和拆开。 将三类输入下标代入 DFT 定义:

X[k]=∑r=0N/2−1x[2r]WN2rk+∑r=0Q−1x[4r+1]WN(4r+1)k+∑r=0Q−1x[4r+3]WN(4r+3)k.\begin{aligned} X[k]&=\sum_{r=0}^{N/2-1}x[2r]W_N^{2rk}\\ &\quad+\sum_{r=0}^{Q-1}x[4r+1]W_N^{(4r+1)k} +\sum_{r=0}^{Q-1}x[4r+3]W_N^{(4r+3)k}. \end{aligned}

利用 WN2=WN/2W_N^2=W_{N/2}、WN4=WQW_N^4=W_Q,把奇数偏移产生的因子移到求和外,得到

X[k]=E[k]+WNkU[k]+WN3kV[k].X[k]=E[k]+W_N^kU[k]+W_N^{3k}V[k].

注意两条奇数支路的因子不同:下标偏移 11 产生 WNkW_N^k,下标偏移 33 产生 WN3kW_N^{3k}。如果两条支路都乘同一个因子,输入分组仍然看似正确,频谱却已经改变。

第三步:一次组合产生四个输出。 只遍历 0≤k<Q0\le k<Q,设

Ak=WNkU[k],Bk=WN3kV[k],Sk=Ak+Bk,Dk=Ak−Bk.A_k=W_N^kU[k],\qquad B_k=W_N^{3k}V[k],\qquad S_k=A_k+B_k,\qquad D_k=A_k-B_k.

频率下标增加 QQ 时,E[k]E[k] 变为 E[k+Q]E[k+Q],而 UU、VV 因周期性回到原值。两条旋转支路分别多乘

WNQ=−j,WN3Q=j.W_N^Q=-j,\qquad W_N^{3Q}=j.

因此 X[k+Q]=E[k+Q]−jAk+jBk=E[k+Q]−jDkX[k+Q]=E[k+Q]-jA_k+jB_k=E[k+Q]-jD_k。下标增加 2Q=N/22Q=N/2 时,偶组回到 E[k]E[k],两条旋转支路都多乘 −1-1;增加 3Q3Q 时,偶组为 E[k+Q]E[k+Q],两条支路分别多乘 jj 和 −j-j。四个输出合起来是

X[k]=E[k]+Sk,X[k+Q]=E[k+Q]−jDk,X[k+2Q]=E[k]−Sk,X[k+3Q]=E[k+Q]+jDk,0≤k<Q.\boxed{\begin{aligned} X[k]&=E[k]+S_k,\\ X[k+Q]&=E[k+Q]-jD_k,\\ X[k+2Q]&=E[k]-S_k,\\ X[k+3Q]&=E[k+Q]+jD_k, \qquad 0\le k<Q. \end{aligned}}

每个 kk 产生四个相隔 QQ 的频率点;遍历全部 QQ 个 kk,恰好写完 NN 个输出。按公式中的下标存放结果,就得到自然频率顺序。不能把某一次循环产生的四个值直接连续拼接,否则一般会打乱顺序。

完整算例:对 [1,2,3,4,5,6,7,8][1,2,3,4,5,6,7,8] 做八点 DFT。 此时 N=8N=8、Q=2Q=2,输入分成

e=[1,3,5,7],u=[2,6],v=[4,8].e=[1,3,5,7],\qquad u=[2,6],\qquad v=[4,8].

先算两个二点 DFT。二点变换的输出是两数之和与两数之差,所以 U=[8,−4]U=[8,-4]、V=[12,−4]V=[12,-4]。偶组做四点 DFT,利用 W4=−jW_4=-j,逐项计算为

E[0]=1+3+5+7=16,E[1]=1−3j−5+7j=−4+4j,E[2]=1−3+5−7=−4,E[3]=1+3j−5−7j=−4−4j.\begin{aligned} E[0]&=1+3+5+7=16,\\ E[1]&=1-3j-5+7j=-4+4j,\\ E[2]&=1-3+5-7=-4,\\ E[3]&=1+3j-5-7j=-4-4j. \end{aligned}

先取 k=0k=0。旋转因子都为 11,因此 A0=8A_0=8、B0=12B_0=12、S0=20S_0=20、D0=−4D_0=-4。代入四组公式:

X[0]=16+20=36,X[2]=−4−j(−4)=−4+4j,X[4]=16−20=−4,X[6]=−4+j(−4)=−4−4j.\begin{aligned} X[0]&=16+20=36,\\ X[2]&=-4-j(-4)=-4+4j,\\ X[4]&=16-20=-4,\\ X[6]&=-4+j(-4)=-4-4j. \end{aligned}

再取 k=1k=1。此时 W8=(1−j)/2W_8=(1-j)/\sqrt2、W83=(−1−j)/2W_8^3=(-1-j)/\sqrt2,而 U[1]=V[1]=−4U[1]=V[1]=-4,所以

A1=−22+22j,B1=22+22j,S1=42j,D1=−42.\begin{aligned} A_1&=-2\sqrt2+2\sqrt2j,\qquad B_1=2\sqrt2+2\sqrt2j,\\ S_1&=4\sqrt2j,\qquad D_1=-4\sqrt2. \end{aligned}

这一轮必须同时使用 E[1]E[1] 和 E[3]E[3],不能让所有输出都加 E[1]E[1]:

X[1]=(−4+4j)+42j=−4+4(1+2)j,X[3]=(−4−4j)−j(−42)=−4+4(2−1)j,X[5]=(−4+4j)−42j=−4−4(2−1)j,X[7]=(−4−4j)+j(−42)=−4−4(1+2)j.\begin{aligned} X[1]&=(-4+4j)+4\sqrt2j=-4+4(1+\sqrt2)j,\\ X[3]&=(-4-4j)-j(-4\sqrt2)=-4+4(\sqrt2-1)j,\\ X[5]&=(-4+4j)-4\sqrt2j=-4-4(\sqrt2-1)j,\\ X[7]&=(-4-4j)+j(-4\sqrt2)=-4-4(1+\sqrt2)j. \end{aligned}

按自然下标排列,完整结果为

X=[ 36, −4+4(1+2)j, −4+4j, −4+4(2−1)j,−4, −4−4(2−1)j, −4−4j, −4−4(1+2)j ].\begin{aligned} X=[\,&36,\ -4+4(1+\sqrt2)j,\ -4+4j,\ -4+4(\sqrt2-1)j,\\ &-4,\ -4-4(\sqrt2-1)j,\ -4-4j,\ -4-4(1+\sqrt2)j\,]. \end{aligned}

不依赖 FFT 流程,怎样独立验算? 直接把 x[n]=n+1x[n]=n+1 放回八点 DFT。直流值是 X[0]=1+2+⋯+8=36X[0]=1+2+\cdots+8=36。对 k=1,…,7k=1,\ldots,7,令 z=W8kz=W_8^k,有 z8=1z^8=1 且 z≠1z\ne1。几何级数及其求导给出

∑n=07zn=1−z81−z,∑n=07(n+1)zn=1−9z8+8z9(1−z)2.\sum_{n=0}^{7}z^n=\frac{1-z^8}{1-z},\qquad \sum_{n=0}^{7}(n+1)z^n=\frac{1-9z^8+8z^9}{(1-z)^2}.

把 z8=1z^8=1 代入第二式,得到

X[k]=−81−e−jπk/4=−4+4jcot⁡(πk8),k=1,…,7.X[k]=\frac{-8}{1-e^{-j\pi k/4}}=-4+4j\cot\left(\frac{\pi k}{8}\right),\qquad k=1,\ldots,7.

例如 cot⁡(π/8)=1+2\cot(\pi/8)=1+\sqrt2、cot⁡(3π/8)=2−1\cot(3\pi/8)=\sqrt2-1,正好复核 X[1]X[1] 与 X[3]X[3]。因输入为实数,还应有 X[7]=X∗[1]X[7]=X^*[1]、X[6]=X∗[2]X[6]=X^*[2]、X[5]=X∗[3]X[5]=X^*[3];X[0]X[0] 和 X[4]X[4] 应为实数。共轭对称是检查手段,不能替代全部输出的计算。

递归什么时候停,什么情况不能照套? 长度为 11 时,输出就是输入;长度为 22 时,直接计算 [x[0]+x[1],x[0]−x[1]][x[0]+x[1],x[0]-x[1]]。长度为 44 时,两个奇组已经各只有一个数。每次拆分使用当前子序列的局部下标,不能反复按原始八点输入的下标取样。

标准分裂基算法用于 N=2mN=2^m。单层分组在 NN 能被四整除时同样成立,但长度不是二的幂时,小变换还需要别的算法完成,不能默认这套递归直接闭合。分裂基让偶支路采用二分规模、奇支路采用四分规模;这与上一节按任意因子组合的混合基分解应当区分。为凑长度而补零会改变 DFT 的频率栅格,不能把八点结果当成原六点 DFT。

每层组合只做与当前长度成正比的运算,总工作量满足 T(N)=T(N/2)+2T(N/4)+O(N)T(N)=T(N/2)+2T(N/4)+O(N),得到 O(Nlog⁡N)O(N\log N) 的复杂度。传统分裂基在常见实加、实乘计数下可减少运算,但不能据此断言任何硬件上都最快;访存、向量化和实现方式也影响耗时。本节不把基二 FFT 的乘法计数直接套到分裂基上。

这些公式对复数输入同样成立,此时不要再要求共轭对称。如果改算逆 DFT,需要将旋转因子的指数改为正号,四组公式中的 −j-j 与 +j+j 相应交换,最后按约定除以 NN;仅把正变换结果除以 NN 并不能得到逆变换。

自己做一次最短检查。 取八点单位冲激 x=[1,0,0,0,0,0,0,0]x=[1,0,0,0,0,0,0,0],两条奇支路均为零,偶组的四点 DFT 全为 11,四组组合应得到八个 11。再把冲激移到下标一,取 x=[0,1,0,0,0,0,0,0]x=[0,1,0,0,0,0,0,0],结果应为 X[k]=W8kX[k]=W_8^k。前者检查是否遗漏输出,后者检查旋转因子的方向和输出位置。

来源:主讲义第 1-125 行

模考补充:两个门函数的圆周卷积为什么要折回尾部

原题第 11 页。以下是按统一约定独立推导的考点补充;教学例子会注明,不能替代原卷全部小问的逐题解析。

DTFT 以 2π2\pi 为周期,两个序列相乘对应一个周期内的频谱卷积:

x[n]v[n]⟷12π∫−ππX(ejθ)V(ej(ω−θ)) dθ.x[n]v[n]\longleftrightarrow\frac1{2\pi}\int_{-\pi}^{\pi} X(e^{j\theta})V(e^{j(\omega-\theta)})\,d\theta.

第二个频谱的自变量要按 2π2\pi 折回。先用普通卷积计算,再把其相隔 2π2\pi 的副本相加,也能得到相同结果。

原题

h[n]=2sin⁡(πn/2)πnsin⁡(3πn/4)πn,h[0]=34.h[n]=2\frac{\sin(\pi n/2)}{\pi n}\frac{\sin(3\pi n/4)}{\pi n},\qquad h[0]=\frac34.

两个 sinc 序列分别对应全宽 π\pi 与 3π/23\pi/2、高度1的周期门。普通门卷积的重叠长度在中心为 π\pi,从 ∣ω∣=π/4|\omega|=\pi/4 线性下降,到 5π/45\pi/4 才为零。乘上 2/(2π)=1/π2/(2\pi)=1/\pi 后,得到普通梯形;其支撑超过了主周期,尾部必须叠回。

对 3π/4<ω<π3\pi/4<\omega<\pi,中心副本贡献 5/4−ω/π5/4-\omega/\pi,来自 2π2\pi 的副本贡献 ω/π−3/4\omega/\pi-3/4,相加恰为 1/21/2。因此

H(ejω)={1,∣ω∣≤π/4,5/4−∣ω∣/π,π/4<∣ω∣<3π/4,1/2,3π/4≤∣ω∣≤π,H(e^{j\omega})=\begin{cases} 1,&|\omega|\le\pi/4,\\ 5/4-|\omega|/\pi,&\pi/4<|\omega|<3\pi/4,\\ 1/2,&3\pi/4\le|\omega|\le\pi, \end{cases}

并周期延拓。特别是 Nyquist 点为 1/21/2,不是未叠回时的 1/41/4。

检查面积也能发现漏谱:∫−ππH dω=3π/2=2πh[0]\int_{-\pi}^{\pi}H\,d\omega=3\pi/2=2\pi h[0]。若面积不符,优先检查卷积的 1/(2π)1/(2\pi)、原式的2,以及越过 ±π\pm\pi 的尾部。

同一套宽度约定:调制后的门高不能漏掉

2024汇编第六套·原题第 42 页 令 a=π/5a=\pi/5,G(v)G(v) 在 ∣v∣<1/2|v|<1/2 为1。原题

h[n]=4sin⁡(an/2)πncos⁡(an),h[0]=2aπ=25.h[n]=4\frac{\sin(an/2)}{\pi n}\cos(an),\qquad h[0]=\frac{2a}{\pi}=\frac25.

先把正弦核认成半宽 a/2a/2、高度4的低通门,再由余弦拆成两份各乘 1/21/2:

H(ejΩ)=2G ⁣(Ω−aa)+2G ⁣(Ω+aa),H(e^{j\Omega})=2G\!\left(\frac{\Omega-a}{a}\right)+2G\!\left(\frac{\Omega+a}{a}\right),

按 2π2\pi 周期延拓。两通带各全宽 aa、高度2,积分为 4a=2πh[0]4a=2\pi h[0]。若直接写成高度1,面积检查就会失败。

原三角谱 L(Ω)L(\Omega) 的峰为1、半宽为 aa,第一次乘 cos⁡(an)\cos(an) 得 12[L(Ω−a)+L(Ω+a)]\frac12[L(\Omega-a)+L(\Omega+a)]。过上述高度2的带通后,两侧只剩全宽 aa 的截顶三角峰,峰高回到1、边缘内侧为 1/21/2。再乘余弦,令 Lc(Ω)=(1−∣Ω∣/a)G(Ω/a)L_c(\Omega)=(1-|\Omega|/a)G(\Omega/a):

X3(Ω)=Lc(Ω)+12Lc(Ω−2a)+12Lc(Ω+2a).X_3(\Omega)=L_c(\Omega)+\frac12L_c(\Omega-2a)+\frac12L_c(\Omega+2a).

中央两份频移谱相加后峰高为1,两个外侧峰各为 1/21/2。每一步同时标门宽、门高与调制的 1/21/2,才能解释最终波形;端点普通取值不改变积分,不能把非零边缘误画成降到零。

低通保留内侧半瓣,为什么会出现 V 形谱

对应 2025汇编第六套·原题第 53 页 的调制、低通与周期抽样题。以下 Ω\Omega 是离散角频率,单位为 rad/sample,所有 DTFT 都按 2π2\pi 周期延拓。继续用 G(u)=1G(u)=1(∣u∣<1/2|u|<1/2)及 Sa⁡(u)=sin⁡u/u\operatorname{Sa}(u)=\sin u/u。

先把题中输入写成 Sa 形式,零点不必另猜:

x[n]=8[sin⁡(πn/8)πn]2=18Sa⁡2 ⁣(πn8),x[0]=18.x[n]=8\left[\frac{\sin(\pi n/8)}{\pi n}\right]^2 =\frac18\operatorname{Sa}^2\!\left(\frac{\pi n}{8}\right),\qquad x[0]=\frac18.

单个正弦核的 DTFT 是全宽 π/4\pi/4、高度1的周期门 G(4Ω/π)G(4\Omega/\pi)。时域平方对应门的周期卷积并带 1/(2π)1/(2\pi);本题重叠支撑未越出主周期,卷积重叠长度是 (π/4−∣Ω∣)+(\pi/4-|\Omega|)_+。再乘原式的8,得到

X(ejΩ)=Λ(4Ω/π),Λ(u)=max⁡(1−∣u∣,0),−π≤Ω≤π.X(e^{j\Omega})=\Lambda(4\Omega/\pi),\qquad \Lambda(u)=\max(1-|u|,0),\quad -\pi\le\Omega\le\pi.

谱顶为1、两端为 ±π/4\pm\pi/4;面积 π/4=2πx[0]\pi/4=2\pi x[0],检查了所有幅度因子。

乘 cos⁡(πn/4)\cos(\pi n/4) 后,两份三角谱向 ±π/4\pm\pi/4 平移,各乘 1/21/2:

G1(ejΩ)=12 ⁣[Λ ⁣(4(Ω−π/4)π)+Λ ⁣(4(Ω+π/4)π)].G_1(e^{j\Omega})=\frac12\!\left[ \Lambda\!\left(\frac{4(\Omega-\pi/4)}{\pi}\right)+ \Lambda\!\left(\frac{4(\Omega+\pi/4)}{\pi}\right)\right].

原低通是 H1(ejΩ)=2G(2Ω/π)H_1(e^{j\Omega})=2G(2\Omega/\pi),通带全宽 π/2\pi/2、高度2。在 0<Ω<π/40<\Omega<\pi/4,右移三角的内侧高度为 4Ω/π4\Omega/\pi;先乘调制的 1/21/2,再乘滤波器的2,两者抵消。负半轴对称,故

G2(ejΩ)=4∣Ω∣πG(2Ω/π).G_2(e^{j\Omega})=\frac{4|\Omega|}{\pi}G(2\Omega/\pi).

中心是谷底0,通带边缘内侧趋于1。低通截取的是两个侧瓣的内半边,因此不能凭“低通”二字画成中心最高的小三角。截止点单值沿用半值约定,不影响反变换。

周期4的点乘保留样本,1/4 从哪里来

原图最后一步在原整数时轴上只保留 n=4ln=4l 的样本:

p[n]=∑l∈Zδ[n−4l]=14∑r=03ejrπn/2,y[n]=g2[n]p[n].p[n]=\sum_{l\in\mathbb Z}\delta[n-4l] =\frac14\sum_{r=0}^{3}e^{jr\pi n/2},\qquad y[n]=g_2[n]p[n].

右侧四个复指数在 nn 是4的倍数时同相相加,其余整数点相消。逐项使用调制定理,而不改变样本编号,得到

Y(ejΩ)=14∑r=03G2(ej(Ω−rπ/2)).Y(e^{j\Omega})=\frac14\sum_{r=0}^{3}G_2(e^{j(\Omega-r\pi/2)}).

每一瓣只移位,横轴不压缩;这与重新编号的抽取序列 g2[4n]g_2[4n] 所用公式不同。在第 kk 个长度 π/2\pi/2 的区间内,

Y(ejΩ)=∣Ω−kπ/2∣π,∣Ω−kπ/2∣<π/4.Y(e^{j\Omega})=\frac{|\Omega-k\pi/2|}{\pi}, \qquad |\Omega-k\pi/2|<\pi/4.

谷点 kπ/2k\pi/2 为0,邻接峰的单侧极限是 1/41/4。一主周期内四个 V 形单元的面积合计仍为 π/4\pi/4,故 y[0]=1/8y[0]=1/8,与 p[0]=1p[0]=1 一致;漏掉 1/41/4 会直接破坏这个零时刻检查。

2025第六套:输入、调制、低通与周期4点乘的四级DTFT

手写笔记对照: 手写笔记 PDF 15—19 页 · 手写笔记 PDF 20—23 页 · 手写笔记 PDF 102—110 页。这份资料没有可核实的作者与版次,作为补充笔记使用。

带着这个问题阅读: 先对有限矩形序列求 DTFT,再在离散频点取样得到 DFT。比较线性卷积与循环卷积,写清补零长度。

读后自检: DTFT 对 ω\omega 为 2π2\pi 周期;DFT 只有 N 个频点。用 DFT 算两有限序列的线性卷积时,变换长度至少为 Lx+Lh−1L_x+L_h-1。

相关练习 · S015 资料与审查说明

来源:主讲义第 1-1 行