基2与基4时分FFT算法浅析及其比较.doc

基2与基4时分FFT算法浅析及其比较学生姓名：田秀军 指导教师：王川龙摘要：在简要介绍快速傅里叶变换（FFT）相关知识的基础上，研究离散傅里叶变换（DFT）的算法，包括DFT的直接算法、基2时分FFT算法和基4时分FFT算法，并就各算法给出了复杂度分析，并进行了算法间的比较。关键词：FFT；基2时分蝶式运算定理；基2时分FFT；基4时分FFT引言：傅里叶变换作为图像分析的重要工具和数字信号处理的重要内容，在图像处理、语音分析、雷达、声呐、地震、通讯系统、遥感遥测、地质勘探、航空航天、生物医学等众多领域都有着极其广泛的应用。于是傅里叶变换的快速算法就有了至关重要的意义。1、基础知识1.1、离散傅里叶变换（DFT）为了在科学计算和数字信号处理等领域使用计算机进行傅立叶变换，必须将函数定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅立叶变换。定义1：称 Keg(k,n)=Wr(n) (1.1.1)为N点典型有限序列，式中，W是周期单位复指数序列 W=e (1.1.2)r(n)是单位矩形序列 r(n)= (1.1.3)k为归一化数字频率。定义2：对长度为N的复序列x(n),称 X(k)=，k=0,1,N-1 (1.1.4)为序列A的离散傅里叶变换（DFT）。1.2、快速离散傅里叶变换（FFT）快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。1.3、基2时分蝶式运算定理内容：设X(k)=DFTx(n)(0n,kN-1,n,k,为整数，N为偶数)，x(i)=x(2i)，x(i)=x(2i+1)(0i-1，i为整数)。若X(k)=DFTx(i)，X(k)=DFTx(i)，0k-1，则 (1.3.1)证明：若0k-1，则X(k)=+ =+W 由于W=e= e= W 因此，由（1.3.2）式可得X(k)= +W = 由于= 而W=e=e=-1因此=+= -W= (证毕)。1.4、多基时分蝶式运算定理内容：设X(k)=DFTx(n),0n,kN-1,n,k为整数，N=pq，p和q为大于1的正整数。x(i)=x(ip+m),i=0,1,，q-1；m=0,1,p-1。若XI=DFTx(i),r=0,1,q-1,则X(k)=X(sq+r)= (1.4.1)（0kN-1,0sp-1,0rq-1,k,s,r均为整数）证明： X(k)=X(sq+r)= = =（0kN-1,0sp-1,0rq-1,k,s,r均为整数）（证毕）。2、DFT的直接算法2.1、算法直接按DFT的定义式进行计算：按照DFT的定义式有 X(k)= (2.1.1)（k=0,1,N-1）通常所遇到的序列都是实序列，因此 X(k)= (2.1.2)=U(k)-jV(k) （k=0,1,N-1） (2.1.3)式中 U(k) = （k=0,1,N-1） (2.1.4) V(k)= （k=0,1,N-1） (2.1.5)2.2、复杂度分析在整个计算过程中，若不考虑正弦函数和余弦函数的计算量，则直接计算N点DFT所需要的复数乘法次数M和复数加法次数A，由（1.1.1）式容易求得M=N (2.2.1)A=N(N-1)N (2.2.2)由于x(n)是实序列，而仅仅是复数，因此上述复数乘法实际上是实数和复数相乘。易知，这样的一次复数乘法相当于两次实数乘法。因此，所需要的实数乘法次数 M=2N (2.2.3)由于1次复数加法运算相当于2次实数相加，因此所需要的实数加法次数A=2N(N-1)2N (2.2.4)在x(n)为复序列的一般情况下，由于两个复数相乘需要4次实数相乘和2次实数相加，因此与（2.2.1）是相当的实数乘法次数为 M=4N (2.2.5)同时需要的实数加法次数 =2 N (2.2.6)考虑到（2.2.3）式所需要的实数加法次数，因此，总共所需要的实数加法次数 A4N (2.2.7)由此可见，无论是复数运算次数还是实数运算次数都表明，直接计算DFT时的运算量与N成正比。当N较大时，如N=2048，运算量将是巨大的，运算时间长。3、基2时分FFT算法3.1、基本思想与原理 基2 FFT算法是把长度N=2的序列一分为二，将N点D FT表示为两个N /2点D FT的线性组合。然后再把N /2点D FT一分为二，表示为两个N /4点的D FT。如此重复下去，直至分解成两点DFT的运算，两点D FT实际上只是加减运算。1.3节中的基2时分蝶式运算定理是基2时分FFT算法的基础。相应的运算称为蝶式运算。相应的运算流图称为运算蝶。基2时分蝶式运算定理表明：若将任何一偶数点序列按n的奇偶性分为两个子列，则原序列的DFT可由两子序列DFT的线性组合得到。3.2、算法将x(n)(n=0,1,2,N一1)按n的奇偶分成以下两组:x (2r=x(r) r =0,1,2,(N/2)一1; （3.2.1）x(2r+1)=x(r) r =0,1,2,(N/2)一1 (3.2.2)将以上两式带入(1.1.4)式并化简就得到以下(3.2.3)式和(3.2.4)式。这样N点序列X(k)就变成了两个N /2点序列x(r)和x(r)离散傅立叶变换的组合: k=0,1,2,(N/2)一1 (3.2.3) k=0,1,2,(N/2)一1 (3.2.4)对于和可以继续利用（3.2.3）式和（3.2.4）式进一步分解，直到变换停止。3.3、复杂度分析由蝶式运算定理，计算偶数N点的DFT，可先计算两个点子序列的DFT，然后由蝶式运算，得到所需的结果。若各子序列DFT的计算应用直接计算法，则由2.2节的讨论可知，它们的复数乘法和加法次数分别为和。又每1次蝶式运算只需1次复数乘法和2次复数加法。因为k取中的个整数值，即总共有次蝶式运算，因此，蝶式运算共需要复数乘法和N次复数加法。对于N=2的情形，第一次分解得到的子序列的长度为2，第二次分解后子序列的长度为2，若要求最后子序列的长度为1=2，则一共需做=logN次分解。因此，总共需要的复数乘法次数和复数加法次数分别为 M=logN (3.3.1) A=NlogN (3.3.2)4、基4时分FFT算法4.1、基本思想与原理基4FFT算法是把长度N=4的序列一分为四，将N点D FT表示为4个N /4点D FT的线性组合。然后再把N /4点D FT一分为四，表示为四个N /16点的D FT。如此重复下去，直至分解成两点DFT的运算。1.4节中的多基时分蝶式运算定理是基4时分FFT算法的基础。多基时分蝶式运算定理在形式上比基2时分碟式运算定理复杂，但在本质上是一致的。前者表明：对N=pq的情形，若按x(i)=x(ip+m)将原N点序列分解成p个q点的子序列，则原序列x(n)的DFT可由各子序列x(i)的DFT的线性组合得到。基4时分FFT算法是多基算法的特例，因此从多基时分FFT的蝶式运算定理即可推导出基4时分FFT算法的蝶式运算公式。4.2、算法设p=4,q=4。这时由多基时分蝶式运算定理，输入序列x(n)可以分解成如下的4个子序列x(i)=x(4i+m) (4.2.1)子序列x(i)均为点序列，设它们的点DFT为X(r)，则由（1.4.1）式可得X(k)=X= (4.2.2)（0kN-1,0s3,0r-1,k,s,r均为整数）将s=0,1,2,3代入上式，则 (4.2.3)上式就是基4时分蝶式运算公式。其具体算法和基2时分FFT算法相近，略过。4.3、复杂度分析（4.2.3）式可以简化成下式 (4.3.1)从上式可以看出，基4运算需要3次复数乘法和12次复数加法。若令 (4.3.2)则由（4.3.1）式可以得到 (4.3.3)通过以上改变，容易看出，复数加法次数从12次下降到8次。另外，每个运算蝶有4点输入和4点输出，因此总共有个运算蝶。由于每一个蝶式运算仅需3次复数乘法和8次复数加法，因此，对每一次分解，蝶式运算所需的复数乘法次数和复数加法次数分别为N次和2N次。在N=4（为正整数）的一般情形下，N点序列分解成一点序列需要作=logN次分解，因此，基4时分FFT算法所需要的复数乘法次数为M=NlogN (4.3.4)A=2NlogN (4.3.5)5、三种算法的比较衡量算法好坏的一个重要指标就是运算量的大小。5.1、DFT的直接算法和基2时分FFT算法的比较由（2.2.1）和（2.2.2）式与（3.3.1）和（3.3.2）式，DFT的直接算法和基2时分FFT算法的复数乘法之比为a= (5.1.1)复数加法之比为a= (5.1.2)若N=2，则a，a，即运算量分别为原来的和。由此可见，运算量上基2时分FFT算法比DFT的直接算法节省了很多。5.2基2时分FFT算法和基4时分FFT算法的比较为了好比较，此处取N=4用基2时分FFT算法，由（3.3.1）和（3.3.2）式，N=2，则需要的复数乘法次数为=NlogN (5.2.1)复数加法次数为=2NlogN (5.2.2)分别比较（5.2.1）式和（4.3.4）式与（5.2.2）式和（4.3.5）式，可以看出，基2时分FFT算法和基4时分FFT算法由相同的复数加法次数，但基4时分FFT算法的复数乘法仅为基2时分FFT算法的3/4。由此可见，基4时分FFT算法的运算量较少。综上，从运算量角度来说，基4时分FFT算法最好，基2时分FFT算法次之，DFT的直接算法最差。但由于基4时分FFT算法要求N=4，相应的变换长度N更少，灵活性就不如基2时分FFT算法。参考文献1 毕文义,姜建国,罗笑南.基2基4基8型FFT算法计算量的极小化及其证明C.上海:上海市计算技术研究所,1987:21-222 杜义君.按时间抽取基2的FFT算法的实现J.塔里木大学学报,2007.6,19(2):85-863 甘秋歌.快速傅里叶变换(FFT)的另一种推导方法及实现J,西南民族大学学报(自然科学版).2007,33(2):275-2784 季虎,夏胜平,郁文贤.快速傅立叶变换算法概述J,现代电子技术报,2001,8:11-125 蒋长锦,蒋勇.快速傅里叶变换及其C程序M.合肥:中国科学技术大学出版社,2004.7:111-1206 蒋尔雄,赵风光.数值逼近M.上海:复旦大学出版社,1996.7:209-2147 冷建华.傅里叶变换M.北京:清华大学出版社,2004:165-1748 毛俊,张学智.快速傅立叶变换算法的比较J,西安工业学院学报,2002,22(2):1079 戎洪军,焦良葆.快速傅立叶变换算法的比较分析J,中国新技术新产品报,2009,21:24110 史贤勇,陈子为.基于BF533的基4FFT算法的DSP实现J,成都信息工程学院学报.2006,21(增):43-4411 汪家云,吴升昌.快速傅里叶变换和IBM3838的快速傅里叶变换算法分析C:30-3312 王秋卉.基2FFT算法的研究与改进J.西南交通大学学报,1994,29(6):647-64813 张登奇,李宏民,李丹.按时间抽取的基2FFT算法分析及MATLAB实现D.电子技术研发报：75-7614 Bracewell,R.N.The Fourier Transform and Its ApplicationsM.北京:机械工业出版社,2002:275-28015 James W.Cooley. The Re-Discovery of the Fsat Fourier Trandform AlgorithmJ.USA:Thomas J.Watson Research Center,1987,3:36-38The analysis and compare ofbase-2 and base-4 time division FFT algorithmStudent: tian xiujun Tutor: wang chuanlongAbstract: On the basis of the brief introduction of the related knowledge of FFT, we discuss the algorithm of DFT, include direct algorithm of DFT，b