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