离散傅里叶变换及其快速计算方法.ppt

1、DFS 和 DFT 的导出 DFS 和 DFT 的性质 Z 变换与 DFS 的关系 FFT IDFT 频谱分析,第三章 DFT离散付氏变换,2,连续信号 xa(t)，其傅里叶变换为： xa(t) 为时域连续信号 Xa() 为频域连续信号,3.1 问题的提出：连续信号的傅里叶变换,3,离散信号在两种变换域中的表示方法 （1）离散时间傅里叶变换 DTFT - 提供了绝对可加的离散时间序列在频域（）中的表示方法。 （2）Z 变换 - 提供任意序列的 z 域表示。,这两种变换有两个共同特征： （1）变换适合于无限长序列 （2）它们是连续变量 或 z 的函数,3.1 问题的提出：离散信号的变换,4,问题

2、：X(z)，X(ejw) 都是连续的，利用计算机处理有困难，例如使用 Matlab，因此 提出了在频域内取样，使频谱离散化的问题； 必须截断序列，得到有限个点的序列。 目标：我们需要得到一个可进行数值计算的变换 方法： （1）DTFT - 频域中原始信号频谱的周期拓展 （2）对 DTFT 在频域中采样 - DFS （3）将 DFS 推广到有限持续时间序列 DFT （DFT 避免了前面提到的那两个问题，并且它是计算机可实现 的变换方式。） DFT 已成为 DSP 算法中的核心变换，原因： （1）有限长序列傅里叶变换的重要方法 （2）有快速算法,3.1 问题的提出：可计算性,5,3.1 问题的提出

3、：傅里叶变换的四种形式 （1）,非周期连续时间傅里叶变换(FT)连续频率 周期连续时间傅里叶级数(FS)离散频率 非周期离散时间离散时间傅里叶变换(DTFT)连续频率 周期离散时间离散傅里叶级数(DFS)离散频率,6,3.1 问题的提出：傅里叶变换的四种形式 （2）,1. 连续信号（非周期）的付氏变换,时域连续函数造成频域是非周期的谱 时域的非周期造成频域是连续的谱,7,2. 周期连续时间信号：傅里叶级数 FS,时域连续函数造成频域是非周期的谱。 频域的离散对应时域是周期函数。,3.1 问题的提出：傅里叶变换的四种形式 （3）,时域周期频域离散,8,3. 非周期离散信号：离散时间傅里叶变换 D

4、TFT,时域的离散化造成频域的周期延拓 时域的非周期对应于频域的连续,3.1 问题的提出：傅里叶变换的四种形式 （4）,时域离散频域周期,取样定理,9,4. 周期离散时间信号：离散傅里叶级数 DFS,一个域的离散造成另一个域的周期延拓 离散傅里叶级数的时域和频域都是离散的和周期的,3.1 问题的提出：傅里叶变换的四种形式 (5),时域周期、离散频域周期、离散,10,四种傅里叶变换形式的归纳总结：,离散时间函数的取样间隔：T1，取样频率：,离散频率函数的取样间隔：F0，时间周期：,3.1 问题的提出：傅里叶变换的四种形式 （6）,结论： 时域中函数取样(离散) （映射）频域中函数周期重复； 频域

5、中函数取样 （映射） 时域中函数周期重复； 取样间隔 （映射） 周期（2/间隔）,0,时域中函数的取样和频域中函数的取样,3.1 问题的提出：傅里叶变换的四种形式 (7),12,由以上讨论可以清楚地看到，时域取样将引起频域的周期延拓，频域取样也将引起时域的周期延拓。 因此可以设想，如果同时对频域和时域取样，其结果是时域和频域的波形都变成离散、周期性的波形，从而我们可以利用付氏级数这一工具，得到它们之间的离散付氏级数 DFS 关系。,3.2 DFS 及其性质,13,基本关系式 若 r，m 都是整数,则:,其中:,DFS 定义：预备知识,证明: 对于r=m：不论 k 取何值，显然等式成立。 对于r

6、m：,14,为了推导 的关系，作下列变量代换： 时域： 频域： 则得：,?,DFS 定义：正变换,15,周期离散序列的 Z 变换存在（收敛）的问题 因为周期离散序列， 而对于周期信号，严格数学意义上讲，其 Z 变换不收敛，因为： 而对于 找不到衰减因子使它绝对可和（收敛）。为此，定义新函数，其 Z 变换：,DFS 定义：正变换,16,其频谱：（ 是连续变量，需要对其离散化）,DFS 定义：正变换,（取 的一个主周期进行 Z 变换）,17,频域取样 X(ej) 是连续变量 的周期函数，周期为2。把 离散化，即在02区间内等间隔取 N 个点，取样间隔为 2/N。 另一个角度看， X(ej) 是 Z

