第三节变换.ppt

《第三节变换.ppt》由会员分享，可在线阅读，更多相关《第三节变换.ppt（69页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三节变换现在学习的是第1页，共69页2.2 利用DFT进行连续信号的频谱分析 1、混叠 2、泄漏 3、栏栅效应 4、DFT的分辨率 5、周期信号的谱分析数字信号处理数字信号处理现在学习的是第2页，共69页数字信号处理数字信号处理现在学习的是第3页，共69页3.3 快速傅里叶变换快速傅里叶变换 有限长序列通过离散傅里叶变换(DFT)将其频 域离散化成有限长序列。但其计算量太大(与N的平方成正比），很难 实时地处理问题，因 此 引 出 了 快 速傅 里 叶 变 换(FFT)。FFT并 不是 一 种 新 的 变 换 形 式，它 只 是 DFT 的一 种 快 速 算 法，并 且 根 据 对 序 列

2、分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法。FFT 在 离 散 傅 里 叶 反 变 换、线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用。数字信号处理数字信号处理现在学习的是第4页，共69页直接计算直接计算DFT算法存在的问题算法存在的问题及改进途径及改进途径问题提出：问题提出：设有限长序列设有限长序列x(n),非零值长度为非零值长度为N,计算对计算对x(n)进行一次进行一次DFT运算，共运算，共需多大的运算工作量需多大的运算工作量?数字信号处理数字信号处理现在学习的是第5页，共69页1.1.比较比较DFTDFT与与IDFTIDFT

3、的运算量的运算量10)()()(NnknNDFTWnxkXnx101()()()NIDFTknNkX kx nX k WN 其中x(n)为复数，也为复数所以DFT与IDFT二者计算量相同。knNjknNeW2数字信号处理数字信号处理现在学习的是第6页，共69页2.2.以以DFTDFT为例复数运算量为例复数运算量计算一个X(k)(一个频率成分)值，运算量为例k=1则要进行:N次复数乘法 +(N-1)次复数加法所以，要完成整个DFT运算，其计算量为：N*N次复数相乘和次复数相乘和N*(N-1)次复数加法次复数加法1210)1()2()1()0()1(NNNNNWNxWxWxWxX数字信号处理数字信

4、号处理现在学习的是第7页，共69页3.一次复数乘法换算成实数运算量一个复数乘法包括4个实数乘法和个实数乘法和2个实数相法个实数相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)所以所有X(k)就要4N2次实数乘法运算,2N22N(N-1)N(4N-2)次实数加法运算.当N很大时,运算量将是惊人的,这样,难以做到实时处理。4次实数乘法2次实数加法数字信号处理数字信号处理现在学习的是第8页，共69页例子例1:当N=1024点时，直接计算DFT需要：N2=220=1048576次，即一百多万次的复乘运算这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求-迫切需

5、要改进DFT的计算方法，以减少总的运算次数。例2：石油勘探，24通道记录，每通道波形记录长度5秒，若每秒抽样500点/秒，每通道道总抽样点数=500*5=2500点24通道总抽样点数=24*2500=6万点DFT运算时间=N2=(60000)2=36*108次数字信号处理数字信号处理现在学习的是第9页，共69页5、FFT的计算工作量FFT算法对于N点DFT,仅需(N/2)log2N 次复数乘法运算和Nlog2N 次复数加法。数字信号处理数字信号处理现在学习的是第10页，共69页如果计算机的速度为平均每次复数乘需要510-6秒，每次复加需要110-6秒，用来计算N=1024点DFT,问1)直接计

