1、测试信号分析与处理测试信号分析与处理课程课程 第四章第四章 离散傅里叶变换及其离散傅里叶变换及其快速算法快速算法 第一节第一节 序列的傅里叶变换（序列的傅里叶变换（DTFTDTFT）第二节第二节 离散傅里叶级数（离散傅里叶级数（DFSDFS）第三节第三节 离散傅里叶变换（离散傅里叶变换（DFTDFT）第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质测试信号分析与处理测试信号分析与处理课程课程第五节第五节 快速傅里叶变换（快速傅里叶变换（FFTFFT）第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）第七节第七节 实序列的实序列的FFTFFT高效算法高效算法第八节第八
2、节 用用FFTFFT计算线卷积和相关运算计算线卷积和相关运算第九节第九节 MATLABMATLAB中用于中用于FFTFFT计算的函数简介计算的函数简介第一节第一节 序列的傅里叶变换序列的傅里叶变换一、定义一、定义已知序列 的Z变换为如X(Z)在单位圆上是收敛的，则将在单位圆上的Z变换定义为序列的傅里叶变换序列的傅里叶变换，即 由于序列的傅里叶变换定义为单位圆上的Z变换，因此其同Z变换具有相同的性质。()x n()()nnX zx n z()()()jjjnz enX zX ex n 第一节第一节 序列的傅里叶变换序列的傅里叶变换二、物理意义与存在条件二、物理意义与存在条件连续信号的傅里叶反变换
3、为Z反变换的围线积分公式为将积分围线c取在单位圆上，则有11()()2ncx nX z zdzj 1()()2j tx tXed11()()()()22jjjnjjjjnz ex nX eeed eX 第一节第一节 序列的傅里叶变换序列的傅里叶变换两者相比v前者是连续信号不同频率的复指数分量，前者是连续信号不同频率的复指数分量，后者是序列不同频率的复指数分量；后者是序列不同频率的复指数分量；v两者都是频域中频率的概念，两者都是频域中频率的概念，表示模拟角频率，表示模拟角频率，表示数字角频率；表示数字角频率；v前者是连续信号在时域的表示，可以分解前者是连续信号在时域的表示，可以分解为一系列不同频
4、率的复指数分量的叠加，为一系列不同频率的复指数分量的叠加，分量的复振幅为分量的复振幅为 ，后者是序列在时，后者是序列在时域的表示，可以分解为一系列不同数字角域的表示，可以分解为一系列不同数字角频率分量的叠加，分量的复振幅频率分量的叠加，分量的复振幅为为 。j tjnee()()x tx n()Xd()jX 第一节第一节 序列的傅里叶变换序列的傅里叶变换v前者有连续信号频谱密度的意义，是频前者有连续信号频谱密度的意义，是频谱的概念，后者是序列的傅里叶变换，谱的概念，后者是序列的傅里叶变换，可以看作是序列的频谱。可以看作是序列的频谱。v是模拟角频率，变化范围是没有限制是模拟角频率，变化范围是没有限
5、制的，高频部分可以趋于的，高频部分可以趋于；而数字角频；而数字角频率率的变化虽然是连续的，但变化范围的变化虽然是连续的，但变化范围限制在限制在内内()()jXX e序列的傅里叶变换对-1F()()()1F()()()2jjnnjjjnx nX ex n eX ex nX 第一节第一节 序列的傅里叶变换序列的傅里叶变换 序列的傅里叶变换既然定义为单位圆上的Z变换，所以它的存在条件是序列的Z变换必须在单位圆上是收敛的，即 上式说明序列的傅里叶变换存在的条件是序列必须绝对可和。11()()nznzX zx n z()nx n 第一节第一节 序列的傅里叶变换序列的傅里叶变换 三、特点与应用三、特点与应
6、用v非周期序列的傅里叶变换（频谱）的特点在于它是 的连续周期函数，其周期为 。v序列x(n)与其傅里叶变换两者正好是互为傅里叶级数的变换关系。第一节第一节 序列的傅里叶变换序列的傅里叶变换 序列可以表示为复指数序列分量的叠加，适用于叠加原理在线性时不变系统的分析。这种系统对复指数序列的响应完全由系统的频率响应 确定。一个线性时不变系统对于输入 的输出响应，就是对它的每个复指数序列分量的响应的叠加，则输出响应 应为则输出的傅里叶变换为()jH e()x n()y n)1()()()2jjy nH eX ed()()()jjjY eX eH 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）一
7、、傅里叶变换在时域和频域中的对称规律一、傅里叶变换在时域和频域中的对称规律a)时域上的非周期性对应频域上的连续性 第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）b)时域上的周期性将产生频域的离散性。第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）c)时域上的离散性将产生频谱的周期性。第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）d)时域上的离散周期信号，其频谱是周期离散的。第二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）v一个域中（时域或频域）是连续的，对应另一个域中（频域或时域）是非周期的。v一个域中（时域或频域）是离散的，对应另一个域中（频域或时域）是周期的。第
8、二节第二节 离散傅里叶级数（离散傅里叶级数（DFS）二、离散傅里叶级数二、离散傅里叶级数v离散周期信号的频谱，即离散傅里叶级数(DFS)。v离散傅里叶级数的变换对表达式其中 10()()()NnkpppNnXkDFS xnxn W101()()()NnkpppNkxnIDFS XkXk WNNjNeW第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）一、离散傅里叶变换一、离散傅里叶变换DFT定义式定义式v离散傅里叶变换就是对有限长序列进行傅里叶变换的表示式。v主值序列：对于一个周期序列 ，定义它的第一个周期的有限长序列值为此周期序列的主值序列，用表示 为 主值序列也可以表示为周期序列和一个
9、矩形序列相乘的结果，即()pxn)(nx(),0-1()0 ,pxnnNx n其他()()()pNx nxn R第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）周期序列 也可以看作是长度为N的有限长序列以N为周期延拓而形成了。有了主值序列的概念，再来考察DFS的定义式，只需用主值序列 ，即可求出并完全地表达周期无限长序列 ，这样就得到了任意有限长序列的离散傅立叶变换对()pxn()()prxnx nrN)(kX)(nx()pXk()pxn10)()()(NnnkNWnxnxDFTkX101()()()NnkNkx nIDFT X kX k WN10Nk10N第三节第三节 离散傅里叶变换（
10、离散傅里叶变换（DFT）v矩阵形式或 )1()1()0()1()1()0(1)(1)-(N1)-(N21)-(N1011)-(N121100000NxxxWWWWWWWWWWWWNXXXN)1()1()0(1)1()1()0(1)(1)-(N-1)-(N2-1)-(N1-011)-(N-12-11-00000NXXXWWWWWWWWWWWWNNxxxNn nk kX X(k k)=W W x x(n n)1N-n nk kx x(n n)=W WX X(k k)第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）例例4-14-1 用矩阵表示式求矩形序列 的DFT，再由所得 经IDFT反求 ，
11、验证所求结果的正确性。解：，故 再由 反变换求)()(4nRnx)(kX)(nx4NjeeWjNjN42200041111j-1-j 11-1 1-1j 1-j-1 1 1 1 1)3()2()1()0()3()2()1()0(9630642032100000 xxxxWWWWWWWWWWWWWWWWXXXX)(kX)(第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）11110004j 1-j-11-1 1-1j -1 -j 1 1 1 1 141)3()2()1()0(13()2()1()0(9-6-3-06-4-2-03-2-1-00000XXXXWWWWWWWWWWWWWWWWN第
12、三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）二、二、DFT的物理意义的物理意义设一有限长序列 的长度为N点，其Z变换为因序列为有限长，满足绝对可和的条件，其Z变换的收敛域必定包含单位圆在内，则序列的傅里叶变换，即单位圆上的Z变换存在，且为)(nx10)()(NnnznxzX10)()()(NnjnezenxzXzX第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）以 为间隔，把单位圆均匀等分为N个点，则在第k个等分点，即 点上的值为故有限长序列的离散傅里叶变换DFT是这一序列频谱（序列傅里叶变换）的抽样值。12/N12/kkN2120()()()()NjknjNknNX ex n
13、eDFT x nX k22()()()jkNjz ekNX kX eX 第三节第三节 离散傅里叶变换（离散傅里叶变换（DFT）v有限长序列的DFT就是序列在单位圆上的Z变换（即有限长序列的傅里叶变换或频谱）以 为间隔的抽样值 12/N第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v线性特性线性特性 若 ，则式中a、b为任意常数。如果两个序列的长度不相等，以最长的序列为基准，对短序列要补零，使序列长度相等，才能进行线性相加，经过补零的序列频谱会变密，但不影响问题的性质。)()(nxDFTkX)()(nyDFTkY)()()()(kbYkaXnbynaxDFT第四节第四节 离散傅里叶变换的
14、性质离散傅里叶变换的性质v时移特性时移特性 1）圆周移位序列将长度为N的序列 进行周期延拓，周期为N，构成周期序列 ，然后对周期序列 作m位平行移位处理，得移位序列 ，再取其主值序列（与一矩形序列 相乘），得到的 就是圆周移位序列。()pxnm)(nx()pxn()pxn)(nRN()()pNxnm R第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质 第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质2）时移定理若 则 时移定理表明，序列在时域上圆周移位，频域上将产生附加相移，对上式进行反变换可以得到 DFT()()x nX kDFT()()()mkpNNxnm RnWX kIDFT
15、()()()mkNpNWX kxnm R第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v频移特性频移特性 若则 上述特性说明，若序列在时域上乘以复指数序列 ，则在频域上 将圆周移 位，这可以看作调制信号的频谱搬移，因而又称为“调制定理”。DFT()()()nlNpNx n WXkl RkIDFT()()()nlpNNXkl Rkx n WDFT()()x nX knlNW)(kX第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v圆周卷积特性 1）时域圆周卷积 若对N点序列有 ，则 2）频域圆卷积 若1p0()()()()()()()NNmy nIDFT Y kx nh nx m
16、h nm Rn)()()(nhnxny101()()()()()NpNlY kDFT y nX l Hkl RkN()DFT()X kx n()DFT()H kh n)()()(kHkXkY第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v实数序列奇偶性（对称性）设x(n)是实序列，则X(k)的幅度和相位分别为他们分别为k的偶函数和奇函数，并分别具有半周期偶对称和奇对称的特点。()DFT()X kx n2101100()()22()cos()sin()()NjnkNnNNRInnX kx n ex nnkjx nnkXkjXkNN22()()()RIX kXkXk()arg()arcta
17、n()IRXkX kX第四节第四节 离散傅里叶变换的性质离散傅里叶变换的性质v帕斯瓦尔定理若 ，则 式左端代表离散信号在时域中的能量，右端代表在频域中的能量，该式表明变换过程中能量是守恒的。()DFT()X kx n2112001()()NNnkx nX kN第五节第五节 快速傅里叶变换快速傅里叶变换一、一、DFT运算的特点运算的特点1.DFT直接运算的工作量 N点序列x(n)的DFT为 按定义计算DFT时，需作 次复数乘和 次复数加。由于直接计算量非常大，不可能实现信号的实时处理，因此必须改进DFT的算法。112/00()()()NNjnk NnkNnnX kx n ex n W0,1,2,
18、1kN2NNN)1(第五节第五节 快速傅里叶变换快速傅里叶变换2.DFT运算特点 1)的周期性2)的对称性 因为 故nkNW)()()(mNklNnNmNknNklNnNnkNWWWWnkNW2221 NjNNNWe nkNNNnkNNnkNWWWW 2)2(第五节第五节 快速傅里叶变换快速傅里叶变换v3)的可约性nkNWm/nkm/NmnkmNnkNWWW 第五节第五节 快速傅里叶变换快速傅里叶变换利用上述结果，如对应于N=4的矩阵W可以简化为 上式右端的矩阵中的元素有许多是相等的，计算量明显减少。由原来的16个元素变成只有两个独立元素需要计算。10100000101000009630642
19、032100000 WW-W-W W-WW-W W-W-WW W W WW W W WW W W WW W W WW W W WW第五节第五节 快速傅里叶变换快速傅里叶变换二、基二、基2时析型时析型FFT算法（时间抽取法）算法（时间抽取法）1.1.算法原理算法原理 对长度为 （L为正整数，若原序列的长度不满足此条件，则可用零补足）的序列x(n),按序列各项序号的奇偶将序列分成两个子序列（大点数化为小点数），有偶序号序列 奇序号序列其中 ，两序列的长度均为N/2。且其DFT分别为LN2)2()(rxry)12()(rxrz12,2,1,0N第五节第五节 快速傅里叶变换快速傅里叶变换上式中，右边即
20、为x(n)的前一半DFT值kNNkNNNrrkNNrNWNxWxWxWrxerykYrrkj)2(2012021202)2()2()0()2()()(2)1()3()1()12()()()1(3120)12(12022kNNkNkNkNNrkNkrNNrNWNxWxWxWWWrxerzkZrrkjkNNkNkNNkNWNxWxWxWxkZWkY)1(20)1()2()1()0()()()()()(kZWkYkXkN12,2,1,0N第五节第五节 快速傅里叶变换快速傅里叶变换对于另外N/2个点的DFT,即 的 ，可表示为根据周期性，有由对称性，有 1/2,/2 1,1kNNN)(1kX)2()(
21、1NkXkX)12(,2,1,0Nk)()2(kYNkY)()2(kZNkZkNNkNWW2)()()2()2()2(2kZWkYNkZWNkYNkXKNNKN12,2,1,0N第五节第五节 快速傅里叶变换快速傅里叶变换 x(n)的DFT最后结果 x(n)的DFT可由奇偶对分序列的DFT合成而获得。该计算关系可用右图来表示。由于图形酷似蝴蝶，所以称之为蝶形图（或蝶形单元）。上式也因而称为蝶形算法。)()()2()()()(kZWkYNkXkZWkYkXkNkN第五节第五节 快速傅里叶变换快速傅里叶变换2.2.算法的具体实现算法的具体实现 对于长度为 的序列逐次奇偶对分，则最后一定能得到N个单项
22、序列（序列的长度为1），而单项序列的DFT就是其本身。因此根据蝶形图，计算N项序列的DFT，只需要按照蝶形算法逐次合成，即由N个1点长序列的DFT合成N/2个2点长序列的DFT，再由N/2个2点长序列的DFT合成N/4个4点长序列的DFT，如此继续下去，最后由两个N/2点长序列的DFT合成N点长序列的DFT。LN第五节第五节 快速傅里叶变换快速傅里叶变换第五节第五节 快速傅里叶变换快速傅里叶变换当序列的长度为 时，根据基2时析型FFT的算法，可画出如下蝶形图，求出序列的DFT值。823N第五节第五节 快速傅里叶变换快速傅里叶变换3.3.流程图规律流程图规律1)蝶形图参数蝶群序号蝶群序号蝶距（序
23、号蝶距（序号差）差）蝶群宽（点蝶群宽（点数）数）蝶群数蝶群数第一级（第一级（2 2点点DFTDFT）第第i i级（级（点点DFT)DFT)第第L L级（级（点点DFT)DFT)021212N2i2i12i2iN12LL221LNL第五节第五节 快速傅里叶变换快速傅里叶变换2）每个蝶形单元的运算，都包括乘 ，并与相应的DFT结果加减各一次 3）同一级中，的分布规律相同第一级（2点DFT）：第二级（4点DFT）：；第 i级(点DFT):;.;kNWkNW2i02iW12iW1221iiW02W14W04W第五节第五节 快速傅里叶变换快速傅里叶变换)7()6()5()4()3()2()1()0(xx
24、xxxxxx7654321000000101001110010111011111101110100111001010000073516240)7()3()5()1()6()2()4()0(xxxxxxxx序列输入序列输入的的自然顺序自然顺序十进制十进制二进制码二进制码码位倒码位倒置结果置结果（二进（二进制码）制码）乱序十乱序十进制进制序列乱序列乱序的输序的输入顺序入顺序4）输入重排 第五节第五节 快速傅里叶变换快速傅里叶变换4.4.运算量比较运算量比较N（）点的FFT总运算量为复数乘复数加 利用基2时析型FFT求序列的DFT同直接计算序列的DFT的复数乘运算次数之比为LN2NNMc2log2N
25、NNNAc22loglog22222(log)/log22NRNNNN第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）利用利用FFTFFT的程序求的程序求IFFTIFFT的方法的方法 先对DFT和IDFT两者的定义式进行比较，二者没有本质上的区别，可以利用FFT流图（蝶形图）来计算IFFT。1010)(1)()()()()(NknkNNnnkNWkXNnxkXIDFTWnxkXnxDFT第六节第六节 IDFTIDFT的快速算法（的快速算法（IFFTIFFT）对DFT的反变换取共轭，有与DFT的正变换式比较可知，完全可以利用FFT的计算程序，只需将 作为输入序列，并将最后
26、结果取共轭，再除以N就得到了)(1)(1)(10*10*nkNNknkNNkWkXNWkXNnx(0,1,1)nN)(*kX)(第七节第七节 实序列的实序列的FFT高效算法高效算法一、同时计算两组实序列的一、同时计算两组实序列的DFTDFT 设有两组长度均为N的实序列 和 ，构成新序列 ，根据DFT定义因为 ，有因此)(nx)(ny)()()(njynxnz111000()()()()()(),(0,1,2,1)NNNnknknkNNNnnnZ kz n Wx n Wjy n WX kjY kkN*()()X NkXk*()()Y NkYk*()()()()()Z NkX NkjY NkXkj
27、Yk*()()()ZNkX kjY 第七节第七节 实序列的实序列的FFT高效算法高效算法解得由此说明用FFT子程序求得 的DFT后，和 的DFT（、）可由 的DFT()分离出来。*1()()()21()()(),(0,1,2,1)2X kZ kZNkY kZ kZNkkNj)()()(njynxnz)(nx)(ny)(kX)(kY)(nz)(kZ第七节第七节 实序列的实序列的FFT高效算法高效算法二、用二、用N N点序列的点序列的DFTDFT结果获得结果获得2N2N点长实序列的点长实序列的DFTDFT结果结果 将一个2N点的实序列 按奇偶顺序对分成两个序列再将 和 组合成N点的复序列可用N点F
28、FT程序求出y(n)的DFT结果 ，然后从 中分离出实数序列 和 的DFT结果)(nx12()(2),0,1,2,1()(21)x nxnnNx nxn)()()(21njxnxny)(1nx)(2nx0,1,2,1nN)1,2,1,0)(NkkY)(kY)(1nx)(第七节第七节 实序列的实序列的FFT高效算法高效算法 由于 和 是 的奇偶对分序列，所以 的DFT可用蝶形算法合成*1*21()()()2,0,1,2,11()()()2X kY kYNkkNXkY kYNkj)(1nx)(2nx)(nx)(nx122122()()(),0,1,2,1()()()kNkNX kX kWXkkNX
29、 NkX kWXv本节将讨论两有限长序列的圆卷积与线卷积的等本节将讨论两有限长序列的圆卷积与线卷积的等价条件，从而将圆卷积的快速算法应用于线性卷价条件，从而将圆卷积的快速算法应用于线性卷积和相关的快速算法中。积和相关的快速算法中。第八节第八节 用用FFT计算线卷积和相关运算计算线卷积和相关运算主要内容主要内容圆卷积的计算方法一圆卷积与线卷积的关系二用FFT计算有限长序列的线卷积三分段快速卷积重叠相加法四离散时间序列的相关运算五一、圆卷积的计算方法一、圆卷积的计算方法v两个长度均为两个长度均为 （如长度不等，将短序列补零至（如长度不等，将短序列补零至等长）的有限长序列等长）的有限长序列 、，其圆
30、卷积，其圆卷积 定义为定义为 N)(nx)(nh)(ny110()()()()()()()NNpNpNmm py nx m h nm Rnh m xnm Rn1010)()()()()(NmNNmNmnxmhmnhmxny或(5-13)(5-14)其主要计算方法有下面几种。一、圆卷积的计算方法一、圆卷积的计算方法v1 1公式法（解析法）公式法（解析法）直接利用圆卷积的上述定义式来求解，如下例所直接利用圆卷积的上述定义式来求解，如下例所述。述。例例5-1 5-1 设设 ，计算，计算5 5点点长圆卷积长圆卷积 。解：解：为为4 4点长序列，在其尾部补零使其成为点长序列，在其尾部补零使其成为5 5点
31、长点长序列序列 ，然后进行圆卷积。，然后进行圆卷积。根据卷积定义式，根据卷积定义式，5 5点长序列的圆卷积为点长序列的圆卷积为5,4,3,2,1)(nx9,8,7,6)(nh)(ny)(nh0,9,8,7,6)(nh450()()(),(0,1,2,3,4)my nx m h 一、圆卷积的计算方法一、圆卷积的计算方法v则 时0n45055555(0)()(0)(0)(0)(1)(1)(2)(2)(3)(3)(4)(4)(0)(0)(1)(4)(2)(3)(3)(2)(4)(1)1 6 2 0 3 9 4 8 5 7 100myx m hmxhxhxhxhxhxhxhxhxhxh v则 时1n4
32、5055555(1)()(1)(0)(1)(1)(0)(2)(1)(3)(2)(4)(3)(0)(1)(1)(0)(2)(4)(3)(3)(4)(2)1 72 63 04 95 895myx m hmxhxhxhxhxhxhxhxhxhxh 一、圆卷积的计算方法一、圆卷积的计算方法v同理同理 ；。因此，因此，。85)2(y70)3(y100)4(y100,70,85,95,100)(一、圆卷积的计算方法一、圆卷积的计算方法v2 2图形法图形法v先变量置换，然后保持其中的一个序列不动，将先变量置换，然后保持其中的一个序列不动，将另外一个序列进行反折、圆移位，最后将两个序另外一个序列进行反折、圆移
33、位，最后将两个序列对应的元素相乘、求和。列对应的元素相乘、求和。一、圆卷积的计算方法一、圆卷积的计算方法v 由于圆移位的特点，还可以利用由于圆移位的特点，还可以利用同心圆法同心圆法求圆卷积，如图求圆卷积，如图5-85-8所示。将所示。将 、分别分别分布在两个同心圆上，内圆按顺时针方向分布在两个同心圆上，内圆按顺时针方向刻度刻度 ，外圈按逆时针方向刻度，外圈按逆时针方向刻度 ，并，并 使使 与与 对齐。然后将两个圆上的对对齐。然后将两个圆上的对应值相乘并相加，则得到应值相乘并相加，则得到 。再将外圆。再将外圆按顺时针方向旋转一位，对应值相乘并相按顺时针方向旋转一位，对应值相乘并相加，得到加，得到
34、 ，如此下去，直到求，如此下去，直到求出出 。)(nx)(nh)(nx)(nh)(nx)(nh)0(y)1(y)1(N一、圆卷积的计算方法一、圆卷积的计算方法 图5-8 用同心圆作图求圆卷积 一、圆卷积的计算方法一、圆卷积的计算方法v3 3矩阵法矩阵法v利用矩阵相乘来计算圆卷积。根据圆卷积的定义，利用矩阵相乘来计算圆卷积。根据圆卷积的定义，式（式（5-145-14）可用矩阵表示为）可用矩阵表示为 即即HXY)1()2()1()0()0()3()2()1()3()0()1()2()2()1()0()1()1()2()1()0()1()2()1()0(NxxxxhNhNhNhhhhhhNhhhhN
35、hNhhNyyyy（5-15）一、圆卷积的计算方法一、圆卷积的计算方法v注意注意:式（式（5-155-15）表示序列）表示序列 不动，序列不动，序列 对对 进行了求模运算。为循环矩阵，其元素进行了求模运算。为循环矩阵，其元素排列是有规律的，第一行表示的是原点（排列是有规律的，第一行表示的是原点（）不动时，序列的反折（倒序）；接下来的各行分不动时，序列的反折（倒序）；接下来的各行分别是上一行序列的循环右移。别是上一行序列的循环右移。)(nx)(nx)(nh()N一、圆卷积的计算方法一、圆卷积的计算方法v4 4时域圆卷积定理法时域圆卷积定理法v利用利用DFTDFT的一个重要性质的一个重要性质时域圆
36、卷积定理来计时域圆卷积定理来计算圆卷积。若算圆卷积。若 ，则则)()(nxDFTkX)()(nhDFTkH)()(IDFT()(IDFT)(kHkXkY二、二、圆卷积与线卷积的关系圆卷积与线卷积的关系 v线卷积具有明确的物理意义，直接计算比较复杂。线卷积具有明确的物理意义，直接计算比较复杂。对于两个有限长序列求线卷积能否用圆卷积来代对于两个有限长序列求线卷积能否用圆卷积来代替，即采用替，即采用FFTFFT计算线卷积而使两者结果又完全相计算线卷积而使两者结果又完全相同呢？答案是肯定的，但需要满足一个条件：就同呢？答案是肯定的，但需要满足一个条件：就是将进行线卷积的两序列的长度（设两序列的点是将进
37、行线卷积的两序列的长度（设两序列的点数分别为数分别为 ）均通过补零的办法，加长）均通过补零的办法，加长至至 ，然后再进行，然后再进行N N点的圆卷积，则点的圆卷积，则圆卷积的结果与线卷积的结果相同。圆卷积的结果与线卷积的结果相同。21NN 和121NNN二、二、圆卷积与线卷积的关系圆卷积与线卷积的关系v设设 分别由点通过补零，加长至分别由点通过补零，加长至N N点，其线点，其线卷积为，可表示为卷积为，可表示为 计算结果的长度要多出一些零值，但非零值长度计算结果的长度要多出一些零值，但非零值长度仍为仍为 点。点。其圆卷积为其圆卷积为 ，可表示为，可表示为)(),(nhnx101)()()()()
38、(Nmmnhmxnhnxny121 NN)(2ny)()()()()()()()()(10102nRmnxmhnRmnhmxnhnxnyNNmpNN二、二、圆卷积与线卷积的关系圆卷积与线卷积的关系v而而 可得可得 （5-165-16）式中，下标式中，下标p p表示序列的周期化；表示序列的周期化；是指对线是指对线卷积卷积 进行周期为进行周期为N N的延拓后得到的周期序的延拓后得到的周期序 列；列；两序列的圆卷积的结果，是两序列的圆卷积的结果，是的主值序列。的主值序列。rprNmNmrNmpnyrNnymrNnhmxmrNnhmxmnhmx)()()()()()()()(11101010)()()
39、(12nRnynyNp)(1nyp)(1ny)()()(1p2nRnynyN二、二、圆卷积与线卷积的关系圆卷积与线卷积的关系v上述过程说明上述过程说明:加长至加长至N N点长的点长的 、两序列的两序列的圆卷积圆卷积 与与 线卷积作周期延拓所得到的序线卷积作周期延拓所得到的序列列 的主值序列相同。在这个条件下（两序列的主值序列相同。在这个条件下（两序列均加长至均加长至N N点），就可以通过计算序列的圆卷积来点），就可以通过计算序列的圆卷积来求解线卷积。从式（求解线卷积。从式（5-165-16）的推导过程还可以看）的推导过程还可以看出，如果两序列不加长至出，如果两序列不加长至N N，其线卷积的周期
40、延拓，其线卷积的周期延拓序列将发生重叠或混叠现象（因为序列将发生重叠或混叠现象（因为 线卷积长线卷积长度为度为 ），相应计算出的圆卷积也将产生），相应计算出的圆卷积也将产生失真，圆卷积的主值序列和线卷积就不相同。失真，圆卷积的主值序列和线卷积就不相同。()x n()h n)(2ny)(1ny)(1nyp121 NN)(三、三、用用FFT计算有限长序列的线卷积计算有限长序列的线卷积v 根据上述圆卷积与线卷积的关系，可以得出用根据上述圆卷积与线卷积的关系，可以得出用FFTFFT求解两求解两序列线卷积的原理框图，如图序列线卷积的原理框图，如图5-9 5-9 所示。其计算的所示。其计算的具体步具体步骤
41、如下骤如下v 1 1）若两序列）若两序列 、的长度为的长度为N N，将序列加长至，将序列加长至2N2N1 1，并应修正为，并应修正为2 2的幂次（基的幂次（基2 2算法）；算法）；v 2 2）计算）计算 、；v 3 3）计算）计算 ；v 4 4）计算）计算 。)(nx)(nh)(FFT)(nxkX)(FFT)(nhkH)()()(kHkXkY)(IFFT)(kYny图5-9 用FFT求线性卷积三、三、用用FFT计算有限长序列的线卷积计算有限长序列的线卷积v在在MATLABMATLAB中直接实现线卷积计算的函数有中直接实现线卷积计算的函数有 conv,conv,conv2,convnconv2,
42、convn。其中。其中conv2conv2和和 convnconvn分别用于分别用于2 2维、维、n n维的卷积运算。维的卷积运算。convconv则用于向量卷积与多项式乘则用于向量卷积与多项式乘的计算，调用的格式为的计算，调用的格式为c cconvconv（a a，b b）。式中，）。式中，a a、b b表示两个序列，表示两个序列，c ca a*b b。在。在MATLABMATLAB中，序列中，序列可用向量来表示，若向量可用向量来表示，若向量a a的长度为的长度为nana，向量，向量b b的的长度为长度为nbnb，则向量，则向量c c的长度为的长度为nananbnb1 1。四、分段快速卷积四
43、、分段快速卷积重叠相加法重叠相加法v分段快速卷积的方法分段快速卷积的方法:将长序列分成若干小段，每将长序列分成若干小段，每小段分别与短序列作卷积运算，然后将所有的分小段分别与短序列作卷积运算，然后将所有的分段卷积结果相叠加，就是线卷积的最后结果，这段卷积结果相叠加，就是线卷积的最后结果，这种方法又称为重叠相加法。种方法又称为重叠相加法。四、分段快速卷积四、分段快速卷积重叠相加法重叠相加法v设设 的长度为的长度为M M，为一长序列，将为一长序列，将 进行分进行分段，每段的长度为段，每段的长度为 ，将每一段分别与，将每一段分别与 进行进行线卷积，然后将结果重叠相加，如图线卷积，然后将结果重叠相加，
44、如图5-105-10所示。所示。图5-10 叠加相加法的分段以及的重叠情况 )(nx)(nx1N)(nh)(四、分段快速卷积四、分段快速卷积重叠相加法重叠相加法v设将设将 分为分为 第第 段段 表示为表示为 （5-175-17）v则则 （5-185-18）)(nx,),(),(10nxnxk)(nxk其他01)1()()(11NknkNnxnxk0)()(kknxnx000)()(*)()(*)()()()(四、分段快速卷积四、分段快速卷积重叠相加法重叠相加法v由于由于 长度为长度为 ，的长度为的长度为M M，故，故 的长度的长度为为 ，即的范围为，即的范围为 （5-195-19）v将式（将式
45、（5-195-19）与式（）与式（5-175-17）的范围比较，的范围比较，显显然然 比长点，而比长点，而 的范围是的范围是 （5-20）)(nxk1N)(nh)(nyk11MNN2)1(11111MNkMNkNnkN)(nxk)(nyk)(nxk)(1nyk2)2(2)1()1(1111MNkMNNknN四、分段快速卷积四、分段快速卷积重叠重叠相加法相加法v将式（将式（5-195-19）与式（）与式（5-205-20）比较，可知的）比较，可知的 后后部分与的部分与的 前部分，有前部分，有 个点发生重叠。个点发生重叠。这样，对于在此范围的每一个这样，对于在此范围的每一个 值，原序列值，原序列
46、和和 的卷积的卷积 之值应为之值应为 （5-215-21）v这就是说，式（这就是说，式（5-185-18）中的求和并不是将各段线）中的求和并不是将各段线卷积的结果简单地拼接在一起，在某些点上是需卷积的结果简单地拼接在一起，在某些点上是需要前后两段的结果重叠相加的。要前后两段的结果重叠相加的。)(nyk)(1nyk1M)(nh)(nx)(ny)()()(五、离散时间序列的相关运算五、离散时间序列的相关运算v设序列设序列 ，（，（），称下述运算），称下述运算 为序列为序列 和和 的线性相关。的线性相关。v对对 和和 均为实序列的情形，由式（均为实序列的情形，由式（5-225-22）可以得到可以得到
47、 ()x ny()nn )(*)()(mymnxnRmxy(5-22)()x ny()n()x ny()n)()()(mymnxnRmxy（5-23）五、离散时间序列的相关运算五、离散时间序列的相关运算v若序列若序列 和和 是不同的两个序列，则称相关为是不同的两个序列，则称相关为互相关，若互相关，若 ，则称相关为，则称相关为自相关自相关。v注意：注意：相关和卷积是两个不同的概念，它相关和卷积是两个不同的概念，它们的区别是明显的。除了形式上的差异，们的区别是明显的。除了形式上的差异，它们还有一些其他的不同。例如，对相关它们还有一些其他的不同。例如，对相关运算来说，既不具有交换性，也不具有结运算来
48、说，既不具有交换性，也不具有结合性。一般来说，合性。一般来说，()x ny()ny()n()x n)()(nRnRyxxy)()()(nRnRyzxxyz，第九节第九节 MATLABMATLAB中用于中用于FFTFFT计算的函数简介计算的函数简介 MATLAB中提供了多种实现快速变换的函数，如fft，ifft，fft2，ifft2，fftn，ifftn，fftshift，ifftshift等函数。由于MATLAB中没有零下标，因此，它采用的公式上、下标都相应右移一位，即(1)(1)1()(),(1,2,)NnkNnX kx n WkN(1)(1)11()(),(1,2,)NnkNnx nX k
49、 WnNN第九节第九节 MATLABMATLAB中用于中用于FFTFFT计算的函数简介计算的函数简介 一、函数一、函数fftfft功能：一维快速傅里叶变换（FFT）格式：y=fft(x)y=fft(x,n)说明：fft函数用于计算矢量或矩阵的离散傅里叶变换。其中y=fft(x)为利用FFT算法计算矢量x的离散傅里叶变换，当x为矩阵时，y为矩阵x每一列的FFT。当x的长度为2的整数次幂时，则fft函数采用基2的FFT算法，否则采用稍慢的混合基算法。而y=fft(x,n)采用n点FFT。当x的长度小于n时，fft函数在x的尾部补零，以构成n点数据；当x的长度大于n时，fft函数会截断序列x。第九节
50、第九节 MATLABMATLAB中用于中用于FFTFFT计算的函数简介计算的函数简介 二、函数二、函数ifftifft功能：一维逆快速傅里叶变换（IFFT）格式：y=ifft(x)y=ifft(x,n)说明：ifft函数用于计算矢量或矩阵的逆傅里叶变换。其函数使用同fft函数类似。第九节第九节 MATLABMATLAB中用于中用于FFTFFT计算的函数简介计算的函数简介 三、应用实例三、应用实例 考虑一被噪声污染的信号，很难看出它所包含的频率分量，如一个50 Hz和120 Hz正弦信号构成的信号，受零均值随机噪声的干扰，采样频率为1000 Hz。现可通过fft函数来分析其信号频率成分。程序如下