7、 平面单位圆上的 Z 变换。连续变量 的离散化也可以认为是把单位圆分 N 等分，每分为 2/N 。 其中： 称为频域中的取样间隔， 也称为频率分辨率。,DFS 定义：正变换,18,DFS 定义：正变换,19,DFS：,DFS 定义：正变换,也仅有 0，1，N-1 个独立值,周期为 N。,因为,所以,20,反变换IDFS 正变换两端乘以 ，m=0,1,N-1 然后令 k=0，1，N-1 求和，得：,DFS 定义：反变换,用正交条件：,21,DFS 定义：反变换,即,（只有 m=n 时，才有值，而 m 不等于 n 时，为零，因此，x(n) 只取 x(m) ）,变量m替换为n，得,22,DFS 变换

8、对：时域周期序列与频域周期序列间的关系,DFS 定义：反变换,其中,23,在什么条件下不产生混迭失真？ 频率取样 频率取样：若时间信号有限长，当满足下列条件时，X(ej) 的样本值 X(k) 能不失真的恢复成原信号。 为了避免时间上的混迭： （1）必须是时间限制（有限时宽） （2）取样频率间隔小于,DFS 定义：几点说明,24,频率分量 如果变量 DFS 可表示为： 因此，时域 n 及频域 k 都是有物理意义的。,DFS 定义：几点说明,（指数项 kn 不变）,25,更具体地，傅里叶系数的标号 k 和频率 f 的关系为： 所以： 对应关系： 傅里叶系数标号k ：0N 数字频率：02 模拟频率

9、f ：0fs,DFS 定义：几点说明,26,DFS 定义：几点说明,频率成份 直流分量： 当 k=0 时， ，此时得到的傅里叶级数的系数称为信号的直流分量（DC Component）， 是信号的平均值； 交流分量： 其它频率（k0）称为周期信号的谐波，此时的傅里叶级数系数称为信号的交流分量。 k=1 时的频率为信号的一次谐波，或基频，频率大小为 fs/N，时间为 NTs，等于完成一个周期所需要的时间。其它谐波为基频的整数倍。 离散傅里叶级数包含了 0 到 (N-1)fs/N 的频率，因而 N 个傅里叶级数的系数位于从 0 直到接近取样频率的频率上。,时域,27,DFS 定义：几点说明,周期信号

10、的频谱 由傅里叶系数 可得到 的幅度频谱 和相位频谱 ，不难证明，如果 是实序列，那么幅度频谱是周期性偶函数，相位频谱是周期性奇函数。 周期信号由离散傅里叶级数 DFS 得到的频谱，和非周期信号由离散时间傅里叶变换 DTFT 得到的频谱之间有重要区别。 DTFT 产生连续频谱，这意味着频谱在所有的频率处都有值，因而非周期信号的幅度和相位频谱是光滑无间断的曲线。 与之相反，DFS 仅有 N 点的频谱，仅包含有限个频率，因而周期信号的幅度和相位频谱是线谱，即相等间隔的竖线，当频谱的横坐标变量用实际频率 f 代替 k 时，谱线间隔为 fs/N。并不是所有的周期信号都含有全部谐波，例如有些频谱只有奇次

11、谐波，比如三角波，偶次谐波为0，而有些频谱仅在一些谐波处的值为0。,28,DFS 的 Matlab 的实现,由 DFS 的定义可以看出它是一种可进行数值计算表示式，它可由多种方式实现。 （1）利用循环语句 for.end 实现 为了计算每个样本 ，可用 for . end 语句实现求和。 为了计算所有的 DFS 系数，需要另外一个for.end 循环，这将导致运行嵌套的两个for .end 循环。显然，这种方法的效率较低。,29,设 和 代表序列 x(n) 和 X(k) 主周期的列向量，则 DFS 的正反变换表达式由下式给出： 其中矩阵 WN 由下式给出：,矩阵 WN 为方阵，叫做 DFS 矩

12、阵.,（2）利用矩阵矢量乘法,30,function Xk = dfs(xn,N) n = 0:1:N-1; % row vector for n k = 0:1:N-1; % row vecor for k WN = exp(-j*2*pi/N); % Wn factor nk = n*k; % creates a N by N matrix of nk values WNnk = WN . nk; % DFS matrix Xk = xn * WNnk; % row vector for DFS coefficients function xn = idfs(Xk,N) n = 0:1:N

13、-1; % row vector for n k = 0:1:N-1; % row vecor for k WN = exp(-j*2*pi/N); % Wn factor nk = n*k; % creates a N by N matrix of nk values WNnk = WN . (-nk); % IDFS matrix xn = (Xk * WNnk)/N; % row vector for IDFS values,DFS 的 Matlab 的实现,例 ：求出下面周期序列的 DFS 表示式,解：上述序列的基本周期为 N=4，因而 W4 = e-j2/4 = -j，,例: 下面给