6、算需要多少时间？2）用FFT算法计算需要多少时间？msNNTsNNNTNN84.35log10log2105FFT)229.610231024101024105)1(10105)12626626626计算需要时间为多少？用直接计算所需时间为：例例数字信号处理数字信号处理现在学习的是第11页，共69页6.FFT算法分类：算法分类：1.按抽取方法分：时间抽取法(DIT Decimation-In-Time);频率抽取法(DIF Decimation-In-Frequency)2.按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法3.其它方法：线性调频Z变换(Chr

7、ip-z法)数字信号处理数字信号处理现在学习的是第12页，共69页3.3.1 按时间抽取的DFT 1、的特性nkNWkNNkNNNNmnkmNnkNmnkmNnkNNknNknNNnkNknNNnkNnkNnkNjnkNWWWWWWWWWWWWWWeW)2(20/)()(-2,11)4,)3)2)1，特殊点：可约性：周期性：）对称性：（数字信号处理数字信号处理现在学习的是第13页，共69页例子1454)54(494WWWW1898178258WWWW利用以上特性,得到改进DFT直接算法的方法.数字信号处理数字信号处理现在学习的是第14页，共69页2、DFT的基本思想快速傅里叶变换(FFT)就是

8、在此特性基础上发展起来的：因合并与分解方法的不同产生了多种DFT的快速算法。数字信号处理数字信号处理现在学习的是第15页，共69页3.3.1 时域抽取法基时域抽取法基2FFT基本原理基本原理Decimation-in-Time(DIT)1、时域抽取算法原理 设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数2-N=2M，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M数字信号处理数字信号处理现在学习的是第16页，共69页设一序列设一序列x(n)的长度

9、为的长度为L=9,应加零补长为应加零补长为N=24=16 应补应补7个零值。个零值。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 nx(n)例子数字信号处理数字信号处理现在学习的是第17页，共69页2.算法步骤算法步骤设序列点数 N=2M，M为整数。若不满足，则补零1,1,0 ),()12(1,1,0 ),()2(DFT)()()(DFT)(222110NNNnknNrrxrxnrrxrxnnnxWnxkXnx为奇数时：为偶数时：，的奇偶分为两组作按将为：数字信号处理数字信号处理现在学习的是第18页，共69页)()()12()2()12()2()12()2()()

10、()(21101010210210)12(102101022222222kXWkXWrxWWrxWrxWWrxWrxWrxWnxWnxkXkNrrkkNrrkrrkNkNrrkNrkrNrrkNNnnNnnkNnnkNNNNNNNNN奇数偶数1021012222)12()()2()(NNNNrrkrrkWrxkXWrxkX其中：12,.1,0Nk现在学习的是第19页，共69页注)()()2()2()2(1212,.1,0),()()(120DFT2DFT,2)(),(2)(),(212)2(1212121kXWkXNkXWNkXNkXNNkNkkXWkXkXNkNNNrxrxNkXkXkNNk

11、NkN后半部分前半部分来计算点的可以用两个点的所以的长度也为，而的长度为数字信号处理数字信号处理kNNkNWW)2(其中现在学习的是第20页，共69页4.蝶形运算)1,1,0()()()2()1,1,0()()()(221221NkNNkNkkXWkXNkXkkXWkXkX，1 1 11-1-1)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW数字信号处理数字信号处理1 1 11-1-1)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW现在学习的是第21页，共69页(1)N/2点的DFT运算量:复乘

12、次数:复加次数:(2)两个N/2点的DFT运算量:复乘次数:复加次数:(3)N/2个蝶形运算的运算量:复乘次数:复加次数:复乘:复加:4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN总共运算量:*但是,N N点DFTDFT的复乘为N N2 2;复加N(N-1);N(N-1);与分解后相比可知,计算工作点差不多减少 一半。数字信号处理数字信号处理现在学习的是第22页，共69页例 8点FFT的算法首先可以分解为两个N/2=4N/2=4点的DFTDFT.具体方法如下:)7()3(),5()2(),3()1(),1()0()()();6()3(),4()

