数字信号处理 第三章 快速傅里叶变换 复习ppt课件

1、第3章 快速傅里叶变换 数字信号处理数字信号处理Digital Signal Processing(DSP)信息学院电子系信息学院电子系第3章 快速傅里叶变换 第3章 快速傅里叶变换 3.1 引言引言 3.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 3.3 按时间抽取按时间抽取DIT的基的基2-FFT算法算法3.4 按频率抽取按频率抽取DIF的基的基2-FFT算法算法3.5 N为复合数的为复合数的FFT算法算法 3.6 线性调频线性调频Z变换变换Chirp-Z变换变换算法算法 3.7 利用利用FFT分析时域连续信号频谱分析时域连续信号频谱 3.8 FFT的其他应用的其他应用

2、 第3章 快速傅里叶变换 3.1 引引 言言 DFT实现了时域序列的频域离散化, 因此在数字信号处理中用途很广 但是DFT的计算量太大，不适于实时处理，所以没有得到真正的运用 快速傅里叶变换(FFT)就是为了缩短DFT运算时间而产生的, 运算时间一般可缩短一二个数量级 FFT并不是一种新的变换,而是DFT的一种快速算法第3章 快速傅里叶变换 3.2 直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 3.2.1 直接计算直接计算DFT的运算量问题的运算量问题10)()(NnnkNWnxkXk=0, 1, , N-1 设x(n)为N点有限长序列，其DFT为 通常x(n)和WNnk都是复数

3、，因此一个X(k)需要N次复数乘法和N-1次复数加法 完成整个DFT运算则需要N2次复数乘法及N(N-1)次复数加法 由于DFT的运算次数与N2成正比, N较大时, 运算量非常可观第3章 快速傅里叶变换 例对一幅例对一幅NN点的二维图像进行点的二维图像进行DFT变换，当变换，当N=1024时时, 直接直接计算计算DFT所需复乘次数为所需复乘次数为1012次，用每秒可做次，用每秒可做10万次复数乘法的万次复数乘法的计算机计算需要近计算机计算需要近3000小时小时3.2.2 改善途径改善途径 把长序列的DFT分解成短序列的DFT运算利用系数Wnk的特性 对称性 2*()()jnknknkNNNWe

4、W周期性 )()(NknNkNnNnkNWWW可约性 2jmnknknmkmNNmNWeW/2(/2)1,NkNkNNNWWW 其它第3章 快速傅里叶变换 3.3 按时间抽取按时间抽取DIT的基的基 -2 FFT算法算法 设序列x(n)长度为N，且满足N=2M，M为正整数。按n的奇偶把x(n)分解为两个N/2点的子序列： 12, 1 , 0)() 12()()2(21Nrrxrxrxrx FFT分为两大类: 按时间抽取法(Decimation in Time) 和按频率抽取法(Decimation in Frequency) ,本节先介绍第一种算法3.3.1 算法原理算法原理 一个N点DFT的

5、分解第3章 快速傅里叶变换 将DFT x (n)分解为DFTx1(r) 与DFTx2(r)的线性组合 10( ) ( )( )NnkNnX kDFT x nx n W12( )( )kNX kW Xk11222(21)00(2 )(21)NNrkrkNNrrxr WxrW1122221200( )( )NNrkrkNkNNrrWx r Wx r W11221200/2/2( )( )rkkrNNrrkNNNWWx rx r W12(2 )( )(21)( )xrx rxrx r代入 /2/2 1110/2 12202( )( )( )( )rkNrkNNrNrDFT x rx rDFTWx r

6、x r W第3章 快速傅里叶变换 重写DFT12( )( )(0,1,2)/1kNXkkXNkkW X(X1(k)与X2(k)分别是x1(r)及x2(r)的N/2点DFT ) 112211/2/200112222/2/200( )( )(2 )( )( )(21)NNrkrkNNrrNNrkrkNNrrX kx r Wxr WXkx r WxrW上式为X(k)的前一半值,而后一半值可表示为212()()()0,1,/21222NkNNNNX kXkWXkkN第3章 快速傅里叶变换 12NXk121/20( )NrkNrx r W22NXk/22NkNkNNNWWWkNW 212()()()0,

7、1,/21222NkNNNNX kX kWXkkN化简1221/20( )NNrkNrx r W1( )X k2( )Xk22NjkNNeW12()( )( )0,1,/2 12kNkNX kX kW XkN得到第3章 快速傅里叶变换 上式将N点DFT分解为两个N/2点的DFT运算，运算过程如下图示X2(k)X1(k)kNW1X1(k)kNWX2(k)X1(k)kNWX2(k)时间抽取法蝶形运算流图分解后运算工作量节省了近一半12120,1,120,1,12( )( )( )( )( )2kNkNX kX kW XkNX kX kW XkNkNk 将X(k)表达式为前后两部分,重写如下第3章

8、快速傅里叶变换 N点DFT的一次时域抽取分解过程见下图N=8） 第3章 快速傅里叶变换 两个N/2点DFT的分解N点DFT分解1212( )( )( )( )( )2kNkNX kXkWXkNXkXkWXk12(2 )( )(21)( )xrx rxrx r,0,1,12Nr k X1(k)的分解的分解 由于N=2M仍是偶数，可以把每个N/2点子序列再进行分解1314(2 )( )(21)( )xlx lxlx l134134/2/2( )( )( )( )( )4kNkNXkXkXkNXkXkWXWk,0,1,14Nr k第3章 快速傅里叶变换 1314(2 )( )(21)( )xlx l

9、xlx l134134/2/2( )( )( )( )( )4kNkNXkXkXkNXkXkWXWkN/2点DFT分解,0,1,14Nr k X1(k)分解图示分解图示2222/2/2jkjkkkNNNNWeeW第3章 快速傅里叶变换 X2(k)的分解图示的分解图示)()(4)()()(62/5262/52kXWkXkNXkXWkXkXkNkN,0,1,14Nr k2526(2 )( )(21)( )xlx lxlx l第3章 快速傅里叶变换 N点DFT的第二次时域抽取分解图N=8）第3章 快速傅里叶变换 N点DFT的第二次时域抽取分解图N=8）DFT4点NX3(0)X3(1)x3(0) x1

10、(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4点NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)110NW2NWX(0)X(1)X(2)X(3)DFT4点NX5(0)X5(1)x5(0) x2(0) x(1)x5(1) x2(2) x(5)X2(0)X2(1)DFT4点NX6(0)X6(1)x6(0) x2(1) x(3)x6(1) x2(3) x(7)X2(2)X2(3)11X(4)X(5)X(6)X(7)0NW1NW2NW3NW11110NW2NW第3章 快速傅里叶变换 上式不需要乘法, 类似可求出X4

11、(k)，X5(k)，X6(k) 四个N/4点DFT的计算 X3(k)的分解的分解0021NWW 032032(0)(0)(4)(1)(0)(4)XxW xXxW x0303(0)(0)(4)(1)(0)(4)NNXxW xXxW x第3章 快速傅里叶变换 完整的N=8 DIT-FFT运算流图x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X(7)10NW0NW2NW110NW1NW2NW3NW1111由于输入序列在时域上进行奇偶分解，故称为“按时间抽取法” N=2M点的FFT共进行M

12、级运算，每级由N/2个蝶形运算组成第3章 快速傅里叶变换 3.3.2 DIT-FFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较 直接计算DFT与FFT算法的计算量之比为 22222NNNlog Nlog NN越大，FFT的优点越为明显例例3-2 P109 3000h-2m第3章 快速傅里叶变换 3.3.3 按时间抽取的按时间抽取的FFT算法的特点算法的特点1. 1. 原位运算同址运算）原位运算同址运算） 定义：利用同一存贮单元存贮蝶形运算输入、输出数据的方法 DIT-FFT的运算规律 同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，可采用原位运算，则全部运算过程只需要N个存

13、储单元 1rNWXm 1(k)Xm 1( j)Xm(k) Xm 1(k) Xm 1( j)Xm( j) Xm 1(k) Xm 1( j)rNWrNW第3章 快速傅里叶变换 2. 倒位序规律 （ N=2M） 输入序列的排序为N的二进制倒位序，输出序列则为自然顺序N8时的输入输出值第3章 快速傅里叶变换 3. 蝶形运算两节点的“间隔” 对N=2M点FFT，当输入为倒位序， 输出为正常顺序时，其第m级运算，每个蝶形的两节点“间隔为2m-1 x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X

14、(7)10NW0NW2NW110NW1NW2NW3NW1111x(0), x(1)x(0), x(2)x(0), x(4)第3章 快速傅里叶变换 3.3.4 按时间抽取的按时间抽取的FFT算法的其他形式流图算法的其他形式流图 对于任何流图，只要保持各节点所连的支路及传输系数不变，则不论节点位置怎么排列所得流图总是等效的将左图x(4)与 x(1) , x(6)与x(3)对调第3章 快速傅里叶变换 时间抽取、 输入自然顺序、 输出倒位序的FFT流图特点 数据存放的方式不同 取用系数的顺序不同第3章 快速傅里叶变换 3.4 按频率抽取按频率抽取DIF的基的基 -2 FFT算法算法 3.4.1 算法原

15、理算法原理10( )( )NnkNnX kx n W将长度为N=2M的序列x(n)前后对半分开, 其N点DFT可表示为1122200( )2NNNnknkNNnnNx n Wx nWk=0, 1, , N-1 12/20( )2NNknkNNnNx nx nWW统一求和区间11202( )( )NNnknkNNNnnx n Wx n W第3章 快速傅里叶变换 按k的奇偶可将X(k)分为两部分: 1220(2 )( )2NnrNnNXrx nx nW12, 1 , 0Nr/21,( 1)1kNkNkWk 偶数 奇数 式中k=0, 1, , N-1 12/20( )( )2NNknkNNnNX k

16、x nx nWW k取偶数时120/2( )2nrNNnNx nx nWx(n)前后两部分和的N/2点DFT第3章 快速傅里叶变换 k取奇数时12(21)0(21)( )2NnrNnNXrx nx nW12, 1 , 0Nr2120/( )2nnrNnNNNx nx nWWx(n)前后两部分差再乘以WNn后的N/2点DFT12/20( )2(2 )NnrNnNXnrxWx n k取偶数时令12( )2( )2( )( )nNNx nx nNx nxx nnWnx12, 1 , 0Nr代入上式第3章 快速傅里叶变换 1x(n)x(n N / 2)nNWx(n) x(n N / 2)x(n) x(

17、n N / 2)nNW上式表明, X(k)按k的奇偶分为两组,其偶(奇)数组是x1(n)(x2(n)的N/2点DFT. x1(n), x2(n)与x(n)间的关系也可用下面蝶形运算流图表示式中12( )2( )2( )( )nNNx nx nNx nxx nnWnx/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W得到第3章 快速傅里叶变换 按频率抽取的N点DFT第一次分解(N=8) /2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W式中12( )2( )2( )( )nNNx

18、nx nNx nxx nnWnx第3章 快速傅里叶变换 与DIT-FFT一样，由于N/2仍为偶数，继续将每个N/2点DFT输出再分解为偶数组与奇数组,直到第M次N=2M） 按频率抽取完整的N点DFT运算流图 (N=8) 第3章 快速傅里叶变换 3.4.2 DIF-FFT与与DIT-FFT的联系的联系 DIF的基本蝶形与DIT的基本蝶形互为转置DIT蝶形运算流图DIF蝶形运算流图第3章 快速傅里叶变换 两种FFT运算方法等价 DIT-FFTDIF-FFT 第3章 快速傅里叶变换 3.4.3 IDFT的高效算法的高效算法FFT算法同样可以用于 IDFT，称为快速傅里叶反变换(IFFT)比较DFT和

19、IDFT的运算公式:1010( ) ( )( )1( )( )( )NknNnNknNkX kDFT x nx n Wx nIDFT X kX k WN第3章 快速傅里叶变换 左图为在DIF-FFT流图上改动后，得到的DIT-IFFT运算流图第3章 快速傅里叶变换 3.4.3 IDFT的高效算法的高效算法上述IFFT算法需要改动FFT的程序和参数才能实现。也可以利用DFT的性质，直接用FFT程序来完成IDFT的运算101( )( )NknNkx nX k WN知101( )( )NknNkx nXk WN 两边取共轭1( )( )x nDFT XkN(1)DFT XNk两边再取共轭第3章 快速

20、傅里叶变换 3.5 N为复合数的为复合数的FFT算法算法 第3章 快速傅里叶变换 3.6 线性调频线性调频Z变换变换Chirp-Z变换算法变换算法 vFFT算法用于计算有限长序列的z变换X(z)在z平面单位圆上N个等间隔抽样点zk上的采样值v实际应用中在很多情况下并不一定需要计算全部频谱值,而仅需对某一频带内的信号频谱作较密集的分析v另外，采样也不一定局限于单位圆上，而需要计算出某一螺旋线上的等角度间隔的采样值v 例如语音信号分析时，往往在靠近语音信号序列z变换的极点的螺旋线上进行采样，可以使语音信号的共振峰变得更尖锐，便于精确确定共振峰频率第3章 快速傅里叶变换 3.6 线性调频线性调频Z变

21、换变换Chirp-Z变换变换算法算法 v线性调频z变换就是利用FFT快速计算螺旋线采样的算法ooooABX(ej)RezRezjImzjImzAB(a)(b)X(ej) 沿单位圆采样 沿AB弧采样 第3章 快速傅里叶变换 3.6.1 算法基本原理算法基本原理为适应z可以沿Z平面更一般的路径取值，沿Z平面上的一段螺线作等分角的采样，采样点zk为 10)()(NnnznxzX设有限长序列x(n)的Z变换为 式中: A和W都是任意复数, 设0000jjAA eWW ezk=AW-k k=0, 1, , M-1 M为采样点的总数0000jjkkkzA eWe综合上式得到 00()00jkkAWe第3章

22、 快速傅里叶变换 )(00000000kjkjkkjkeWAeWeAz zk参数的物理意义 0jImzRezo0A01.0zM1A0W01z0(M I)0螺线采样 A0: 起始采样点z0的矢量半径0: 起始采样点z0的相角0: 两相邻采样点之间的角度差 W0: 表示螺线的伸展率序列的DFT是Chirp-Z变换的特例第3章 快速傅里叶变换 1100()( )( )NNnnnkkknnX zx n zx n A W 0kM-1 将zk=AW-k代入x(n)的Z变换变换表达式中,得到 Chirp-Z变换公式 Chirp-Z变换的FFT 算法直接计算Chirp-Z变换公式的计算量很大, 但可以将其转换

23、为卷积形式, 从而利用FFT算法, 提高运算速度 第3章 快速傅里叶变换 将公式中的nk做一变换2221() 2nknkkn Chirp-Z变换公式的卷积形式1100()( )( )NNnnnkkknnX zx n zx n A W 0kM-1 代入公式, 整理后得到222()12220() ( )knk nNnknX zWx n A WW(卷积形式 )与卷积公式比较 10( )( )( ) ()Nng kh kg n h kn2222( )( )( )nnng nx n A Wh nW当X(zk)可表示成卷积形式第3章 快速傅里叶变换 )()()(22khkgWzXkkk=0, 1, , M

24、-1 卷积形式的Chirp-Z公式可采用FFT算法，从而提高运算速度x(n)2/ 2 )(nWnh2/ 2nnWAg(n)h(n)1 / h(n)X(zn) Chirp-Z变换的计算框图如下第3章 快速傅里叶变换 3.6.2 Chirp-Z变换的特点变换的特点输入序列和输出序列长度不需要相等, 且二者均可为素数 分析频率点zk的起始点z0及相邻两点的夹角0是任意的(即频率分辨率是任意的)， 因此可从任意频率上开始， 对输入数据进行窄带高分辨率的谱分析 谱分析路径可以是螺旋形的 Chirp-Z变换在一定条件下就是序列的DFT 与标准DFT(FFT)算法相比较， Chirp-Z变换有以下特点:第3

25、章 快速傅里叶变换 3.7 利用利用FFT分析时域连续信号频谱分析时域连续信号频谱 3.7.1 基本步骤基本步骤 时域连续信号离散傅里叶分析的处理步骤如下图示 LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)频谱分析是指计算信号各个频率的幅值, 相位和功率 处理过程分析第3章 快速傅里叶变换 LPF : 避免在模拟信号转换成序列时, 可能出现的频谱混叠现象TmjTjXTeXmcj21)(LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)A/D: 时域离散化,得到采样序列x(n)，其频谱用X(ej)表示第3章 快速傅里叶变换