14、出一周期“方波”序列： 其中， 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)对所得结果进行讨论。,解：(a) 由 DFS 定义可得,而：,的幅值可表示为：,b. Matlab 程序如下： % Chapter 3: Example 3.03 L = 5; N = 20;(改变参数） x = ones(1,L), zeros(1,N-L); xn = x * ones(1,3); xn = (xn(:); n = -

15、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),% 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); a

16、xis(-N/2,N/2,-0.5,5.5) xlabel(k); ylabel(Xtilde(k) title(DFS of SQ. wave: L=5, N=20),注意： 是周期信号，图中只画出了从 N/2 到 N/2 的部分。 c. 从图中可以看到，方波的 DFS 系数的包络像“ Sinc ”函数， K=0 时的幅度等于 L； 同时函数的零点位于 N/L（占空比的倒数）的整数倍处； L=5 不变，N变大（即填0，但有效信息没有增加），则形状不变，只是更平滑，即获得了一个高密度谱； N=60 不变，L 变大（即增加了原始数据长度），则变换后得形状发生了变化，获得了更多的信息，即高分辨率谱

17、。,例 ： 设 当 N=5、10、20、50 时，分别对其 Z 变换在单位圆上取样，研究不同的 N 对时域的影响。,% 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个周期 xtil

18、de = (xtilde(:); subplot(2,2,1);stem(0:39,xtilde); axis(0,40,-0.1,1.5);xlabel(n);ylabel(xtilde(n); title(N=5),从图中清楚地表明在时域中出现的混叠，尤其是当 N=5 与 N=10 时。对于大的 N 值，其 x(n) 的尾部足够小，实际上不会导致明显的混迭。这对于变换前，有效截取无限序列，是非常有效的。,1.2020,1.0291,1.0008,1.0000,42,线性,且：,则, a,b为任意常数,DFS 的性质：线性,43,序列的周期移位（时域） 若 是周期序列，其周期为N，移位后仍为

19、周期序列，且：,DFS 的性质：序列的周期移位,证明：,44,调制特性（频域周期移位）,DFS 的性质：调制特性,证明：,45,周期卷积（时域）,若,则,频域相乘 时域卷积 周期卷积：两个周期序列在一个周期上的线性卷积，是一种特殊的卷积计算形式。,DFS 的性质：周期卷积 （1）,46,DFS 的性质：周期卷积 （2）,证明：,47,DFS 的性质：周期卷积 （3）,（1）x1(n)和x2(n)是周期的。 （2）求和范围为一个周期 （3）周期序列周期卷积后，序列的长度仍然是周期的；,位置保持不变,48,序列的线性卷积与周期卷积的几点区别： 线性卷积的求和对参与卷积的两个序列无任何 要求，而周期

20、卷积要求两个序列是周期相同的周期序列。 线性卷积的求和范围由两个序列的长度 和所在的区间决定，而周期卷积的求和范围是一个周期 N。 线性卷积所得序列的长度 (M+N-1) 由参与卷积的两个序列的长度确定，而周期卷积的结果仍是周期序列 ，且周期与原来的两个序列周期相同。 周期卷积等同于两个周期序列在一个周期上的线性卷积计算。,DFS 的性质：周期卷积 （4）,解：,例： 已知序列 x1(n)=R4(n)，x2(n)=(n+1)R5(n)，分别将序列以周期为 N=6 拓展成周期序列，求两个周期序列的周期卷积和。,1,5,4,5,1,2,51,频域周期卷积 利用 DFS 的对偶性有：,若,则,时域相

21、乘 频域卷积,DFS 的性质：周期卷积 (5),注意频域卷积的求和号前面有 1/N。,52,DFS 的性质：共轭对称性,由任一周期性序列 ，定义如下两个序列： 共轭偶对称周期性序列 共轭奇对称周期性序列,且具有如下关系：,其它对称性质见教科书,53,DFS 定义和性质：小结,时域周期序列与频域周期序列的关系 DFS DFS 的性质 重点：周期移位 调制特性 周期卷积,54,对于一段有限长信号（连续），分析频谱问题是付氏积分问题，进行时域周期重复和取样两过程，就可把广义积分问题变成有限项求和，即由CTFTDFS。 DFS 变换：周期离散时间函数与一周期离散频率函数的组合，它们是有限求和（而不是积

22、分），常用 DFS 来逼近连续时间过程的傅氏变换。 也即要用数字运算能完全计算出付氏积分，必须对时间函数和频率函数取样（即DFS），选择时间有限和频率有限的信号。 时间取样：取样频率大于信号最高频率两倍； 频率取样：取样间隔足够小，使时间函数的周期（单位圆上等分（取样）的点数）大于信号的时域长度。 结果：频域和时域中均不出现混迭现象。,3.3 有限离散傅里叶变换及其性质 (1),55,离散傅氏级数提供了一种对离散时间傅氏变换作数值计算的技巧，它在时域和频域都是周期的，但在实际中大多数信号不具有周期性，它们很可能具有有限持续时间。 对这些信号，怎样探讨一种可数值计算的傅氏表达式？ 理论上，可通过

23、构造一周期信号，其基本形状为有限持续时间信号，然后计算此周期信号的 DFS。 实际上，这也就是定义了一种新的变换，称为离散傅氏变换（DFT），它是 DFS 的主周期。 DFT 是对任意有限持续时间序列可数值计算的傅氏变换。,3.3 有限离散傅里叶变换及其性质 (2),56,同样：X(k)也是一个N点的有限长序列,关系 ?,其中:,DFT 定义：表达式 (1),周期序列的表示,57,DFT 定义：表达式 (2),若 n=n1+n2N 成立，且 n1 满足 0n1N-1，则把 n1 称做 n 对N的模数，用符号 (n)N 表示，即：n 模 N=(n)N=n1，也就是 n 对 N 取余数。 例: 是

24、周期为 N=6 的序列，求 n=19及 n= -2 两数对N的余数。 解： n=19=1+36 ， (19)6=1 n=-2=(-1)6+4 ，(-2)6=4 即：,58,在无混迭的情况下，我们看如何把 DFS 变成 DFT ?,DFS:,DFT 定义：表达式 (3),因无混迭，则时域中一个周期长的主值序列对应于频域中一个周期长的主值序列。从DFS的时域和频域中各取出一个周期，即得到有限长度离散序列的时域和频域傅氏变换。,59,有限长序列的 DFT 正变换和反变换：,其中：,DFT,DFT 定义：表达式 (4),或,注意：从工程角度看，DFS 和 DFT 的表达式没有本质区别。,60,DFT的

25、矩阵表示形式,若令：,则：,DFT 定义：表达式 (5),61,DFT 定义：表达式 (6),DFT图形解释,62,不仅浓缩了 的全部内容，同时也浓缩了 的全部内容。 能够如实、全面地表示 的频域特征，所以 DFT 具备明确的物理含义。,DFT 定义：表达式 （7）,DFT 意义,63,由上面的讨论可知，在 0nN-1 上，DFS 和 DFT 相同。 因此，可用类似的方法实现 DFT。把原先名为 dfs 和 idfs 的 Matlab 函数改名为 dft 和 idft 函数，即可实现离散傅氏变换 DFT。 实际中，我们用的更多的是 DFT 的快速算法 FFT，见后续内容。,DFT 定义：Mat

26、lab 实现,64,例： x(n) 是一个 4 点序列： （1）计算离散时间傅氏变换 X(ejw)，并画出它的幅度和相位。 （2）计算 x(n) 的 4 点 DFT。,DFT 定义：举例,65,解：（1） 离散时间傅氏变换为：,因而,DFT 定义：举例,66,DFT 定义：举例,67,(2)用 X4(k) 表示 4 点 DFT:,DFT 定义：举例,% b) 4-point DFT N = 4; w1 = 2*pi/N; k = 0:N-1; X = dft(x,N); magX = abs(X), phaX = angle(X)*180/pi subplot(2,1,1); plot(w*N

27、/(2*pi),magH,-); axis(-0.1,4.1,-1,5); hold on stem(k,magX);,68,k,DFT 定义：举例,69,例: 怎样得到 DTFT X(ejw) 的其他样本？ 解：显然，我们的采样频率应更小一些，也就是说，应增加 N 的长度。 有两种方法， 一种是采样时就采样更多的样本； 另一种是在序列后面添加一定长度的零，叫做填零运算，在实际中，为了得到一个较密的频谱，这种运算是必要的。,3.3.1 DFT 定义：举例,70,（a）给 x(n) 后附加 4 个零得到一个 8 点序列。 x(n) = 1,1,1,1,0,0,0,0 设 X8(k) 为一 8 点

28、 DFT， 则 在这种情况下，频率分辨率为 w1 = 2/8 = /4。,DFT 定义：举例,71,% b) 8-point DFT N = 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

29、 67.5000,DFT 定义：举例,72,DFT 定义：举例,73,（b) 更进一步，给 x(n) 填充 12 个零，变成一个 16 点序列， 即： x(n)=1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0 在这种情况下，频率分辨率为 w1 = 2/16 = /8。,DFT 定义：举例,74,% c) 16-point DFT subplot(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(

30、2,1,1);plot(w*N/(2*pi),magH,-); axis(-0.1,16.1,-1,5); hold on stem(k,magX); xlabel(k); ylabel(|X(k)|); title(Magnitude of the DFT: N=16) hold off subplot(2,1,2);plot(w*N/(2*pi),phaH*180/pi,-); axis(-0.1,16.1,-200,200); hold on stem(k,phaX); xlabel(k); ylabel(Degrees); title(Angle of the DFT: N=16),D

31、FT 定义：举例,75,DFT 定义：举例,76,结论：基于以上两个例子，可以得到以下结论。 填零是给原始序列填零的运算。这导致较长的 DFT，它会给原始序列的离散时间傅氏变换提供间隔更密的样本。在 Matlab 中，用 zeros 函数实现填零运算。 为精确地画出离散时间傅氏变换 X(ejw) ，只需要 4 点 DFT X4(k)。这是因为 x(n) 仅有 4 个非零样本，因此，可通过填零得到 X8(k)、X16(k) 等等，用它们来填充 X(ejw) 的值。 填零运算提供了一个较密的频谱和较好的图示形式，但因为在信号中只是附加了零，而没有增加任何新的信息，因此，它不能提供更高分辨率的频谱。

32、 为了得到更高分辨率的频谱，需要获得更多的数据。其他的先进方法则是利用边缘信息和非线性技术。,DFT 定义：举例,77,例：为了说明高密度频谱和高分辨率频谱之间的区别，考察序列 求出它基于有限个样本的频谱。 （a）当 0n10 时，确定并画出 x(n) 的离散傅氏变换。 （b）当 0n100 时，确定并画出 x(n) 的离散傅氏变换。,DFT 定义：举例,78,(a) 首先确定 x(n) 的 10 点DFT，得到其离散时间傅氏变换的估计 %High resolution spectrum based on 100 samples of the signal x(n) subplot(1,1,1

33、);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);%(

34、只画了一半的点，原因是镜像对称的点） title(Samples of DTFT Magnitude); xlabel(frequency in pi units); axis(0,1,0,10); disp(Press RETURN to continue);pause;,DFT 定义：举例,79,DFT 定义：举例,80,填充 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

35、(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 RETU

36、RN to continue);hold off; pause;,DFT 定义：举例,81,DFT 定义：举例,从结果图中可以看到，此序列在 w=0.5 处有一主频率，原始序列则没有说明这一点 。填零运算提供了更加平滑,高密度的频谱曲线,82,（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);xlabe

