fft算法代碼注釋及流程框圖

1、基2的DIT蝶形算法源代碼及注釋如下:*FFT*/整個程序輸入和輸出利用同一個空間xN,節(jié)約空間#in elude<stdio.h>#in elude <math.h>#include <stdlib.h>#defi ne typedef struct1000定義輸入或者輸出空間的最人長度doubledoublesystem(,cls,)；Pl=atan(l)*4;prin tf("Please in put the size of x:rf); scanf("%d,/&size_x);printf("Please in

2、put the data in xN:(such as:5 6)n")； for(i=0;i<size_x;i+)scanf("%lf %lf"/&xi.real/&xi.img);initW();output();廠輸入序列的長度穴/廠輸入序列對應的值計算 W(0)W(size_xl)的值 利用fft快速算法進行DFT變化 順序輸岀size_x個fft的結果complex;定義復數(shù)型變量的結構體void快速傅里葉變換函數(shù)聲明voidinitW();計算W(0)W(size_x-l)的值函數(shù)聲明voidchange();碼元位置倒置函數(shù)函數(shù)聲

3、明voidadd(complex,complex,complex *);/*復數(shù)加法*7voidmul(complexzcomplex,complex *);/*復數(shù)乘法*/voidsub(complex,complex,complex *);/*復數(shù)減法*7voiddivi(complex,complex,complex *);/*復數(shù)除法-7voidoutput();/*輸出結果-7complex xN,*W;/*輸出序列的值-7intsize_x=0;廠輸入序列的長度，只限2的N次方*/doublePI;/pi的值intmain()real;img;intreturn 0;廠進行基J F

4、FT運算，蝶形算法。這個算法的思路就是，先把計算過程分為log(size_x)/log(2)-l級(用i控制級數(shù))；然后把每一級蝶形單元分組(用j控制組的第一個元素起始下標)； 最后算出某一級某一組每一個蝶形單元(用k控制個數(shù)，共I個)。*/ void fft()int i=O/j=O/k=O/l=O;complex up,dow n,product;change();實現(xiàn)對碼位的倒置for(i=0;i<log(size_x)/log(2);i+)循環(huán)算出 fft 的結果l=l«i;for(j=0;j<size_x;j+=2* I)算出第m二i級的結果【i從0到(log(

5、size_x)/log(2) -1for(k=0;k<l;k+)算出第i級內(nèi)j組蝶形單元的結果算出j組中第k個蝶形單元mul(xj+k+l,W(size_xZVI)*k,&product); /*size/l 是該級 W 的相鄰上標差，I是該級該組取的w總個數(shù)p/addlxD+kJ.product,&up); sub(xj+k,productz&down); xj+k=up;xj+k+l=down;/up為蝶形單元右上方的值/down為蝶形單元右卞方的值void initW()計算W的實現(xiàn)函數(shù)W=(complex *)malloc(sizeof(complex)

6、* size_x);for(i=0;i<(size_x/2);i+)/*申請size_x個復數(shù)W的空間(這部 申請的空間有點多，實際上只要 申請size_x左個即口J)*/廠預先計算出size_x/2個W的值，存 放，由于蝶形算法只需要前 size_x/2個值即可*/Wi.real=cos(2*PI/size_x*i);Wi.img=-l*sin(2*PI/size_x*i);計算W的實部計算W的虛部void change()complex temp;unsigned short i=OJ=O,k=O; double t;for(i=0;i<size_x;i+)k=i;輸入的碼組碼

7、位倒置實現(xiàn)函數(shù)j=0;t=(log(size_x)/log(2);while(t-)>0)j|=(k &1)； k=k»l;if(j>i)temp=xi;xi=xj;xj=temp;void output()輸出結果實現(xiàn)函數(shù)int i;printf(HThe result are asfollowsnJ;for(i=0;i<size_x;i+)printf(”.4f“,xi.real);輸出實部if(xi.img>=0.0001)如果虎部的值人于0.0001,輸出+jx.img的形式printf("+j%.4fn,/xi.img);else

8、if(fabs(xi.img)<0.0001) 如果虛部的絕對值小于0.0001,無需輸出 printf(“n“)；elseprintf(,-j%.4fn,/fabs(xi.img);如果虎部的值小于-0.0001,輸出-jx.img的形式復數(shù)加法實現(xiàn)函數(shù)復數(shù)實部相加復數(shù)虛部相加復數(shù)乘法實現(xiàn)函數(shù)獲取相乘結果的實部獲取相乘結果的虛部復數(shù)減法實現(xiàn)函數(shù)復數(shù)實部相減復數(shù)虛部相減復數(shù)除法實現(xiàn)函數(shù)void add(complex a,complex b,complex *c) c->real = a.real + b.real;c->img = a.img + b.img;void mu

9、l(complex a,complex b,complex *c) c->real = a.real*b.real - a.img*b.img; c->img = a.real*b.img + a.img*b.real;void sub(complex a,complex b,complex *c) c->real = a.reaI b.real;c->img = a.img - b.img;void divi(complex a,complex b,complex *c)c->real = (a.real*b.real + a.img*b.img) / (b.real*b.real+b.img*b.img);獲取相除結果的實部c->img =