26、DFT(FFT)运算: 加窗后的DFT是 102)()(NnnkNjenvkV0kN-1 LPFsc(t)Ha(j)xc(t)A / Dx(n)w(n)v(n)DFTV(k)w(n): 窗函数.为进行FFT，须对x(n)加窗处理，即v(n)=x(n)w(n)第3章 快速傅里叶变换 对连续信号进行谱分析时，主要关心两个问题：即谱分析范围与频率分辨率 谱分析范围与频率分辨率 谱分析范围(所能分析的最高频率)受采样频率的限制 频率分辨率用频率采样间隔F描述，表示谱分析中能够分辨的两个频谱分量最小间隔。F较小时，称频率分辨率较高第3章 快速傅里叶变换 有限长序列v(n)=x(n)w(n)的DFT相当于

27、v(n)FT的等间隔采样 kNjeVkV2)()(V(k)是sc(t)的离散频率函数， V(k)的第k点对应的模拟频率为: NTkTk22kkkfNT 谱分析范围与频率分辨率显然，数字域频率间隔=2/N 对应的模拟域谱线间距应为 NfNTFs1( fs 为采样频率) 谱线间距: 即频谱分辨率，指可分辨两频率的最小间距第3章 快速傅里叶变换 NfNTFs1( fs 为采样频率) T为采样时间间隔(s) fs为采样频率(Hz) F为谱线间距,频谱分辨率(Hz) tp为截取连续时间信号的样本长度, 又称记录长度(s) DFT对连续信号谱分析时，参数间的关系及选择原则例 时间序列v(n)=(1.1)n

28、R16(n)与16点的DFT 的如下图所示第3章 快速傅里叶变换 参数间的关系11psptNTfFNNTt 参数的选择(T、tp和N)实际应用中, 根据信号最高频率fh和频谱分辨率F的要求来确定三个参数 DFT对连续信号谱分析时，参数间的关系及选择原则第3章 快速傅里叶变换 采样周期T的选择：1 2hTf为保证采样信号不失真应满足，fs2fh，即周期T11psptNTfFNNTt说明：信号的谱分析范围 fh与频率分辨率F存在矛盾关系解释：如果保持采样点数N不变，而提高谱的分辨率(F减小)， 必须降低采样速率fs ，从而引起谱分析范围 fh 减少解决方法：如维持fs不变, 为提高分辨率，可以考虑

29、增加采样点数N与观察时间Tp第3章 快速傅里叶变换 N的选择由频谱分辨率F和T确定）1sfNFFT11psptNTfFNNTt 最小记录长度tp的选择由N, T确定）1ptNTF第3章 快速傅里叶变换 例例 一频谱分析器，其采样点数必须是一频谱分析器，其采样点数必须是2的整数幂，知的整数幂，知 频率分辨率频率分辨率10 Hz; 信号最高频率信号最高频率4kHz。试求。试求(1) 最小记录长度最小记录长度tp；(2) 最大采样间隔最大采样间隔T即最小采样频率即最小采样频率)；(3) 在一个记录中的最少点数在一个记录中的最少点数N 1 211hspTffNFFTtNTF解题思路知 F=10 Hz,

