《快速傅里叶变换FFT》由会员分享,可在线阅读,更多相关《快速傅里叶变换FFT(89页珍藏版)》请在金锄头文库上搜索。
1、第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.1 引言引言4.2 基基2FFT算法算法4.3 进一步减少运算量的措施进一步减少运算量的措施4.4 分裂基分裂基FFT算法算法4.5 离散哈特莱变换离散哈特莱变换(DHT)1第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.1 引言引言DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比,当N较大时,计算量太大,所以在快速傅里叶变换(简称FFT)出现以前,直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种
2、快速算法以后,情况才发生了根本的变化。2第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.2 基基2FFT算法算法4.2.1直接计算DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况,对某一个k值,直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。(4.2.1)3第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 如前所述,N点DFT的复乘次数等于N2。显然,把N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外,旋转因子WmN具有明显的周期性和对称性。其周期性表现为(4.2.2)其对称性表现为或者4
3、第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.2.2时域抽取法基2FFT基本原理FFT算 法 基 本 上 分 为 两 大 类 : 时 域 抽 取 法FFT(DecimationInTimeFFT,简称DIT-FFT)和频域抽取法FFT(DecimationInFrequencyFFT,简称DIFFFT)。下面先介绍DITFFT算法。设序列x(n)的长度为N,且满足为自然数按n的奇偶把x(n)分解为两个N/2点的子序列5第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 则x(n)的DFT为由于所以6第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 其中X1(k)和X2(k)分别为x
4、1(r)和x2(r)的N/2点DFT,即(4.2.5)(4.2.6)由于X1(k)和X2(k)均以N/2为周期,且,所以X(k)又可表示为(4.2.7)(4.2.8)7第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.1蝶形运算符号8第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.2N点DFT的一次时域抽取分解图(N=8)9第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 与第一次分解相同,将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l),即那么,X1(k)又可表示为(4.2.9)10第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 式中同理,由
5、X3(k)和X4(k)的周期性和WmN/2的对称性Wk+N/4N/2=-WkN/2最后得到:(4.2.10)11第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 用同样的方法可计算出(4.2.11)其中12第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.3N点DFT的第二次时域抽取分解图(N=8)13第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.4N点DITFFT运算流图(N=8)14第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.2.3DITFFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所
6、以,M级运算总共需要的复数乘次数为复数加次数为例如,N=210=1024时15第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.5FFT算法与直接计算DFT所需乘法次数的比较曲线16第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.2.4DITFFT的运算规律及编程思想1.原位计算由图4.2.4可以看出,DITFFT的运算过程很有规律。N=2M点的FFT共进行M级运算,每级由N/2个蝶形运算组成。2.旋转因子的变化规律如上所述,N点DITFFT运算流图中,每级都有N/2个蝶形。每个蝶形都要乘以因子WpN,称其为旋转因子,p称为旋转因子的指数。17第第4章章 快速傅里叶变换快速
7、傅里叶变换(FFT) 观察图4.2.4不难发现,第L级共有2L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下:L=1时,WpN=WJN/4=WJ2L,J=0L=2时,WpN=WJN/2=WJ2L,J=0,1L=3时,WpN=WJN=WJ2L,J=0,1,2,3对N=2M的一般情况,第L级的旋转因子为(4.2.12)(4.2.13)18第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 3.蝶形运算规律设序列x(n)经时域抽选(倒序)后,存入数组X中。如果蝶形运算的两个输入数据相距B个点,应用原位计算,则蝶形运算可表示成如下形式:X(J)XL-1(J)+XL-1(J+B)WpNXL(
8、J+B)XL-1(J)-XL-1(J+B)WpN式中p=J2M-L;J=0,1,,2L-1-1;L=1,2,,M19第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 下标L表示第L级运算,XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算,可按下面的算法进行。设T=XL-1(J+B)WpN=TR+jTIXL-1(J)=XR(J)+jXI(J)式中下标R表示取实部,I表示取虚部,20第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 则21第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.编程思想及程序框图图4.2.6DITFFT运算和程序框图22第第4章
9、章 快速傅里叶变换快速傅里叶变换(FFT) 5.序列的倒序DITFFT算法的输入序列的排序看起来似乎很乱,但仔细分析就会发现这种倒序是很有规律的。由于N=2M,所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。图4.2.7形成倒序的树状图(N=23)23第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 表4.2.1顺序和倒序二进制数对照表24第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.8倒序规律25第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.9倒序程序框图26第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.2.5频域抽取法FFT(DIFF
10、FT)在基2快速算法中,频域抽取法FFT也是一种常用的快速算法,简称DIFFFT。设序列x(n)长度为N=2M,首先将x(n)前后对半分开,得到两个子序列,其DFT可表示为如下形式:27第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 偶数奇数将X(k)分解成偶数组与奇数组,当k取偶数(k=2r,r=0,1,N/2-1)时(4.2.14)28第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 当k取奇数(k=2r+1,r=0,1,N/2-1)时(4.2.15)将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式,可得(4.2.16)29第第4章章 快速傅里叶变换快速傅里叶变换
11、(FFT) 图4.2.10DIFFFT蝶形运算流图符号30第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.11DIFFFT一次分解运算流图(N=8)31第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.12DIFFFT二次分解运算流图(N=8)32第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.13DIFFFT运算流图(N=8)33第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.14DITFFT的一种变形运算流图34第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.15DITFFT的一种变形运算流图35第第4章章 快速傅里叶变换
12、快速傅里叶变换(FFT) 4.2.6IDFT的高效算法上述FFT算法流图也可以用于离散傅里叶逆变换(InverseDiscreteFourierTransform,简称IDFT)。比较DFT和IDFT的运算公式:36第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.16DITIFFT运算流图37第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.2.17DITIFFT运算流图(防止溢出)38第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 如果希望直接调用FFT子程序计算IFFT,则可用下面的方法:由于对上式两边同时取共轭,得39第第4章章 快速傅里叶变换快速傅里叶变换(F
13、FT) 4.3 进一步减少运算量的措施进一步减少运算量的措施4.3.1多类蝶形单元运算由DITFFT运算流图已得出结论,N=2M点FFT共需要MN/2次复数乘法。由 (4.2.12)式 , 当 L=1时 , 只 有 一 种 旋 转 因 子W0N=1,所以,第一级不需要乘法运算。40第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 综上所述,先除去第一、二两级后,所需复数乘法次数应是从L=3至L=M共减少复数乘法次数为(4.3.1)(4.3.2)因此,DITFFT的复乘次数降至(4.3.3)41第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 42第第4章章 快速傅里叶变换快速傅里叶变换(F
14、FT) 从实数运算考虑,计算N=2M点DITFFT所需实数乘法次数为(4.3.4)43第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.3.2旋转因子的生成在FFT运算中,旋转因子WmN=cos(2m/N)-jsin(2m/N),求正弦和余弦函数值的计算量是很大的。44第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.3.3实序列的FFT算法设x(n)为N点实序列,取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部,即对y(n)进行N/2点FFT,输出Y(k),则根据DITFFT的思想及式(4.2.7)和(4.2.8),可得到45第第4章章 快速傅里叶变换快速傅里叶变
15、换(FFT) 由于x(n)为实序列,所以X(k)具有共轭对称性,X(k)的另外N/2点的值为46第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.4 分裂基分裂基FFT算法算法 4.4.1分裂基FFT算法原理当n=pq,且p=N/4,q=4时,n可表示为并有47第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 再将上式中的k表示为48第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 可得对k0=0,1,2,3,并用k表示k1,用n表示n0,可以写出49第第4章章 快速傅里叶变换快速傅里叶变换(FFT) (4.4.1)50第第4章章 快速傅里叶变换快速傅里叶变换(FFT) (4.4.2
16、)51第第4章章 快速傅里叶变换快速傅里叶变换(FFT) (4.4.3)令52第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 则(4.4.2)式可写成如下更简明的形式:(4.4.4)53第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.1分裂基第一次分解L形流图54第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 例如,N=16,第一次抽选分解时,由式(4.4.3)得x2(n)=x(n)+x(n+8),0n7x14(n)=x(n)-x(n+8)-jx(n+4)-x(n+12)Wn16,0n3x24(n)=x(n)-x(n+8)+jx(n+4)-x(n+12)W3n16,0n3
17、把上式代入式(4.4.4),可得X(2k)=DFTx2(n),0k7X(4k+1)=DFTx14(n),0k3X(4k+3)=DFTx24(n),0k355第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.2分裂基FFT算法L形排列示意图与结构示意图(a)分裂基FFT算法L形排列示意图;(b)分裂基FFT算法运算流图结构示意图56第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.316点分裂基第一次分解L形流图(图中省去箭头)57第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 第二次分解:先对图4.4.3中N/2点DFT进行分解。令X1(l)=X(2l),则有X1(
18、2l)=DFTy2(n),0l3X1(4l+1)=DFTy14(n),0l1X1(4l+3)=DFTy24(n),0l158第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 其中y2(n)=x2(n)+x2(n+4),0n3y14(n)=x2(n)-x2(n+4)-x2(n+2)x(n+6)Wn8,n=0,1y24(n)=x2(n)-x2(n+4)+jx2(n+2)x2(n+6)W3n8,n=0,159第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.4图4.4.4中N/2点DFT的分解L形流图60第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.54点分裂基L形运算
19、流图61第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.4.616点分裂基FFT运算流图62第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.4.2分裂基FFT算法的运算量设第j级有lj个L形,j=1,2,M-1,M=log2N,则有l1=N/4。由图4.4.2(b)可见,第j-1列中的L形包含了第j列中的一部分结点的计算,即空白部分,所占结点数刚好等于第j-1列中所有L形对应结点的一半,所以第j列L形个数就减少lj-1/2个,即63第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 64第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 由于每个L形有两次复(数)乘运算,所以
20、全部复乘次数为(4.4.5)65第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5 离散哈特莱变换离散哈特莱变换(DHT) 4.5.1离散哈特莱变换定义设x(n),n=0,1,N-1,为一实序列,其DHT定义为式中,cas()=cos+sin。其逆变换(IDHT)为(4.5.3)66第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 逆变换证明如下:(4.5.4)67第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 将式(4.5.2)代入式(4.5.3)得68第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.2DHT与DFT之间的关系为了便于比较,重写DFT如下:(4.5.
21、5)(4.5.6)容易看出,DHT的核函数DFT的核函数的实部与虚部之和。69第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 将XH(k)分解为奇对称分量XHo(k)与偶对称分量XHe(k)之和(4.5.7)(4.5.8)(4.5.9)由DHT定义有(4.5.10a)(4.5.10b)70第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 所以,x(n)的DFT可表示为同理,x(n)的DHT可表示为因此,已知x(n)的DHT,则DFT可用下式求得:(4.5.11)(4.5.12)(4.5.13)71第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.3DHT的主要优点(1)DHT是
22、实值变换,在对实信号或实数据进行谱分析时避免了复数运算,从而提高了运算效率,相应的硬件也更简单、更经济;(2)DHT的正、反变换(除因子1/N外)具有相同的形式,因而,实现DHT的硬件或软件既能进行DHT,也能进行IDHT;(3)DHT与DFT间的关系简单,容易实现两种谱之间的相互转换。72第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.4DHT的性质1.线性性质(4.5.14)2.x(N-n)的DHT(4.5.15)其中,当k=0时,XH(N-k)=XH(N)=XH(0)。73第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 证明由DHT定义而74第第4章章 快速傅里叶变换快速
23、傅里叶变换(FFT) 3.循环移位性质(4.5.16)(4.5.17)证明由DHT定义有75第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 76第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.奇偶性奇对称序列和偶对称序列的DHT仍然是奇对称序列或偶对称序列,即DHT不改变序列的奇偶性。5.循环卷积定理(4.5.18)(4.5.19)77第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 证明下面利用DFT的循环卷积定理和DHT与DFT之间的关系来证明其中,X1(k)=DFTx1(n),X2(k)=DFTx2(n),根据DHT与DFT之间的关系,则有78第第4章章 快速傅里叶变换快速
24、傅里叶变换(FFT) 将上面两式代入式(4.5.20)并整理后,得所以式(4.5.18)成立。同理可证明式(4.5.19)亦成立。当x1(n)或x2(n)是偶对称序列时,则由DHT的奇偶性有(4.5.21)79第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.5DHT的快速算法(FHT)1.基2DITFHT算法及运算流图仿照快速DFT的分解方法,可通过时域抽取或频域抽取的方式实现快速DHT。x(n)的N=2M点DHT如下式:对x(n)进行奇偶抽取(4.5.22)(4.5.23)80第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 与DFT的时域抽取分解比较,不是一个指数函数,所以处
25、理要比W(2r+1)kN麻烦一些。根据三角公式有(4.5.24)(4.5.25)81第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 令X0H(k)=DHTx0(n),X1H(k)=DHTx1(n),并考虑DHT的周期性,(4.5.25)式可写成为了使以下推导中公式简明,记C(k)=cos(2/N)k,S(k)=sin(2/N)/k。将式(4.5.26)中的k分别取k,N/2+k,N/2-k和N-k四个值,并考虑X0H(k)和X1H(k)以N/2为周期,得到82第第4章章 快速傅里叶变换快速傅里叶变换(FFT) (4.5.27)83第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 当k=0
26、时,式(4.5.27)中有重复,可单独写成(4.5.28)同理,在k=N/4时有(4.5.29)84第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.5.1基2DIT-FHT原理和哈特莱碟形85第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.5.24点DFHT蝶形图86第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 图4.5.316点基2DITFHT流图87第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 2.基2DITFHT的运算量观察图4.5.3可知,运算流图中都是实数运算。N=2M点FHT流图共分为M级。用L表示流图自右向左的蝶形级数。第L级乘法次数为2L(N/2L-2),但最后二级无乘法运算,所以,总的乘法次数MH为(4.5.30)(4.5.31)同理可求得总的加法次数AH为88第第4章章 快速傅里叶变换快速傅里叶变换(FFT) 4.5.6实信号的快速循环卷积用DITFFT计算两个实信号x1(n)和x2(n)的循环卷积时,最直接的方法是将信号的虚部都置为零,再按复序列用FFT计算。显然这样做是很浪费的。现在我们可用基2DITFHT直接进行实正交变换来处理实信号的循环卷积问题。计算式(4.5.18)89