37、l(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 定义：举例,83,DFT 清楚地表明了两个靠得很近的频率，这是 x(n) 的高分辨率的频谱,采样更多的数据提供了更多的信息,DFT 定义：举例,84,分辨率 N 点

38、 DFT 覆盖了 0 到 fs （取样频率）的频率范围。因此，频率取样点以 fs/N 为间隔。该频率间隔称为 DFT 的频率分辨率，它描述了 DFT 分辨相邻信号频率的程度。频率间隔越小，分辨率越好；间隔越大，DFT 分辨率越差。 假定取样频率保持不变，当取样点越大时，DFT 分辨率就会越好，这样频率间隔小，可获得频谱的许多细节。,DFT 定义：DFT 频谱,85,例: 欲做频谱分析的模拟数据以10KHz速率被取样，且计算了1024个取样的离散傅氏变换，试求频谱取样之间的频率间隔。,解： fs= 10KHz，即绕单位圆一周（2）为10KHz， N=1024 所以间隔,DFT 频谱：举例,86,

39、例： 以 256Hz 取样频率对信号 取样，得到离散信号 x(n)，计算其频谱。 解： 数字频率： 数字信号： 数字周期： 数字周期为 64，覆盖了15个模拟信号周期。,DFT 频谱：举例,87,DFT 频谱：举例,30,88,序列 x(n)的 Z 变换在单位圆上进行 N 等分，即2/N，就是序列的DFT变换。(取样） Z 变换和 DFT的关系是取样和内插的关系，这在实际应用中很重要。,DFT 与 DTFT 和 Z 变换的关系,89,取样 Z 变换 设 x(n) 为一个长度为N的有限长序列，则有：,DFT 与 Z 变换的关系：取样 Z 变换,90,从 DTFT 的角度看：有限长序列的 DFT

40、结果包含了 N 个离散频率点处的 DTFT 结果，这个离散频率点等间隔地分布在区间 0，2) 内；,从 Z 变换的角度看： DFT结果包含了 z 平面上 N 个离散点处的 Z 变换结果，这 N 个离散点均匀地分布在单位圆上，由此也称DFT为单位圆上的取样 Z 变换。,DFT 与 Z 变换的关系：取样 Z 变换,91,频域取样定理：若序列长度为 M，则只有当频域采样点数 N 满足 NM 时，才有: 即可由频域取样 X(k) 不失真地恢复原信号 x(n)，否则产生时域混叠现象。 此时可由 N 个取样值 X(k) 内插恢复出 X(z)或 X(ejw)。,DFT 与 Z 变换的关系： z 域内插,时域

41、取样定理：在满足奈奎斯特定理条件下，时域取样信号可以不失真地还原原连续信号。 频域取样情况如何？取样条件？内插公式？,92,Z 域内插公式：由 DFT X(k) 可以确定 z平面上任一点处的 X(z),DFT 与 Z 变换的关系： z 域内插,z 平面内插公式,内插函数,93,内插函数的零极点分布 极点：(N-1)阶极点z = 0； 一阶极点 z=1； 零点：N 个一阶零点: 抵消：z=1 处的一阶极点和一阶零点互相抵消，一阶零点数量变为 （N-1）个。,3.3.2 DFT 与 Z 变换的关系： z 域内插,(z) 的零、极点分布,94,3.3.2 DFT 与 Z 变换的关系： F 域内插,F

42、 域内插公式：由频域取样 DFT X(k) 表示 DTFT X(ejw),95,即:,其中:,频域内插函数,频域内插公式,3.3.2 DFT 与 Z 变换的关系： F 域内插,96,F 内插函数的零极点分布 根据(z) 的零极点分布规律可知： (零极点对系统频率响应的影响) 极点：ej 到极点 z=0 的距离恒为1，对 幅频特性没有影响 零点： 在区间 0, 2 内，|()| 存在(N-1)个零值点 存在 (N-1)个极值点，分别为：,(z) 的零、极点分布,3.3.2 DFT 与 Z 变换的关系： F 域内插,97,插值函数的幅度特性（N=5),DFT 与 Z 变换的关系： F 域内插,98