13、2(),2()1(),0()0()()()()()2()()()(3,2,1,0,)12()2()(22222111112121302/302/xxxxxxxxnxrxxxxxxxxxnxrxkXWkXNkXkXWkXkXkWrxWWrxkXkNkNrrkNkNrrkN分别对应的值分别对应现在学习的是第23页，共69页3821282118210821)3()3(3)2()2(2)1()1(1)0()0(0WXXXWXXXWXXXWXXX）（）（）（）（如：（1）N=8点分解成2个4点的DFT的信号流图 x(0)(0)x(2)(2)N/2N/2点点 x(4)(4)DFT DFT x(6)(6)x

14、(1)(1)x(3)(3)N/2N/2点点 x(5)(5)DFT DFT x(7)(7)X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)(0)X X2(1)(1)X X2(2)(2)X X2(3)(3)WN2NW1NW0-1-1-1X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)WN3现在学习的是第24页，共69页(2)N/2(4点)-N/4(2点)FFT由于N=2N=2 L,所以 N/2N/2仍为偶数,可以进一步把每个N/2N/2点的序列再按其奇偶部分分解为两个N/4

15、N/4的子序列。奇序列、偶序列、)3()6()1()2()2()4()0()0(:)(11111xxxxxxxxrx奇序列、偶序列、同理：)3()7()1()3()2()5()0()1(:)(22222xxxxxxxxrx现在学习的是第25页，共69页14,.1,0)()()()()4()()()()()()()()()()4()()()()()()()(,)()()()()()(42662/5252562/5242342/3142342/3122/104422/1033)12(2/104140243120411444NkkXWkXkXWkXNkXkXWkXkXWkXkXkXWkXkXWkXN

16、kXkXWkXkXWkXkXWlxkXWlxkXWlxWlxWrxkXkNkNkNkNkNkNkNkNlkNllkNlklNlNllkNrrkNNN3,2,1,0),()()4()()()(2121kkXWkXkXkXWkXkXkNkN现在学习的是第26页，共69页02NN02NN-1-1-1-1-1-1WWWWX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xN/4DFTN/4DFTN/4DFTN/4DFTX(0)X(2)X(6)X(1)X(5)X(3)X(7)X(4)WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X3

17、(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)1()1()3()0()0()2()1()1()1()0()0()0(42831408314283140831XWXXXWXXXWXXXWXX其中)1()1()1()0()0()2()1()1()1()0()0()0(62852608526285260852XWXXXWXXXWXXXWXX其中现在学习的是第27页，共69页(3)N/4（2点）-2个1点DFT，这里用到对称性这是一蝶形结代入上面流图可知：nkNnkNnnkWWWxWxWxWxXWxWxWxWxXWnxkXN2080812023080802023102)4

18、()0()4()0()1()4()0()4()0()0()()(最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。现在学习的是第28页，共69页1点DFTx(0)1点DFTx(4)X3(0)X3(1)08W)4()0()4()0()1()4()0()4()0()0(083083xxxWxXxxxWxX其中：2个1点的DFT蝶形流图-1现在学习的是第29页，共69页一个完整的按时间抽取的一个完整的按时间抽取的8点点FFT现在学习的是第30页，共69页6、对 N=2L点FFT流程图画法 1）输入倒位序，输出自然

19、序自然顺序n n 二进制n n n n n n 倒位序二进制n n n n n n 倒位顺序n n2 1 0 0 1 2 0 00 0 0 0 0 00 0 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0 1 11 1 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7

20、 数字信号处理数字信号处理现在学习的是第31页，共69页2）蝶形运算对N=2L点FFT，共需L级蝶形运算，每级有N/2个蝶形运算组成，蝶形运算两节点的距离:2L-1（L表示级数）每个蝶形运算有一次复乘和再次复加。如数字信号处理数字信号处理1 1 11-1-1)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW现在学习的是第32页，共69页3）WNr 的确定(仅给出方法)数字信号处理数字信号处理3J3,L2J3,L1J3,L0J3,L:21J2,L0J2L:2:23M8N2L12.2,1,0).3,2,1(L32102220210N0,12/2222

21、01L12L-ML-M111；个为第三级；，；个为第二级个为第一级级，共有如个，类型数为级的蝶形运算系数因子即第，级的系数因子为第NNNNJNNNJNJLJJJLJWWWWWWWWWWWWJWMLMMMML现在学习的是第33页，共69页-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxX(0)X(2)X(6)X(1)X(5)X(3)X(7)X(4)000，000001，100010，010011，110100，001101，101110，011111，111X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN0WN2WN0

22、WN2X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3-1-1-1-1WN0WN0WN0WN0数字信号处理数字信号处理现在学习的是第34页，共69页N=16X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)0000，00000001，10000010，01000011，11000100，00100101，10100110，01100111，11101000，00011001，10011010，01011011，11011100，00111101，10