30、 fh=4 kHz1ptNTF(1)1 2hTf(2)1sfNFFT(3)取 2mN 第3章 快速傅里叶变换 由信号的时域波形图估计最高频率 最高频率1/(2*相邻峰谷间的最小距离) 信号最高频率fh的估计tt3t4ot1t2x(t)例：如下图示)(214Hztfh第3章 快速傅里叶变换 3.7.2 利用利用FFT对连续信号进行傅里叶分析时可能造成的误差对连续信号进行傅里叶分析时可能造成的误差1. 频谱混叠失真频谱混叠失真 当时域采样频率不满足fs2fh 时，会产生频谱混叠失真 对于FFT，频率函数也要采样成离散序列，因此为兼顾fh与F，必要时需增加记录长度的点数N一般取 fs=(2.53.0

31、) fh 第3章 快速傅里叶变换 3.7.2 利用利用FFT对连续信号进行傅里叶分析时可能造成的误差对连续信号进行傅里叶分析时可能造成的误差2. 栅栏效应栅栏效应利用FFT计算频谱，只能得到有限点的频谱采样值，而采样点间的频谱函数是不知道的，这就像通过一个“栅栏观看信号频谱,只能在离散点上看到信号频谱，称之为“栅栏效应”。由于栅栏效应，有可能漏掉(挡住)大的频谱分量第3章 快速傅里叶变换 减小栅栏效应的方法： 增加频域采样点数N，通过在时域数据末端添加零点，使一个周期内的点数增加，但并不改变原有的记录数据 说明：补零不能提高频率分辨率2. 栅栏效应栅栏效应第3章 快速傅里叶变换 cos(n/4

32、) 频谱 3. 由截断效应引起的频谱泄漏与谱间干扰由截断效应引起的频谱泄漏与谱间干扰实际中的序列x(n)有可能是无限长的，为进行DFT运算，x(n)需要进行加窗处理变成有限长序列，截断后序列的频谱与原序列频谱必然有差别, 主要表现为泄漏与谱间干扰矩形窗函数的幅度谱 加矩形窗后的频谱 第3章 快速傅里叶变换 泄漏：截断后的序列不再是单一谱线，而是向附近展宽。泄漏使频谱变模糊，使谱分辨率降低谱间干扰：主谱线两边形成很多旁瓣，将引起不同频率分量间的干扰。特别是强信号谱的旁瓣可能湮没弱信号的主谱线加矩形窗后的频谱 cos(n/4) 频谱 第3章 快速傅里叶变换 加矩形窗后的频谱 减小两种影响的措施：c

33、os(n/4) 频谱 增加窗的时域宽度N 可使频域主瓣变窄 采用其它缓变的窗代替矩阵窗，可使旁瓣能量更小，从而减少谱间干扰 N一定时，旁瓣越小的窗函数，其主瓣就越宽。因此只能以降低谱分辨率为代价，换取谱间干扰的减小第3章 快速傅里叶变换 3.7.3 频谱分析的应用频谱分析的应用)()()(1kjXkXkXR实信号x(n)的频谱是共轭偶对称的，故只要求出k在0, 1, N/2上的X(k)即可。 将X(k)写成极坐标形式 )(arg| )(|)(kXjekXkX式中，|X(k)|称为幅频谱，argX(k)称为相频谱。 频谱图 一个长度为N的时域离散序列x(n)，其DFT可表示为 由上式绘成的图形称

34、为频谱图。从图中可以知道信号存在哪些频率分量第3章 快速傅里叶变换 实际也常用功率谱表示，主要用于分析带有噪声干扰的信号NkXkPSD2| )(|)( 功率谱 频率轴几种定标方式的对应关系oooooN / 4N / 2k / (rad / s)f / Hzf / rad0.5fs / 2s / 2第3章 快速傅里叶变换 例例 用频谱分析下列时域信号的组成用频谱分析下列时域信号的组成( fs=32 Hz )对序列作32点DFT，|X(k)|如右图示。频率分辨率 F=fs/N=1Hz 2 10120102030(a )(b )0051015816nkx(n )|X (k)| 2 101201020

35、30(a )(b )0051015816nkx (n )|X (k)|第3章 快速傅里叶变换 3.8 FFT的其它应用的其它应用 3.8.1 线性卷积的线性卷积的FFT算法算法快速卷积快速卷积 1. FFT的快速卷积法利用圆周卷积的的快速卷积法利用圆周卷积的FFT计算线性卷积）计算线性卷积）补L N个零点L点DFT补L M个零点L点DFTL点IDFTy(n)h(n)x(n) FFT计算y(n)的步骤 求H(k)=DFTh(n) 求X(k)=DFTx(n) 计算Y(k)=X(k)H(k); 求y(n)=IDFTY(k) 第3章 快速傅里叶变换 运算量的比较直接线性卷积和FFT法计算线性卷积） x

36、(n)与h(n)点数差不多时, 有如下结果(KM为两种卷积运算量比值)M=L8163264128256512102420484096Km0.572 0.9411.62.785.928.821629.2453.999.9当M=L且M超过32以后，M越长， FFT法的优势越明显 x(n)与h(n)点数相差很大时采用FFT运算时，要求长序列全部输入，短序列补充很多零点，这样既不经济，运算时间也长。解决的方法是将长序列分段计算，即重叠相加法与重叠保留法第3章 快速傅里叶变换 设h(n)的点数为M，长序列x(n)可被分成为若干长度为L点的段0)()(nxnxiiLn(i+1)L-1 其他n i=0, 1

37、, 输入序列表示 0)()(iinxnx 2. 重叠相加法重叠相加法x(n)和h(n)的线性卷积等于00( )( )( )( )( )( )iiiiy nx nh nx nh ny n第3章 快速傅里叶变换 计算N点FFT， H(k)=DFTh(n) （ N=2mL+M-1 ）计算N点FFT，Xi(k)=DFTxi(n) （ N=2mL+M-1 ）相乘，Yi(k)=Xi(k)H(k)计算N点IFFT，yi(n)=IDFTYi(k) 计算步骤)()(0nynyii将各段yi(n)（包括重叠部分相加 xi(n)与yi(n)序列长度不同, 导致相邻两段输出有若干点重叠，应该将重叠部分相加后再和不重叠的部分共同组成输出y(n) 第3章 快速傅里叶变换 h ( n )0N 1M 1x ( n )0L2 L3 LnnnnnL 10 x0( n )N 10 x1( n )L2 L 1L N 13 L 10 x2( n )2 L2 L N 1 重叠相加法卷积图示 h ( n )0N 1M 1x ( n )0L2 L3 LnnnnnL 10 x0( n )N 10 x1( n )L2 L 1L