FFT快速傅里叶变换(蝶形算法)详解解读课件.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《FFT快速傅里叶变换(蝶形算法)详解解读课件.ppt》由会员分享,可在线阅读,更多相关《FFT快速傅里叶变换(蝶形算法)详解解读课件.ppt(53页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第五章 快速傅里叶变换本章目录n直接计算直接计算DFT的问题及改进的途径的问题及改进的途径n n按按时间抽取时间抽取的的基基2-FFT算法算法 n n按按频率抽取频率抽取的基的基2-FFT算算法法 n n快速快速傅里叶逆变换傅里叶逆变换(IFFT)算法算法 n nMatlab实现实现25.1 引言 n nDFTDFT在实际应用中很重要在实际应用中很重要在实际应用中很重要在实际应用中很重要:可以计算信号的可以计算信号的可以计算信号的可以计算信号的频谱、功率谱和线性卷积等。频谱、功率谱和线性卷积等。频谱、功率谱和线性卷积等。频谱、功率谱和线性卷积等。n n直接按直接按直接按直接按DFTDFT变换进
2、行计算,当序列长度变换进行计算,当序列长度变换进行计算,当序列长度变换进行计算,当序列长度N N很大很大很大很大时,计算量非常大,所需时间会很长。时,计算量非常大,所需时间会很长。时,计算量非常大,所需时间会很长。时,计算量非常大,所需时间会很长。n nFFTFFT并不是一种与并不是一种与并不是一种与并不是一种与DFTDFT不同的变换,而是不同的变换,而是不同的变换,而是不同的变换,而是DFTDFT的一种快速计算的算法。的一种快速计算的算法。的一种快速计算的算法。的一种快速计算的算法。35.2 直接计算DFT的问题及改进的途径 n nDFTDFT的运算量的运算量的运算量的运算量 设复序列设复序
3、列x(n)长度为长度为N点,其点,其DFT为为k=0,N-1(1)计算一个)计算一个X(k)值的运算量值的运算量复数乘法次数:复数乘法次数:N复数加法次数:复数加法次数:N145.2.1 DFT的运算量(2)计算全部)计算全部N个个X(k)值的运算量值的运算量复数乘法次数:复数乘法次数:N2复数加法次数:复数加法次数:N(N1)(3)对应的实数运算量)对应的实数运算量5一次复数乘法一次复数乘法:4次实数乘法次实数乘法 2次实数加法次实数加法 一个一个X(k):4N次实数乘法次实数乘法2N+2(N-1)=2(2N-1)次实数加法次实数加法 所以所以 整个整个N点点DFT运算共需要:运算共需要:N
4、2(2N-1)=2N(2N-1)实数乘法次数:实数乘法次数:4 N2实数加法次数:实数加法次数:6DFT运算量的结论N点点DFT的复数乘法次数举例的复数乘法次数举例NN2NN22464404941612816384864256 65 536 16256512 262 144 3210281024 1 048 576 结论结论:当:当N很大时,其运算量很大,对实时性很强的信号很大时,其运算量很大,对实时性很强的信号处理来说,要求计算速度快,因此需要改进处理来说,要求计算速度快,因此需要改进DFT的计算的计算方法,以大大减少运算次数。方法,以大大减少运算次数。7 5.2.2 减少运算工作量的途径
5、主要原理是利用系数主要原理是利用系数 的以下特性对的以下特性对DFT进行分解:进行分解:(1)对称性)对称性(2)周期性)周期性(3)可约性)可约性 另外,另外,85.3 按时间抽取的基2-FFT算法 n n算法原理算法原理n n按时间抽取基按时间抽取基-2FFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较n n按时间抽取的按时间抽取的FFT算法的特点算法的特点n n按时间抽取按时间抽取FFT算法的其它形式流程图算法的其它形式流程图95.3.1 算法原理 设设N2L,将,将x(n)按按 n 的奇偶分为两组:的奇偶分为两组:r=0,1,则则10式中,式中,X1(k)和和X2(k)分
6、别是分别是x1(n)和和x2(n)的的N/2的的DFT。另外,式中另外,式中k的取值范围是:的取值范围是:0,1,N/21。11因此,因此,只能计算出只能计算出X(k)的前一半值。的前一半值。后一半后一半X(k)值,值,N/2,N/2 1,N?利用利用可得到可得到 同理可得同理可得12考虑到考虑到 因此可得后半部分因此可得后半部分X(k)及前半部分及前半部分X(k)k=0,1,N/21k=0,1,N/2113蝶形运算蝶形运算式蝶形运算式蝶形运算信蝶形运算信号流图符号号流图符号 因此,只要求出因此,只要求出2个个N/2点的点的DFT,即,即X1(k)和和X2(k),再经过蝶形运算就可求出全部再经
7、过蝶形运算就可求出全部X(k)的值,运算量大大减少。的值,运算量大大减少。14以8点为例第一次按奇偶分解以以N=8为例,为例,分解为分解为2个个4点点的的DFT,然后,然后做做8/2=4次蝶形次蝶形运算即可求出运算即可求出所有所有8点点X(k)的的值。值。15蝶形运算量比较复数乘法次数:N2复数加法次数:N(N1)复数乘法次数:2*(N/2)2+N/2=N2/2+N/2复数加法次数:2*(N/2)(N/21)+2*N/2=N2/2nN点DFTDFT的运算量的运算量的运算量的运算量 n n分解一次后所需的运算量分解一次后所需的运算量分解一次后所需的运算量分解一次后所需的运算量2 2个个个个N/2
8、N/2的的的的DFTDFTN/2N/2蝶形:蝶形:蝶形:蝶形:n n因此通过一次分解后,运算工作量减少了差因此通过一次分解后,运算工作量减少了差因此通过一次分解后,运算工作量减少了差因此通过一次分解后,运算工作量减少了差不多一半。不多一半。不多一半。不多一半。16进一步按奇偶分解 由于N2L,因而N/2仍是偶数,可以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的子序列。以N/2点序列x1(r)为例 则有 k=0,1,17且且k=0,1,由此可见,一个由此可见,一个N/2点点DFT可分解成两个可分解成两个N/4点点DFT。同理,也可对同理,也可对x2(n)进行同样的分解,求出进行同
9、样的分解,求出X2(k)。18以8点为例第二次按奇偶分解19算法原理 对此例对此例N=8,最后剩下的是,最后剩下的是4个个N/4=2点的点的DFT,2点点DFT也可以由蝶形运算来完成。以也可以由蝶形运算来完成。以X3(k)为例。为例。k=0,1即即这说明,这说明,N=2M的的DFT可全部由蝶形运算来完成。可全部由蝶形运算来完成。20以8点为例第三次按奇偶分解N=8按时间抽取法按时间抽取法FFT信号流图信号流图 215.3.2 5.3.2 按时间抽取基按时间抽取基2-FFT2-FFT算法与直接计算算法与直接计算DFTDFT运算量的比较运算量的比较 由按时间抽取法FFT的信号流图可知,当N=2L时
10、,共有 级蝶形运算;每级都由 个蝶形运算组成,而每个蝶形有 次复乘、次复加,因此每级运算都需 次复乘和 次复加。LN/2 N/2 12N22这样这样 级运算总共需要:级运算总共需要:L复数乘法:复数加法:直接直接DFT算法运算量算法运算量 复数乘法:复数加法:N2N(N1)直接计算直接计算DFT与与FFT算法的计算量之比为算法的计算量之比为M23FFT算法与直接DFT算法运算量的比较NN2计算量之比M NN2计算量之比M 2414.012816 38444836.641644.025665 5361 02464.0864125.4512262 1442 304113.816256328.010
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FFT 快速 傅里叶变换 蝶形 算法 详解 解读 课件
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内