43、,频域内插的物理含义,只有当频域取样点数 N 大于序列长度 M 时， 中不会出现混迭现象，这时能够从 中如实恢复 x(n)，即能够由 X(k) 准确重建 X(z) 和 X(ejw)。 对序列作 DFT 变换点数不应低于序列的长度。 X(k) 浓缩了 x(n) 在变换域中的全部特性。,DFT 与 Z 变换的关系： F 域内插,99,这里，序列长度及 DFT 点数均为 N 若不等，分别为 N1、N2，则需补零使两序列长度相等，均为 N，且,若两序列 x1(n) 和 x2(n) 的长度均为 N，且其 N 点 DFT 分别为：,则：,DFT 的性质：线性,a, b 为任意常数,100,对于周期序列，有

44、： 其中： 周期共轭偶对称分量 周期共轭奇对称分量 又定义： 又由于 则： 即有限长序列由共轭偶对称和共轭奇对称两部分组成。,DFT 的性质：对称性,共轭奇对称分量,共轭偶对称分量,101,DFT 的性质：对称性,102,若存在有限长序列 x(n)，长度为 N，其 N 点 DFT 的结果为X(k)，则有，,证明：,DFT 的性质：帕斯瓦尔定理,该定理表明:可利用序列的 DFT 结果表示信号的能量，序列在时域计算的能量与在频域计算的能量相等，即变换前后的能量保持不变。 这进一步说明，虽然 DFT 有别于 DTFT，但其仍然具有明确的物理含义。,103,DFT 的性质：反转定理,循环反转的定义 如

