第三章离散傅里叶变换快速精选文档.ppt

《第三章离散傅里叶变换快速精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章离散傅里叶变换快速精选文档.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 离散傅里叶变换快速本讲稿第一页，共三十二页问题的提出问题的提出例：例：4点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度共需：复数加法共需：复数加法N(N-1)次次复数乘法复数乘法N 2次次如果如果N N 运算次数运算次数；那么如何提高；那么如何提高DFTDFT的运算效率的运算效率?本讲稿第二页，共三十二页快快速速傅傅里里叶叶变变换换(Fast(Fast Fourier Fourier TransformTransform，简简称称FFT),FFTFFT),FFT是是计计算算DFTDFT的的各各种种快快速速算算法法的的统统称称。DFTDFT在在信信号号处处理理中中得得到到广广

2、泛泛应用，一个非常重要的原因就是其存在高效算法。应用，一个非常重要的原因就是其存在高效算法。直直接接计计算算N N点点序序列列的的DFTDFT，对对每每一一频频率率分分量量XmXm，需需计计算算N N次次复复数数乘乘法法，N N1 1次次复复数数加加法法。因因此此，计计算算N N个个不不同同频频率率分分量量XmXm，共共需需N N2 2次复数乘法，次复数乘法，(N(N1)N1)N次复数加法。次复数加法。IDFTIDFT的的直直接接计计算算与与DFTDFT的的直直接接计计算算具具有有相相同同的的运运算算量量。显显然然，随着随着N N的增大，的增大，DFTDFT和和IDFTIDFT的运算量将急剧增

3、加。的运算量将急剧增加。FFTFFT的的出出现现以以及及数数字字计计算算系系统统的的问问世世极极大大地地推推动动了了DFTDFT应应用用，并并可可以以满满足足许许多多工工程程实实际际中中实实时时处处理理需需求求。FFTFFT算算法法的的复复乘乘运运算量只是直接计算算量只是直接计算DFTDFT的约的约0 02727左右。左右。解决问题的思路与方法解决问题的思路与方法本讲稿第三页，共三十二页3.1 3.1 基基2 2时间抽取时间抽取FFTFFT算法算法331算法原理算法原理DIT的基本思想的基本思想:基基2时间抽取时间抽取(Decimation in Time，简称，简称DIT)算法原理是利用旋转

4、因子算法原理是利用旋转因子WmkN的特性，通过在时域将序列逐次分解为一组子序列，然后利用子序的特性，通过在时域将序列逐次分解为一组子序列，然后利用子序列的列的DFT来实现整个序列的来实现整个序列的DFT，从而提高，从而提高DFT的运算效率。的运算效率。旋转因子旋转因子WmkN（）v旋转因子具有周期性旋转因子具有周期性WmkN以以N为周期为周期WmkN Wm（k+N）N Wk（m+N）Nv旋转因子具有对称性：旋转因子具有对称性：v旋转因子具有可约性：旋转因子具有可约性：本讲稿第四页，共三十二页 计算方法：计算方法：设序列设序列的长度为的长度为N2M，M为正整数为正整数：将序列将序列补零以满足该条

5、件；补零以满足该条件；将将分解为两个长度分解为两个长度N2点的短序列：点的短序列：1 2（0，1，N/21）偶数点偶数点2 21（0，1，N/21）奇数点奇数点将长序列分解为短序列，通过短序列的将长序列分解为短序列，通过短序列的DFT来实现长序列的来实现长序列的DFT，以减少运，以减少运算量。算量。利用旋转因子的周期性、对称性、可约性，利用旋转因子的周期性、对称性、可约性，将两个短序列的将两个短序列的DFTDFT合成为对合成为对应的长序列应的长序列DFTDFT。基基2频率抽取频率抽取(Decimation in frequency)FFT算法：算法：本讲稿第五页，共三十二页基基2 2时间抽取时

6、间抽取FFTFFT算法流图算法流图N=2xk=x0,x1 由于这个图形呈蝶形，故称为蝶形计算结构，这是基由于这个图形呈蝶形，故称为蝶形计算结构，这是基2 2时间抽取时间抽取FFTFFT运算的基本单元。运算的基本单元。蝶形图左边的两个节点叫输入节点，右边的两个节点叫输蝶形图左边的两个节点叫输入节点，右边的两个节点叫输出节点，支路中的箭头表示信号流的方向，支路旁的数字表示出节点，支路中的箭头表示信号流的方向，支路旁的数字表示该支路的传输函数，未标数字的支路其传输函数为该支路的传输函数，未标数字的支路其传输函数为1 1。由图可。由图可见，完成一个蝶形运算需要一次复数乘法和两次复数加法。见，完成一个蝶

7、形运算需要一次复数乘法和两次复数加法。本讲稿第六页，共三十二页4点基2时间抽取FFT算法流图x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 3本讲稿第七页，共三十二页4点基2时间抽取FFT算法流图本讲稿第八页，共三十二页8 8点基点基2 2时间抽时间抽取取FFTFFT算法流算法流图图4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-1本讲稿第九页，共三十二页4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X