23、111110，01111111，1111x(0)x(8)x(4)x(12)x(2)x(10)x(6)x(14)x(1)x(9)x(5)x(13)x(3)x(11)x(7)x(15)X1(0)X1(1)X1(2)X1(3)X1(4)X1(5)X1(6)X1(7)X2(0)X2(1)X2(2)X2(3)X2(4)X2(5)X2(6)X2(7)X3(0)X3(1)X3(2)X3(3)X4(0)X4(1)X4(2)X4(3)X5(0)X5(1)X5(2)X5(3)X6(0)X6(1)X6(2)X6(3)X7(0)X7(1)X8(0)X8(1)X9(0)X9(1)X10(0)X10(1)X11(0)X1

24、1(1)X12(0)X12(1)X13(0)X13(1)X14(0)X14(1)WN0WN1WN2WN3WN4WN5WN6WN7WN0WN2WN4WN6WN0WN2WN4WN6WN0WN4WN0WN4WN0WN4WN0WN4WN0WN0WN0WN0WN0WN0WN0WN0数字信号处理数字信号处理现在学习的是第35页，共69页6 6、FFTFFT运算量运算量由上述分析可知,N=8N=8需三级蝶形运算 N=2N=23 3=8,=8,由此可知,N=2N=2L L 共需L L级蝶形运算,而且每级都由N/2N/2个蝶形运算 组成,每个蝶形运算有一次复乘,两次复加。因此,N N点的FFTFFT的运算量为复

25、乘:m mF F=（N/2N/2）L=L=（N/N/2）loglog2 2 N N复加:a aF F=N L=N log=N L=N log2 2 N N 数字信号处理数字信号处理由于计算机的乘法运算比加法运算所 需的时间多得多，故以乘法作为比较基准.现在学习的是第36页，共69页222()2()loglog2FFmDFTNNNmFFTNN比较比较DFT 数字信号处理数字信号处理现在学习的是第37页，共69页3.3.2 按频率抽取的FFT 1、算法原理设序列点数N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：nkNnkNnknNnnkNNNnnkNnnk