45、果 x(n) 是长度为 N 的序列，则称 x(-n)N RN(n) 为 x(n) 的循环反转运算。,循环反转运算是有限长序列所特有的一种运算，其结果仍然是集合 0, 1, ., (N-1) 上的有限长序列，特别注意 n=0 时情况。 计算过程：（1）补零为 N；（2）周期延拓；（3）纵轴镜像；（4）取主值序列。,104,DFT 的性质：反转定理,循环反转的 DFT,若,则,证明：,105,DFT 的性质：序列的循环移位(圆周移位),循环移位的定义：,称其为循环移位的原因在于，当序列从一端移出范围时，移出的部分又会从另一端移入该范围。 线性移位：若 N 点序列沿一方向线性移位，它将不再位于区间

46、0nN-1 上。,106,DFT 的性质：序列的循环移位(圆周移位),有的书上称为圆周移位。把x(n)看作排列在N等分的圆周上，循环移位就相当于序列 x(n) 在圆周上移动，故称为圆周移位。实际上重复观察几周时，看到的就是周期序列。,107,例： 设 x(n) = 10(0.8)n， 0n10 为 11 点序列 (a) 画出 x(n+4)11R11(n)， 也就是向左循环移位 4 个样本的序列； (b) 画出 x(n-3)15R15(n)， 也就是假定 x(n) 为 15 点序列，向右循环移位 3 个样本。,DFT 的性质：序列的循环移位(圆周移位),108,(b) 在这种情况下，给 x(n)

