




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解2 n直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解3 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解4 设复序列设复序列x(n) 长度为长度为N点,其点,其DFT为为 1 0 ( )( ) N nk N n X kx n W k=0,N-1 (1)计算一个)计算一个X(k) 值的运算量值的运算量 复数乘法次数:复数乘法次数: N 复数加法次数:复数加法次数: N1 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解5 (2)计算全部)计算全部
2、N个个X(k) 值的运算量值的运算量 复数乘法次数:复数乘法次数: N2 复数加法次数:复数加法次数: N(N1) (3)对应的实数运算量)对应的实数运算量 11 00 ( )( )Re ( )Im ( )ReIm NN nknknk NNN nn X kx n Wx njx nWjW 1 0 Re ( ) ReIm ( ) Im N nknk NN n x nWx nW Re ( ) ImIm ( ) Re nknk NN jx nWx nW FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解6 一次复数乘法:一次复数乘法: 4次实数乘法次实数乘法 2次实数加法次实数加法 一个一个X
3、(k) :4N次实数乘法次实数乘法 2N+2(N-1)= 2(2N-1)次实数加法次实数加法 所以所以 整个整个N点点DFT运算共需要:运算共需要: N2(2N-1)= 2N(2N-1) 实数乘法次数:实数乘法次数: 4 N2 实数加法次数:实数加法次数: FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解7 N点点DFT的复数乘法次数举例的复数乘法次数举例 NN2NN2 24644049 41612816384 864256 65 536 16256512 262 144 3210281024 1 048 576 结论:当结论:当N很大时,其运算量很大,对实时性很强的信号很大时,其运
4、算量很大,对实时性很强的信号 处理来说,要求计算速度快,因此需要改进处理来说,要求计算速度快,因此需要改进DFT的计算的计算 方法,以大大减少运算次数。方法,以大大减少运算次数。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解8 nk N W 主要原理是利用系数主要原理是利用系数 的以下特性对的以下特性对DFT进行分解:进行分解: nk N W (1)对称性)对称性 () nk N W ()k N n N W (2)周期性)周期性 ()()n N kn k Nnk NNN WWW (3)可约性)可约性 mnknk mNN WW / / nknk m NN m WW 另外,另外, 1
5、 2/ N N W k N Nk N WW )2/( FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解9 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解10 1 (2 )( )xrx r 设设N2L,将,将x(n)按按 n 的奇偶分为两组:的奇偶分为两组: 2 (21)( )xrx r r =0,1, 1 2 N 1 0 ( ) ( )( ) N nk N n X kDFT x nx n W 则则 1 0 1 0 )()( N n n nk N N n n nk N WnxWnx 为奇数为偶数 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解11 1 2 0 )
6、12( 1 2 0 2 ) 12()2( N r kr N N r rk N WrxWrx 1 2 0 2 2 1 2 0 2 1 )()( N r rk N k N N r rk N WrxWWrx )()( 21 kXWkX k N 1 0 1 0 )()( N n n nk N N n n nk N WnxWnx 为奇数为偶数 式中,式中,X1(k)和和X2(k)分别是分别是x1(n)和和x2(n)的的N/2的的DFT。 另外,式中另外,式中k的取值范围是:的取值范围是:0,1, ,N/21 。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解12 因此,因此, 只能计算出只能
7、计算出X(k)的前一半值。的前一半值。 12 ( )( )( ) k N X kX kW Xk 后一半后一半X(k) 值,值, N/2 , N/2 1, ,N ? rk N W 2 (2) 2 r Nk N W 利用利用 可得到可得到 1( ) 2 N Xk 2 1 (2) 12 0 ( ) N r Nk N r x r W 2 1 12 0 ( ) N rk N r x r W )( 1 kX 同理可得同理可得 22 ()( ) 2 N XkXk FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解13 考虑到考虑到 k N k N N N kN N WWWW 2)2( 因此可得后半部
8、分因此可得后半部分X(k) ) 2 () 2 () 2 ( 2 2 1 N kXW N kX N kX Nk N 12 ( )( )( ) k N X kX kW Xk 及前半部分及前半部分X(k) )()( 21 kXWkX k N k=0,1, ,N/21 k=0,1, ,N/21 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解14 12 ( )( )( ) k N X kX kW Xk 12 ( )( )( ) k N X kX kW Xk 蝶形运算式蝶形运算式 蝶形运算信蝶形运算信 号流图符号号流图符号 因此,只要求出因此,只要求出2个个N/2点的点的DFT,即,即X1(k
9、)和和X2(k),再,再 经过蝶形运算就可求出全部经过蝶形运算就可求出全部X(k)的值,运算量大大减少。的值,运算量大大减少。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解15 0 N W 1 N W 2 N W 3 N W 以以N=8为例,为例, 分解为分解为2个个4点点 的的DFT,然后,然后 做做8/2=4次蝶形次蝶形 运算即可求出运算即可求出 所有所有8点点X(k)的的 值。值。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解16 复数乘法次数: N2 复数加法次数: N(N1) 复数乘法次数: 2*(N/2)2+N/2=N2/2+N/2 复数加法次数: 2*
10、(N/2)(N/21)+2*N/2=N2/2 nN点 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解17 由于N2L,因而N/2仍是偶数 ,可以进一步把每个N/2点 子序列再按其奇偶部分分解为两个N/4点的子序列。 以N/2点序列x1(r)为例 13 14 (2 )( ) 0,1,1 (21)( )4 xlx l N l xlx l 则有 rk N N r WrxkX 2 12 0 11 )()( kl N N l lk N N l WlxWlx )12( 2 14 0 1 2 2 14 0 1 ) 12()2( lk N N l k N lk N N l WlxWWlx 4 14
11、 0 424 14 0 3 )()( )()( 42/3 kXWkX k N k=0,1, 1 4 N FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解18 且且 13/24 ( )( ) 4 k N N XkXkWXk k=0,1, 1 4 N 由此可见,一个由此可见,一个N/2点点DFT可分解成两个可分解成两个N/4点点DFT。 同理,也可对同理,也可对x2(n)进行同样的分解,求出进行同样的分解,求出X2(k)。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解19 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解20 1 3/4 0 ( ) lk N l
12、x l W 0 2 (0)(4)xW x 0 (0)(4) N xW x 对此例对此例N=8,最后剩下的是,最后剩下的是4个个N/4= 2点的点的DFT,2点点 DFT也可以由蝶形运算来完成。以也可以由蝶形运算来完成。以X3(k)为例。为例。 /4 1 33/4 0 ( )( ) N lk N l Xkx l W k=0, 1 即即 0 3323 (0)(0)(1)XxW x 1 3323 (1)(0)(1)XxW x 1 2 (0)(4)xW x 0 (0)(4) N xW x 这说明,这说明,N=2M的的DFT可全部由蝶形运算来完成。可全部由蝶形运算来完成。 FFT快速傅里叶变换蝶形算法详
13、解快速傅里叶变换蝶形算法详解21 N=8按时间抽取法按时间抽取法FFT信号流图信号流图 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解22 由按时间抽取法FFT的信号流图可知,当N=2L时,共有 级 蝶形运算;每级都由 个蝶形运算组成,而每个蝶形有 次复乘、 次复加,因此每级运算都需 次复乘和 次复加。 L N/2 N/2 12 N FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解23 这样这样 级运算总共需要:级运算总共需要: L 复数乘法: N N L N 2 log 22 复数加法: NNLN 2 log 直接直接DFT算法运算量算法运算量 复数乘法: 复数加法:
14、N2 N(N1) 直接计算直接计算DFT与与FFT算法的计算量之比为算法的计算量之比为M N N N N N M 2 2 2 log 2 log 2 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解24 NN2 计算量 之比M NN2 计算量 之比M 2414.012816 38444836.6 41644.025665 5361 02464.0 864125.4512262 1442 304113.8 16256328.010241 048 5765 120204.8 3210288012.820484 194 30411 264372.4 64404919221.4 N N 2
15、log 2 N N 2 log 2 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解25 n序列的逆序排列 n同址运算(原位运算) n蝶形运算两节点间的距离 n 的确定 r N W FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解26 )(01221)( )( BINMMDEC nnnnnn 由于由于 x(n) 被反复地按奇、偶分组,所以流图输被反复地按奇、偶分组,所以流图输入端的入端的 排列不再是顺序的,但仍有规律可循:排列不再是顺序的,但仍有规律可循: 因为因为 N=2M , 对于任意对于任意 n(0n N-1),可以用,可以用M个个 二进制码表示为:二进制码表示为:
16、1 0 , 01221 nnnnn MM n 反复按奇、偶分解时,即按二进制码的反复按奇、偶分解时,即按二进制码的“0” “1” 分解。分解。 n序列的逆序排列 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解27 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解28 自然顺序自然顺序 n二进制数二进制数倒位序二进制数倒位序二进制数倒位序顺序数倒位序顺序数 00000000 10011004 20100102 30111106 41000011 51011015 61100113 71111117 n FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解29 FFT快
17、速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解30 某一列任何两个节点某一列任何两个节点k 和和j 的节点变量进行蝶形运算的节点变量进行蝶形运算 后,得到结果为下一列后,得到结果为下一列k、j两节点的节点变量,而和其他两节点的节点变量,而和其他 节点变量无关。这种原位运算结构可以节省存储单元,节点变量无关。这种原位运算结构可以节省存储单元, 降低设备成本。降低设备成本。 )(kX ) 2 ( N kX )( 1 kX )( 2 kX k N W 运算前运算前运算后运算后 ) 2 ( N kA )(kA ) 2 ( N kA )(kA 例例 n同址运算(原位运算) FFT快速傅里叶变换蝶形算
18、法详解快速傅里叶变换蝶形算法详解31 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解32 以以N=8为例:为例: 第一级蝶形,距离为:第一级蝶形,距离为: 第二级蝶形,距离为:第二级蝶形,距离为: 第三级蝶形,距离为:第三级蝶形,距离为: 规律:对于共规律:对于共L级的蝶形而言,其级的蝶形而言,其m级蝶形运算的节级蝶形运算的节 点间的距离为点间的距离为 1 2 4 1 2 m n蝶形运算两节点间的距离 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解33 r N W 以N=8为例: 0,1 0 2 2 4/ jWWWWm jj N r N m 时, 1 , 0,2 4 2
19、 2/ jWWWWm jjj N r N m 时, 3 , 2 , 1 , 0,3 8 2 jWWWWm jjj N r N m 时, 级:第LN M ,2 12 , 2 , 1 , 0, 1 2 Ljr N jWW L MLMLML N 2222 LM LM ML ML j N j N jj N j j N r N WeeWW 2 2 2 2 2 2 r N W n 的确定 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解34 n算法原理算法原理 再把输出再把输出X(k)按按k的奇偶分组的奇偶分组 先把输入按先把输入按n的顺序分成前后两半的顺序分成前后两半 设序列长度为设序列长度为
20、N=2L,L为整数为整数 前半子序列前半子序列x(n) 后半子序列后半子序列) 2 ( N nx 0n 1 2 N 0n 1 2 N FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解35 1 0 ( )( ) N nk N n X kx n W 由由DFT定义得定义得 /2 11 0/2 ( )( ) NN nknk NN nn N x n Wx n W 12/ 0 ) 2 ( 12/ 0 ) 2 ()( N n k N n N N n nk N W N nxWnx 12/ 0 2 ) 2 ()( N n nk N k N N WW N nxnxk=0,1, ,N FFT快速傅里叶变
21、换蝶形算法详解快速傅里叶变换蝶形算法详解36 由于由于 1 2 2 2 j N N j N N eeW /2 1 2 0 ( )( )() 2 N N k nk NN n N X kx nx nWW 所以所以 k k N N W) 1( 2 则则 12/ 0 ) 2 () 1()()( N n nk N k W N nxnxkX k=0,1, ,N FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解37 然后按然后按k的奇偶可将的奇偶可将X(k)分为两部分分为两部分 2 21 kr kr r=0,1, , 1 2 N 则式则式 12/ 0 ) 2 () 1()()( N n nk N
22、k W N nxnxkX 可转化为可转化为 nr N N n W N nxnxrX 2 12/ 0 ) 2 ()()2( 12/ 0 2/ ) 2 ()( N n nr N W N nxnx )12( 12/ 0 ) 2 ()() 12( rn N N n W N nxnxrX nr N n N N n WW N nxnx 2 12/ 0 ) 2 ()( FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解38 /2 1 /2 0 (2 )( )() 2 N nr N n N Xrx nx nW 令令 n N W N nxnxnx N nxnxnx ) 2 ()()( ) 2 ()()(
23、 2 1 n=0,1, , 1 2 N 代入代入 /2 1 2 0 (21) ( )() 2 N nnr NN n N Xrx nx nWW nr N N n nr N N n Wnxr Wnxr 2 12 0 2 2 12 0 1 )() 12( )()2( r=0,1, , 1 2 N 可得可得 为为2个个N/2点的点的DFT,合起来正好是,合起来正好是N点点X(k)的值。的值。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解39 n N W N nxnxnx N nxnxnx ) 2 ()()( ) 2 ()()( 2 1 将将 称为蝶形运算称为蝶形运算 与时间抽选基与时间抽
24、选基2FFT算法中的蝶形运算符号略有不同。算法中的蝶形运算符号略有不同。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解40 例例 按频率抽取,将按频率抽取,将N点点DFT分解为两个分解为两个N/2点点DFT的组合的组合(N=8) FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解41 与时间抽取法的推导过程一样,由于与时间抽取法的推导过程一样,由于 N=2L,N/2仍然是仍然是 一个偶数,因而可以将每个一个偶数,因而可以将每个N/2点点DFT的输出再分解为偶数组的输出再分解为偶数组 与奇数组,这就将与奇数组,这就将N/2点点DFT进一步分解为两个进一步分解为两个N/4点点
25、DFT。 N=8 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解42 n频率抽取法输入是自然顺序,输出是倒位序 的;时间抽取法正好相反。 n频率抽取法的基本蝶形与时间抽取法的基本 蝶形有所不同。 n频率抽取法运算量与时间抽取法相同。 n频率抽取法与时间抽取法的基本蝶形是互为 转置的。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解43 M N 2 IDFT公式公式 1 0 )( 1 N k nk N WkX N kXIDFTnx DFT公式公式 nk N N n WnxnxDFTkX 1 0 )()()( 比较可以看出,比较可以看出, nk N W nk N W M N
26、 2 11 IDFT多出多出 M个个1/2可分解到可分解到M级蝶形运算中。级蝶形运算中。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解44 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解45 1 0 )( 1 )( N k nk N WkX N kXIDFT 1 0 )( 1 N k nk N WkX N 1 0 )( 1 N k nk N WkX N 1 ( )( )IFFT X kFFT Xk N ( )X k 求共轭 ( )Xk FFT 求 ( )FFT Xk ( )FFT Xk N 除以 ( )x n 求共轭 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形
27、算法详解46 n用用FFT进行谱分析的进行谱分析的Matlab实现实现 n用用CZT进行谱分析的进行谱分析的Matlab实现实现 n在在Matlab中使用的线性调频中使用的线性调频z变换函数为变换函数为czt, 其调用格式为其调用格式为 nX= czt(x, M, W, A) n其中,其中,x是待变换的时域信号是待变换的时域信号x(n),其长度为,其长度为N,M 是变换的长度,是变换的长度,W确定变换的步长,确定变换的步长,A确定变换的确定变换的 起点。若起点。若M= N,A= 1,则,则CZT变成变成DFT。 FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解47 例例5.1 设模拟
28、信号设模拟信号 ,以,以 t= 0.01n (n=0: N-1) 进行取样,试用进行取样,试用fft函数对其做频谱分析。函数对其做频谱分析。N分别分别 为:为:(1) N=45;(2) N=50;(3) N=55;(2) N=60。 ( )2sin(4)5cos(8)x ttt 程序清单如下程序清单如下 %计算计算N=45的的FFT并绘出其幅频曲线并绘出其幅频曲线 N=45;n=0:N-1;t=0.01*n; q=n*2*pi/N; x=2*sin(4*pi*t)+5*cos(8*pi*t); y=fft(x,N); figure(1) subplot(2,2,1) plot(q,abs(y) title(FFT N=45) FFT快速傅里叶变换蝶形算法详解快速傅里叶变换蝶形算法详解48 %计算计算N=50的的FFT并绘出其幅频曲线并绘出其幅频曲线 N=50;n=0:N-1;t=0.01*n; q=n*2*pi/N; x=2*sin(4*pi*t)+5*cos(8*pi*t); y=fft(x,N
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 巷道掘进基础知识培训课件
- 工程造价费用组成
- 2025版建筑工程劳务分包与材料供应综合合同
- 二零二五年度共有产权房买卖收据及产权份额变更合同
- 工程计量与计价课件
- 我的乐园下册作文400字7篇
- 工程结算资料课件
- 疫情下德育班会课件
- 活动设计:按键不伤人-小学生拒绝网络欺凌心理活动设计
- 会展策划与执行服务委托合同
- 军品维修现场管理办法
- 2025年江苏省苏州市中考招生考试数学真题试卷(真题+答案)
- 2025云南省临沧市大数据有限公司招聘(8人)笔试参考题库附带答案详解版
- 搬迁项目临时设施拆除与废弃物处理合同
- 2025年食品安全知识考试试题库及解析答案
- 上海市青浦区2025年物理高一下期末考试试题含解析
- 小学一年级升二年级暑假数学作业-思维应用题训练50题(附答案)
- 腹透患者健康指导
- 初中语文新课程标准试题及答案
- 宗教场所消防培训课件
- 隧道建设施工进度计划与工期保证措施
评论
0/150
提交评论