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

基2与基4时分FFT算法浅析及其比较 学生姓名:田秀军 指导教师:王川龙 摘要:在简要介绍快速傅里叶变换,FFT,相关知识的基础上～研究离散傅里叶变换,DFT,的算法～包括DFT的直接算法、基2时分FFT算法和基4时分FFT算法～并就各算法给出了复杂度 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ～并进行了算法间的比较。 关键词:FFT,基2时分蝶式运算定理,基2时分FFT,基4时分FFT 引言:傅里叶变换作为图像分析的重要工具和数字信号处理的重要内容，在图像处理、语音分析、雷达、声呐、地震、通讯系统、遥感遥测、地质勘探、航空航天、生物医学等众多领域都有着极其广泛的应用。于是傅里叶变换的快速算法就有了至关重要的意义。 1、基础知识 1.1、离散傅里叶变换,DFT, 为了在科学计算和数字信号处理等领域使用计算机进行傅立叶变换，必须将函数定义在离散点而非连续域内，且须满足有限性或周期性条件。这种情况下，使用离散傅立叶变换。 定义1:称 -nk Keg(k,n)=Wr(n) (1.1.1) NN 为N点典型有限序列， -nk式中，W是周期单位复指数序列 N 2,jnk-nkN W=e (1.1.2) N r(n)是单位矩形序列 N 1,n,0,1,2,？,N-1, r(n)= (1.1.3) ,N0,其他整数, k为归一化数字频率。 定义2:对长度为N的复序列x(n),称 N,1nkx(n)W X(k)=，k=0,1,…,N-1 (1.1.4) ,Nn,0 为序列{A}的离散傅里叶变换(DFT)。 k 1.2、快速离散傅里叶变换,FFT, 快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。 1 1.3、基2时分蝶式运算定理 内容:设X(k)=DFT[x(n)](0n,kN-1,n,k,为整数，N为偶数)，x(i)=x(2i)，,,0 Nx(i)=x(2i+1)(0i-1，i为整数)。若X(k)=DFT[x(i)]，X(k)=DFT[x(i)]，,,001112 N0k-1，则 ,,2 k,,，X(k)X(k)X(k)W01NN,,,0,k,,1，k为整数 (1.3.1) ,,,N,,k2，,,XkX(k)X(k)W,,,,01N,2,,, N证明:若0k-1，则 ,,2 NN,1,1,1N22nk2(2，1)ikikx(n)WX(k)==+ x(2i)Wx(2i，1)W,N,,NNn,0,0,0ii NN,1,122N,,k22ikik0,k,,1=+W x(i)Wx(i)W,,,,N01NN2,,,0,0ii 由于 ,2,j,ki2N,,j,2ikN,,2ikik2N0,i,k,,1W=e= e= W ,,NN22,, 因此，由(1.3.2)式可得 NN,1,122kikikX(k)= +W x(i)Wx(i)W,,N01NN22,0,0ii N,,k0,k,,1 = X(k)，X(k)W,,01N2,, 由于 N,,N,1N1,Nnk，,,nNN,,,,nk2,,2WXk，x(n)W0,k,,1=x(n)W= ,,,,,NN,N22,,,,n,00,n 而 2NN,-j,,j,2N2W=e=e=-1 N 因此 N,1N,,nnkx(n)(-1)WXk，= ,,,N2,,n0, NN1,1,222i2ik2i，1(2i，1)k=+ x(2i)(-1)Wx(2i，1)(-1)W,,NNn,0n0, 2 NN,1,122kikik= -W x(i)Wx(i)W,,N01NN22,0,0ii N,,k0,k,,1 (证毕)。 =X(k),X(k)W,,01N2,,1.4、多基时分蝶式运算定理 内容:设X(k)=DFT[x(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=DFT[x(i)],r=0,1,…,q-1,则 mmm ,1p(，)msqrWX(r)X(k)=X(sq+r)= (1.4.1) ,Nmk,sq，r,0m ,,,,,(0kN-1,0sp-1,0rq-1,k,s,r均为整数) , p,1n(sq，r)Wx(n)证明: X(k)=X(sq+r)= ,Nk,sq，rm,0 p,1q,1(ip，m)(sq，r)x(ip，m)Wn,ip，m ,,Nm,0i,0 p,1q,1ispqirpm(sq，r)x(i)WWW = ,,mNNNm,0i,0 ,1,1,1pqp(sq，r)(，)mirmsqrWx(i)WWX(r) == ,,,NmqNm,0,0,0mim ,,,,,(0,kN-1,0sp-1,0rq-1,k,s,r均为整数)(证毕)。 2、DFT的直接算法 2.1、算法 直接按DFT的定义式进行计算: 按照DFT的定义式有 N,1N,12,2,,,nkx(n)Wxnnkjnk()cos,sin X(k)== (2.1.1) ,,,,NNN,,n,0n,0 (k=0,1,…,N-1) 通常所遇到的序列都是实序列，因此 N,1N,12,2,xnnk,jxnnk()cos()sin X(k)= (2.1.2) ,,NNn,0n,0 =U(k)-jV(k) (k=0,1,…,N-1) (2.1.3) 式中 N,12,xnnk()cos U(k) = (k=0,1,…,N-1) (2.1.4) ,Nn,0 3 N,12,xnnk()sin V(k)= (k=0,1,…,N-1) (2.1.5) ,Nn,0 2.2、复杂度分析 在整个计算过程中，若不考虑正弦函数和余弦函数的计算量，则直接计算N点DFT所需要的复数乘法次数M和复数加法次数A，由(1.1.1)式容易求得 cc 2M=N (2.2.1) c 2A=N(N-1)N (2.2.2) ,c nk由于x(n)是实序列，而仅仅是复数，因此上述复数乘法实际上是实数和复数相乘。易知，WN 这样的一次复数乘法相当于两次实数乘法。因此，所需要的实数乘法次数 2 M=2N (2.2.3) r 由于1次复数加法运算相当于2次实数相加，因此所需要的实数加法次数 2A=2N(N-1)2N (2.2.4) ,r 在x(n)为复序列的一般情况下，由于两个复数相乘需要4次实数相乘和2次实数相加，因此与(2.2.1)是相当的实数乘法次数为 2 M=4N (2.2.5) r 同时需要的实数加法次数 2 =2 N (2.2.6) A'r 考虑到(2.2.3)式所需要的实数加法次数，因此，总共所需要的实数加法次数 2 A4N (2.2.7) ,r 由此可见，无论是复数运算次数还是实数运算次数都 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明，直接计算DFT时的运算量 2与N成正比。当N较大时，如N=2048，运算量将是巨大的，运算时间长。 3、基2时分FFT算法 3.1、基本思想与原理 l 基2 FFT算法是把长度N=2的序列一分为二，将N点D FT表示为两个N /2点D FT的线性组合。然后再把N /2点D FT一分为二，表示为两个N /4点的D FT。如此重复下去， 4 直至分解成两点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) 1 x(2r+1)=x(r) r =0,1,2,…,(N/2)一1 (3.2.2) 2 将以上两式带入(1.1.4)式并化简就得到以下(3.2.3)式和(3.2.4)式。这样N点序列X(k)就变成了两个N /2点序列x(r)和x(r)离散傅立叶变换的组合: 12 k k=0,1,2,…,(N/2)一1 (3.2.3) X(k),X(k)，X(k)W01N N,,kXk，,X(k),X(k)W k=0,1,2,…,(N/2)一1 (3.2.4) ,,01N2,, 对于和可以继续利用(3.2.3)式和(3.2.4)式进一步分解，直到变换停X(k)X(k)01 止。 3.3、复杂度分析 N由蝶式运算定理，计算偶数N点的DFT，可先计算两个点子序列的DFT，然后由蝶2 式运算，得到所需的结果。若各子序列DFT的计算应用直接计算法，则由2.2节的讨论可 2NNN,,,,-1知，它们的复数乘法和加法次数分别为和。又每1次蝶式运算只需1次复,,,,222,,,, NNN，，0，-1数乘法和2次复数加法。因为k取中的个整数值，即总共有次蝶式运算，,,222，， N因此，蝶式运算共需要复数乘法和N次复数加法。 2 ll,1对于N=2的情形，第一次分解得到的子序列的长度为2，第二次分解后子序列的长 l,20，若要求最后子序列的长度为1=2，则一共需做=logN次分解。 度为2l2 因此，总共需要的复数乘法次数和复数加法次数分别为 NN M==logN (3.3.1) lc222 Nl A==NlogN (3.3.2) c2 4、基4时分FFT算法 5 4.1、基本思想与原理 l基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点的子序列，，m 则原序列x(n)的DFT可由各子序列x(i)的DFT的线性组合得到。 m 基4时分FFT算法是多基算法的特例，因此从多基时分FFT的蝶式运算定理即可推导出基4时分FFT算法的蝶式运算 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 。 4.2、算法 Nl,1设p=4,q==4。这时由多基时分蝶式运算定理，输入序列x(n)可以分解成如下的44 个子序列 N,,m,0,1,2,3;0,i,,1,i为整数x(i)=x(4i+m) (4.2.1) ,,m4,, NN子序列x(i)均为点序列，设它们的点DFT为X(r)，则由(1.4.1)式可得 mm44 N,,3，msr,,N,,4,,s +rX(k)=X=WX(r) (4.2.2) ,,,NNmk,sr4,,,m04 N,,,,,(0kN-1,0s3,0r-1,k,s,r均为整数) ,4 将s=0,1,2,3代入上式，则 rrr23,,，，，X(r)X(r)WX(r)WX(r)WX(r)NNN0123,NNN,,,,,,rrr，，，23,,,,,,,N,,444,,,,,,Xr，,X(r)，WX(r)，WX(r)，WX(r),,NNN,01234,,,,NNN,,,,,, (4.2.3) r，r，r，23,,,,,,,N,,222,,,,,,Xr，,X(r)，WX(r)，WX(r)，WX(r),,,NNN01232,,, NNN333,,,,,,,rrr，，，23,,,,,,3N,,444,,,,,,,XrX(r)WX(r)WX(r)WX(r)，,，，，,,NNN0123,4,,, N,,0,r,,1，r为整数 ,,4,, 上式就是基4时分蝶式运算公式。其具体算法和基2时分FFT算法相近，略过。 4.3、复杂度分析 (4.2.3)式可以简化成下式 6 r2r3r,(),()，()，()，()XrXrWXrWXrWXr0N1N2N3,N,,r2r3r,Xr，,X(r),jWX(r),WX(r)，jWX(r),,0N1N2N3,4,,, (4.3.1) ,N,,r2r3rXr，,X(r),WX(r)，WX(r),WX(r),,NNN0123,2,,, ,3N,,rrr23XrXrWXrWXrjWXr，,()，j(),(),(),,,0N1N2N34,,,从上式可以看出，基4运算需要3次复数乘法和12次复数加法。若令 2r,UrXrWXr(),()，()00N2,r3rU(r),WX(r)，WX(r)N,,,1N1N30,r,,1，r为整数 (4.3.2) ,,,2r4U(r),X(r),WX(r),,,20N2 ,rr3U(r),WX(r),WX(r)3N1N3, 则由(4.3.1)式可以得到 X(r),U(r)，U(r),01,N,,,Xr，,U(r),jU(r),,23,4,,N,,,0,r,,1，r为整数 (4.3.3) ,,N,,,4Xr，,U(r),U(r),,,,01,2,,, ,3N,,XrUrjUr，,()，(),,23,4,,, 通过以上改变，容易看出，复数加法次数从12次下降到8次。 N另外，每个运算蝶有4点输入和4点输出，因此总共有个运算蝶。由于每一个蝶式4 运算仅需3次复数乘法和8次复数加法，因此，对每一次分解，蝶式运算所需的复数乘法 3次数和复数加法次数分别为N次和2N次。 4 l在N=4(l为正整数)的一般情形下，N点序列分解成一点序列需要作l=logN次分4解，因此，基4时分FFT算法所需要的复数乘法次数为 3M=NlogN (4.3.4) c44 A=2NlogN (4.3.5) c4 5、三种算法的比较 衡量算法好坏的一个重要指标就是运算量的大小。 5.1、DFT的直接算法和基2时分FFT算法的比较 由(2.2.1)和(2.2.2)式与(3.3.1)和(3.3.2)式，DFT的直接算法和基2时分FFT算法的复数乘法之比为 7 NlogN212a== (5.1.1) logN2M22NN 复数加法之比为 NlogN12a= (5.1.2) logN,2A2NN 111110若N=2，则a，a，即运算量分别为原来的和。由此可见，运,,MA200100200100算量上基2时分FFT算法比DFT的直接算法节省了很多。 5.2基2时分FFT算法和基4时分FFT算法的比较 l为了好比较，此处取N=4 2l用基2时分FFT算法，由(3.3.1)和(3.3.2)式，N=2，则需要的复数乘法次数为 N,==NlogN (5.2.1) M,2lc42 复数加法次数为 ,=2NlogN (5.2.2) Ac4 分别比较(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的 l直接算法最差。但由于基4时分FFT算法要求N=4，相应的变换长度N更少，灵活性就不如基2时分FFT算法。 参考文献 [1] 毕文义,姜建国,罗笑南.基2基4基8型FFT算法计算量的极小化及其证明[C].上海:上海市计算技术研究所,1987:21-22 [2] 杜义君.按时间抽取基2的FFT算法的实现[J].塔里木大学学报,2007.6,19(2):85-86 [3] 甘秋歌.快速傅里叶变换(FFT)的另一种推导 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 及实现[J],西南民族大学学报(自然科学版).2007,33(2):275-278 [4] 季虎,夏胜平,郁文贤.快速傅立叶变换算法概述[J],现代电子技术报,2001,8:11-12 [5] 蒋长锦,蒋勇.快速傅里叶变换及其C程序[M].合肥:中国科学技术大学出版社,2004.7:111-120 [6] 蒋尔雄,赵风光.数值逼近[M].上海:复旦大学出版社,1996.7:209-214 [7] 冷建华.傅里叶变换[M].北京:清华大学出版社,2004:165-174 [8] 毛俊,张学智.快速傅立叶变换算法的比较[J],西安工业学院学报,2002,22(2):107 [9] 戎洪军,焦良葆.快速傅立叶变换算法的比较分析[J],中国新技术新产品报,2009,21:241 [10] 史贤勇,陈子为.基于BF533的基4FFT算法的DSP实现[J],成都信息 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院学 8 报.2006,21(增):43-44 [11] 汪家云,吴升昌.快速傅里叶变换和IBM3838的快速傅里叶变换算法分析[C]:30-33 [12] 王秋卉.基2FFT算法的研究与改进[J].西南交通大学学报,1994,29(6):647-648 [13] 张登奇,李宏民,李丹.按时间抽取的基2FFT算法分析及MATLAB实现[D].电子技术研发 报:75-76 [14] Bracewell,R.N.The Fourier Transform and It’s Applications[M].北京:机械工业 出版社,2002:275-280 [15] James W.Cooley. The Re-Discovery of the Fsat Fourier Trandform Algorithm[J].USA:Thomas J.Watson Research Center,1987,3:36-38 The analysis and compare of base-2 and base-4 time division FFT algorithm Student: tian xiujun Tutor: wang chuanlong Abstract: On the basis of the brief introduction of the related knowledge of FFT, we discuss the algorithm of DFT, include direct algorithm of DFT，base-2 time division FFT algorithm，base-4 time division FFT algorithm.Then we come up with the complexity analysis of them and compare them with each other. Keywords: FFT; base-2 time division butterfly operation theorem; base-2 time division FFT;base-4 time division FFT 9