8、13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图本讲稿第十页，共三十二页基基2 2时间抽取时间抽取FFTFFT算法算法第一级第一级第二级第二级第三级第三级本讲稿第十一页，共三十二页312 算法的计算复杂度算法的计算复杂度复数乘法次数：复数乘法次数：复乘次数复乘次数NN 2 N=8N=8时基时基2 2时间抽取时间抽取FFTFFT的信号流图由的信号流图由3 3级构成。级构成。第一级包含第一级包含N/2=4N/2=4个蝶形，一般情况下，个蝶形，一般情况下，N=2N=2M M点，则基点，则基2 2时时间抽取间抽取FFTFFT的信

9、号流图应有的信号流图应有M M级，每一级有级，每一级有M M2 2个蝶形，所以个蝶形，所以总共有总共有MN/2MN/2个蝶形；每个蝶形需要一次复数乘法和二次复个蝶形；每个蝶形需要一次复数乘法和二次复数加法，因此总共需要：数加法，因此总共需要：复数加法次数：复数加法次数：N本讲稿第十二页，共三十二页FFT算法流图旋转因子 规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级 的蝶形系数为 ，蝶形节点的距离为N/2。本讲稿第十三页，共三十二页倒序倒序k0k1k2xk2 k1k0 x000 x100 x010010

10、1112 xk k0 xk2 k101x110 x001x101x011x11101010101本讲稿第十四页，共三十二页 3.2 3.2 基基2频率抽取频率抽取FFT算法算法本讲稿第十五页，共三十二页3NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X7本讲稿第十六页，共三十二页X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT

11、本讲稿第十七页，共三十二页0NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1本讲稿第十八页，共三十二页FFT算法应用算法应用利用利用N点复序列的点复序列的FFT计算两个计算两个N点实序列点实序列FFT利用利用N点复序列的点复序列的FFT，计算，计算2N点序列的点序列的FFT利用利用FFT计算计算IFFT本讲稿第十九页，共三十二页利用利用N点复序列的点复序列的FFT算法计算算法计算两个两个N点实序列点实序列FFTx

12、1k,x2k是实序列，将其构成复序列yk=x1k+j x2kDFTx1k+j x2k=YR m+jYI m本讲稿第二十页，共三十二页利用利用N点复序列的点复序列的FFT，计算，计算2N点序列的点序列的FFTyk是一个长度为2N的序列问题：如何利用如何利用N点点FFT，计算，计算4N点序列的点序列的FFT？本讲稿第二十一页，共三十二页利用利用FFT实现实现IFFT步骤：A)将X m取共轭C)对B)中结果取共轭并除以N本讲稿第二十二页，共三十二页3.3 3.3 线性调频线性调频z z变换算法变换算法线性调频线性调频z变换变换(Chirp Z Transform，简称，简称CZT)CZT的基本思想的

13、基本思想:在在z z平面上采用螺旋曲线抽样，以解决离散傅立叶变换在单位圆平面上采用螺旋曲线抽样，以解决离散傅立叶变换在单位圆等间隔抽样与输出、输入序列长度必须相等的局限。等间隔抽样与输出、输入序列长度必须相等的局限。CZTCZT的特点：的特点：v可以求解序列可以求解序列z z变换在变换在z z平面单位圆上某一段频谱的样点，也可以求解平面单位圆上某一段频谱的样点，也可以求解在在z z平面上非单位圆上的样点；平面上非单位圆上的样点；旋转因子旋转因子WmkN（）v输入序列的点数输入序列的点数N N和输出序列的点数和输出序列的点数M M可以不等。可以不等。本讲稿第二十三页，共三十二页CZTCZT定义定

14、义有限长序列的有限长序列的z变换定义为变换定义为:其中：其中：A0、W0为任意的正实数；为任意的正实数；0为起始抽样点的相角，可以为正也可为起始抽样点的相角，可以为正也可以为负；以为负；0表示两相邻样点之间的间隔。表示两相邻样点之间的间隔。给定给定A0、W0、0、0，当，当m0，1，M1时，可得到时，可得到z平面上的一平面上的一系列离散点系列离散点z0，z1，zM1：，取这些点的：，取这些点的z变换，即得有限长序列变换，即得有限长序列 xk的的M点点CZT：本讲稿第二十四页，共三十二页CZTCZT变换的轨迹变换的轨迹CZT变换的轨迹变换的轨迹通常为一条螺旋通常为一条螺旋曲线曲线(如图如图318

15、所示所示)：(1)(1)当当A A0 01 1时，螺旋曲线在时，螺旋曲线在z z平面的单位平面的单位圆外，圆外，A A0 01 1时，在单位圆内；时，在单位圆内；(2)(2)当当W W0 0 1 1时，时，A A0 0W W0 0-1-1 A A0 0，螺旋曲，螺旋曲线内旋，反之，则外旋；线内旋，反之，则外旋；(3)(3)当当A A0 0W W0 01 1时，时，CZTCZT变换的轨迹为单变换的轨迹为单位圆上的一段圆弧；位圆上的一段圆弧；(4)(4)当当A A0 01 1，W We ej2j2/N/N，M M N N时，时，CZTCZT变为变为DFTDFT。CZT变换的轨迹曲线变换的轨迹曲线的

