快速傅里葉變換(FFT)原理及源程序.doc

《快速傅里葉變換(FFT)原理及源程序.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、《測(cè)試信號(hào)分析及處理》課程作業(yè)快速傅里葉變換一、程序設(shè)計(jì)思路快速傅里葉變換的目的是減少運(yùn)算量，其用到的方法是分級(jí)進(jìn)行運(yùn)算。全部計(jì)算分解為級(jí)，其中；在輸入序列中是按碼位倒序排列的，輸出序列是按順序排列；每級(jí)包含個(gè)蝶形單元，第級(jí)有個(gè)群，每個(gè)群有個(gè)蝶形單元；每個(gè)蝶形單元都包含乘和系數(shù)的運(yùn)算，每個(gè)蝶形單元數(shù)據(jù)的間隔為，i為第i級(jí)；同一級(jí)中各個(gè)群的系數(shù)分布規(guī)律完全相同。將輸入序列按碼位倒序排列時(shí)，用到的是倒序算法——雷德算法。自然序排列的二進(jìn)制數(shù)，其下面一個(gè)數(shù)總比上面的數(shù)大1，而倒序二進(jìn)制數(shù)的下面一個(gè)數(shù)是上面一個(gè)數(shù)在最高位加1并由高位向低位僅為而得到的。若已知某數(shù)的倒序數(shù)是，求下一個(gè)倒序數(shù)

2、，應(yīng)先判斷的最高位是否為0，與進(jìn)行比較即可得到結(jié)果。如果，說(shuō)明最高位為0，應(yīng)把其變成1，即，這樣就得到倒序數(shù)了。如果，即的最高位為1，將最高位化為0，即，再判斷次高位；與進(jìn)行比較，若為0，將其變位1，即，即得到倒序數(shù)，如果次高位為1，將其化為0，再判斷下一位……即從高位到低位依次判斷其是否為1，為1將其變位0，若這一位為0，將其變位1，即可得到倒序數(shù)。若倒序數(shù)小于順序數(shù)，進(jìn)行換位，否則不變，防治重復(fù)交換，變回原數(shù)。注：因?yàn)?的倒序數(shù)為0，所以可從1開(kāi)始進(jìn)行求解。二、程序設(shè)計(jì)框圖（1）倒序算法——雷德算法流程圖(2)FFT算法流程一、FFT源程序voidfft(x,n)intn;d

3、oublex[];{inti,j,k,l,m,n1,n2;doublec,c1,e,s,s1,t,tr;for(j=1,i=1;i

4、=j+k;//把0改為1}for(i=0;i

5、算系數(shù)不同的蝶形結(jié){i1=i+j;i2=i-j+n2;i3=i+j+n2;i4=i-j+n1;cc=cos(a);ss=sin(a);a=a+e;t1=cc*x[i3]+ss*x[i4];t2=ss*x[i3]-cc*x[i4];x[i4]=x[i2]-t2;x[i3]=-x[i2]-t2;x[i2]=x[i1]-t1;x[i1]=x[i1]+t1;}}}}一、計(jì)算實(shí)例及運(yùn)行結(jié)果設(shè)輸入序列為其離散傅里葉變換為這里。選n=512,計(jì)算離散傅里葉變換。所用軟件為T(mén)urboc2.0，操作界面如圖1所示圖1Turboc2.0操作界面程序運(yùn)行結(jié)束后的界面如圖2所示圖2程序運(yùn)行后的界面例子的

6、具體程序如下：#include#include#include#definepi3.14159265359voidfft(x,n)intn;doublex[];{inti,j,k,l,i1,i2,i3,i4,n4,m,n1,n2;doublea,e,cc,ss,tr,t1,t2;for(j=1,i=1;i

7、(j+1)){j=j-k;k=k/2;}j=j+k;}for(i=0;i