47、 后填充 4 个零，将其看作一个 15 点序列。此时的循环移位与 N=11 时不同，看起来像线性移位 x(n-3)。因此，序列的周期长度是非常重要的一个参数。,DFT 的性质：序列的循环移位(圆周移位),109,结论： 有限长序列的循环移位，在离散频域中只引入了一个和频率成正比 的线性相移 ，对幅频特性没有影响。,DFT 的性质：序列循环移位后的 DFT,若,，则,证明：,110,时域序列的调制等效于频域的循环移位,DFT 的性质：频域循环移位后的 IDFT,频域循环移位后的 IDFT（调制特性） 由 DFT 所具有的对偶特性不难看出，在频域内循环移位时，将有类似的结果，即：,证明：,111,

48、DFT 的性质：频域循环移位后的 IDFT,证明：,112,DFT 的性质：循环卷积(圆周卷积),循环卷积定义： 设 x1(n) 和 x2(n) 都是长度为 N 的有限长序列，把它们分别拓展为周期序列 和 ，定义循环卷积为：,周期序列卷积后取主值,113,因为上式的求和范围是 m 由 0 到 N-1，因此第一个序列 x1(m) 可以不作周期拓展，即 注意两个 N 点序列的线性卷积将导致一个更长的序列。而循环卷积将区间限制在 0nN-1，结果仍为 N 点序列，它与线性卷积的结构类似。不同点在于求和范围和 N 点循环移位。它与 N 有关，也叫做 N 点循环卷积。,DFT 的性质：循环卷积(圆周卷积

49、),N,窗函数限定了循环卷积的范围,114,循环卷积过程： （1）补零 （2）周期延拓 （3）反转，取主值序列 （循环反转） （4）对应位相乘，然后求和， 得到n=0时的卷积结果。 （5）向右循环移位（圆周移位） （6）重复，n=1(N-1),DFT 的性质：循环卷积(圆周卷积),注意 n=0 时的循环反转,115,循环卷积的时频映射关系 由 DTFT 的性质可知，两个序列时域上的线性卷积运算在频域上表现为两个序列 DTFT 结果的乘积。 同样的，若 则 即当在频域中进行两个 N 点 DFT 相乘时，在时域中映射为循环卷积（而不是通常的线性卷积 ！）。,DFT 的性质：循环卷积(圆周卷积),1

50、16,证明： 将 X1(k) 和 X2(k) 作周期延拓，分别得到 X1(k) N 和 X2(k) N。,则,再设,于是,DFT 的性质：循环卷积(圆周卷积),令,117,因为,所以,此时上式最后一个求和号中，已不对 r 求和，故此求和号可以去掉，因此，,因而，,即,DFT 的性质：循环卷积(圆周卷积),118,利用时域、频域的对偶性可得频域循环卷积:,若,则,时域循环卷积可在频域中完成:,DFT 的性质：循环卷积(圆周卷积),119,（1) 同心圆法 （2) 利用求周期卷积的作图法 （3) 解析式法 （4) Matlab 方法,DFT 的性质：循环卷积计算方法,120,同心圆法 可用两个同心

51、圆来表示： x1(n) ：内圆顺时针方向排列 x2(n) ：外圆逆时针方向排列 x1(0) 与 x2(0) 对齐。,DFT 的性质：循环卷积计算方法,121,两圆上对应数两两相乘后求和，得 x3(0) ; 将x2(n-m)移位一位，即外圆顺时针转动一位，重复（1）步骤，得x3(1) ； 依次下去，求得,DFT 的性质：循环卷积计算方法,122,作图法 (1) x1(m) 和 x2(m) 在 m 轴上周期延拓，成为 (2)将 反转 ； (3)计算周期卷积 (4)取 一个周期，得到,DFT 的性质：循环卷积计算方法,上述过程：只需将 x1(n) 和 x2(n) 分别做周期延拓，得到 和 ，再按照计

52、算周期卷积的作图法，计算出n 由 0 到 N-1 的周期卷积，即为循环卷积。,124,DFT 的性质：循环卷积计算方法,例: 设 x1(n) = 1,2,2，x2(n)=1,2,3,4，计算 4 点循环卷积 解： 注意 x1(n) 为 3 点序列，进行循环卷积之前在其尾部填一个零，使其成为 4 点序列，分别在时域和频域中求解这个问题。,125,（1）时域方法 4 点循环卷积由下式给出 对每个 n 产生一个循环移位序列，将它的样本逐个与 x1(m) 相乘，然后求和，得此 n 值的循环卷值，在 0n 3 上重复此过程。考虑 x1(m) = 1,2,2,0 和 x2(m) = 1,2,3,4。 n=