16、特点：的特点：本讲稿第二十五页，共三十二页序列序列CZTCZT的的算法算法CZT算法框图算法框图(如图如图319所示所示)：计算序列计算序列CZT的关键是实现序列的关键是实现序列gk与与hk的线性卷积，可以通过的线性卷积，可以通过FFT来实现。来实现。中间序列变量的取值范围：中间序列变量的取值范围：由于序列由于序列xk的长度是的长度是N，因而序列，因而序列gk的长度也是的长度也是N点，点，序列序列hk有用值的范围是有用值的范围是（N1），），M1；经线性卷积所得序列经线性卷积所得序列yk的长度应为的长度应为2N+M2。由于只需要卷积结果的一部分，所以用循环卷积由于只需要卷积结果的一部分，所以用

17、循环卷积gk hk实现时允实现时允许有混叠，这时循环卷积点数只要许有混叠，这时循环卷积点数只要N+M1即可。即可。序列序列CZT的计算公式：的计算公式：本讲稿第二十六页，共三十二页保证保证yyk k 在在00，M1)M1)区间上不混叠的措施区间上不混叠的措施本讲稿第二十七页，共三十二页CZTCZT计算量统计：计算量统计：(1)计算gk需N次乘法；(2)计算Gm DFT gk 需1/2L2L乘法。(3)一般Hm DFT hk 可以事先计算；(4)计算Ym GmHm需L N+M1次乘法；(5)计算gk IDFT Ym 需1/2(N+M1)2L(N+M1)次乘法(6)计算 需M次乘法(7)总共需乘法

18、的次数Count（N+M-1）2L(N+M1)+2本讲稿第二十八页，共三十二页CZTCZT与与DFTDFT比较比较CZT与与DFT比较，具有以下特点：比较，具有以下特点：输入序列长度与输出序列长度不必相等；输入序列长度与输出序列长度不必相等；M M和和N N可以不是组合数，甚至可为素数；可以不是组合数，甚至可为素数；z zk k相邻点的间隔相邻点的间隔0 0是任意的，因此频率分辨率可以任意设定；是任意的，因此频率分辨率可以任意设定；变换轨迹不必是圆，这对分析在单位圆内的极点有利；变换轨迹不必是圆，这对分析在单位圆内的极点有利；起始点起始点z z0 0不必在不必在z z1 1处，可以在任意频率开

19、始计算，因而适用于窄带高分辨处，可以在任意频率开始计算，因而适用于窄带高分辨率的计算；率的计算；若若A A1 1、M MN N、W We ej2j2/N/N，则，则CZTCZT即为即为DFTDFT，因此，因此DFTDFT可以用可以用CZTCZT算法实现，算法实现，即使即使N N为素数也有效。为素数也有效。在MATLABMATLAB软件工具中有专门的函数cztczt，可以直接计算序列的线性调频z z变换，其调用格式为：y ycztxcztx，M M，W W，AA 其中：x x为输入序列，该函数可以计算序列x x沿着W W和A A定义的轨迹上的z z变换，M M为指定的cztczt长度。当M M，

20、A A，W W未指定时，其相当于FFTFFT。本讲稿第二十九页，共三十二页本讲稿第三十页，共三十二页图例图例F以以蓄蓄电电池池作作动动力力源源结结构构，如如图图（a a）所示。）所示。环保环保v 节能高效、行驶费用低节能高效、行驶费用低F电动汽车的再生阶段：电动汽车的再生阶段：二十世纪二十世纪7070年代年代 能源危机促使电动汽车重获生机；能源危机促使电动汽车重获生机；能源问题缓解促使电动汽车发展走入低谷。能源问题缓解促使电动汽车发展走入低谷。电动汽车系统可分为三个子系统：电动汽车系统可分为三个子系统：电力驱动子系统；电力驱动子系统；主能源子系统；主能源子系统；辅助控制子系统。辅助控制子系统。动态特性动态特性：被测量为时间函数，输出被测量为时间函数，输出y(t)y(t)随输入随输入x(t)x(t)变化的关变化的关系。系。本讲稿第三十一页，共三十二页图例图例2辅助辅助控制控制 减速断油功能减速断油功能 排放，排放，be；分析：分析：白金热线白金热线 感知空气流量；感知空气流量；检测电路简单；检测电路简单；半导体压敏电阻式半导体压敏电阻式 水温传感器电路水温传感器电路对对 应应对对 应应本讲稿第三十二页，共三十二页