用c語言實現(xiàn)的FFT

1/7.1.FFT〔FastFourierTransformation,即為快速傅里葉變換,是離散傅里葉變換的快速算法,它是根據(jù)離散傅里葉變換的奇、偶、虛、實等特性,對離散傅里葉變換的算法進(jìn)行改進(jìn)獲得的。3.迭代關(guān)系4、本次程序的基本過程。<1>所以首先,我們先定義了一個復(fù)數(shù)結(jié)構(gòu)體,因為是進(jìn)行復(fù)數(shù)的運算,我們又相繼定義復(fù)數(shù)的加減乘運算的函數(shù)。<2>緊接著,我們定義了進(jìn)行FFT計算的fft<>快速傅里葉變換函數(shù)initW<>初始化變換核函數(shù)即旋轉(zhuǎn)因子的計算,change<>變址函數(shù),output<>輸出傅里葉變換的結(jié)果的函數(shù)。<3>定義主函數(shù),并調(diào)用定義好的相關(guān)子函數(shù),利用fft<>中的蝶形運算2/7.<1>簡單的利用按位與、或循環(huán)實現(xiàn)<2>利用公式推導(dǎo)的迭代方法2、為什么要進(jìn)行碼位倒置置的話,就會以亂序輸出,就不便于我們后續(xù)對信號的相關(guān)性質(zhì)進(jìn)行研倒置運算,即二進(jìn)制數(shù)的倒位。三、蝶形運算由3/7.根據(jù)乘數(shù)進(jìn)行控制,保證對于每一個蝶形因子第三層循環(huán)要執(zhí)行一次,這樣,第三層循環(huán)在第二層循環(huán)控制下,每一級要進(jìn)行2^<L-1>次循環(huán)計不同群的乘數(shù)分布相同,當(dāng)?shù)诙友h(huán)確定某一乘數(shù)后,第三層循環(huán)要將本級中每個群中具有這一乘數(shù)的蝶形計算一次,即第三層循環(huán)每執(zhí)行形運算二層循環(huán)使第三層循環(huán)進(jìn)行2^<L-1>次,因此,第二層循環(huán)完成時,共進(jìn)LNLN成spanstyle="font-size:18px;">#include<stdio.h>4/7.#include<math.h>#include<stdlib.h>#defineN1000/*定義復(fù)數(shù)類型*/typedefstruct{doublereal;doubleimg;}complex;complexx[N],*W;/*輸入序列,變換核*/intsize_x=0;/*輸入序列的大小,在本程序中僅限2的次冪*/doublePI;/*圓周率*/voidfft<>;/*快速傅里葉變換*/voidinitW<>;/*初始化變換核*/voidchange<>;/*變址*/voidadd<complex,complex,complex*>;/*復(fù)數(shù)加法*/voidmul<complex,complex,complex*>;/*復(fù)數(shù)乘法*/voidsub<complex,complex,complex*>;/*復(fù)數(shù)減法*/voidoutput<>;/*輸出快速傅里葉變換的結(jié)果*/{inti;/*輸出結(jié)果*/system<"cls">;PI=atan<1>*4;\n">;printf<"Pleaseinputthesizeofx:\n">;//輸入序列的大小scanf<"%d",&size_x>;printf<"Pleaseinputthedatainx[N]:\n">;//輸入序列的實部和虛部for<i=0;i<size_x;i++>{iscanf<"%lf%lf",&x[i].real,&x[i].img>;}printf<"輸出倒序后的序列\(zhòng)n">;initW<>;//調(diào)用變換核fft<>;//調(diào)用快速傅里葉變換ntfFFTnoutput<>;//調(diào)用輸出傅里葉變換結(jié)果函數(shù)return0;}/*快速傅里葉變換*/voidfft<>{inti=0,j=0,k=0,l=0;5/7.complexup,down,product;change<>;//調(diào)用變址函數(shù)for<i=0;i<log<size_x>/log<2>;i++>/*一級蝶形運算stage*/{for<j=0;j<size_x;j+=2*l>/*一組蝶形運算group,每個group的蝶形因子乘數(shù)不同*/{for<k=0;k<l;k++>/*一個蝶形運算每個group內(nèi)的蝶形運算*/{mul<x[j+k+l],W[size_x*k/2/l],&product>;add<x[j+k],product,&up>;sub<x[j+k],product,&down>;x[j+k]=up;x[j+k+l]=down;}}}}/*初始化變換核,定義一個變換核,相當(dāng)于旋轉(zhuǎn)因子WAP*/voidinitW<>{W=<complex*>malloc<sizeof<complex>*size_x>;//生成變換核for<i=0;i<size_x;i++>{W[i].real=cos<2*PI/size_x*i>;//用歐拉公式計算旋轉(zhuǎn)因子W[i].img=-1*sin<2*PI/size_x*i>;}}/*變址計算,將x<n>碼位倒置*/voidchange<>{complextemp;unsignedshorti=0,j=0,k=0;doublet;for<i=0;i<size_x;i++>{k=i;j=0;t=<log<size_x>/log<2>>;while<<t-->>0>//利用按位與以及循環(huán)實現(xiàn)碼位顛倒{j=j<<1;6/7.j|=<k&1>;k=k>>1;}if<j>i>//將x<n>的碼位互換{temp=x[i];x[i]=x[j];x[j]=temp;}}output<>;}/*輸出傅里葉變換的結(jié)果*/voidoutput<>{printf<"Theresultareasfollows：\n">;for<i=0;i<size_x;i++>{printf<"%.4f",x[i].real>;if<x[i].img>=0.0001>printf<"+%.4fj\n",x[i].img>;elseif<fabs<x[i].img><0.0001>printf<"\n">;elseprintf<"%.4fj\n",x[i].img>;}}voidadd<complexa,complexb,complex*c>//復(fù)數(shù)加法的定義{c->real=a.real+b.real;c->img=a.img+b.img;}voidmul<complexa,complexb,complex*c>//復(fù)數(shù)乘法的定義{c->real=a.real*b.real-a.img*b.img;c->img=a.real*b.img+a.img*b.real;}voidsub<complexa,complexb,complex*c>//復(fù)數(shù)減法的定義{c->real=a.real-b.real;c->img=a.img-b.img;}</span>7/7.<3>不理解變址計算的原理<4>對蝶形運算的推導(dǎo)與原理的理解不透徹<5>編程過程中對變址計算即對按位與的變換形式的不理解<1>到圖書館借相關(guān)的書籍理解相關(guān)的原理和過程<2>到百度收索相關(guān)的資料促進(jìn)理解相應(yīng)的原理過程<3>向?qū)W長學(xué)姐請教或老師的指導(dǎo)七、總結(jié)從這次的考核中我學(xué)到了一些有關(guān)數(shù)字信號處理的相關(guān)知識,