53、0 时,DFT 的性质：循环卷积计算方法,注意此为 x2(0)，而不是 4,3,2,1,126,n = 2 时，,DFT 的性质：循环卷积计算方法,n = 3 时，,因此，,127,(2) 频域方法： 首先计算 x1(n) 和 x2(n) 的 4 点 DFT，逐个样本相乘，取IDFT，得到循环卷积。,DFT 的性质：循环卷积计算方法,则（注意：X1(k) 和 X2(k) 对应位相乘）,IDFT 后，得,表面看来，这样做反而更复杂，且涉及复数运算。但后面我们会看到，DFT 有快速算法 FFT，特别是当 N 很大时，效率会显著提高。,128,利用 DFT 求离散线性卷积 条件：NN1+N2-1 方

54、法：时域转换到频域，处理后再转换回时域 用 DFT 进行信号频谱分析 参数选择 频谱泄漏 栅栏效应,DFT 的应用,129,线性移不变离散系统,当长度 N 增大时，线性卷积的运算量较大，需寻找实用的线性卷积的快速计算方法！,DFT 的应用：线性卷积求解,130,线性卷积：,N点循环卷积：,DFT 的应用：线性卷积求解,循环卷积和线性卷积的关系,131,讨论线性卷积 y(n)=x(n)*h(n) 的长度 从 x(m) 看， 非零值区为： 0mN-1 从 h(n-m) 看，非零值区为： 0n-mM-1 将二不等式相加，得到 y(n) 的非零区： 0 n M+N-2 在此区间之外，不是 x(m)=0

55、，就是 h(n-m)=0，即y(n)=0，因此，y(n) 的长度为 M+N-1,DFT 的应用：线性卷积求解,132,讨论循环卷积的长度 循环卷积是周期卷积的主值序列。为了研究长度不等的两个序列的周期卷积，构造周期序列，使它们的长度相等，且均为 L。,表示为,DFT 的应用：线性卷积求解,133,周期卷积如下：,周期卷积是线性卷积的周期延拓，周期为 L。 当周期为 LN+M-1 时，不会发生混迭，线性卷积正好是周期卷积的一个周期 。 循环卷积又是周期卷积的主值序列 。,DFT 的应用：线性卷积求解,因为 ，即 0mL-1 范围内 x(m+qL) 只有一个周期。,134,由于循环卷积是周期卷积的

56、主值序列。因此，此时循环卷积与线性卷积完全相同。即：,因此，循环卷积等于线性卷积的条件是： 即对于 N 长度的 x(n)，M 长度的 h(n)，在它们后面补零，使其长度均变为 LM+N-1。,DFT 的应用：线性卷积求解,136,讨论,若序列 的长度为 ， 序列的长度为 ，且有 大于 ，那么， 和 的 点循环卷积结果为：,其中，,此时，两序列的线性卷积结果 的长度 ，对其在时域作周期为 的延拓相加得到序列,主值序列的前 个点存在混迭。因此，在 中 也就是说，序列 中最后 个点与两序列的线性卷积结果相同。,答： （1）719点 （2）27点,139,即时域循环卷积 频域相乘,DFT 的应用：线性

57、卷积求解,设,若,则,用 DFT 求解线性卷积,140,如果循环卷积的长度 N 满足 NN1+N2-1，则此循环卷积 Y(k) 就等于 x(n) 和 h(n) 的线性卷积。用流程图表示法求 y(n)=x(n)*h(n) 的过程如下： 因为 DFT、IDFT 都有快速算法，因此，线性卷积可以实现快速算法。,DFT 的应用：线性卷积求解,141,DFT 的应用：线性卷积求解,乘法次数 循环卷积：在上述 DFT 求解线性卷积过程中，需要 3 次DFT（FFT）运算，后面我们会讲到 N 点 FFT 所需要的乘法次数为 ，因此，用 DFT 求线性卷积所需要的总的乘法次数：,线性卷积：每一个输入值 x(n

58、) 都必须和全部的 h(n) 值乘一次，因此，总共需要 N1N2 次乘法运算，ML=N1N2。,设,若 N1=N2 时，则,142,DFT 的应用：线性卷积求解,结论：N1=N2 越长，循环卷积的优越性越大。但当其中一个序列很长时，例如 x(n) 当很长时，即：,这时,Cm下降，循环卷积快速算法的优点不能发挥出来。,克服的办法：分段卷积 将长序列分段，每一段分别与短序列进行循环卷积（即用 FFT 运算） 分为重叠相加法，重叠保留法。,143,线性卷积求解小结 时域直接求解,z 变换法,DFT 法,DFT 的应用：线性卷积求解,144,上面介绍的是两个有限长序列 x1(n)、x2(n) 的线性卷积。但有时其中某个序列会很长或无限长，若等长序列存储或输入完后再做卷积运算，将产生问题： (1) 存储量过大，运算量也太大； (2) 等待输入的时间很长，引起不能忍受的延迟； (3) 采用 DFT/FFT 快速算法的效率降低,具体方法：重叠保留法、重叠相加法,解决此问题的思路：