• DFS 和 DFT 的导出• DFS 和 DFT 的性质• Z 变换与 DFS 的关系• FFT• IDFT• 频谱分析频谱分析第三章第三章 DFT——离散付氏变换离散付氏变换1 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 连续连续信号信号 xa(t)，其傅里叶，其傅里叶变换为变换为：：³ xa(t) 为为时时域域连续连续信号信号³ Xa(Ω) 为为频频域域连续连续信号信号3.1 问题问题的提出：的提出：连续连续信号的傅里叶信号的傅里叶变换变换2 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n离散信号在两种离散信号在两种变换变换域中的表示方法域中的表示方法 （（1））离离散散时时间间傅傅里里叶叶变变换换 DTFT -- 提提供供了了绝绝对对可可加加的的离离散散时时间间序序列列在在频频域（域（ω）中的表示方法中的表示方法 （（2））Z 变换变换 -- 提供任意序列的提供任意序列的 z 域表示 这两种变换有两个共同特征：这两种变换有两个共同特征： （（1））变换适合于变换适合于无限长序列无限长序列 （（2）它们是）它们是连续变量连续变量 ω 或或 z 的函数的函数3.1 问题问题的提出：离散信号的的提出：离散信号的变换变换3 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n问问题题：：X(z)，，X(ejw) 都都是是连连续续的的，，利利用用计计算算机机处处理理有有困困难难，，例例如如使使用用 Matlab，因此，因此³提出了在频域内取样，使频谱离散化的问题；提出了在频域内取样，使频谱离散化的问题；³必须截断序列，得到有限个点的序列。
必须截断序列，得到有限个点的序列n目标：目标：我们需要得到一个我们需要得到一个可进行数值计算可进行数值计算的变换的变换n方法：方法： （（1 1））DTFT - 频频域中原始信号域中原始信号频谱频谱的周期拓展的周期拓展 （（2））对对 DTFT 在在频频域中采域中采样样 -- DFS （（3））将将 DFS 推广到有限持推广到有限持续时间续时间序列序列 DFT （（DFT 避免了前面提到的那两个避免了前面提到的那两个问题问题，并且它是，并且它是计计算机可算机可实现实现 的的变换变换方式nDFT DFT 已成为已成为 DSP DSP 算法中的核心变换，算法中的核心变换，原因：原因： （（1 1）有限长序列傅里叶变换的重要方法）有限长序列傅里叶变换的重要方法 （（2 2）有快速算法）有快速算法3.1 问题问题的提出：可的提出：可计计算性算性4 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 时间函数时间函数 频率函数频率函数3.1 问题问题的提出：傅里叶的提出：傅里叶变换变换的四种形式的四种形式 （（1））n非周期连续时间非周期连续时间——傅里叶变换傅里叶变换(FT)(FT)－连续频率－连续频率n周期连续时间周期连续时间——傅里叶级数傅里叶级数(FS)(FS)－离散频率－离散频率n非周期离散时间非周期离散时间——离散时间傅里叶变换离散时间傅里叶变换(DTFT)(DTFT)－连续频率－连续频率n周期离散时间周期离散时间——离散傅里叶级数离散傅里叶级数(DFS)(DFS)－离散频率－离散频率 5 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.1 问题的提出：傅里叶变换的四种形式问题的提出：傅里叶变换的四种形式 （（2））1. 连续信号（非周期）的付氏变换连续信号（非周期）的付氏变换n时域连续时域连续函数造成频域是函数造成频域是非周期的谱非周期的谱n时域的非周期时域的非周期造成频域是造成频域是连续的谱连续的谱6 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 2. 周期连续时间信号：周期连续时间信号：傅里叶级数傅里叶级数 FSn时域连续时域连续函数函数造成频域造成频域是是非周期的谱非周期的谱。
n频域的离散频域的离散对应对应时域是周期函数时域是周期函数3.1 问题的提出：傅里叶变换的四种形式问题的提出：傅里叶变换的四种形式 （（3））时域周期时域周期频域离散频域离散)(0WnXWTp20=W)(~txtT7 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3. 非周期离散信号：非周期离散信号：离散时间傅里叶变换离散时间傅里叶变换 DTFTn时域的离散化时域的离散化造成频域的造成频域的周期延拓周期延拓n时域的非周期时域的非周期对应于对应于频域的连续频域的连续3.1 问题问题的提出：傅里叶的提出：傅里叶变换变换的四种形式的四种形式 （（4））时域离散时域离散频域周期频域周期取样定理取样定理8 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院4. 周期离散时间信号：离散傅里叶级数周期离散时间信号：离散傅里叶级数 DFSn一个域的离散造成另一个域的周期延拓一个域的离散造成另一个域的周期延拓n离散傅里叶级数的时域和频域都是离散傅里叶级数的时域和频域都是离散的离散的和和周期的周期的3.1 问题问题的提出：傅里叶的提出：傅里叶变换变换的四种形式的四种形式 (5)kTT1n周期取样间隔时域周期、离散时域周期、离散频域周期、离散频域周期、离散9 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n四种傅里叶变换形式的归纳总结：四种傅里叶变换形式的归纳总结：形式形式时间函数时间函数频率函数频率函数傅里叶傅里叶变换变换 FT连续连续非周期非周期非周期非周期连续连续傅里叶傅里叶级数级数 FS连续连续周期周期(T0)非周期非周期离散离散(Ω0=2π/T0)离离散散时时间间傅傅里里叶叶变变换换DTFT离散离散(T)非周期非周期周期周期(Ωs=2π/T)连续连续离离散散傅傅里里叶级数叶级数DFS离散离散(T)周期周期(T0)周期周期(Ωs=2π/T)离散离散(Ω0=2π/T0)离散时间函数的取样间隔：离散时间函数的取样间隔：T1，取样频率：，取样频率：离散频率函数的取样间隔：离散频率函数的取样间隔：F0，，时间周期：时间周期：3.1 问题问题的提出：傅里叶的提出：傅里叶变换变换的四种形式的四种形式 （（6））结论结论：：①① 时时域中函数取域中函数取样样(离散离散) （（映射）映射）频频域中函数周期重复；域中函数周期重复；②② 频频域中函数取域中函数取样样 （映射）（映射） 时时域中函数周期重复；域中函数周期重复；③③ 取取样间样间隔隔 （映射）（映射） 周期（周期（2π/间间隔）隔）10 0nN(d) DFSk0N-N1/T-N(c) FSW-ΩmXa(kΩ1)tTm0T1-T11Ω1Ωmnx(n) = xa(nT)Tm0(b) DTFTWΩm-ΩmΩs-Ωs1/TTtxa(t)Tm0(a) FTWΩm-ΩmXa(Ω)时域中函数的取样和频域中函数的取样时域中函数的取样和频域中函数的取样3.1 问题问题的提出：傅里叶的提出：傅里叶变换变换的四种形式的四种形式 (7)11 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n由由以以上上讨讨论论可可以以清清楚楚地地看看到到，，时时域域取取样样将将引引起起频频域域的的周周期期延延拓拓，，频频域域取取样样也也将将引引起起时时域域的的周周期期延延拓拓。
n因因此此可可以以设设想想，，如如果果同同时时对对频频域域和和时时域域取取样样，，其其结结果果是是时时域域和和频频域域的的波波形形都都变变成成离离散散、、周周期期性性的的波波形形，，从从而而我我们们可可以以利利用用付付氏氏级级数数这这一一工工具具，，得得到它们之间的到它们之间的离散付氏级数离散付氏级数 DFS DFS 关系关系3.2 DFS 及其性质及其性质12 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n基本关系式基本关系式 若若 r，，m 都是整数都是整数,则则:其中其中:DFS 定义：定义：预备知识预备知识证明证明: 对于对于r=m：不论：不论 k 取何值，显然等式成立取何值，显然等式成立 对于对于r≠m：：13 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n为了推导为了推导 的关系，作下列变量代换：的关系，作下列变量代换：³时域：时域：³频域：频域：n则得：则得：?DFS 定义：定义：正变换正变换14 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n周期离散序列的周期离散序列的 Z Z 变换存在（收敛）的问题变换存在（收敛）的问题 ³因为周期离散序列，因为周期离散序列， 而而对对于于周周期期信信号号，，严严格格数数学学意意义义上上讲讲，，其其 Z 变变换换不不收收敛敛，，因为：因为： 而对于而对于 找找不不到到衰衰减减因因子子使使它它绝绝对对可可和和（（收收敛敛））。
为为此此，，定定义义新新函函数数，，其其 Z 变换：变换：DFS 定义：定义：正变换正变换15 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n其频谱：（其频谱：（ω 是连续变量，需要对其离散化）是连续变量，需要对其离散化） DFS 定义：定义：正变换正变换（（取取 的一个主周期进行的一个主周期进行 Z 变换变换）） 16 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n频域取样频域取样³X(ejω) 是是连连续续变变量量 ω 的的周周期期函函数数，，周周期期为为2π把把ω 离离散散化化，，即即在在0～～2π区区间间内等内等间间隔取隔取 N 个点，取个点，取样间样间隔隔为为 2π/N³另另一一个个角角度度看看，， X(ejω) 是是 Z 平平面面单单位位圆圆上上的的 Z 变变换换连连续续变变量量 ω 的离散化也可以的离散化也可以认为认为是把是把单单位位圆圆分分 N 等分，每分等分，每分为为 2π/N ³ 其中：其中： 称称为为频频域中的取域中的取样间样间隔隔，， 也称也称为为频频率分辨率率分辨率。
DFS 定义：定义：正变换正变换17 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 定义：定义：正变换正变换则则其中其中18 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS：：DFS 定义：定义：正变换正变换也仅有也仅有 0 0，，1 1，，……，，N-1 N-1 个独立值个独立值, ,周期为周期为 N N因为因为随随 k 周期变化，周期变化，仅有仅有 0，，1，，…，，N-1 个独立值个独立值仅有仅有 0，，1，，…，，N-1 个独立值个独立值所以所以19 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n反变换反变换IDFS IDFS 正变换两端乘以正变换两端乘以 ，，m=0,1,…,N-1 然后令然后令 k=0，，1，，…，，N-1 求和，得：求和，得：DFS 定义：定义：反变换反变换 用正交条件：用正交条件： 20 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 定义：定义：反变换反变换即即（只有（只有 m=n 时，才有值，而时，才有值，而 m 不等于不等于 n 时，为零，因此，时，为零，因此，x(n) 只取只取 x(m) ））变量变量m替换为替换为n，得，得21 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nDFS 变换对变换对：：时域周期序列与频域周期序列间的关系时域周期序列与频域周期序列间的关系DFS 定义：定义：反变换反变换其中其中22 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n在什么条件下不产生混迭失真？在什么条件下不产生混迭失真？ —频率取样频率取样³频频率率取取样样：：若若时时间间信信号号有有限限长长，，当当满满足足下下列列条条件件时时，，X(ejω) 的的样样本本值值 X(k) 能不失真的恢复成原信号。
能不失真的恢复成原信号³为了避免时间上的混迭：为了避免时间上的混迭： （（1）必须是时间限制（有限时宽））必须是时间限制（有限时宽） （（2）取样频率间隔小于）取样频率间隔小于DFS 定义：定义：几点说明几点说明23 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 频率分量频率分量 ³如果变量如果变量 ³DFS 可表示为：可表示为： ³因此，因此，时域时域 n n 及频域及频域 k k 都是有物理意义的都是有物理意义的DFS 定义：定义：几点说明几点说明（指数项（指数项 kn 不变）不变）24 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³更具体地，傅里叶系数的标号更具体地，傅里叶系数的标号 k 和频率和频率 f 的关系为：的关系为：³所以：所以： ³对应关系对应关系：： 傅里叶系数标号傅里叶系数标号k ：：0～～N 数字频率数字频率ω：：0～～2π 模拟频率模拟频率 f ：：0～～fs DFS 定义：定义：几点说明几点说明25 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 定义：定义：几点说明几点说明³频率成份频率成份±直流分量直流分量：： 当当 k=0 时时，， ，，此此时时得得到到的的傅傅里里叶叶级级数数的的系系数数称称为信号的直流分量（为信号的直流分量（DC Component），）， 是信号的平均值；是信号的平均值；±交流分量交流分量：：¯其其它它频频率率（（k>0））称称为为周周期期信信号号的的谐谐波波，，此此时时的的傅傅里里叶叶级级数数系系数数称称为为信号的交流分量。
信号的交流分量¯k=1 时时的的频频率率为为信信号号的的一一次次谐谐波波，，或或基基频频，，频频率率大大小小为为 fs/N，，时时间间为为 NTs，等于完成一个周期所需要的时间其它谐波为基频的整数倍等于完成一个周期所需要的时间其它谐波为基频的整数倍±离离散散傅傅里里叶叶级级数数包包含含了了 0 到到 (N-1)fs/N 的的频频率率，，因因而而 N 个个傅傅里里叶叶级级数数的的系系数位于从数位于从 0 直到接近取样频率的频率上直到接近取样频率的频率上时域时域频域频域26 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 定义：定义：几点说明几点说明³周期信号的频谱周期信号的频谱±由由傅傅里里叶叶系系数数 可可得得到到 的的幅幅度度频频谱谱 和和相相位位频频谱谱 ，，不不难难证证明明，，如如果果 是是实实序序列列，，那那么么幅幅度度频频谱谱是是周周期期性性偶偶函函数数，，相位频谱是周期性奇函数相位频谱是周期性奇函数±周周期期信信号号由由离离散散傅傅里里叶叶级级数数 DFS 得得到到的的频频谱谱，，和和非非周周期期信信号号由由离离散时间傅里叶变换散时间傅里叶变换 DTFT 得到的频谱之间有重要区别。
得到的频谱之间有重要区别①① DTFT 产产生生连连续续频频谱谱，，这这意意味味着着频频谱谱在在所所有有的的频频率率处处都都有有值值，，因因而而非非周期信号的幅度和相位频谱是光滑无间断的曲线周期信号的幅度和相位频谱是光滑无间断的曲线②② 与与之之相相反反，，DFS 仅仅有有 N 点点的的频频谱谱，，仅仅包包含含有有限限个个频频率率，，因因而而周周期期信信号号的的幅幅度度和和相相位位频频谱谱是是线线谱谱，，即即相相等等间间隔隔的的竖竖线线，，当当频频谱谱的的横横坐坐标标变变量量用用实实际际频频率率 f 代代替替 k 时时，，谱谱线线间间隔隔为为 fs/N并并不不是是所所有有的的周周期期信信号号都都含含有有全全部部谐谐波波，，例例如如有有些些频频谱谱只只有有奇奇次次谐谐波波，，比比如如三三角角波波，，偶偶次次谐谐波为波为0，而有些频谱仅在一些谐波处的值为，而有些频谱仅在一些谐波处的值为027 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 的的 Matlab 的实现的实现 由由 DFS 的的定定义义可可以以看看出出它它是是一一种种可可进进行行数数值值计计算算表表示示式式，，它它可由多种方式实现。
可由多种方式实现 （1）利用循环语句 for…..end 实现 为了计算每个样本为了计算每个样本 ，可用，可用 for ….. end 语句实现求和语句实现求和 为为了了计计算算所所有有的的 DFS 系系数数，，需需要要另另外外一一个个for…..end 循循环环，，这这将将导导致致运运行行嵌嵌套套的的两两个个for ….end 循循环环显显然然，，这这种种方法的效率较低方法的效率较低28 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院设设 和和 代代表表序序列列 x(n) 和和 X(k) 主主周周期期的的列列向向量量，，则则 DFS 的正反变换表达式由下式给出：的正反变换表达式由下式给出： 其中矩阵其中矩阵 WN 由下式给出：由下式给出： 矩阵矩阵 WN 为方阵，叫做为方阵，叫做 DFS 矩阵矩阵. . （（2）利用矩阵）利用矩阵——矢量乘法矢量乘法29 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院function [Xk] = dfs(xn,N)n = [0:1:N-1]; % row vector for nk = [0:1:N-1]; % row vecor for kWN = exp(-j*2*pi/N); % Wn factornk = n'*k; % creates a N by N matrix of nk valuesWNnk = WN .^ nk; % DFS matrixXk = xn * WNnk; % row vector for DFS coefficients function [xn] = idfs(Xk,N)n = [0:1:N-1]; % row vector for nk = [0:1:N-1]; % row vecor for kWN = exp(-j*2*pi/N); % Wn factornk = n'*k; % creates a N by N matrix of nk valuesWNnk = WN .^ (-nk); % IDFS matrixxn = (Xk * WNnk)/N; % row vector for IDFS valuesDFS 的的 Matlab 的实现的实现30 例例 ：：求出下面周期序列的 DFS 表示式 解解：上述序列的基本周期为 N=4，因而 W4 = e-j2π/4 = -j， 31 32 33 例例: 下面给出一周期下面给出一周期“方波方波”序列：序列： 其中，其中， m=0, ±1, ±2,…，，N 是基本周期，是基本周期， L/N 是占空比。
是占空比a)确定一种用确定一种用 L 与与 N 描述的描述的 的表达式的表达式b)分分别别画画出出当当 L =5, N = 20；；L=5，，N=40；；L=5，，N=60；；L=7，，N=60 时时 表达式c)对所得结果进行讨论对所得结果进行讨论34 解：解：(a) 由由 DFS 定义可得定义可得而：而： 的幅值可表示为：的幅值可表示为： 35 b. Matlab 程序如下：程序如下：% Chapter 3: Example 3.03L = 5; N = 20;(改改变变参数）参数）x = [ones(1,L), zeros(1,N-L)];xn = x' * ones(1,3);xn = (xn(:))';n = -N:1:2*N-1;subplot(1,1,1);subplot(2,1,2);stem(n,xn); xlabel('n');ylabel('xtilde(n)')title('Three periods of xtilde(n)')axis([-N,2*N-1,-0.5,1.5]) -20-100102030-0.500.511.5nxtilde(n)Three periods of xtilde(n)36 % Part (b)L = 5; N = 20;(改变参数）改变参数）xn = [ones(1,L), zeros(1,N-L)];Xk = dfs(xn,N);magXk = abs([Xk(N/2+1:N) Xk(1:N/2+1)]);k = [-N/2:N/2];subplot(2,2,1); stem(k,magXk); axis([-N/2,N/2,-0.5,5.5])xlabel('k'); ylabel('Xtilde(k)')title('DFS of SQ. wave: L=5, N=20')37 5个峰值个峰值5个峰值个峰值5个峰值个峰值7个峰值个峰值n注意： 是周期信号，图中只画出了从 –N/2 到 N/2 的部分。
n c. 从图中可以看到，方波的 DFS 系数的包络像“ Sinc ”函数， ① K=0 时的幅度等于 L；② 同时函数的零点位于 N/L（占空比的倒数）的整数倍处；③ L=5 不变，N变大（即填0，但有效信息没有增加），则形状不变，只是更平滑，即获得了一个高密度谱；④ N=60 不变，L 变大（即增加了原始数据长度），则变换后得形状发生了变化，获得了更多的信息，即高分辨率谱38 例例 ：： 设设 当当 N=5、、10、、20、、50 时时，，分分别别对对其其 Z 变变换换在在单单位位圆圆上取样，研究不同的上取样，研究不同的 N 对时域的影响对时域的影响可用可用 Matlab 来实现取样运算：来实现取样运算：用用 IDFS 计算，确定相应的时域序列计算，确定相应的时域序列解：可得解：可得 x(n) 的的 Z 变换为：变换为：39 % Frequency-domain sampling% x(n)=(0.7)^n * u(n)% X(z)=z/(z-0.7); |z|>0.7 subplot(1,1,1)N = 5; (改改变变参数）参数）k = 0:1:N-1;wk = 2*pi*k/N;zk = exp(j*wk);Xk = (zk)./(zk-0.7);xn = real(idfs(Xk,N));%只取只取实实部，去掉部，去掉产产生的虚部生的虚部误误差差xtilde = xn'* ones(1,8); % 画出画出8个周期个周期 xtilde = (xtilde(:))';subplot(2,2,1);stem(0:39,xtilde);axis([0,40,-0.1,1.5]);xlabel('n');ylabel('xtilde(n)'); title('N=5')40 0204000.511.5nxtilde(n)N=50204000.511.5nxtilde(n)N=100204000.511.5nxtilde(n)N=200204000.511.5nxtilde(n)N=40n从从图图中中清清楚楚地地表表明明在在时时域域中中出出现现的的混混叠叠，，尤尤其其是是当当 N=5 与与 N=10 时时。
对对于于大大的的 N 值值，，其其 x(n) 的的尾尾部部足足够够小小，，实实际际上上不不会会导导致致明明显显的的混混迭迭这对于变换前，有效截取无限序列，是非常有效的这对于变换前，有效截取无限序列，是非常有效的1.20201.02911.00081.000041 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n线性线性且：且：则则－－－－ a,b为任意常数为任意常数DFS 的性质：的性质：线性线性42 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n序列的周期移位（时域）序列的周期移位（时域） 若若 是周期序列，其周期为是周期序列，其周期为N，移位后仍为周期序列，且：，移位后仍为周期序列，且：DFS 的性质：的性质：序列的周期移位序列的周期移位证明：证明：43 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n调制特性（频域周期移位）调制特性（频域周期移位）DFS 的性质：的性质：调制特性调制特性证明：证明：44 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 周期卷积（时域）周期卷积（时域）若若则则频域相乘频域相乘 时域卷积时域卷积周周期期卷卷积积：：两两个个周周期期序序列列在在一一个个周周期期上上的的线线性性卷卷积积，，是是一一种种特殊的特殊的卷积计算形式。
卷积计算形式DFS 的性质：的性质：周期卷积周期卷积 （（1））45 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 的性质：的性质：周期卷积周期卷积 （（2））证明：证明：46 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 的性质：的性质：周期卷积周期卷积 （（3））0N-Nm0N-Nm0N-Nm0N-Nm（（1））x1(n)和和x2(n)是周期的是周期的 （（2）求和范围为）求和范围为一个周期一个周期（（3）周期序列周）周期序列周期卷积后，序期卷积后，序列的长度仍然列的长度仍然是周期的；是周期的；位置保持位置保持不变不变47 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n序列的线性卷积与周期卷积的几点区别：序列的线性卷积与周期卷积的几点区别：线性卷积的求和对参与卷积的两个序列无任何线性卷积的求和对参与卷积的两个序列无任何 要求，要求，而周期卷积要求两个序列是周期相同的周期序列而周期卷积要求两个序列是周期相同的周期序列线性卷积的求和范围由两个序列的长度线性卷积的求和范围由两个序列的长度 和所在的区间和所在的区间决定，决定，而周期卷积的求和范围是一个周期而周期卷积的求和范围是一个周期 N。
线性卷积所得序列的长度线性卷积所得序列的长度 (M+N-1) 由参与卷积的两个由参与卷积的两个序列的长度确定，序列的长度确定，而周期卷积的结果仍是周期序列而周期卷积的结果仍是周期序列 ，且周期与原来的两个序列周期相同且周期与原来的两个序列周期相同周期卷积等同于两个周期序列在一个周期上的线性卷周期卷积等同于两个周期序列在一个周期上的线性卷积计算 DFS 的性质：的性质：周期卷积周期卷积 （（4））48 解：解：例：例： 已知序列已知序列 x1(n)=R4(n)，，x2(n)=(n+1)R5(n)，，分别将序列以周期为分别将序列以周期为 N=6 拓展成周期序列，求拓展成周期序列，求两个周期序列的周期卷积和两个周期序列的周期卷积和49 15451250 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n频域周期卷积频域周期卷积 利用利用 DFS DFS 的对偶性有：的对偶性有： 若若则则时域相乘时域相乘 频域卷积频域卷积DFS 的性质：的性质：周期卷积周期卷积 (5)注注意意频频域域卷卷积积的的求求和和号号前面有前面有 1/N51 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 的性质：的性质：共轭对称性共轭对称性n由任一周期性序列由任一周期性序列 ，定义如下两个序列：，定义如下两个序列：³共轭偶对称周期性序列共轭偶对称周期性序列³共轭奇对称周期性序列共轭奇对称周期性序列 ³ 且具有如下关系：且具有如下关系：其它对称性其它对称性质见教科书质见教科书52 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFS 定义和性质：定义和性质：小结小结n时域周期序列与频域周期序列的关系 DFSnDFS 的性质 重点：周期移位 调制特性 周期卷积53 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n对对于于一一段段有有限限长长信信号号（（连连续续）），，分分析析频频谱谱问问题题是是付付氏氏积积分分问问题题，，进进行行时时域域周周期期重重复复和和取取样样两两过过程程，，就就可可把把广广义义积积分分问题变成问题变成有限项求和有限项求和，即由，即由CTFTDFS。
nDFS 变变换换：：周周期期离离散散时时间间函函数数与与一一周周期期离离散散频频率率函函数数的的组组合合，，它它们们是是有有限限求求和和（（而而不不是是积积分分）），，常常用用 DFS 来来逼逼近连续时间过程的傅氏变换近连续时间过程的傅氏变换³也也即即要要用用数数字字运运算算能能完完全全计计算算出出付付氏氏积积分分，，必必须须对对时时间间函函数数和和频频率函数取样（即率函数取样（即DFS），选择时间有限和频率有限的信号选择时间有限和频率有限的信号①① 时间取样：取样频率大于信号最高频率两倍；时间取样：取样频率大于信号最高频率两倍；②② 频频率率取取样样：：取取样样间间隔隔足足够够小小，，使使时时间间函函数数的的周周期期（（单单位位圆圆上上等分（取样）的点数等分（取样）的点数）大于信号的时域长度大于信号的时域长度³结果：频域和时域中均不出现混迭现象结果：频域和时域中均不出现混迭现象3.3 有限离散傅里叶变换及其性质有限离散傅里叶变换及其性质 (1)54 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n离离散散傅傅氏氏级级数数提提供供了了一一种种对对离离散散时时间间傅傅氏氏变变换换作作数数值值计计算算的的技技巧巧，，它它在在时时域域和和频频域域都都是是周周期期的的，，但但在在实实际际中中大大多多数数信号不具有周期性，它们很可能具有有限持续时间。
信号不具有周期性，它们很可能具有有限持续时间n对这些信号，怎样探讨一种可数值计算的傅氏表达式？对这些信号，怎样探讨一种可数值计算的傅氏表达式？³理理论论上上，，可可通通过过构构造造一一周周期期信信号号，，其其基基本本形形状状为为有有限限持持续时间续时间信号，然后信号，然后计计算此周期信号的算此周期信号的 DFS³实实际际上上，，这这也也就就是是定定义义了了一一种种新新的的变变换换，，称称为为离离散散傅傅氏氏变换变换（（DFT），它是），它是 DFS 的主周期的主周期³DFT 是是对对任任意意有有限限持持续续时时间间序序列列可可数数值值计计算算的的傅傅氏氏变变换换3.3 有限离散傅里叶变换及其性质有限离散傅里叶变换及其性质 (2)55 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院同样：同样：X(k)也是一个也是一个N点的有限长序列点的有限长序列关系关系 ?其中其中:DFT 定义：表达式定义：表达式 (1)n周期序列的表示周期序列的表示56 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 定义：表达式定义：表达式 (2)n若若 n=n1+n2N 成成立立，，且且 n1 满满足足 0≤n1≤N-1，，则则把把 n1 称称做做 n 对对N的的模模数数，，用用符符号号 ((n))N 表表示示，，即即：：n 模模 N=((n))N=n1，也就是，也就是 n 对对 N 取余数。
取余数例例: 是是周周期期为为 N=6 的的序序列列，，求求 n=19及及 n= -2 两两数数对对N的的余数解：解： n=19=1+3×6 ，， ((19))6=1n=-2=(-1)×6+4 ，，((-2))6=4即：即：57 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n在无混迭的情况下，我们看如何把在无混迭的情况下，我们看如何把 DFS 变成变成 DFT ?DFS:DFT 定义：表达式定义：表达式 (3)n因因无无混混迭迭，，则则时时域域中中一一个个周周期期长长的的主主值值序序列列对对应应于于频频域域中中一一个个周周期期长长的的主主值值序序列列从从DFS的的时时域域和和频频域域中中各各取取出出一一个个周周期期，，即即得得到到有有限限长长度度离离散散序序列列的的时时域域和和频频域域傅傅氏变换58 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 有限长序列的有限长序列的 DFT 正变换和反变换：正变换和反变换：其中：其中：DFTDFT 定义：表达式定义：表达式 (4)或或注意：注意：从工程角度看，从工程角度看，DFS 和和 DFT 的表达式没有本质区别。
的表达式没有本质区别 59 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n DFT的矩阵表示形式的矩阵表示形式若令：若令：则：则：DFT 定义：定义：表达式表达式 (5)60 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 定义：定义：表达式表达式 (6) DFT图形解释图形解释61 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 不仅浓缩了不仅浓缩了 的全部内容，同时也浓缩了的全部内容，同时也浓缩了 的全部内容的全部内容n 能能够够如如实实、、全全面面地地表表示示 的的频频域域特特征征，，所所以以 DFT DFT 具备明确的物理含义具备明确的物理含义 DFT 定义：定义：表达式表达式 （（7））nDFT 意意义义62 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n由上面的讨论可知，由上面的讨论可知，在在 0≤n≤N-1 上，上，DFS 和和 DFT 相同相同。
n因因此此，，可可用用类类似似的的方方法法实实现现 DFT把把原原先先名名为为 dfs 和和 idfs 的的 Matlab 函函数数改改名名为为 dft 和和 idft 函函数数，，即即可可实实现现离离散散傅傅氏变换氏变换 DFTn实实际际中中，，我我们们用用的的更更多多的的是是 DFT 的的快快速速算算法法 FFT，，见见后后续内容DFT 定义：定义：Matlab 实现实现63 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例：例： x(n) 是一个是一个 4 点序列：点序列： （（1）计算离散时间傅氏变换）计算离散时间傅氏变换 X(ejw)，并画出它的幅度和相位并画出它的幅度和相位2）计算）计算 x(n) 的的 4 点点 DFTDFT 定义：定义：举例举例64 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院解解：（：（1）） 离散时间傅氏变换为：离散时间傅氏变换为：因而因而DFT 定义：定义：举例举例65 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院00.511.5201234frequency in pi units|X|Magnitude of the DTFT00.511.52-200-1000100200frequency in pi unitsDegreesAngle of the DTFTDFT 定义：定义：举例举例66 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院(2)(2)用用 X4(k) 表示表示 4 点点 DFT:DFT 定义：定义：举例举例% b) 4-point DFTN = 4; w1 = 2*pi/N; k = 0:N-1;X = dft(x,N);magX = abs(X), phaX = angle(X)*180/pisubplot(2,1,1);plot(w*N/(2*pi),magH,'--'); axis([-0.1,4.1,-1,5]); hold onstem(k,magX); 67 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院k00.511.522.533.54-1012345k|X(k)|Magnitude of the DFT: N=400.511.522.533.54-200-1000100200DegreesAngle of the DFT: N=4DFT 定义：定义：举例举例68 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例: 怎样得到怎样得到 DTFT X(ejw) 的其他样本？的其他样本？解解：：显显然然，，我我们们的的采采样样频频率率应应更更小小一一些些，，也也就就是是说说，，应应增增加加 N 的长度的长度。
n有两种方法，有两种方法，³一种是采样时就采样更多的样本；一种是采样时就采样更多的样本；³另另一一种种是是在在序序列列后后面面添添加加一一定定长长度度的的零零，，叫叫做做填填零零运运算算，，在在实实际际中中，，为为了了得得到到一一个个较较密密的的频频谱谱，，这这种种运运算算是必要的是必要的 3.3.1 DFT 定义：定义：举例举例69 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院（（a a）给）给 x(n) 后后附加附加 4 个零得到一个个零得到一个 8 点序列点序列 x(n) = {1,1,1,1,0,0,0,0} x(n) = {1,1,1,1,0,0,0,0} 设设 X X8 8(k) (k) 为一为一 8 8 点点 DFT DFT，， 则则 在这种情况下，频率分辨率为在这种情况下，频率分辨率为 w1 = 2ππ/8 = ππ/4 DFT 定义：定义：举例举例70 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院% b) 8-point DFTN = 8; w1 = 2*pi/N; k = 0:N-1;x = [x, zeros(1,4)];X = dft(x,N);magX = abs(X), phaX = angle(X)*180/pi 结结果如下：果如下： magX = 4.0000 2.6131 0.0000 1.0824 0.0000 1.0824 0.0000 2.6131 phaX = 0 -67.5000 -153.4349 -22.5000 -90.0000 22.5000 -53.1301 67.5000 DFT 定义：定义：举例举例71 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 定义：定义：举例举例72 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院（（b) b) 更更进进一一步步，，给给 x(n) x(n) 填填充充 12 12 个个零零，，变变成成一一个个 16 16 点点序列序列，， 即：即： x(n)={1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0} x(n)={1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0} 在这种情况下，频率分辨率为在这种情况下，频率分辨率为 w1 = 2ππ/16 = ππ/8。
DFT 定义：定义：举例举例73 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院% c) 16-point DFTsubplot(1,1,1)N = 16; w1 = 2*pi/N; k = 0:N-1;x = [x, zeros(1,8)];X = dft(x,N);magX = abs(X), phaX = angle(X)*180/pi subplot(2,1,1);plot(w*N/(2*pi),magH,'--'); axis([-0.1,16.1,-1,5]); hold onstem(k,magX);xlabel('k');ylabel('|X(k)|'); title('Magnitude of the DFT: N=16')hold offsubplot(2,1,2);plot(w*N/(2*pi),phaH*180/pi,'--');axis([-0.1,16.1,-200,200]); hold onstem(k,phaX);xlabel('k');ylabel('Degrees'); title('Angle of the DFT: N=16')DFT 定义：定义：举例举例74 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 定义：定义：举例举例75 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院结论：基于以上两个例子，可以得到以下结论。
结论：基于以上两个例子，可以得到以下结论填填零零是是给给原原始始序序列列填填零零的的运运算算这这导导致致较较长长的的 DFT，，它它会会给给原原始始序序列列的的离离散散时时间间傅傅氏氏变变换换提提供供间间隔隔更更密密的的样样本本在在 Matlab 中中，，用用 zeros 函数实现填零运算函数实现填零运算为为精精确确地地画画出出离离散散时时间间傅傅氏氏变变换换 X(ejw) ，，只只需需要要 4 点点 DFT X4(k)这这是是因因为为 x(n) 仅仅有有 4 个个非非零零样样本本，，因因此此，，可可通通过过填填零零得得到到 X8(k)、、X16(k) 等等，用它们来填充等等，用它们来填充 X(ejw) 的值填填零零运运算算提提供供了了一一个个较较密密的的频频谱谱和和较较好好的的图图示示形形式式，，但但因因为为在在信信号号中中只只是是附附加加了了零零，，而而没没有有增增加加任任何何新新的的信信息息，，因因此此，，它它不不能能提提供供更更高分辨率的频谱高分辨率的频谱为为了了得得到到更更高高分分辨辨率率的的频频谱谱，，需需要要获获得得更更多多的的数数据据其其他他的的先先进进方方法则是利用边缘信息和非线性技术。
法则是利用边缘信息和非线性技术 DFT 定义：定义：举例举例76 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例：：为为了了说说明明高高密密度度频频谱谱和和高高分分辨辨率率频频谱谱之之间间的的区区别别，，考考察序列察序列 求出它基于有限个样本的频谱求出它基于有限个样本的频谱 （（a）当）当 0≤n≤10 时，确定并画出时，确定并画出 x(n) 的离散傅氏变换的离散傅氏变换 （（b）当）当 0≤n≤100 时，确定并画出时，确定并画出 x(n) 的离散傅氏变换的离散傅氏变换DFT 定义：定义：举例举例77 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院(a) 首先确定首先确定 x(n) 的的 10 点点DFT，得到其离散时间傅氏变换的估计，得到其离散时间傅氏变换的估计 %High resolution spectrum based on 100 samples of the signal x(n)subplot(1,1,1);n=[0:1:99];x=cos(0.48*pi*n)+cos(0.52*pi*n);% Spectrum based on the first 10 samples of x(n)n1=[0:1:9];y1=x(1:1:10);subplot(2,1,1);stem(n1,y1);title('signal x(n), 0 <= n <= 9');xlabel('n')axis([0,10,-2.5,2.5]);Y1=dft(y1,10);magY1=abs(Y1(1:1:6));k1=0:1:5;w1=2*pi/10*k1;subplot(2,1,2);stem(w1/pi,magY1);%(只只画画了了一一半半的的点点，，原原因因是是镜镜像像对对称称的点的点））title('Samples of DTFT Magnitude');xlabel('frequency in pi units');axis([0,1,0,10]);disp('Press RETURN to continue');pause; DFT 定义：定义：举例举例78 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院频谱的密度比较低，没有足够的样本数来下结论频谱的密度比较低，没有足够的样本数来下结论 DFT 定义：定义：举例举例79 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n填充填充 90 个零以得到较密的频谱个零以得到较密的频谱 % High density spectrum (100 samples) based on the first 10 samples of x(n)n2=[0:1:99];y2=[x(1:1:10) zeros(1,90)];subplot(2,1,1);stem(n2,y2);title('signal x(n), 0 <= n <= 9 + 90 zeros');xlabel('n')axis([0,100,-2.5,2.5]) Y2=dft(y2,100);magY2=abs(Y2(1:1:51));k2=0:1:50;w2=2*pi/100*k2;subplot(2,1,2);plot(w2/pi,magY2); Hold on;stem(w2/pi,magY2);title('DTFT Magnitude');xlabel('frequency in pi units')axis([0,1,0,10])disp('Press RETURN to continue');hold off; pause; DFT 定义：定义：举例举例80 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 定义：定义：举例举例从从结结果果图图中中可可以以看看到到 ，， 此此 序序 列列 在在 w=0.5ππ 处处有有一一主主频频率率，，原原始始序序列列则则没没有有说说明明这这一一点点 。
填填零零运运算算提提供供了了更更加加平平滑滑, ,高高密密度度的频谱曲线的频谱曲线 81 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院（（b））为为得得到到更更多多的的频频谱谱信信息息，，采采集集更更多多的的样样本本，，用用 x(n) 的的 100 个样本来确定它的个样本来确定它的 DFT High resolution spectrum based on 100 samples of the signal x(n)subplot(2,1,1);stem(n,x);title('signal x(n), 0 <= n <= 99');xlabel('n')axis([0,100,-2.5,2.5]) X=dft(x,100);magX=abs(X(1:1:51));k=0:1:50;w=2*pi/100*k;subplot(2,1,2);plot(w/pi,magX);title('DTFT Magnitude');xlabel('frequency in pi units')axis([0,1,0,60])disp('Press RETURN to continue'); DFT 定义：定义：举例举例82 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 清楚地表清楚地表明了两个靠得明了两个靠得很紧的频率，很紧的频率，这是这是 x(n) 的的高分辨率的频高分辨率的频谱谱采样更多的采样更多的数据提供了数据提供了更多的信息更多的信息DFT 定义：定义：举例举例83 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nDFT DFT 从整体上可看成是由窄带相邻滤波器组成的滤波器组从整体上可看成是由窄带相邻滤波器组成的滤波器组³DFT 的的每每个个分分量量 X(k) 可可看看成成是是窄窄带带滤滤波波器器的的输输出出，，此此窄窄带带滤滤波波器器的的中中心心位位于于数数字字频率频率 2πk/N 弧度，带宽为弧度，带宽为 2π/N 。
³此此概概念念的的一一个个典典型型应应用用是是数数字字音音频频压压缩缩中中的的分分析析滤滤波波器器，，例例如如 AC3 和和MPEG Audio 都是如此都是如此n分辨率（子带带宽）分辨率（子带带宽）³N 点点 DFT 覆覆盖盖了了 0 到到 fs （（取取样样频频率率））的的频频率率范范围围因因此此，，频频率率取取样样点点以以 fs/N 为为间间隔隔该该频频率率间间隔隔称称为为 DFT 的的频频率率分分辨辨率率，，它它描描述述了了 DFT 分分辨辨相相邻邻信信号号频频率率的的程程度度频率间隔越小，分辨率越好；间隔越大，频率间隔越小，分辨率越好；间隔越大，DFT 分辨率越差分辨率越差³假假定定取取样样频频率率保保持持不不变变，，当当取取样样点点越越大大时时，，DFT 分分辨辨率率就就会会越越好好，，这这样样频频率率间间隔隔小小，，可获得频谱的许多细节可获得频谱的许多细节³从滤波器组的角度看，分辨率好的从滤波器组的角度看，分辨率好的 DFT是由大量非常窄的带通滤波器构成的是由大量非常窄的带通滤波器构成的DFT 定义：定义：DFT 频谱频谱84 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 定义：定义：DFT 频谱频谱n滤波器的中心频率滤波器的中心频率³DFT 分量分量 X(k) 位于以下频率处：位于以下频率处：³如如果果画画出出对对频频率率 f（（Hz））而而不不是是对对 k 的的频频谱谱，，则则更更容容易从实际角度解释易从实际角度解释 DFT 频谱。
频谱³当当 k=N/2 时时，，f 到到达达了了 fs/2 奈奈奎奎斯斯特特频频率率因因而而，，k=0 到到 k=N/2 的的DFT 点点携携带带了了 DFT 全全部部必必要要的的幅幅度度和和相相位位信信息息其其余余点点只只是是基基带带重重要要信信号号频频率率的的镜镜像像副副本本，，是取样的人为结果即幅度频谱是周期性的偶对称是取样的人为结果即幅度频谱是周期性的偶对称85 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例: 为为了了体体会会 DFT 的的滤滤波波器器组组解解释释，，x(t) 由由两两个个余余弦弦信信号号和和随机噪声构成：随机噪声构成：取样频率取样频率 fs = 6.4Hz请分析其频谱请分析其频谱解：解： x(t) 包包含含两两个个频频率率 1/16Hz 和和 3/8Hz，，以以 6.4Hz 取取样样后后，，相相应应的的数数字字频频率率由由 ω= ΩT=2πf/fs，，分分别别为为 ω1=2π/102.4 和和ω2=6π/51.2 弧度 则则在在 40秒内以秒内以6.4Hz 进行取样，共得进行取样，共得 40×6.4=256个取样点个取样点。
DFT 定义：定义：DFT 频谱频谱86 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.3.1 DFT 定义：定义：DFT 频谱频谱1587 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n在在上上图图中中随随机机噪噪声声采采用用的的是是正正态态分分布布的的高高斯斯白白噪噪声声（（randn 函函数数）），，由于白噪声信号中所有频率的贡献均相等，所以白噪声频谱近似平坦由于白噪声信号中所有频率的贡献均相等，所以白噪声频谱近似平坦n对于对于 N=256 点点DFT，每个标号，每个标号 k 对应于数字频率对应于数字频率 2πk/256 弧度³由由于于 DFT 可可以以看看作作一一组组相相邻邻窄窄带带滤滤波波器器构构成成，，每每个个滤滤波波器器以以数数字字频频率率 2πk/256 弧度为中心弧度为中心³因因而而频频谱谱峰峰值值应应位位于于 2πk/256=2π/102.4 和和2πk/256=6π/51.2，，即即 k=2.5 （（非非整整数数））和和 k=15（（整整数数））处处由由于于 k 必必须须是是整整数数，，k=2.5 处处的的峰峰值值又又分成分成 k=2 和和 k=3 处的两个小峰。
处的两个小峰n当当 DFT 变变换换的的长长度度 N 是是多多个个数数字字频频率率公公倍倍数数的的整整数数倍倍时时，，即即数数字字频频率正好位于子带滤波器的中心频率上时，则得到理想的谱线率正好位于子带滤波器的中心频率上时，则得到理想的谱线nDFT 是是在在频频谱谱中中对对连连续续频频谱谱进进行行取取样样，，因因此此DFT 不不能能超超过过 DFT 频频率率分分辨辨率率所所允允许许的的范范围围而而去去准准确确定定位位频频率率即即当当信信号号谱谱线线所所在在位位置置与与 DFT 频频率率分分辨辨率率位位置置保保持持一一致致时时，，则则能能准准确确定定位位此此谱谱线线；；当当DFT 中中没没有有频频率率与与所所分分析析信信号号的的重重要要频频率率相相符符时时，，DFT 就就将将导导致致真真实实频频谱谱的模糊DFT 定义：定义：DFT 频谱频谱88 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例: 以以 256Hz 取取样样频频率率对对信信号号 取取样样，，得得到离散信号到离散信号 x(n)，计算其频谱计算其频谱。
解：解： 数字频率：数字频率： 数字信号：数字信号： 数字周期：数字周期： 数字周期为数字周期为 64，覆盖了，覆盖了15个模拟信号周期个模拟信号周期DFT 定义：定义：DFT 频谱频谱89 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 对对上上述述离离散散信信号号进进行行 N=128 和和 N=130 点点DFT，，因因为为 128 是是 64的的整整数数倍倍（（2倍倍）），，从从图图中中看看，，128点点DFT 的的幅幅度度频频谱谱中中有有两两个个理理想想尖尖锋锋，，第二个尖锋是第一个的镜像，频谱中的理想尖锋就标志着正弦的频率第二个尖锋是第一个的镜像，频谱中的理想尖锋就标志着正弦的频率n而而当当 N=130 不不是是该该数数字字信信号号的的数数字字周周期期64的的整整数数倍倍，，尖尖锋锋变变宽宽并并变变小了，这就是频谱模糊现象小了，这就是频谱模糊现象3.3.1 DFT 定义：定义：DFT 频谱频谱3090 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n序序列列 x(n)的的 Z 变变换换在在单单位位圆圆上上进进行行 N 等等分分，，即即 ＝＝2 /N，就是序列的，就是序列的DFT变换。
变换 (取样）取样）nZ 变变换换和和 DFT的的关关系系是是取取样样和和内内插插的的关关系系，，这这在在实际应用中很重要实际应用中很重要DFT 与与 DTFT 和和 Z 变换的关系变换的关系91 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n取取样样 Z Z 变换变换n设设 x(nx(n) ) 为为一个一个长长度度为为N N的有限的有限长长序列，序列，则则有：有：DFT 与与 Z 变换的关系：变换的关系：取样取样 Z 变换变换92 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n从从 DTFT 的角度看：的角度看：有限长序列的有限长序列的 DFT 结果包含了结果包含了 N 个个离散频率点处的离散频率点处的 DTFT 结果，这个离散频率点等间隔地分结果，这个离散频率点等间隔地分布在区间布在区间 [0，，2π) 内；内；n从从 Z 变换的角度看：变换的角度看： DFT结结果包含了果包含了 z 平面上平面上 N 个离散点个离散点处的处的 Z 变换结果，这变换结果，这 N 个离个离散点均匀地分布在单位圆上，散点均匀地分布在单位圆上，由此也称由此也称DFT为单位圆上的取为单位圆上的取样样 Z 变换。
变换 DFT 与与 Z 变换的关系：变换的关系：取样取样 Z 变换变换93 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n频频域域取取样样定定理理：：若若序序列列长长度度为为 M，，则则只只有有当当频频域采样点数域采样点数 N 满足满足 N≥M 时，才有时，才有:³即即可可由由频频域域取取样样 X(k) 不不失失真真地地恢恢复复原原信信号号 x(n)，，否否则产生时域混叠现象则产生时域混叠现象³此时可由此时可由 N 个取样值个取样值 X(k) 内插恢复内插恢复出出 X(z)或或 X(ejw)DFT 与与 Z 变换的关系：变换的关系： z 域内插域内插n时时域域取取样样定定理理：：在在满满足足奈奈奎奎斯斯特特定定理理条条件件下下，，时时域取样信号可以不失真地还原原连续信号域取样信号可以不失真地还原原连续信号n频域取样频域取样情况如何？取样条件？内插公式？情况如何？取样条件？内插公式？94 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nZ 域内插公式：域内插公式：由由 DFT X(k) 可以确定可以确定 z平面上任一点处的平面上任一点处的 X(z)DFT 与与 Z 变换的关系：变换的关系： z 域内插域内插z 平面内插公式平面内插公式 内插函数内插函数 95 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n内插函数的零极点分布内插函数的零极点分布³极点：极点：(N-1)阶极点阶极点z = 0；； 一阶极点一阶极点 z=1；； ³零点：零点：N 个一阶零点个一阶零点: ³抵抵消消：：z=1 处处的的一一阶阶极极点点和和一一阶阶零零点点互互相相抵抵消消，，一一阶阶零零点点数数量量变变为为 （（N-1）个）个。
3.3.2 DFT 与与 Z 变换的关系：变换的关系： z 域内插域内插Φ(z) 的零、极点分布的零、极点分布 零、极点零、极点互相抵消互相抵消96 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.3.2 DFT 与与 Z 变换的关系：变换的关系： F 域内插域内插nF 域内插公式：域内插公式：由频域取样由频域取样 DFT X(k) 表示表示 DTFT X(ejw)97 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院即即:其中其中:频频域内插函数域内插函数 频频域内插公式域内插公式 3.3.2 DFT 与与 Z 变换的关系：变换的关系： F 域内插域内插98 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nF 内插函数的零极点分布内插函数的零极点分布根据根据Φ(z) 的零极点分布规律可知：的零极点分布规律可知：(零极点对系统频率响应的影响零极点对系统频率响应的影响)极点：极点：ejω 到极点到极点 z=0 的距离恒为的距离恒为1，对，对 幅频特性没有影响幅频特性没有影响零点：零点：³在在区区间间 [0, 2π] 内内，，|Φ(ω)| 存存在在(N-1)个零值点个零值点³存在存在 (N-1)个极值点，分别为：个极值点，分别为：Φ(z) 的零、极点分布的零、极点分布 零、极点零、极点互相抵消互相抵消3.3.2 DFT 与与 Z 变换的关系：变换的关系： F 域内插域内插99 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院插值函数的幅度特性与相位特性（插值函数的幅度特性与相位特性（N=5)DFT 与与 Z 变换的关系：变换的关系： F 域内插域内插100 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n频域内插的物理含义频域内插的物理含义 k0N-NnN0-Nnx(n) 0n只只有有当当频频域域取取样样点点数数 N 大大于于序序列列长长度度 M 时时，， 中中不不会会出出现现混混迭迭现现象象，，这这时时能能够够从从 中中如如实实恢恢复复 x(n)，，即即能能够够由由 X(k) 准准确确重重建建 X(z) 和和 X(ejw)。
n对序列作对序列作 DFT 变换点数不应低于序列的长度变换点数不应低于序列的长度nX(k) 浓缩了浓缩了 x(n) 在变换域中的全部特性在变换域中的全部特性DFT 与与 Z 变换的关系：变换的关系： F 域内插域内插101 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n这里，序列长度及这里，序列长度及 DFT 点数均为点数均为 Nn若不等，分别为若不等，分别为 N1、、N2，，则需补零使两序列长度相等，均则需补零使两序列长度相等，均为为 N，，且且 若两序列若两序列 x1(n) 和和 x2(n) 的长度均为的长度均为 N，且其，且其 N 点点 DFT 分别为：分别为：则：则：DFT 的性质：的性质：线性线性a, b 为任意常数为任意常数102 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n对于周期序列，有：对于周期序列，有： 其中：其中： — 周期共轭偶对称分量周期共轭偶对称分量 — 周期共轭奇对称分量周期共轭奇对称分量n又定义：又定义： n又由于又由于 则：则：n即有限长序列由共轭偶对称和共轭奇对称两部分组成。
即有限长序列由共轭偶对称和共轭奇对称两部分组成DFT 的性质：的性质：对称性对称性—共轭奇对称分量共轭奇对称分量—共轭偶对称分量共轭偶对称分量103 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：对称性对称性104 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n若若存存在在有有限限长长序序列列 x(n)，，长长度度为为 N，，其其 N 点点 DFT 的的结结果果为为X(k)，，则则有，有，证明：证明：DFT 的性质：的性质：帕斯瓦尔定理帕斯瓦尔定理n该定理表明该定理表明: :可利用序列的可利用序列的 DFT DFT 结果表示信号的能量，序列在结果表示信号的能量，序列在时域计算的时域计算的能量与在频域计算的能量相等，即变换前后的能量保持不变能量与在频域计算的能量相等，即变换前后的能量保持不变n这进一步说明，虽然这进一步说明，虽然 DFT 有别于有别于 DTFT，但其仍然具有明确的物理含义，但其仍然具有明确的物理含义105 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：反转定理反转定理n 循环反转的定义循环反转的定义³如如果果 x(n) 是是长长度度为为 N 的的序序列列，，则则称称 x((-n))N RN(n) 为为 x(n) 的的循环反转运算循环反转运算。
循循环环反反转转运算是有限运算是有限长长序列所特有的一种运算，其序列所特有的一种运算，其结结果仍然是集合果仍然是集合 {0, 1, ….., (N-1) } 上的有限上的有限长长序列，序列，特别注意特别注意 n=0 n=0 时情况时情况 计计算算过过程程：：（（1））补补零零为为 N；；（（2））周周期期延延拓拓；；（（3））纵纵轴轴镜镜像像；；（（4））取取主主值值序列106 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：反转定理反转定理n 循环反转的循环反转的 DFT若若则则证明：证明：107 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：序列的循环移位序列的循环移位(圆周移位圆周移位)n 循环移位的定义：循环移位的定义：³称称其其为为循循环环移移位位的的原原因因在在于于，，当当序序列列从从一一端端移移出出范范围围时时，，移移出出的的部分又会从另一端移入该范围部分又会从另一端移入该范围³线线性性移移位位：：若若 N 点点序序列列沿沿一一方方向向线线性性移移位位，，它它将将不不再再位位于于区区间间 0≤n≤N-1 上。
上 108 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：序列的循环移位序列的循环移位(圆周移位圆周移位)有的有的书书上称上称为为圆圆周移位周移位把x(n)看作排列在看作排列在N等分的等分的圆圆周上，循周上，循环环移位就相当于移位就相当于序列序列 x(n) 在在圆圆周上移周上移动动，故称，故称为圆为圆周移位实际实际上重复上重复观观察几周察几周时时，看到的就，看到的就是周期序列是周期序列 109 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例：例： 设设 x(n) = 10(0.8)n，， 0≤n≤10 为为 11 点序列点序列(a) 画出画出 x((n+4))11R11(n)，， 也就是向左循环移位也就是向左循环移位 4 个样本的序列；个样本的序列；(b) 画画出出 x((n-3))15R15(n)，， 也也就就是是假假定定 x(n) 为为 15 点点序序列列，，向向右右循循环环移移位位 3 个样本DFT 的性质：的性质：序列的循环移位序列的循环移位(圆周移位圆周移位)解：解：x((n+4))11R11(n)，， 也也就就是是向向左左循循环环移位移位 4 个样本的序列；个样本的序列；特别注意当样本从一个方向移出特别注意当样本从一个方向移出 [0,N-1]，它们将从相反方向再现。
它们将从相反方向再现这就是循环移位的含义，它不同于这就是循环移位的含义，它不同于线性移位线性移位 110 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院(b) (b) 在在这这种种情情况况下下，，给给 x(n) x(n) 后后填填充充 4 4 个个零零，，将将其其看看作作一一个个 15 15 点点序序列列此此时时的的循循环环移移位位与与 N=11 N=11 时时不不同同，，看看起起来来像像线线性性移移位位 x(n-3)x(n-3)因因此此，，序列的周期长度是非常重要的一个参数序列的周期长度是非常重要的一个参数DFT 的性质：的性质：序列的循环移位序列的循环移位(圆周移位圆周移位)111 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院结论：结论： 有限长序列的循环移位，在离散频域中只引入了一个和频率成正比有限长序列的循环移位，在离散频域中只引入了一个和频率成正比的线性相移的线性相移 ，对幅频特性没有影响对幅频特性没有影响DFT 的性质：的性质：序列循环移位后的序列循环移位后的 DFT若若，则，则证明：证明：112 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院时域序列的调制等效于频域的循环移位时域序列的调制等效于频域的循环移位DFT 的性质：的性质：频域循环移位后的频域循环移位后的 IDFTn 频域循环移位后的频域循环移位后的 IDFT（（调制特性调制特性））³由由 DFT 所所具具有有的的对对偶偶特特性性不不难难看看出出，，在在频频域域内内循循环环移移位位时时，，将将有类似的结果，即：有类似的结果，即：证明：证明：113 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：频域循环移位后的频域循环移位后的 IDFT证明：证明：114 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：循环卷积循环卷积(圆周卷积圆周卷积)n 循环卷积定义：循环卷积定义：³设设 x1(n) 和和 x2(n) 都都是是长长度度为为 N 的的有有限限长长序序列列，，把把它它们们分别拓展为周期序列分别拓展为周期序列 和和 ，定义循环卷积为：，定义循环卷积为： ——周期序列卷积后取主值周期序列卷积后取主值115 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³因因为为上上式式的的求求和和范范围围是是 m 由由 0 到到 N-1，，因因此此第第一一个个序列序列 x1(m) 可以不作周期拓展，即可以不作周期拓展，即³注注意意两两个个 N 点点序序列列的的线线性性卷卷积积将将导导致致一一个个更更长长的的序序列列。
而而循循环环卷卷积积将将区区间间限限制制在在 0≤n≤N-1，，结结果果仍仍为为 N 点点序序列列，，它它与与线线性性卷卷积积的的结结构构类类似似不不同同点点在在于于求求和和范范围围和和 N 点点循循环环移移位位它它与与 N 有有关关，，也也叫叫做做 N 点循环卷积点循环卷积DFT 的性质：的性质：循环卷积循环卷积(圆周卷积圆周卷积)N窗窗函函数数限限定定了了循循环卷积的范围环卷积的范围116 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n循环卷积过程：循环卷积过程： （（1）补零）补零 （（2）周期延拓）周期延拓 （（3）反转，取主值序列）反转，取主值序列 （循环反转）（循环反转） （（4）对应位相乘，然后求和，）对应位相乘，然后求和， 得到得到n=0时的卷积结果时的卷积结果 （（5）向右）向右循环移位循环移位（圆周移位）（圆周移位） （（6）重复，）重复，n=1~(N-1)DFT 的性质：的性质：循环卷积循环卷积(圆周卷积圆周卷积)mx2(m)mx1(m)00NNmx2((0-m))N0Nmx2((1-m))N0Nn0N注意注意 n=0 时的循环反转时的循环反转117 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n循环卷积的时频映射关系循环卷积的时频映射关系³由由 DTFT 的的性性质质可可知知，，两两个个序序列列时时域域上上的的线线性性卷卷积积运运算在频域上表现为两个序列算在频域上表现为两个序列 DTFT 结果的乘积。
结果的乘积 ³同样的，同样的，若若³则则 即即当当在在频频域域中中进进行行两两个个 N 点点 DFT 相相乘乘时时，，在在时时域域中中映映射射为循环卷积（而不是通常的线性卷级为循环卷积（而不是通常的线性卷级 ！！！）！！！）DFT 的性质：的性质：循环卷积循环卷积(圆周卷积圆周卷积)118 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院证明：证明： 将将 X1(k) 和和 X2(k) 作周期延拓，分别得到作周期延拓，分别得到 X1((k)) N 和和 X2((k)) N则则 再设再设 于是于是 DFT 的性质：的性质：循环卷积循环卷积(圆周卷积圆周卷积)令令119 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院因为因为 所以所以 此时上式最后一个求和号中，已不对此时上式最后一个求和号中，已不对 r 求和，故此求和号可以去求和，故此求和号可以去掉，掉，因此，因此，因而，因而， 即即DFT 的性质：的性质：循环卷积循环卷积(圆周卷积圆周卷积)120 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n利用时域、频域的对偶性可得频域循环卷积利用时域、频域的对偶性可得频域循环卷积:若则n 时域循环卷积可在频域中完成时域循环卷积可在频域中完成:DFT 的性质：的性质：循环卷积循环卷积(圆周卷积圆周卷积)121 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院（（1) 同心圆法同心圆法（（2) 利用求周期卷积的作图法利用求周期卷积的作图法（（3) 解析式法解析式法（（4) Matlab 方法方法DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法122 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n同心圆法同心圆法 可可用用两两个个同同心心圆圆来来表表示示：：x1(n) ：内圆顺时针方向排列：内圆顺时针方向排列 x2(n) ：外圆逆时针方向排列：外圆逆时针方向排列 x1(0) 与与 x2(0) 对齐。
对齐DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法123 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³两两圆圆上上对对应应数数两两两两相相乘乘后求和，得后求和，得 x3(0) ;³将将x2(n-m)移移位位一一位位，，即即外外圆圆顺顺时时针针转转动动一一位位，，重重复复（（1））步步骤骤，，得得x3(1) ；；³依次下去，求得依次下去，求得 DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法124 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n作图法作图法 (1) x1(m) 和和 x2(m) 在在 m 轴上周期延拓，成为轴上周期延拓，成为 (2)将将 反转反转 ；； (3)计算周期卷积计算周期卷积 (4)取取 一个周期，得到一个周期，得到DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法125 mx2(m)0Nmx1(m)mx2((0-m)NRN(m)0Nmx2((1-m)NRN(m)0Nn0图图示示两个序列的循环卷积两个序列的循环卷积 0N上述过程：只需将上述过程：只需将 x1(n) 和和 x2(n) 分别做周期延拓，得到分别做周期延拓，得到 和和 ，再按照计算周期卷积的作图法，计算出，再按照计算周期卷积的作图法，计算出n 由由 0 到到 N-1 的周的周期卷积，即为循环卷积。
期卷积，即为循环卷积126 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法例例: 设设 x1(n) = {1,2,2}，，x2(n)={1,2,3,4}，计算，计算 4 点循环卷积点循环卷积 解：解： 注注意意 x1(n) 为为 3 点点序序列列，，进进行行循循环环卷卷积积之之前前在在其其尾尾部部填填一一个个零零，，使使其其成成为为 4 点点序序列列，，分分别别在在时时域域和和频频域域中中求求解这个问题解这个问题127 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院（（1）时域方法）时域方法 4 点循环卷积由下式给出点循环卷积由下式给出对对每每个个 n 产产生生一一个个循循环环移移位位序序列列，，将将它它的的样样本本逐逐个个与与 x1(m) 相相乘乘，，然然后后求求和和，，得得此此 n 值值的的循循环环卷卷值值，，在在 0≤n ≤3 上上重重复复此此过过程程考考虑虑 x1(m) = {1,2,2,0} 和和 x2(m) = {1,2,3,4}³n=0 时时,DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法注注意意此此为为 x2(0)，，而而不是不是 {4,3,2,1}128 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³n = 2 时，时，DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法³n = 3 时，时，因此，因此，129 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院(2) 频域方法：频域方法： 首首先先计计算算 x1(n) 和和 x2(n) 的的 4 点点 DFT，，逐逐个个样样本本相相乘乘，，取取IDFT，得到循环卷积。
得到循环卷积DFT 的性质：的性质：循环卷积计算方法循环卷积计算方法则则（注意：（注意：X1(k) 和和 X2(k) 对应位相乘）对应位相乘） IDFT 后，得后，得表面看来，这样做反而更复杂，且涉及复数运算但后面我们会看到，表面看来，这样做反而更复杂，且涉及复数运算但后面我们会看到，DFT 有快速算法有快速算法 FFT，特别是当，特别是当 N 很大时，效率会显著提高很大时，效率会显著提高130 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n利用利用 DFT 求离散线性卷积求离散线性卷积³条件：条件：N≥N1+N2-1³方法：时域转换到频域，处理后再转换回时域方法：时域转换到频域，处理后再转换回时域n用用 DFT 进行信号频谱分析进行信号频谱分析³参数选择参数选择³频谱泄漏频谱泄漏³栅栏效应栅栏效应DFT 的应用的应用131 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 线性移不变离散系统线性移不变离散系统 当长度当长度 N N 增大时，增大时，线性卷积的运算量较大，线性卷积的运算量较大，需寻找实用的线性卷积需寻找实用的线性卷积的快速计算方法！的快速计算方法！DFT 的应用：的应用：线性卷积求解线性卷积求解n 循环卷积的时频映射循环卷积的时频映射 频域中进行两个频域中进行两个 N N 点点 DFT DFT 相乘时，在时域中映射相乘时，在时域中映射为循环卷积（为循环卷积（而不是通常的线性卷级而不是通常的线性卷级 ！！！！！！））。
快速算法快速算法 FFT132 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院线性卷积：线性卷积：N点循环卷积：点循环卷积：DFT 的应用：的应用：线性卷积求解线性卷积求解n循环卷积和线性卷积的关系循环卷积和线性卷积的关系133 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院² 讨论线性卷积讨论线性卷积 y(n)=x(n)*h(n) 的长度的长度 从从 x(m) 看，看， 非零值区为：非零值区为： 0≤m≤N-1 从从 h(n-m) 看，非零值区为：看，非零值区为： 0≤n-m≤M-1 将二不等式相加，得到将二不等式相加，得到 y(n) 的非零区：的非零区： 0 ≤ n ≤ M+N-2在在此此区区间间之之外外，，不不是是 x(m)=0，，就就是是 h(n-m)=0，，即即y(n)=0，，因此，因此，y(n) 的长度为的长度为 M+N-1DFT 的应用：的应用：线性卷积求解线性卷积求解134 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院²讨论循环卷积的长度讨论循环卷积的长度 循循环环卷卷积积是是周周期期卷卷积积的的主主值值序序列列。
为为了了研研究究长长度度不不等等的的两两个个序序列列的周期卷积，的周期卷积，构造周期序列构造周期序列，，使它们的长度相等，且均为使它们的长度相等，且均为 L表示为表示为DFT 的应用：的应用：线性卷积求解线性卷积求解135 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院²周期卷积如下：周期卷积如下：Ø周期卷积是线性卷积的周期延拓，周期为周期卷积是线性卷积的周期延拓，周期为 LØ当周期为当周期为 L≥N+M-1 时，不会发生混迭，线性卷积正好是时，不会发生混迭，线性卷积正好是周期卷积的一个周期周期卷积的一个周期 Ø循环卷积又是周期卷积的主值序列循环卷积又是周期卷积的主值序列 DFT 的应用：的应用：线性卷积求解线性卷积求解因因为为 ，，即即 0≤m≤L-1 范范围围内内 x(m+qL) 只只有有一一个个周期136 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³由由于于循循环环卷卷积积是是周周期期卷卷积积的的主主值值序序列列因因此此，，此此时时循循环卷积与线性卷积完全相同即：环卷积与线性卷积完全相同即： n因此，因此，循环卷积等于线性卷积的条件循环卷积等于线性卷积的条件是：是： 即即对对于于 N 长长度度的的 x(n)，，M 长长度度的的 h(n)，，在在它它们们后后面面补补零零，，使其长度均变为使其长度均变为 L≥M+N-1。
DFT 的应用：的应用：线性卷积求解线性卷积求解137 138 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院讨论讨论若序列若序列 的长度为的长度为 ，， 序列的长度为序列的长度为 ，且，且有有 大于大于 ，那么，，那么， 和和 的的 点循环卷积结点循环卷积结果为：果为： 其中，其中，139 此时，两序列的线性卷积结果此时，两序列的线性卷积结果 的长度的长度 ，，对其在时域作周期为对其在时域作周期为 的延拓相加得到序列的延拓相加得到序列 主值序列的前主值序列的前 个点存在混迭因此，在个点存在混迭因此，在 中中也就是说，序列也就是说，序列 中最后中最后 个点与两序列的个点与两序列的线性卷积结果相同线性卷积结果相同 140 例：现存在两个有限长序列例：现存在两个有限长序列 （（ ）和）和 （（ ），其），其20点循环卷积结果为点循环卷积结果为 ，而其线性卷积结果，而其线性卷积结果为为 ，问：，问： (1) 中哪些点与中哪些点与 相同；相同；(2) 需要进行多少点循环卷积才能保证需要进行多少点循环卷积才能保证 和和 完完全相同。
全相同 答： （1）7～19点 （2）27点141 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 即时域循环卷积即时域循环卷积 频域相乘频域相乘DFT 的应用：的应用：线性卷积求解线性卷积求解设设若若则则n用用 DFT 求解线性卷积求解线性卷积142 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³如如果果循循环环卷卷积积的的长长度度 N 满满足足 N≥N1+N2-1，，则则此此循循环环卷卷积积 Y(k) 就就等等于于 x(n) 和和 h(n) 的的线线性性卷卷积积用用流流程程图图表表示法求示法求 y(n)=x(n)*h(n) 的过程如下：的过程如下：³因因为为 DFT、、IDFT 都都有有快快速速算算法法，，因因此此，，线线性性卷卷积积可可以实现快速算法以实现快速算法DFT 的应用：的应用：线性卷积求解线性卷积求解IDFTN 点点DFTN 点点DFTN 点点)(kX)(kH)(kH)(kX)(ny)(nx)(nh2N长度长度1N长度长度121- -+ += =NNN143 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：线性卷积求解线性卷积求解n乘法次数乘法次数³循循环环卷卷积积：：在在上上述述 DFT 求求解解线线性性卷卷积积过过程程中中，，需需要要 3 次次DFT（（FFT））运运算算，，后后面面我我们们会会讲讲到到 N 点点 FFT 所所需需要要的的乘乘法法次次数数为为 ，，因因此此，，用用 DFT 求求线线性性卷卷积积所所需需要要的的总总的的乘乘法法次次数数：：³线线性性卷卷积积：：每每一一个个输输入入值值 x(n) 都都必必须须和和全全部部的的 h(n) 值值乘乘一一次次，，因此，总共需要因此，总共需要 N1N2 次乘法运算，次乘法运算，ML=N1N2。
设设若若 N1=N2 时，则时，则 144 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：线性卷积求解线性卷积求解²结结论论：：N1=N2 越越长长，，循循环环卷卷积积的的优优越越性性越越大大但但当当其其中中一一个序列很长时，例如个序列很长时，例如 x(n) 当很长时，即：当很长时，即： 这时这时 Cm下降，循环卷积快速算法的优点不能发挥出来下降，循环卷积快速算法的优点不能发挥出来n克服的办法：克服的办法：分段卷积分段卷积³将将长长序序列列分分段段，，每每一一段段分分别别与与短短序序列列进进行行循循环环卷卷积积（即用（即用 FFT 运算）运算）³分为重叠相加法，重叠保留法分为重叠相加法，重叠保留法145 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n线性卷积求解小结线性卷积求解小结³时域直接求解时域直接求解 补补N-N1个零个零x(n)N点点DFT补补N-N2个零个零h(n)N点点DFTN点点IDFTy(n)= x(n)*h(n)³z 变换法变换法³DFT 法法DFT 的应用：的应用：线性卷积求解线性卷积求解146 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n上上面面介介绍绍的的是是两两个个有有限限长长序序列列 x x1 1(n)(n)、、x x2 2(n) (n) 的的线线性性卷卷积积。
但但有有时时其其中中某某个个序序列列会会很很长长或或无无限限长长，，若若等等长长序序列列存存储储或或输输入完后再做卷入完后再做卷积积运算，将运算，将产生问题产生问题：： (1) (1) 存存储储量量过过大，运算量也太大；大，运算量也太大； (2) (2) 等待等待输输入的入的时间时间很很长长，引起不能忍受的延，引起不能忍受的延迟迟；；(3) (3) 采用采用 DFT/FFT DFT/FFT 快速算法的效率降低快速算法的效率降低具体方法：重叠保留法、重叠相加法具体方法：重叠保留法、重叠相加法n 解决此问题的思路：解决此问题的思路： 把长序列分段，每一分段分别与短序列进把长序列分段，每一分段分别与短序列进行卷积行卷积 ——分段卷积分段卷积DFT 的应用：的应用：分段卷积分段卷积147 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n误差分析误差分析³在在分分析析分分段段卷卷积积之之前前，，我我们们首首先先分分析析两两个个有有限限长长度度序列的循环卷积的误差情况序列的循环卷积的误差情况³设设 x(n) 为为 N1 点点序序列列，，h(n) 为为 N2 点点序序列列，，由由前前面面分分析知道，析知道，线性卷积线性卷积 y(n) 和循环卷积和循环卷积 yC(n) 关系为：关系为：DFT 的应用：的应用：分段卷积分段卷积²一一般般地地讲讲，，循循环环卷卷积积是是线线性性卷卷积积的的一一种种混混叠叠形形式式。
但但当当 N≥N1+N2-1，，没没有有混混迭迭产产生生，，此此时时线线性性卷卷积积 y(n) 和和循循环环卷卷积积 yN(n) 相等148 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院²为为了了用用 DFT DFT 计计算算线线性性卷卷积积，，必必须须选选择择适适当当的的 N N，，但但实实际际中中却却可可能能做做不不到到这这一一点点，，尤尤其其是是当当一一个个序序列列的的长长度度很很大大而而存存储储空空间间有有限限时时当当选选择择比比所所需需要要的的小小的的 N N 值值进进行行循循环环卷卷积时积时，会引入，会引入误误差差下面我们计们计算此算此误误差的大小差的大小DFT 的应用：的应用：分段卷积分段卷积²首先首先 N≥max(N1, N2)，假设，假设 此时，循环卷积此时，循环卷积 yc(n) 的取值范围为的取值范围为 而线性卷积而线性卷积 y(n) 的非零范围为的非零范围为149 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院有上式可知，误差为：有上式可知，误差为：DFT 的应用：的应用：分段卷积分段卷积150 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 因因为为 max(N1, N2)≤N≤（（N1＋＋N2－－1）） ，，上上面面的的求求和和式式中中只只剩剩下下对对应应于于 r = ±1 的的项项，，其其它它的的 r 值值超超出出了了 max(N1, N2)≤N≤（（N1＋＋N2－－1）。
因此，）因此，² 一一般般来来讲讲，，如如果果 x(n) 和和 h(n) 为为因因果果序序列列，，则则 y(n) 也也为为因果序列，即：因果序列，即：因此因此 DFT 的应用：的应用：分段卷积分段卷积151 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院²它说明当它说明当 时时，，样样本本 n 处处的的误误差差与与线线性性卷卷积积中中第第 n+N 个个样样本本相相等等N1 + N2 – 1））个个样样本本后后，，线线性性卷卷积积结结果果为为零零这这说说明明循循环环卷卷积积中中的的头头 M 个个样样本本存存在在误误差差，，M 等等于于线线性性卷卷积积长长度度和和循循环环卷卷积积长长度度之之差差，，而而剩剩下下的的则则为为正正确确的的线线性性卷卷积积样样本 DFT 的应用：的应用：分段卷积分段卷积0循环卷积循环卷积长度长度 NN1+N2-1-Ny(n)线性卷积长度线性卷积长度N1+N2-1循环卷积循环卷积的错误样本的错误样本152 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n此结论在用分段处理法实现长卷积时是非常有用的。
此结论在用分段处理法实现长卷积时是非常有用的DFT 的应用：的应用：分段卷积分段卷积错误样本数错误样本数 = = 线性卷积长度线性卷积长度 – – 循环卷积长度循环卷积长度N1N20假设假设 N= N2N1+N2-1-Ne(n)=0e(n)=y(n+N)y(n)yC (n)h(n)x(n)N1+N2-1M-1 点有误差点有误差与线性卷积相同与线性卷积相同假设假设 M= N1153 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例：例： 设设 x1(n) 和和 x2(n) 是两个四点序列：是两个四点序列： x1(n) = {1,2,2,1} ，， x2(n) = {1,-1,-1,1}计计算算当当 N = 6，，5，，4 时时的的循循环环卷卷积积，，并并在在每每种种情情况况下下，，验验证证它们的误差它们的误差 DFT 的应用：的应用：分段卷积分段卷积解：显然，线性卷积为解：显然，线性卷积为 7 点点 x3(n) = {1,1,-1,-2,-1,1,1} 当当 N =6，得到，得到 6 点序列的循环卷积为：点序列的循环卷积为：因此因此154 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n当当 N=5 时，得到时，得到 5 点序列的循环卷积为点序列的循环卷积为 DFT 的应用：的应用：分段卷积分段卷积n当当 N=4 时，得到时，得到 4 点序列的循环卷积为点序列的循环卷积为155 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n重叠保留法重叠保留法 —— —— 对输对输入入 x(n) x(n) 预处预处理理n基本思路基本思路³假假设设把把序序列列 x(n) x(n) 分分成成多多段段 N N 点点序序列列，，一一个个系系统统的的脉脉冲响冲响应为应为 M M 点序列，点序列，M
³由由上上面面的的结结论论可可知知，，输输入入分分段段序序列列和和脉脉冲冲响响应应之之间间的的N N点点循循环环卷卷积积产产生生该该段段的的输输出出序序列列，，其其中中前前 (M-1) (M-1) 个个样样本不是正确的本不是正确的输输出出值值³若若将将 x(n) x(n) 简简单单地地分分成成互互不不重重叠叠的的各各段段，，则则所所得得的的输输出序列会有不正确出序列会有不正确样样本区本区间间存在³输输入数据如何分段？入数据如何分段？结结果如何果如何处处理？理？DFT 的应用：的应用：重叠保留法重叠保留法156 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n为为了了解解决决这这个个问问题题，，将将 x(n) 分分为为长长度度 N1 的的分分段段，，然然后后每每段段再再往往前前多多取取（（M-1））个个样样本本，，即即第第 k 段段的的最最后后 M-1 点点保留下来作保留下来作为为第第 (k+1) 段的前段的前 M-1 点，各段点，各段长变为长变为：： 其其中中最最前前面面的的一一段段 x x0 0(n)(n)，，在在其其前前面面补补上上 M-1 M-1 个个零零，，使使其其长长度也度也为为 N N 。
n其中任一段其中任一段 xk(n) 与与 h(n) 进进行行 N 点卷点卷积积运算 循循环环卷卷积积：：DFT 的应用：的应用：重叠保留法重叠保留法相应的周期卷积相应的周期卷积 的的周期为：周期为：N=N1+M-1线性卷积：线性卷积：157 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院yk(n) 的长度为：的长度为：DFT 的应用：的应用：重叠保留法重叠保留法N1N1N1N’N’N’M-1M-1M-1M-1x(n)nN重叠重叠区域区域线性卷积线性卷积循环卷积循环卷积158 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：重叠保留法重叠保留法159 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院将每一段所得到的将每一段所得到的循环卷积循环卷积的的前前 M-1 个值去掉个值去掉，，保留后面的保留后面的 N1 个值个值，，再将各段保留的再将各段保留的N1个值个值前后拼接起来，就得到所要求的线性卷积前后拼接起来，就得到所要求的线性卷积 y(n)DFT 的应用：的应用：重叠保留法重叠保留法n因因此此，，循循环环卷卷积积 yk’(n) 的的前前 M-1 个个值值是是线线性性卷卷积积 yk(n) 前前面面的的 M-1 个个值值与与 yk-1(n) 后后面面 M-1 个个值值的的混迭，是错误的样本。
混迭，是错误的样本 n循循环环卷卷积积 yk’(n) 的的后后 N1 个个值值才才与与 yk(n) 中中间间的的 N1 个值相同个值相同160 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 这这种种通通过过将将 与与 相相重重叠叠的的部部分分舍舍去去，，即即舍舍去去循循环环卷卷积积 yk’(n) 中中前前 M-1 项项，，保保留留后后面面的的 N1 个个数数值值，，来来得得到到所所求求结结果果的的方方法法称称为为重重叠叠保保留留法法，，有的书中又称为有的书中又称为重叠舍去法重叠舍去法DFT 的应用：的应用：重叠保留法重叠保留法161 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例: 设设 x(n) = (n+1), 0≤n≤9, h(n)={1,0,-1}，，按按 N =6 用用重重叠叠舍舍去法计算去法计算 y(n) = x(n)*h(n)DFT 的应用：的应用：重叠保留法重叠保留法解：由于解：由于 M =3，必须使每一段与前一段重叠两个样本，，必须使每一段与前一段重叠两个样本，x(n) 为为 10 点序列，需要在开头加点序列，需要在开头加 (M-1) = 2 个零。
因为个零因为 N = 6，则可划分为三部分：，则可划分为三部分：因为因为 x(n) 在在 n>9 时无值，因此在时无值，因此在 x3(n) 中必须填两个零中必须填两个零162 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院现在计算每一部分与现在计算每一部分与 h(n) 循环卷积循环卷积 (不是线性卷积不是线性卷积) DFT 的应用：的应用：重叠保留法重叠保留法注意注意舍去前两个样本舍去前两个样本，输出，输出 y(n) 为为也可以直接计算线性卷积，结果为：也可以直接计算线性卷积，结果为：与重叠保留法结果相同与重叠保留法结果相同163 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n重叠相加法重叠相加法—对输对输出出y(n) 后后处处理理n基本思路基本思路³假假设设一一个个系系统统的的输输入入为为长长序序列列项项 x(n), 脉脉冲冲响响应应 h(n) 为为 M 点序列；点序列；³把序列把序列 x(n) 分成分成多段多段 N 点序列点序列，并且，并且M
³问题问题：：重叠部分如何重叠部分如何处处理？理？DFT 的应用：的应用：重叠相加法重叠相加法164 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n步骤步骤（（1））设设 h(n) 长长为为 M，，x(n) 为为长长序序列列，，首首先先把把 x(n) 分分段段，，每每段长为段长为 N1，即把，即把 x(n) 分为分为 x0(n), x1(n),…,xk(n),… 表示为：表示为：∴∴ 反过来反过来 DFT 的应用：的应用：重叠相加法重叠相加法165 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院(2) 因此因此 ∵∵ xk(n) 长为长为 N1，，h(n) 长为长为M ∴∴ yk(n) 的长为：的长为： N=N1+M-1因此因此, yk(n) 比比 xk(n) 长，长，多余的点数多余的点数为为 N - N1 = N1 + M – 1 - N1 = M-1DFT 的应用：的应用：重叠相加法重叠相加法166 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院由于由于 yk(n) 的范围为：的范围为：而而 yk+1(n) 的范围是：的范围是：因因此此，，线线性性卷卷积积 yk(n) 最最后后的的（（M-1））项项与与 yk+1(n) 最开始的（最开始的（M-1）项发生了重叠）项发生了重叠。
DFT 的应用：的应用：重叠相加法重叠相加法167 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：重叠相加法重叠相加法N1N1168 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院(3)对对于于在在 (k+1)N1 到到 (k+1)N1+M-2 的的范范围围内内（（即即重重叠叠部部分分））的的每每一一个个 n 值值，，原原序序列列 x(n) 与与 h(n) 的的线线性性卷卷积积之之值值 y(n) 应为应为：：n这这种种方方法法把把 yk(n) 最最后后的的（（M-1））项项与与 yk＋＋1(n) 最最开开始始的的（（M-1））项项相相加加起起来来得得到到 y((k+1)N1) ,…, y((k+1)N1+M-2) 各项，所以称为各项，所以称为重叠相加法重叠相加法DFT 的应用：的应用：重叠相加法重叠相加法169 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：重叠相加法重叠相加法170 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例 : 设设 x(n) = (n+1), 0≤n≤9, h(n)={1,0,-1}，，按按 N1 =6 用用重重叠叠相加法计算相加法计算 y(n) = x(n)*h(n)解：因为解：因为 N1 = 6，则把，则把 x(n) 分为两段：分为两段：因为因为 x(n) 在在 n>9 时无值，可以填两个零，或者不填零。
时无值，可以填两个零，或者不填零现在计算每一部分与现在计算每一部分与 h(n) 线性卷积线性卷积或或 N=N1+M-1点循环点循环卷积卷积 DFT 的应用：的应用：重叠相加法重叠相加法171 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院把把 y1(n) 最最后后的的 (M-1)=2 项项与与 y2(n) 最最开开始始的的 (M-1)=2 项项相相加起来得到相应的各项，最后输出为：加起来得到相应的各项，最后输出为：DFT 的应用：的应用：重叠相加法重叠相加法172 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n重重叠叠保保留留法法: : 对对输输入入序序列列进进行行重重叠叠分分段段，，构构成成短短序序列列，，分分别别进进行行循循环环卷卷积积运运算算，，对对分分段段输输出出序序列列，，先先舍舍去去再再拼拼接接，，形成最终输出形成最终输出n重重叠叠相相加加法法: : 对对输输入入序序列列分分段段后后进进行行线线性性卷卷积积，，对对分分段段输输出进行重叠相加，形成完整输出出进行重叠相加，形成完整输出n共共同同特特点点: : 以以逐逐段段的的方方式式通通过过循循环环卷卷积积来来完完成成线线性性卷卷积积的的计算，具有相同的运算量和处理效率。
计算，具有相同的运算量和处理效率DFT 的应用：的应用：分段卷积小结分段卷积小结173 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院信号的频谱分析：信号的频谱分析：计算信号的傅里叶变换计算信号的傅里叶变换DFT 的应用：的应用：频谱分析频谱分析174 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：频谱分析频谱分析175 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：频谱分析频谱分析176 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 的应用：的应用：频谱分析频谱分析n参数的选择参数的选择为便于为便于 FFT 计算，一般选计算，一般选择择 N = 2r（（r 为正整数）为正整数）177 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院要同要同时时提高信号最高提高信号最高频频率和率和频频率分辨率，需增加采率分辨率，需增加采样样点数点数 N N，即采集更，即采集更长长的数据n 信号最高频率与频率分辨率之间的矛盾信号最高频率与频率分辨率之间的矛盾 DFT 的应用：的应用：频谱分析频谱分析178 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 DFT 的应用：的应用：频谱分析频谱分析nDFT 计算频谱计算频谱³当当 X(k) X(k) 对应频率为对应频率为 的频谱值。
的频谱值 ³频谱频谱 X(k) 是由实部是由实部 U 和虚部和虚部 V 组成：组成：³于是幅频特性于是幅频特性 A(k)、相位谱、相位谱 Φ(k)、功率谱、功率谱G(k) 分别为：分别为：179 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例: 有有一一频频谱谱分分析析用用的的 DFT/FFT 处处理理器器，，其其取取样样点点数数为为 2 的的整整数数次次幂幂，，假假设设没没有有采采用用任任何何的的数数据据处处理理措措施施，，已已给给条条件为：频率分辨率件为：频率分辨率 ≤10Hz，信号最高频率，信号最高频率≤4kHz试确定以下参量：试确定以下参量： (1)最小记录长度最小记录长度 T0；； (2)取样点最大时间间隔取样点最大时间间隔 T（即最小取样频率）；（即最小取样频率）； (3)在一个记录中最少点数在一个记录中最少点数 N DFT 的应用：的应用：频谱分析频谱分析180 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 DFT 的应用：的应用：频谱分析频谱分析解：解：(1)最小记录长度：最小记录长度：(2)最大取样间隔最大取样间隔(3)最小记录点数最小记录点数181 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例: 有一调幅信号有一调幅信号用用 DFT 做频谱分析，要求能分辨做频谱分析，要求能分辨 xa(t) 的所有频率分量，问的所有频率分量，问 (1) 取样频率应为多少赫兹（取样频率应为多少赫兹（Hz））? (2) 取样时间间隔应为多少秒（取样时间间隔应为多少秒（Sec））? (3) 取样点数应为多少点？取样点数应为多少点？ (4) 若用若用 fs=3kHz 频率取样，取样数据为频率取样，取样数据为512点，做频谱分点，做频谱分 析，求析，求512点点 X(k)，并粗略画出，并粗略画出 X(k) 的幅频特性的幅频特性 |X(k)|，标出主要点的坐标值。
标出主要点的坐标值 DFT 的应用：的应用：频谱分析频谱分析182 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院（（1）取样频率应为）取样频率应为: 解：解：（（2）取样时间间隔应为）取样时间间隔应为: DFT 的应用：的应用：频谱分析频谱分析183 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 DFT 的应用：的应用：频谱分析频谱分析如果如果 是有理数（整数或分数），是有理数（整数或分数），则则仍仍为为周期序列周期序列 所以此例中所以此例中 x(n) 为周期序列，周期为周期序列，周期 N=14因此，取样点数至少为因此，取样点数至少为 14 点，最小记录点数点，最小记录点数 N=14184 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 DFT 的应用：的应用：频谱分析频谱分析185 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 DFT 的应用：的应用：频谱分析频谱分析186 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n对时域截短，使频谱变宽拖尾，称为泄漏对时域截短，使频谱变宽拖尾，称为泄漏³实实际际中中的的离离散散时时间间序序列列 x(n) 可可能能是是非非时时限限的的，，处处理理这这样样序序列列时时需需要要将将它它截截短短，，即即把把该该序序列列限限定定为为 N 点点，，相相当当于于将将 x(n) 乘乘以以一一个个矩矩形窗口形窗口 W(nT) 或或 W(t)，即：，即：x(nT) W(t)³根据频域卷积定理：时域相乘映射为频域卷根据频域卷积定理：时域相乘映射为频域卷³矩形窗口的时域和频域波形如下图，其中矩形窗口的时域和频域波形如下图，其中τ为矩形窗口的宽度。
为矩形窗口的宽度)(tw102t2t-t可以看到：可以看到：1））τ大，则主瓣、大，则主瓣、 旁瓣宽度旁瓣宽度小；小；2）主瓣）主瓣 / 旁瓣旁瓣 = 固定值固定值（（13dB，，Matlab 演示演示 wintool）） DFT 的应用：的应用：频谱泄漏频谱泄漏(窗效应窗效应))( WjWt0 . 1tp2tp2-tp4W主瓣主瓣旁瓣旁瓣187 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例如：例如：在在频频域域中中，，其其谱谱线线大大小小为为 2π/T，，位位于于 Ω0＋＋nΩs 处处但但将将其其截截短短，，即即加加窗窗后后，，频频域域中中要要与与 相相卷卷积积，，其其中中在在 Ω0 处卷积后的频谱变成如下图：处卷积后的频谱变成如下图：DFT DFT 的应用：的应用：频谱泄漏频谱泄漏(窗效应窗效应)188 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n主要问题就是频谱被展宽，同时也会造成混叠失真主要问题就是频谱被展宽，同时也会造成混叠失真³可可以以看看到到原原来来在在 Ω0 处处的的一一根根谱谱线线，，变变成成了了以以 Ω0 为为中中心心的的 的连续谱线。
的连续谱线³也也就就是是说说 X(ejΩT) 的的频频率率成成分分从从 Ω0 泄泄露露到到其其他他频频率率处处去去了了原原来来在在一一个个周周期期 Ωs 内内只只有有一一个个频频率率上上有有非非零零值值，，而而现现在在一一个个周周期期内内几几乎乎所所有有频频率率上上都都有有非非零零值值在在 Ω0＋＋nΩs 处处还还有有相相同同的的卷卷积积结结果果，，考虑所有的卷积结果后，则还有混迭现象产生考虑所有的卷积结果后，则还有混迭现象产生 DFT 的应用：的应用：频谱泄漏频谱泄漏(窗效应窗效应)0Ω0+ΩsΩ0-ΩsΩ0Ω189 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n 对时域截短，使频谱变宽拖尾，称为泄漏对时域截短，使频谱变宽拖尾，称为泄漏改善方法：改善方法： （（1）增加）增加 x(n) 长度长度 N；（；（2）缓慢截短）缓慢截短(窗函数窗函数) DFT 的应用：的应用：频谱泄漏频谱泄漏(窗效应窗效应)190 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n怎样减少泄露效应？怎样减少泄露效应？³选择选择适当适当长度的窗函数使主瓣变窄，提高分析的精度。
长度的窗函数使主瓣变窄，提高分析的精度 ±当当 τ→∞ 时时，，W(jΩ) 变变为为在在 Ω=0 处处的的冲冲激激函函数数，，而而冲冲激激函函数数与任何与任何 X(ejΩT) 相卷积都不会使相卷积都不会使 X(ejΩT) 有所改变，即：有所改变，即：±因因此此加加大大窗窗宽宽度度可可使使泄泄露露减减少少，，但但也也不不能能无无限限加加宽宽，，因因为为当当τ→∞时时，，等等于于没没有有截截短短而而且且实实际际的的信信号号的的窗窗口口长长度度未未必必总总能能随随意意加加长长，，例例如如，，如如果果信信号号是是时时变变的的，，长长窗窗可可能能会会使使计计算算结果发生混淆结果发生混淆选择窗长度需要同时考虑时域和频域 DFT 的应用：的应用：频谱泄漏频谱泄漏(窗效应窗效应)191 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n怎样减少泄露效应？怎样减少泄露效应？ ³ 选择选择适当适当的窗函数的窗函数 ±泄泄露露现现象象是是由由于于矩矩形形窗窗函函数数的的频频谱谱具具有有旁旁瓣瓣，，而而且且主主瓣瓣又又有有一一定定宽宽度度所所造造成成为为了了减减少少泄泄露露，，尽尽量量寻寻找找频频谱谱接接近近冲冲激激函函数的窗函数（即旁瓣小，主瓣窄，数的窗函数（即旁瓣小，主瓣窄，但这是矛盾的但这是矛盾的）。
±常用的窗函数有汉明窗、汉宁窗、布莱克曼窗和凯塞窗等常用的窗函数有汉明窗、汉宁窗、布莱克曼窗和凯塞窗等n注意：注意：①① 窗口宽度应与所需数据长度窗口宽度应与所需数据长度 N 相同；相同；②② 若若计计算算过过程程中中需需要要补补零零，，应应先先乘乘窗窗口口变变为为 N 点点后后，，再再补零，即补零后的点不乘窗函数补零，即补零后的点不乘窗函数 DFT 的应用：的应用：频谱泄漏频谱泄漏(窗效应窗效应)192 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 应用问题：栅栏效应应用问题：栅栏效应n栅栅栏栏效效应应：：DFT 只只计计算算离离散散点点（（基基频频 F0 的的整整数数倍倍处处））的的频谱，而不是连续函数频谱，而不是连续函数 这好象是在栅栏的一边通过缝隙观看另一边的景色一这好象是在栅栏的一边通过缝隙观看另一边的景色一样，所以称之为样，所以称之为栅栏效应栅栏效应被“栅栏栅栏”挡住的景色是看不到挡住的景色是看不到的，所以有可能漏掉大的频谱分量的，所以有可能漏掉大的频谱分量193 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n改改善善方方法法：：增增加加频频域域取取样样点点数数 N（（时时域域补补零零）），，使使谱谱线线更更密密n在在实实际际问问题题中中，，被被““栅栅栏栏””挡挡住住大大的的频频谱谱的的情情况况很很少少，，所所以以栅栅栏栏效效应应不是很严重的问题。
不是很严重的问题n另另外外，，补补0 0不不会会影影响响信信号号的的 DFT DFT 特特性性，，因因为为它它没没有有增增加加信信号号的的信信息息，，也也不不能能提提高高 DFT DFT 频频谱谱的的准准确确性性，，它它只只是是可可以以减减少少频频率率间间隔隔，，移移动动了了““栅栏栅栏””，看到了原来就存在的信息看到了原来就存在的信息 DFT 的应用：的应用：栅栏效应栅栏效应194 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT: Fast Fourier Transformn1965 年年，，James W. Cooley 和和 John W. Tukey 在在《《计计算算数数学学》》（（《《Mathematics of Computation》》））上上发发表表了了“ 一一种种用用机机器器计计算算复复序序列列傅傅立立叶叶级级数数的的算算法法（（An algorithm for the machine calculation of complex Fourier series））” 论文n自自此此之之后后，，新新的的算算法法不不断断涌涌现现。
一一种种是是对对N等等于于 2 的的整整数数次次幂幂的的算算法法，，如如基基 2 算算法法，，基基 4 算算法法另另一一种种是是N不不等等于于 2 的的整整数数次次幂幂的的算算法法，，例例如如 Winagrad 算算法法，，素素因因子算法3.4 FFT （快速离散傅里叶变换）（快速离散傅里叶变换）Dr. James W. CooleyWorked at IBM Watson Research Center in Yorktown Heights, N.Y..After his retirement from IBM in 1991, he joined the Electrical Engineering Department at the University of Rhode Island. 195 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.4 FFT：：直接计算直接计算 DFT 的运算量分析的运算量分析nN 点有限长序列点有限长序列 x(n) 的的 DFT 变换对的定义为：变换对的定义为： 其中其中假设假设 x(n) 是复序列，是复序列， 同时同时 X(k) 一般也是复数。
一般也是复数196 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院复数乘法复数乘法复数加法复数加法每一个每一个X(k)NN – 1N 个个X(k)(N 点点 DFT)N 2N (N – 1)实数乘法实数乘法实数加法实数加法一次复乘一次复乘42一次复加一次复加2每一个每一个 X (k)4N2N+2 (N – 1)=2 (2N – 1)N个个X (k) (N点点DFT)4N 22N (2N – 1)3.4 FFT：：直接计算直接计算 DFT 的运算量分析的运算量分析复乘的加复乘的加法次数法次数复加的加复加的加法次数法次数197 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n如如 N=512、、1024 和和 8192 时，时，DFT 的乘法运算的乘法运算 N2 = 5122 = 218 = 262144（（26万次）万次） N2 = 10242 = 220 = 1048576（（105万次）万次） N2 = 81922 = 226 = 67108864（（6千千7百万次）百万次）³对对于于大大 N，，在在实实际际中中是是不不能能接接受受的的，，无无法法“实实时时”应应用用 DFT。
±一般地，在计算机中，一次加法比一次乘法所需时间要短一般地，在计算机中，一次加法比一次乘法所需时间要短;±在在DSP中中，，由由于于乘乘法法用用特特殊殊的的硬硬件件电电路路专专门门完完成成，，因因此此乘乘法法和加法所需机器周期相同和加法所需机器周期相同³Cooley 与与 Turkey 提提出出的的 FFT 算算法法，，大大大大减减少少了了计计算算次次数数如如 N =512 时时，，FFT 的的乘乘法法次次数数约约为为 2000 次次，，提提高高了了约约 128 倍倍，，而而且且简简化化随随 N 的的增增加加而而巨巨增增，，因因而而，，用数值方法计算频谱得到实际应用用数值方法计算频谱得到实际应用3.4 FFT：：直接计算直接计算 DFT 的运算量分析的运算量分析198 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.4 FFT：：WNkn 的性质的性质199 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n以以 4 点点 DFT 为例：为例： 直直接接计计算算需需要要：：42 = 16 次次复复数数乘乘而而按按周周期期性性及及对对称称性性，，可以将可以将 DFT 表示为：表示为：只需要只需要 1 次复数乘次复数乘3.4 FFT：：WNkn 的性质的性质信号流图信号流图？？x(0)x(2)x(1)x(3)-1-1-1-1W41X(0)X(1)X(2)X(3)200 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT 算法分类算法分类:³时间时间抽选法抽选法 DIT: Decimation-In-Time³频率频率抽选法抽选法 DIF: Decimation-In-Frequency3.4 FFT：：基本思想基本思想n基本思路：基本思路：³虽虽然然存存在在不不同同的的 FFT FFT 方方法法，，但但其其核核心心思思想想大大致致相相同同，，即即通通过过迭迭代代，，反反复复利利用用低低点点数数的的 DFT DFT 完完成成高高点点数数的的 DFT DFT 计计算算，，以以此此达达到到降降低低运算量的目的。
运算量的目的³迭迭代代：：利利用用 W WN Nknkn 的的周周期期性性、、特特殊殊点点和和对对称称性性，，合合并并 DFT DFT 计计算算中中很多重复的计算，达到降低运算量的目的很多重复的计算，达到降低运算量的目的³低低点点数数：：将将傅傅氏氏变变换换 DFT DFT 分分解解成成相相继继小小的的DFTDFT计计算算，，即即 N N 变变小小，，而计算量与而计算量与 N N2 2 成正比201 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n算法原理算法原理 设序列点数设序列点数 N = 2M，，M 为整数若不满足，则补零若不满足，则补零 将序列将序列 x(n) 按按 n 的奇偶分成两组：的奇偶分成两组：N 为为 2 的整数幂的的整数幂的 FFT 算法称基算法称基-2 FFT算法即一组由偶数序号组成，另一组由奇数序号组成即一组由偶数序号组成，另一组由奇数序号组成3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理注意其长度为注意其长度为 N/2 N/2 202 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理203 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院偶数取样点偶数取样点DFT为：为： 3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理奇数取样点奇数取样点DFT为：为： ① ① k 的的整整个个范范围围为为 0～～(N-1)，，而而X1(k)、、X2(k) 是是由由 N/2 个个样样点点形形成成的的 DFT，，x(2r) 和和 x(2r＋＋1）的长度为）的长度为 N/2；；② ② 由由这这两两个个偶偶数数和和奇奇数数 N/2 个个时时域域样样值值可可以以计计算算出出前前 N/2 个个 DFT 系系数数，，也可以计算出后也可以计算出后 N/2 个个 DFT 系数。
系数③ ③ 问问题题：：这这前前后后 N/2 个个 DFT 有有无无关关系系？？k 在在 N/2 ～～(N-1) 时时，， X1(k)、、X2(k)、、WN 情况如何？情况如何？204 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理观察观察则则205 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院因因此此：：整整个个 X(k) 的的计计算算，，可可以以分分解解为为前前、、后后半半部部分分的的运运算而只要求出前一半只要求出前一半，就可以由上式求出整个序列就可以由上式求出整个序列3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理同理同理而而因此因此206 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院上式表示为信号流程图：上式表示为信号流程图：3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理偶数点的偶数点的 DFT奇数点的奇数点的 DFT此信号流程图也称为此信号流程图也称为蝶形蝶形流程图流程图207 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院以以N=8为例，其信号流程图：为例，其信号流程图：3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理偶偶数数序序列列奇奇数数序序列列208 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院N / 2 仍为偶数，进一步分解：仍为偶数，进一步分解：N / 2 N / 43.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理209 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理同理同理210 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院以以N=8为例，其信号流程图为为例，其信号流程图为3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理N/2 点点DFTN/2 点点DFT211 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³由于由于 N=2M，这样逐级分解，直到，这样逐级分解，直到 2 点点 DFT当当 N = 8时，即分解到时，即分解到 X3(k)，，X4(k)，，X5(k)，，X6(k)，，k = 0, 13.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理212 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院每一次分解都是按时间域输入序列的奇偶性每一次分解都是按时间域输入序列的奇偶性次序，分解为两个半长的子序列，所以称为次序，分解为两个半长的子序列，所以称为按时间抽取法。
按时间抽取法仍以仍以 N=8 为例：为例：3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理注注：：复复数数乘乘法法5次次，，原原来来 64次次；；复复数数加加法法为为 24次次，，原原来来56次m=0级级m=1级级m=2级级213 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 2m 点点 DFT 的基的基 2 时间抽选计算过程时间抽选计算过程 n可见：可见：³为什么引入为什么引入FFT？？³出发点：出发点：考虑考虑 W 因子的特点和性质因子的特点和性质，简化算法简化算法³DIT-FFT算法：时间域输入信号算法：时间域输入信号逐级分解逐级分解为奇偶序列为奇偶序列3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理上式中上式中位序位序调整调整第第 0 级级蝶形复合蝶形复合第第 1 级级蝶形复合蝶形复合第第m-1级级蝶形复合蝶形复合x(n)……X(k)214 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例：： 使使用用基基 2 时时间间抽抽选选法法 FFT 流流图图，，计计算算下下列列数数据据的的 8点点 DFT：：x=[4,-3,2,0,-1,-2,3,1]3.4.1 FFT：：基基2时间抽选法时间抽选法-算法原理算法原理4-320-1-23142-13-30-214-123-3-201355-1-5-11-1355j-5-11j85+j-25-j-4-1+j-6-1-j85+j-25-j-4j√26jj√245+j+ j√2-2+6j5-j+ j√2125+j- j√2-2-6j5-j- j√24-320-1-23142-13-30-214-123-3-201355-1-5-11-1355j-5-11j85+j-25-j-4-1+j-6-1-j85+j-25-j-4j√26jj√245+j+ j√2-2+6j5-j+ j√2125+j- j√2-2-6j5-j- j√2215 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n蝶形运算蝶形运算³在在 FFT 信信号号流流图图中中每每一一级级里里节节点点都都是是成成对对存存在在的的，，计计算算时时总总是是下下节节点点的的值值乘乘以以 WNr，，然然后后与与上上节节点点的的值值相相加加减减，，形形成成下下一一列列两两个节点值。
个节点值³这种计算的基本关系是：这种计算的基本关系是： 式中式中 p, q 是上下节点的序号从是上下节点的序号从 0 开始，开始，p, q = 0,1,….N/2）） 每一级中每对节点称为对偶节点，每一级中每对节点称为对偶节点，对偶节点的间距为：对偶节点的间距为：注意：只有下节点乘以加权因子注意：只有下节点乘以加权因子 WNr 3.4.1 FFT：：基基2时间抽选法时间抽选法-蝶形运算蝶形运算216 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n同址计算（同位特性）同址计算（同位特性）3.4.1 FFT：：基基2时间抽选法时间抽选法-同址计算同址计算1) 不同级数的节点序号不变不同级数的节点序号不变 从从蝶蝶形形运运算算可可以以看看出出第第 m 列列的的 xm(p), xm(q) 经经蝶蝶形形运运算算后后，，在在第第(m+1) 列列中中的的节节点点序序号号不不变变，，即即 xm+1(p) 中中的的 p 与与 xm+1(q) 中的中的 q 仍分别是仍分别是 xm(p), xm(q) 中的中的 p 和和 q 值217 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院2) 蝶形运算是自成独立单元蝶形运算是自成独立单元³蝶蝶形形运运算算自自成成独独立立单单元元，，即即xm+1(p)、、xm+1(q) 只只与与 xm(p)、、xm(q) 有有关关，，而而与与其其他他节节点点的的值值无无关关，，同同时时 xm(p)、、xm(q) 也也不不参参与与另另外外的的蝶蝶形形运运算算。
因因此此，，就就可可把把计计算算结结果果xm+1(p) ,xm+1(q)放放入入计计算算前前 xm(p)、、xm(q) 的的存存储储单单元元中中，，而而不不用用再再建建新新的的存存储储单单元元 —同址计算同址计算³同同址址计计算算所所需需存存储储量量仅仅等等于于给给定定数数据据所所需需的的存存储储量量，，这这可可大大大大节省存储单元节省存储单元3.4.1 FFT：：基基2时间抽选法时间抽选法-同址计算同址计算218 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n输入位序重排输入位序重排³N 点点 DFT 分分解解为为两两个个 N/2 点点 DFT输输入入序序列列按按奇奇偶偶分分组组再再分分解解再再奇奇偶偶重重排排直直到到 2 点点DFT 即即 FFT 输输出出自自然然序序列列 输输入入序序列列 x(n) 位位序序重重排排3.4.1 FFT：：基基2时间抽选法时间抽选法-位序重排位序重排010011n0n1n2219 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院³说明：说明：±首先把首先把 x(n) 中的中的 n 表示为二进制。
表示为二进制±假定假定N=8，则，则 x(n) →x(n2n1n0) ni = 0, 1 ±FFT 的的时时间间抽抽选选法法按按 n 的的奇奇偶偶分分离离而而形形成成位位置置重重排排的的原原理理如如上图所示上图所示±由由此此可可以以看看出出，，时时间间抽抽选选法法 FFT 的的输输入入位位序序重重排排，，输输出出分分成成上下两部分，输出结果为自然顺序上下两部分，输出结果为自然顺序³实际操作实际操作±输输入入序序列列重重排排实实际际上上就就是是完完成成二二进进制制前前后后位位序序的的相相互交换：互交换：3.4.1 FFT：：基基2时间抽选法时间抽选法-位序重排位序重排220 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院当当 N = 2M 时时，，共共有有 M=log2N 级级蝶蝶形形；；每每级级 N/2 个个蝶蝶形形；；每每个蝶形有个蝶形有 1 次复数乘法，次复数乘法，2 次复数加法次复数加法复数乘法：复数乘法：复数加法：复数加法：比较比较 DFT/FFT 3.4.1 FFT：：基基2时间抽选法时间抽选法-运算量运算量221 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT 算法算法³上上面面讨讨论论的的 FFT 算算法法假假定定 N 为为 2 的的整整数数次次幂幂，，即即 N = 2M，是，是基基2 FFT 算法算法。
³当当 N=Rv 时时，，这这样样的的算算法法叫叫做做基基R FFT算算法法，，而而当当 N=R1v1R2v2R3v3时，叫做时，叫做混合基算法混合基算法³当当 N 是是一一个个高高度度合合数数时时，，可可得得到到最最有有效效的的算算法法最最受受欢迎也最易编程的算法是欢迎也最易编程的算法是基基2 FFT 算法算法³对对于于不不能能分分解解的的质质数数，，或或者者当当 N 不不是是 2 的的整整数数次次幂幂时时，，可可以以在在信信号号的的末末尾尾补补0，，使使其其成成为为高高度度合合数数或或 2 的的整整数次幂3.4.1 FFT：：基基2时间抽选法时间抽选法-Matlab 实现实现222 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nMatlab FFT 实现实现³Matlab 提提供供了了内内建建的的 X = fft(x, N) 函函数数来来计计算算矢矢量量 x 的的 DFT³fft 函函数数是是机机器器码码写写成成的的，，而而不不是是以以 Matlab 指指令令写写成成的，即不存在的，即不存在 .m 文件因此，它的执行速度很快因此，它的执行速度很快³采用混合算法采用混合算法。
±若若 N 为为 2 的幂，则得到高速的基的幂，则得到高速的基 2 FFT 算法；算法；±若若 N 不不是是 2 的的幂幂，，则则将将 N分分解解成成质质数数，，得得到到较较慢慢的的混混合合基基 FFT；；±若若 N 为质数，则为质数，则 fft 函数采用原始函数采用原始 DFT 算法3.4.1 FFT：：基基2时间抽选法时间抽选法-Matlab 实现实现223 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nDFT 定义表示为矩阵形式为：定义表示为矩阵形式为：3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示224 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n令：令：n矩阵矩阵 WN 为：为：nDFT 矩阵简单地表示为：矩阵简单地表示为：特性特性3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示225 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT 基基 2 时间抽选法信号流图（时间抽选法信号流图（N=8））-1W821×8点点2×4点点4×2点点x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-1-1-1W80W80W82W80W81W82W83C(0)C(1)D(0)D(1)E(0)E(1)F(0)F(1)A(0)A(1)A(2)A(3)B(0)B(1)B(2)B(3)m = 0 级m = 1级m = 2 级位序重排3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示226 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT 矩阵形式表示为：矩阵形式表示为：1) 输入矢量输入矢量 x 与与 P8 相乘，则相乘，则只是输入的位序重排只是输入的位序重排，没有乘法操作。
没有乘法操作3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示227 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院2) 第第 0 级运算：级运算：2 点点 DFT3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示228 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3) 第第 1 级运算：级运算：4 点点 DFT3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示229 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院4) 第第 2 级运算：级运算：8 点点 DFT3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示230 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT算法看成是算法看成是 DFT 矩阵矩阵W8 的分解：的分解： ³这这个个因因式式分分解解对对应应于于快快速速算算法法，，因因为为矩矩阵阵F8(8)，， F8(4) ，， F8(2) 和和 P8 的的大大部部分分元元素素为为 0，，是是稀稀疏疏矩矩阵阵因因此此上上述述每每个个矩矩阵阵的的乘乘法法运运算算最最多多只只需需要要 8 次复乘运算，而次复乘运算，而 P8 只是置换操作，没有乘法操作。
只是置换操作，没有乘法操作n不同的不同的 FFT 算法对应于将算法对应于将 DFT 矩阵矩阵 WN 分解成不同的稀疏矩阵分解成不同的稀疏矩阵 3.4.2 FFT：：基基2时间抽选法时间抽选法-矩阵表示矩阵表示231 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n算法原理：算法原理：根据时间根据时间-频率的对偶性频率的对偶性³时时间间抽抽选选法法：：是是把把输输入入 x(n) 按按奇奇偶偶分分解解成成两两个个子子序序列列，，即即 N 点点x(n) 序序列列→ N/2 点点子子序序列列，，而而输输出出 X(k) 是是按按自然顺序排列的自然顺序排列的³频频率率抽抽选选法法：：是是把把输输入入 x(n) 按按照照前前后后对对半半分分开开，，而而不不是是奇奇偶偶数数分分开开，，而而输输出出 X(k) 逐逐项项分分解解成成偶偶数数点点子子序序列和奇数点子序列列和奇数点子序列nDFT 变换表达式为：变换表达式为：3.4.3 FFT：：基基2频率抽选法频率抽选法 (DIF-FFT)如果将输入如果将输入 x(n) 按前后等分，即将求和分成两部分，范围分别为：按前后等分，即将求和分成两部分，范围分别为：232 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.4.3 FFT：：基基2频率抽选法频率抽选法 –算法原理算法原理233 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 按按 k 的奇偶将的奇偶将X(k)分成两部分：分成两部分：3.4.3 FFT：：基基2频率抽选法频率抽选法 –算法原理算法原理234 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院令令:则则 X(2r) 和和 X(2r+1) 分分别别是是 x1(n) 和和 x2(n) 的的 N/2 点点 DFT，，记为记为 X1(k) 和和 X2(k)。
3.4.3 FFT：：基基2频率抽选法频率抽选法 –算法原理算法原理235 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点点DFTN/2点点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)3.4.3 FFT：：基基2频率抽选法频率抽选法 –算法原理算法原理236 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT 基基 2 频率抽选法信号流图（频率抽选法信号流图（N=8））n逐级分解，直到逐级分解，直到 2 点点 DFT3.4.3 FFT：：基基2频率抽选法频率抽选法 –算法原理算法原理237 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n基本蝶形运算不同基本蝶形运算不同³DIT: 先复乘后加减，先复乘后加减，W 因子在上下节点都有体现因子在上下节点都有体现³DIF: 先减后复乘，先减后复乘，W因子仅体现在下节点因子仅体现在下节点3.4.3 FFT：：基基2时间和频率抽选法的异同时间和频率抽选法的异同238 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n运算量相同运算量相同n同址计算同址计算3.4.3 FFT：：基基2时间和频率抽选法的异同时间和频率抽选法的异同nDIF 输出输出重排，重排，DIT 输入输入重排重排239 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nDIT 和和 DIF 的基本蝶形互为的基本蝶形互为信号流图转置信号流图转置DITDIF3.4.3 FFT：：基基2时间和频率抽选法的异同时间和频率抽选法的异同240 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nDIT－－DIF FFT 算法互为转置（转置定理）算法互为转置（转置定理）-11×8点点2×4点点4×2点点X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1-1-1-1-1-1W80W82W80W81W82W83C(0)C(1)D(0)D(1)E(0)E(1)F(0)F(1)A(0)A(1)A(2)A(3)B(0)B(1)B(2)B(3)m = 0 级m = 1级m = 2 级倒置重排-1-1W80W823.4.3 FFT：：基基2时间和频率抽选法的异同时间和频率抽选法的异同241 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n前前面面讲讲的的都都是是基基 2 的的 FFT 算算法法，，除除此此之之外外，，还还有有基基 4 的的，，基基 8 的的快快速速算算法法。
原原理理和和基基 2 的的类类似似，，分分解解为为 4 个个交交错错的的集集合合相相比比基基 2 的的，，可可以以进进一一步步节节约约复复数数乘乘的的次次数数，，但但是是基基 8 的的和和基基 4 的的差差别别不远n算法原理省略，自学算法原理省略，自学3.4.4 FFT：：基基 4 时间抽选法时间抽选法242 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nDFT 和和 IDFT 的定义：的定义：3.4.5 FFT：：IDFT 快速算法快速算法 (IFFT)nDFT 和和 IDFT 的的区别区别：：①① 因子因子 W 的指数相差一个负号；的指数相差一个负号；②② 相差一个因子相差一个因子 1/N FFT 算算法法中中的的分分组组方方式式、、排排序序方方式式以以及及蝶蝶形形运运算算结结构构都都可可用用于于IFFT 算算法法的的设设计计，，而而这这就就是是可可依依据据现现有有的的 FFT 算算法法直直接接得得出出 IFFT 算法算法的原因 243 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nFFT 和和 IFFT 基本蝶形运算之间的关系基本蝶形运算之间的关系³设有序列设有序列 x(n)，其，其 DFT 为为 X(k)，则，则 IDFT 为为:² 在在 FFT 的的时间时间抽抽选选法中法中: 3.4.5 FFT：：IDFT 快速算法快速算法 (IFFT)²对对于于 IFFT 算法，算法，输输入是入是 X(k) 和和 X(k+N/2)，，输输出是出是 X1(k) 和和 X2(k)。
解上式可以得到解上式可以得到 X1(K)、、X2(K) ：：X(k)X(k+N/2)X1(k)X2(k)-1244 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n8 点点 DIT-IFFT 算法算法-1x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-10.5W8-00.5W8-20.5W8-00.5W8-10.5W8-20.5W8-3-1-10.5W8-00.5W8-20.50.50.50.50.50.50.50.50.50.50.50.5说明：说明：（（1））分组过程是按时间序列分组过程是按时间序列 x(n) 的奇偶性在时域上展开的，的奇偶性在时域上展开的，故称此法为时间抽选算法故称此法为时间抽选算法 DIT-IFFT；；（（2））1/N 的分解，的分解，N=2m 3.4.5 FFT：：IDFT 快速算法快速算法 (IFFT)245 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n8 点点 DIF-IFFT 算法算法 3.4.5 FFT：：IDFT 快速算法快速算法 (IFFT)246 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n用用 FFT 程序求程序求 IFFT 的方法的方法²直接法：利用直接法：利用 DIT、、DIF 的的 FFT 程序，改变参量程序，改变参量①① 把把 X(k) 作为输入序列，而输出序列就是作为输入序列，而输出序列就是 x(n)；；②② 把因子把因子 WNkn 改为改为 WN-kn ；；③③ 输入序列的每一个元素除以输入序列的每一个元素除以 N。
3.4.5 FFT：：IDFT 快速算法快速算法 (IFFT)247 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院流程如下：流程如下：² 共轭法共轭法3.4.5 FFT：：IDFT 快速算法快速算法 (IFFT)共轭共轭FFT共轭共轭乘乘 1/N248 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院DFT 不适用于：不适用于：nDFT 是是均均匀匀分分布布在在 Z 平平面面单单位位圆圆上上 N 点点处处的的频频谱谱，，如如果果取样点不均匀取样点不均匀时，则很麻烦时，则很麻烦n只只研研究究信信号号的的某某一一频频段段，，要要求求对对该该频频段段取取样样密密集集，，提提高高分辨率分辨率(如窄带信号的频谱分析）；如窄带信号的频谱分析）；n研究研究非单位圆上非单位圆上的取样值（如频谱峰值探测）；的取样值（如频谱峰值探测）；n需要准确计算需要准确计算 N点点 DFT，且，且 N 为大的素数为大的素数；；n当当 x(n) 是是短短时时间间序序列列时时，，则则得得到到的的频频率率分分辨辨率率 2pi/N 是是很很低低的的提提高高频频谱谱密密度度的的办办法法：：用用补补零零的的方方法法增增加加点点数数，，但但 DFT 的点数又大大增加，使计算工作量增大。
的点数又大大增加，使计算工作量增大CZT 算算法法：：对对 z 变变换换采采用用螺螺旋旋线线取取样样，，chirp-z 变变换换(线线性性调频调频 z 变换，变换，Chirp z-transform)3.5 线性调频线性调频 z 变换变换 CZT 及其快速算法及其快速算法249 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nCZT 的定义的定义 设设 x(n) 为已知时间序列，其为已知时间序列，其 Z 变换的形式为：变换的形式为： 式中复变量式中复变量 z 为：为： 这里这里 s 为拉普拉斯变量，为拉普拉斯变量， 是个实数是个实数 3.5.1 CZT：：定义定义250 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.5.1 CZT：：定义定义 按按照照上上式式计计算算 Z[x(n)] 必必然然是是从从 z 的的实实轴轴开开始始，，为为得得到到任任意意起起始始点点和和以以螺旋线规律变化螺旋线规律变化的的 z 值，做如下假设：值，做如下假设： 其其中中，，A、、W 为为任任意意复复数数，，θ0 为为 A 的的起起始始角角（（第第1个个取取样样点点（（k=0）） ）），，A0为为 A 起起始始半半径径，，φ0 为为在在 Z 平平面面中中相相邻邻的的 zk （（即即 zk 和和 zk+1 ））之之间间的的夹夹角角，，W0 为为任任意意正正数数值值。
M为为要要分分析析的的点点数数，，不不一一定定等于等于 N251 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nCZT 表达式表达式3.5.1 CZT：：定义定义（（1））取取样样点点沿沿螺螺旋旋线线按按角角度度间间隔隔φ0 分分布布，，φ0 > 0 时时，，取取样样轨轨迹迹逆逆时时针针旋旋转转；；φ0 < 0 时时，取，取样轨样轨迹逆迹逆时针时针旋旋转转2））zk 周周线线是是一一条条螺螺旋旋线线：：W0 表表示示螺螺旋旋线线的的伸伸展展率率；；W0>1，，随随着着 k 的的增增加加，，向向内内盘盘旋旋，，朝朝向向原原点点；；W0<1，，随随着着k 的增加，向外的增加，向外盘盘旋；旋；（（3））若若W0=1，，一一段段圆圆弧弧，，若若同同时时A0=1，，则为单则为单位位圆圆一部分，此一部分，此时时 CZT[x(n)] = DFT[x(n)] （（M=N））252 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例：例： A = 0.8*exp(j*pi/6); ％起始半径％起始半径 0.8，起始角，起始角 pi/6 W = 0.985*exp(-j*pi*0.05); %W0<1，外旋；取样间隔，外旋；取样间隔 0.05pi M = 91; ％计算点数％计算点数 z1 = A*(W.^(-(0:M-1))); Zplane([ ],z1.’)-3-2-10123-2-1.5-1-0.500.511.522.53Real PartImaginary Part3.5.1 CZT：：定义定义253 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院A = 0.8*exp(j*pi/6); ％起始半径％起始半径 0.8，起始角，起始角 pi/6W = 1.031*exp(-j*pi*0.05); %W0>1，内旋；取样间隔，内旋；取样间隔 0.05piM = 91; ％计算点数％计算点数z2 = A*(W.^(-(0:M-1)));Zplane([ ],z2.’)-1-0.500.51-1-0.8-0.6-0.4-0.200.20.40.60.81Real PartImaginary Part3.5.1 CZT：：定义定义254 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院nCZT 表示为线性卷积形式：表示为线性卷积形式：³利用布鲁斯坦利用布鲁斯坦 (Bluestein) 提出的等式提出的等式 把在把在 CZT[x(n)] 中的中的 Wnk 因子展开，得：因子展开，得：3.5.2 CZT：：快速算法快速算法n计计算算量量：：直直接接计计算算 M 点点的的 CZT，，需需要要 MN 次次复复数数乘乘法法，，M(N-1) 次次复复数加法，需要快速算法。
数加法，需要快速算法把上述运算转换为把上述运算转换为线性卷积形式线性卷积形式，从而可以采用，从而可以采用 FFT 算法，提高运算法，提高运算速度255 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.5.2 CZT：：快速算法快速算法令令则则式中式中256 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.5.2 CZT：：快速算法快速算法g(n) 和和 h(n) 的取值范围：的取值范围：257 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院3.5.2 CZT：：快速算法快速算法h(n)x(n)g(n)X(zk)序列：序列：可可以以想想像像为为频频率率随随时时间间（（n））线线性性增增长长的的复复指指数数序序列列，，在在雷雷达达中中这这类类信信号号，，称称为为线线性性调调频频信信号号（（chirp Signal)，，因因此此，，这这里里 z 变变换换称称为为线性调频线性调频 z 变换该信号的瞬时频率该信号的瞬时频率 Ωi=2Ωt 正比于时间正比于时间 t，因此，该信号的频率随时间线性增长因此，该信号的频率随时间线性增长类比：类比：258 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院与与FFT运算比较运算比较 （1）输入与输出序列的长度不需要相等，即不 需要 M=N。
（2）N与M不必是2的整数幂，即两者都为合数 或素数也可以 （3） 点的间隔不必均匀相等，这样可以得到 任意的分辨率CZT变换的特点变换的特点259 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院（4）不必要在Z平面上的同心圆的轮廓上来求z变换 若轮廓是螺旋线的，它在语音分析中很有用处 （5）起始点的选择可以是任意的，因此便于从任意 频率上对输入数据开始进行高分辨率的分析6）当A=1，N=M 时，利用Chirp-Z变换可以求 得x(n) 的DFT.CZT变换的特点变换的特点260 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n CZT (Chirp z-transform) 变换的变换的 Matlab 句法为：句法为： y = czt(x,m,w,a) y = czt(x)³CZT 是是 x 信信号号沿沿着着 w 和和 a 定定义义的的螺螺旋旋线线进进行行的的 z 变变换换m 是是说说明明了了变变换换的的长长度度，，w 是是 z 平平面面上上感感兴兴趣趣的的那那部部分分螺螺旋旋线线上上取取样样点点之之间间的的比比值值，，a 是是螺螺旋旋线线上上的的复复数数起起始始点点。
Z 平平面面上上的的螺螺旋旋线线，， 或或 “线性调频脉冲线性调频脉冲” 定义为：定义为： z = a*(w.^-(0:m-1))²如果如果 x 是矩阵，是矩阵，czt(x,m,w,a) 是是 x 的列变换的列变换³y = czt(x) 使用下列缺省值：使用下列缺省值： m = length(x) w = exp(j*2*pi/m) a = 1 ³对对于于这这些些缺缺省省值值，，czt 返返回回 x 信信号号在在单单位位园园上上 m 份份等等间间隔隔的的 z 变变换换，，也也就就是是 x 的的离离散散傅傅立立叶叶变变换换，，或或者者 fft(x)空空矩矩阵阵[ ] 说说明明了了这些参数的缺省值这些参数的缺省值3.5.3 CZT：：Matlab 实现实现261 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例：例： 用用 czt 放大一个滤波器频率响应的窄带部分（放大一个滤波器频率响应的窄带部分（100~150Hz）n首先设计一个滤波器：首先设计一个滤波器： % 30th order LPF filter, cut-off frequency Wn=125/500,use ‘boxcar’ window h = fir1(30,125/500,boxcar(31)); n建立频率和建立频率和 CZT 初始化参数：初始化参数： Fs = 1000; f1 = 100; f2 = 150; % in Hertz m = 1024; ％％ 取样点数取样点数 w = exp(-j*2*pi*(f2-f1)/(m*Fs)); % 取样点间隔取样点间隔 a = exp(j*2*pi*f1/Fs); ％％ 取样点起始位置取样点起始位置n计算滤波器的计算滤波器的 DFT 和和 CZT 变换：变换： y = fft(h,1000); z = czt(h,m,w,a);n得到频率响应和比较结构：得到频率响应和比较结构： fy = (0:length(y)-1)'*1000/length(y); fz = ((0:length(z)-1)'*(f2-f1)/length(z)) + f1; plot(fy(1:500),abs(y(1:500))); axis([1 500 0 1.2]); plot(fz,abs(z)); axis([f1 f2 0 1.2])3.5.3 CZT：：Matlab 实现实现262 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院例例：：假假设设x(n)由由4个个正正弦弦序序列列组组成成，，频频率率分分别别为为6Hz，，6.3 Hz，，9Hz和和8 Hz，，抽样频率为抽样频率为40Hz，时域取样，时域取样200点。
试求点试求; （（1）用）用 CZT 计算计算DFT；； （（2）直接计算）直接计算DFT；； （（3）在）在5～～10Hz的频段范围求的频段范围求CZTN=200; % 取取样样点数点数f1=6; f2=6.3; f3=9; f4=8;fs=40; % 取取样频样频率率stepf=fs/N; n=0:N-1; t=2*pi*n/fs; n1=0:stepf:fs/2-stepf;x=sin(f1*t)+sin(f2*t)+sin(f3*t)+sin(f4*t); %序列序列x(n)%直接求直接求CZTM=N; W=exp(-j*2*pi/M); A=1; Y1=czt(x,M,W,A);subplot(3,1,1); plot(n1,abs(Y1(1:N/2)));grid on; xlabel('f/Hz'); ylabel('Magnitude');解：CZT：：Matlab 实现实现263 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院%直接求 DFTY2=abs(fft(x)); subplot(3,1,2); plot(n1,abs(Y2(1:N/2)));grid on; xlabel('f/Hz'); ylabel('Magnitude'); %求5～10Hz的CZT，起始点不在z=1处M=100; f0=5; DELf=0.05;W=exp(-j*2*pi*DELf/fs); A=exp(j*2*pi*f0/fs);Y3=czt(x,M,W,A); n2=f0:DELf:f0+(M-1)*DELf;subplot(3,1,3); plot(n2,abs(Y3)); grid on;xlabel('f/Hz'); ylabel('Magnitude');CZT：：Matlab 实现实现264 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院处且从从图图可可以以看看出出，，（（a））是是直直接接利利用用CZT求求取取DFT，，图图（（b））是是直直接接求求DFT，，两两者者结结果果相相同同，，图图中中频频率率为为6Hz和和6.3Hz的的两两个个正正弦弦的的频频谱谱不不易易分分辩辩。
图图（（c））是是在在5～～10Hz这这个个频频率率范范围围内内求求出出的的CZT，，它它的的分分点点比比较较细细，，所所以以四四个个正正弦弦的的谱谱线线都都可以分辨出来可以分辨出来CZT：：Matlab 实现实现265 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院上机作业上机作业 1. 用用Matlab编编程上机程上机练习练习已知： N=25这这里里Q=0.9+j0.3可以推导导出出 ，， 首先根据首先根据这这个式子个式子计计算算X(k)的理的理论值论值，然后，然后计计算算输输入序入序列列x(n)的的32个个值值，再利用基，再利用基2时间时间抽抽选选的的FFT算法，算法，计计算算x(n)的的DFT X(k)，与，与X(k)的理的理论值论值比比较较（要求（要求计计算算结结果最果最少少6位有效数字）位有效数字） 266 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院 （（2）） 离散信号的频谱分析离散信号的频谱分析 假设信号假设信号 x(n) 由下述信号组成：由下述信号组成： 这这个个信信号号有有两两根根主主谱谱线线 0.3pi 和和 0.302pi 靠靠的的非非常常近近，，而而另另一一根根谱谱线线 0.45pi 的的幅幅度度很很小小，，请请选选择择合合适适的的长长度度 N 和和窗窗函数，用函数，用 DFT 分析其频谱，得到清楚的三根谱线分析其频谱，得到清楚的三根谱线。
上机实验作业要求：要求：（（1 1）） 流程图，源程序清单流程图，源程序清单（（2 2）打印出频谱分析的结果）打印出频谱分析的结果267 北京邮电大学信息与通信工程学院北京邮电大学信息与通信工程学院n理解傅里叶变换的几种形式理解傅里叶变换的几种形式n掌握掌握 DFSDFS及性质，掌握周期卷积过程及性质，掌握周期卷积过程n掌握掌握 DFTDFT及性质，掌握循环卷积、线性卷积及两者之间及性质，掌握循环卷积、线性卷积及两者之间的关系的关系n掌握线性卷积的掌握线性卷积的 DFT DFT 算法及分段卷积方法算法及分段卷积方法n掌握按时间抽选的基掌握按时间抽选的基-2 FFT -2 FFT 算法的算法原理、运算流算法的算法原理、运算流图和算法特点及图和算法特点及IFFT IFFT 算法算法n掌握按频率抽选的基掌握按频率抽选的基-2 FFT -2 FFT 算法的算法原理、运算流算法的算法原理、运算流图和算法特点及图和算法特点及IFFT IFFT 算法算法n理解频谱分析过程理解频谱分析过程n了解了解 CZT CZT 算法算法本章小结本章小结268 放映结束 感谢各位的批评指导！ 谢谢 谢！谢！让我们共同进步 。