快速傅里叶变换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(37页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、本章主要内容引言 基2FFT算法进一步减少运算量的措施第4章 快速傅里叶变换(FFT)DFT是信号分析与处理中的一种重要变换。但直接计算DFT的计算量与变换区间长度N的平方成正比,当N较大时,计算量太大,直接用DFT算法进行谱分析和信号的实时处理是不切实际的。1965年发现了DFT的一种快速算法,使DFT的运算效率提高12个数量级,为数字信号处理技术应用于各种信号的实时处理创造了条件,推动了数字处理技术的发展。1984年,提出了分裂基快速算法,使运算效率进一步提高;4.1 引言 4.2.1 直接计算DFT的特点及减少运算量的基本途径 1.直接计算DFT长度为N的有限长序列x(n)的DFT为:2
2、、减少运算量的思路和方法思路:N点DFT的复乘次数等于N2。把N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外,旋转因子WmN具有周期性和对称性。4.2 基2FFT算法考虑x(n)为复数序列的一般情况,对某一个k值,直接按上式计算X(k)值需要N次复数乘法、(N-1)次复数加法。方法:分解N为较小值:把序列分解为几个较短的序列,分别计算其DFT值,可使乘法次数大大减少;利用旋转因子WNk的周期性、对称性进行合并、归类处理,以减少DFT的运算次数。周期性:对称性:3、FFT算法思想不断地把长序列的DFT分解成几个短序列的DFT,并利用旋转因子的周期性和对称性来减少DFT的运算次数。4
3、.2 基2FFT算法 4.2.2 时域抽取法基2FFT基本原理 FFT算法基本上分为两大类:时域抽取法FFT(简称DIT-FFT)和 频域抽取法FFT(简称DIFFFT)。1、时域抽取法FFT的算法思想:将序列x(n)按n为奇、偶数分为x1(n)、x2(n)两组序列;用2个N/2点DFT来完成一个N点DFT的计算。设序列x(n)的长度为N,且满足:(1)按n的奇偶把x(n)分解为两个N/2点的子序列4.2 基2FFT算法为自然数(2)用N/2点X1(k)和X2(k)表示序列x(n)的N点DFT X(k)4.2 基2FFT算法偶数奇数注意:这里的k的取值范围为0,1,N-1由于X1(k)和X2(
4、k)均以N/2为周期,且 ,X(k)又可表示为:对上式的运算用下图所示的流图符号来表示4.2 基2FFT算法这样将N点DFT分解为两个N/2点的DFTX1(k)X2(k)X1(k)+WNkX2(k)X1(k)WNkX2(k)WNk图:蝶形运算符号完成一个蝶形运算需要一次复数乘和两次复数加法运算,经过一次分解后,共需要复数乘和复数加的次数为2(N/2)2+N/2和N2/24.2 基2FFT算法N/2点DFTN/2点DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X
5、(1)X(2)X(3)X(4)X(5)X(6)X(7)N=8点的DIT-2FFT(时域抽取图)一次分解图(3)第二次分解:将x1(r)按r取奇、偶可分解成2个长度为N/4的子序列 x3(l)=x1(2l)、x4(l)=x1(2l+1),根据上面推导可得:X1(k)=X3(k)+WN/2kX4(k),k=0,1,N/2-1将x2(r)按r取奇、偶可分解成2个长N/4的子序列 x5(l)=x2(2l),l=0,1,,N/4 x6(l)=x2(2l+1);同理得4.2 基2FFT算法l=0,1,,N/4-1;X1(k+N/2)=X3(k)WN/2kX4(k),k=0,1,N/4-1;X1(k)=X3
6、(k)+WN/2kX4(k),k=0,1,N/4-1;X2(k)=X5(k)+WN/2kX6(k),k=0,1,N/4-1 ;X2(k+N/2)=X5(k)WN/2kX6(k),k=0,1,N/4-1;4.2 基2FFT算法N/4点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N/4点DFTN/4点DFTN/4点DFTX3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/2
7、0WN/21WN/21WN/20N=8点DFT的二次时域抽取分解图 X1(k+N/2)=X3(k)WN/2kX4(k)X1(k)=X3(k)+WN/2kX4(k)X2(k)=X5(k)+WN/2kX6(k)X2(k+N/2)=X5(k)WN/2kX6(k)k=0,1,N/4-1 ;再次分解,对N=8点,可分解三次。4.2 基2FFT算法X(5)N=8点DIT-FFT运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(6)X3(1)X4(0)X4(
8、1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/20WN0WN0WN0 x(7)WN/21WN0L=1级L=2L=3X(7)X3(0)X1(0)4.2 基2FFT算法N=8点DIT-FFT运算流图x(0)x(4)x(2)x(6)x(1)x(5)x(3)WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)WN0WN2WN0WN0WN0WN0 x(7)WN2WN0L=1级L=2L=3X(7)4.2.3 DITFFT算法与直接计算DFT运算量的比较1、直接DFT运算N点运算:复数乘次数:NN 复数加次数:N(N-1)2、用DIT-FFT作N点运算:复
9、数乘次数:MN/2=N/2log2N;复加次数:2 N/2M=Nlog2N。可见FFT大大减少了运算次数,提高了运算速度。4.2 基2FFT算法整个运算流图中有M级蝶形,每一级运算流图中有N/2个蝶形,每个蝶形需一次复乘和两次复数加运算。4.2.4 DITFFT的运算规律及编程思想1.原位计算序列长为N=2M点的FFT,有M级蝶形,每级有N/2个蝶形运算。同一级中,每个蝶形的两个输入数据只对本蝶形有用,每个蝶形的输入、输出数据节点在用一条水平线上。这样,当计算完一个蝶形后,所得的输出数据可立即存入原输入数据所占用的存储单元。经过M级运算后,原来存放输入序列数据的N个存储单元中可依次存放X(k)
10、的N个值。原位计算:利用同一存储单元存储蝶形计算输入、输出数据的方法。优点:节约存储空间、降低设备成本。4.2 基2FFT算法2.旋转因子的变化规律N点DITFFT运算流图中,每个蝶形都要乘以旋转因子WpN,p称为旋转因子的指数。N8 23 时各级的旋转因子 第一级:L=1,有1个旋转因子:WNp=WN/4J=W2LJ J=0 第二级:L=2,有2个旋转因子:WNp=WN/2J=W2LJ J=0,1 第三级:L=3,有4个旋转因子:WNp=WNJ=W2LJ J=0,1,2,3 对于N2M 的一般情况,第L级共有2L-1个不同的旋转因子:WNp=W2LJ J=0,1,2,2L-11 2L=2LM
11、2M=N2LM 故:按照上面两式可以确定第L级运算的旋转因子。4.2 基2FFT算法JJ2M-LWNp=W2LJ=WN2L-M=WNp=J2M-L,J=0,1,2,2L-113、同一级中,同一旋转因子对应蝶形数目 第L级FFT运算中,同一旋转因子用在2M-L个蝶形中;4、同一级中,蝶形运算使用相同旋转因子之间相隔的“距离”第L级中,蝶距:D=2L。5、同一蝶形运算两输入数据的距离 在输入倒序,输出原序的FFT变换中,第L级的每一个蝶形的2个输入数据相距:B=2L-1。6、码位颠倒 输入序列x(n)经过M级时域奇、偶抽选后,输出序列X(k)的顺序和输入序列的顺序关系为倒位关系。4.2 基2FFT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 快速 傅里叶变换 FFT
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内