26、NNnnkNWWNnxnxWNnxWnxWnxWnxWnxkXNNNNNN1010)(1012/1010222222)2()()2()()()()()(数字信号处理数字信号处理现在学习的是第38页，共69页1,.1,0)2()1()()()1(,110222NkWNnxnxkXWeWnkNnkkkNjNNNN，所以：由于：数字信号处理数字信号处理现在学习的是第39页，共69页2.N点DFT按k的奇偶分组可分为两个N/2的DFT 当k k为偶数,即 k=2rk=2r时,(-1)k=1；当k k为奇数,即 k=2r+1 k=2r+1 时(-1)k=-1 。这时 X(k)X(k)可分为两部分：数字信

27、号处理数字信号处理现在学习的是第40页，共69页1,1,0)2()()2()()12()2()()2()()2(210)12(1010210222222NnrnnNrnNnnrnnrNnrWWNnxnxWNnxnxrXkWNnxnxWNnxnxrXkNNNNNN为奇数时：，为偶数时：可见,上面两式均为N/2N/2的DFTDFT。数字信号处理数字信号处理现在学习的是第41页，共69页3.3.蝶形运算进行如下碟形运算：和)2()(Nnxnx-1-1)2()(Nnxnx1,1,02NnnNWNnxnx)2()(nNW)2(Nnx)(nx数字信号处理数字信号处理现在学习的是第42页，共69页4.N=8

28、时,按k的奇偶分解过程先蝶形运算，后DFT:再将N/2N/2点DFTDFT按k k的奇偶分解为两个N/4N/4点的DFTDFT,如此进行下去,直至分解为2 2点DFTDFT。-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3)0(x)1(x)5(x)4(x)3(x)2(x)7(x)6(x)0(X)2(X)6(X)1(X)3(X)5(X)7(X)4(XDFTN点2DFTN点2现在学习的是第43页，共69页例如 N=8N=8时频域抽取的FFTFFT流图如下：x x(0)X(0)(0)X(0)x(1)X(4)x(1)X(4)x(2)X(2)x(2

29、)X(2)x(3)X(6)x(3)X(6)x(4)X(1)x(4)X(1)x(5)X(5)x(5)X(5)x(6)X(3)x(6)X(3)x(7)X(7)x(7)X(7)-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 02 20 02 2-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0数字信号处理数字信号处理现在学习的是第44页，共69页5.时域抽取和频域抽取FFT的区别 1）基本蝶形不同时域:先复乘后加减频域:先减后复乘

30、2）运算量相同 3）都可原位运算4）两者基本蝶形互为转置2log2FNmN2logFaNN数字信号处理数字信号处理现在学习的是第45页，共69页3.3.3 关于FFT应用中的几个问题 3.3.3.1 用FFT计算IDFT比较两式可知,只要DFTDFT的每个系数 换成 ,最后再乘以常数1/1/N N就可以得到IDFTIDFT的快速算法-IFFT。nkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()()()(nkNWnkNW数字信号处理数字信号处理现在学习的是第46页，共69页)(1)(1)()(1)(1)(,101010*kXDFTNWkXNnxWkXNWkX

31、NnxBABAWWnkNNknkNNkNknkNnkNnkN因此：数字信号处理数字信号处理现在学习的是第47页，共69页这就是说,先将X(k)X(k)取共轭,即将X(k)X(k)的虚部乘-1-1，直接利用FFTFFT程序计算DFT；然后再取一次共轭；最后再乘1/1/N,N,即得 x(n)x(n)。所以FFT,IFFTFFT,IFFT可用一个子程序。共轭FFT共轭乘1/N()X k*()Xk()x n直接调用FFT子程序计算IFFT的方法：数字信号处理数字信号处理现在学习的是第48页，共69页3.3.3.2 线性卷积的FFT算法21102111221)()()(1L1,010),()(1,010

32、),()(NNmnxmhnyNNLnNNnnhnhLnNNnnxnxFFTNm需要运算量直接计算线性卷积满足性卷积法：以循环卷积代替线数字信号处理数字信号处理现在学习的是第49页，共69页LnhLkYIFFTnyLkHkXkYLnxFFTkXLnhFFTkHNNnhnxLLLL222221mlogL)(log2;)()(.5)()()(.4log2)()(.3log2,)()(.2;12L)(),(.1总复数乘法的次数，不需要计算，数，第一步实际上通常是预先设计好的参因为复数乘法的次数，求；复数乘法的次数，求；复数乘法的次数，求复数乘法的次数，求点补零点，至少为将现在学习的是第50页，共69页

33、时速度提高极大当性就越大。越大，循环卷积的优越即两，时当讨论：法计算的运算量比较直接计算和64N3log2)1(log221,)1logFFT212121121212211NNNNkNNNLNNLLNNkNLL数字信号处理数字信号处理现在学习的是第51页，共69页重叠保留法重叠相加法需采用分段卷积，很不经济必须补很多对积时，解长序列和短序列的卷充分发挥，这是因为求得循环卷积的优点不能直接卷积的运算量，使运算量已超过下降，说明循环卷各的增加时，当0)(log1log1N)2221222212211222nhkNNNNNNkNNNLNNN数字信号处理数字信号处理现在学习的是第52页，共69页利用利

