愛華網(wǎng)以前在博客上放的基二FFT源程序，可讀性是比較差的，現(xiàn)在已經(jīng)改過程序，從新發(fā)上去了。這幾天仔細的研究了一下基二FFT算法，受益非淺?，F(xiàn)在簡單的分析一下基二算法的原理。在VISIO里畫了程序框圖，呵呵?？墒遣恢涝趺磦魃蟻?，最后還是存為BMP格式的，傳了上來。希望對大家有所幫助。源程序見我的另一篇文章《基二FFT的C語言實現(xiàn)》
當N太大時，直接進行DFT運算，運算量會很大，這就對計算機的性能提出了很高的要求。但是利用周期性可以大大的降低運算量。利用周期性，可將N點DFT分解為兩個N/2點的DFT。同理可以對x(n)進行繼續(xù)分解，依次類推經(jīng)過M-1次分解，最后將N點DFT分解成N/2個2點的DFT。N點DFT的一次時域分解圖如圖1
根據(jù)DFT的基二分解方法，可以發(fā)現(xiàn)在第L（L表示從左到右的運算級數(shù)，L＝1，2，3…M）級中，每個蝶形的兩個輸入數(shù)據(jù)相距個點，同一旋轉(zhuǎn)因子對應著間隔為2^L點的2^(M-L)個蝶形。從輸入端開始，逐級進行，共進行M級運算。在進行L級運算時，依次求出個2^(L-1)不同的旋轉(zhuǎn)因子，每求出一個旋轉(zhuǎn)因子，就計算完它對應的所有的2^(M-L)個蝶形。因此我們可以用三重循環(huán)程序?qū)崿F(xiàn)FFT變換。同一級中，每個蝶形的兩個輸入數(shù)據(jù)只對本蝶形有用，而且每個蝶形的輸入、輸出數(shù)據(jù)節(jié)點又同在一條水平線上，所以輸出數(shù)據(jù)可以立即存入原輸入數(shù)據(jù)所占用的存儲單元。，這種方法可稱為原址計算，可節(jié)省大量的存儲單元。FFT算法的程序框圖如圖2
FFT算法的輸出X(K)為自然順序，但為了適應原位計算，其輸入序列不是按x(n)的自然順序排序，這種經(jīng)過M-1次奇偶抽選后的排序為序列的倒序。因此，在運算之前應先對序列x(n)進行倒序。倒序的規(guī)律就是把順序數(shù)的二進制位倒置，即可得到倒序值。倒序數(shù)是在M位二進制數(shù)最高位加一，逢2向右進位。對于，M位二進制數(shù)最高位的權(quán)值為N/2，且從左到右二進制位的權(quán)值依次為你N/4，N/8，···，2，1。因此，最高位加一相當于十進制運算J+N/2。（J
詳細的解釋請參考西安電子科學技術(shù)大學出版的《數(shù)字信號處理》
程序void FFT(float data[],int n,int ok)//聲明FFT函數(shù)
{
int mmax,m,j,step,i;
double temp;
double theta,sin_htheta,sin_theta,pwr,wr,wi,tempr,tempi;
n=2*(1<<n);
int nn=n>>1;
// 第一步：整理位序顛倒的次序
j=1;
for(i=1;i<n;i+=2)
{
if(j>i)
{ temp=data[j-1];
data[j-1]=data[i-1];
data[i-1]=temp;
temp=data[j];
data[j]=data[i];
data[i]=temp;
}
// 相反的二進制加法
m=nn;
while(m>=2&&j>m)
{
j-=m;
m>>=1;
}
j+=m;
}
// 程序的 Danielson - Lanczos 引理應用部分
mmax=2;
while(n>mmax) //log2(n)次循環(huán)
{
step=mmax<<1;
theta=ok*DOUBLE_PI/mmax; //三角遞歸初始賦值
sin_htheta=sin(0.5*theta);
sin_theta=sin(theta);
pwr= -2.0*sin_htheta*sin_htheta;
wr=1.0;
wi=0.0;
for(m=1;m<mmax;m+=2)
{
for(i=m;i<=n;i+=step)//以下不是很理解，請指點
{
j=i+mmax;
tempr=wr*data[j-1]-wi*data[j];
tempi=wr*data[j]+wi*data[j-1];
data[j-1]=data[i-1]-tempr;
data[j]=data[i]-tempi;
data[i-1]+=tempr;
data[i]+=tempi;
}
wr=(sin_htheta=wr)*pwr-wi*sin_theta+wr;
wi=wi*pwr+sin_htheta*sin_theta+wi; //三角遞歸
}
mmax = step;
}
}
其中部分代碼不是很理解，請指點，謝謝你 xiao1dian@163.comRe: 基二FFT的原理和算法 [8/29/2007 7:29:59 AM]很好的文章，通俗易懂，但是我看了你的c語言程序，不知道你用的什么嵌入式系統(tǒng)，數(shù)據(jù)處理能力有這么強啊？我用xilinx的MicroBlaze做嵌入式，像你程序里的cos，sin和pow（）函數(shù)肯定是跑不起來的，需要n大的一片程序ram，你用什么做的嵌入式??？Re: 基二FFT的原理和算法 [8/2/2007 12:34:49 PM]