34、用FFTFFT计算线性卷积计算线性卷积 MATLAB程序程序N=1024x=2 3 1 4 5 ones(1,N);h=2 1 7 4 5 7 2 3 ones(1,N);Lenx=length(x);%求序列求序列x的长度的长度Lenh=length(h);%求序列求序列h的长度的长度N=Lenx+Lenh-1;t=cputime(%或或tic)Xk=fft(x,N);%计算计算x序列的序列的DFTHk=fft(h,N);%计算计算h序列的序列的DFTYk=Xk.*Hk;y=ifft(Yk)%求求IDFTt1=cputime-t（或或toc）stem(y);xlabel(n);数字信号处理数

35、字信号处理现在学习的是第53页，共69页数字信号处理数字信号处理现在学习的是第54页，共69页直接线性卷积 MATLAB程序%x,nx为第一个信号%h,nh为第二个信号%conv(x,h)可以实现两个有限长度序列的卷积 x=2 3 1 4 5;h=2 1 7 4 5 7 2 3;ny2=length(x)+length(h)-1;t=cputimeny=0:ny2;y=conv(x,h);T1=cputime-t stem(y)数字信号处理数字信号处理现在学习的是第55页，共69页数字信号处理数字信号处理现在学习的是第56页，共69页1)()()()()()()()()()()()(,0.1,

36、0,1N)1(N),()()(NN)(1222122NNnynhnxnynynynxnhnxnynxnxniininxnxNnhnxiiiiiiiiii的长度为其它等数量级的长度与点，分段，每段对长序列重叠相加法数字信号处理数字信号处理现在学习的是第57页，共69页N1-1L-1h(n)0 x(n)0N22 N23 N2N2-1L-1x0(n)2 N2-1L+N2-1N2x1(n)3 N2-12 N22 N2+L-1x2(n)现在学习的是第58页，共69页*L-1N2LN2-1L2N2-12N2数字信号处理数字信号处理现在学习的是第59页，共69页重叠保留法 分段序列中补零的部分不是补零，而是

37、保留原来的输入序列，于是重叠了输入信号段，省略掉输出段的重叠相加。数字信号处理数字信号处理现在学习的是第60页，共69页舍弃yi(n)的前M-1个点，再将yi(n)顺次连接，即得y(n)。(+1)01()0ix ni NMnNx nn其它分段002()(1)1nMx nx nMMn 右移序列卷积()()*()()()iiiy nx nh nx nh nN*数字信号处理数字信号处理现在学习的是第61页，共69页现在学习的是第62页，共69页现在学习的是第63页，共69页 由于保留法补的不是零值点，而是前段保留下来的（M-1)点有x(n)值，因而每段循环卷积的结果的前（M-1）个点的值不等于线性卷

38、积的值必须舍去。把相临输出段的序列衔接起来就构成了最后正确输出。说明现在学习的是第64页，共69页3.3.4 用FFT计算相关函数 若L点x(n)，M点y(n)，计算线性相关：数字信号处理数字信号处理1010)()()()()(NnNnxynynxnynxrx(n)及y(n)的卷积公式)()()()()(10mymxnynmxmfNn现在学习的是第65页，共69页相关和卷积的时域关系)()()()()()()(1010mymxnynmxnymnxmrNnNnxy现在学习的是第66页，共69页1()()X kFFT x n）()()Y kFFT y n2）*3()()()xyRkX kYk）4(

39、)()xyxyrnIFFT Rk）*11*0011()()()NNnknkxyxyNxyNkkrnRk WRk WNN数字信号处理数字信号处理FFT计算相关计算相关现在学习的是第67页，共69页FFT计算相关程序计算相关程序 x=1 3-1 1 2 3 3 1;y=2 1-1 1 2 0-1 3;k=length(x);xk=fft(x,2*k);yk=fft(y,2*k);rm=real(ifft(conj(xk).*yk);rm=rm(k+2:2*k)rm(1:k);m=(-k+1):(k-1);stem(m,rm)xlabel(m);ylabel(幅度幅度);现在学习的是第68页，共69页幅度现在学习的是第69页，共69页