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

1、基2的DIT蝶形算法源代碼及注釋如下:*FFT*/整個(gè)程序輸入和輸出利用同一個(gè)空間xN,節(jié)約空間#in elude<stdio.h>#in elude <math.h>#include <stdlib.h>#defi ne typedef struct1000定義輸入或者輸出空間的最人長(zhǎng)度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();廠輸入序列的長(zhǎng)度穴/廠輸入序列對(duì)應(yīng)的值計(jì)算 W(0)W(size_xl)的值 利用fft快速算法進(jìn)行DFT變化 順序輸岀size_x個(gè)fft的結(jié)果complex;定義復(fù)數(shù)型變量的結(jié)構(gòu)體void快速傅里葉變換函數(shù)聲明voidinitW();計(jì)算W(0)W(size_x-l)的值函數(shù)聲明voidchange();碼元位置倒置函數(shù)函數(shù)聲

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

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

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

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

7、位倒置實(shí)現(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()輸出結(jié)果實(shí)現(xiàn)函數(shù)int i;printf(HThe result are asfollowsnJ;for(i=0;i<size_x;i+)printf(”.4f“,xi.real);輸出實(shí)部if(xi.img>=0.0001)如果虎部的值人于0.0001,輸出+jx.img的形式printf("+j%.4fn,/xi.img);else

8、if(fabs(xi.img)<0.0001) 如果虛部的絕對(duì)值小于0.0001,無(wú)需輸出 printf(“n“)；elseprintf(,-j%.4fn,/fabs(xi.img);如果虎部的值小于-0.0001,輸出-jx.img的形式復(fù)數(shù)加法實(shí)現(xiàn)函數(shù)復(fù)數(shù)實(shí)部相加復(fù)數(shù)虛部相加復(fù)數(shù)乘法實(shí)現(xiàn)函數(shù)獲取相乘結(jié)果的實(shí)部獲取相乘結(jié)果的虛部復(fù)數(shù)減法實(shí)現(xiàn)函數(shù)復(fù)數(shù)實(shí)部相減復(fù)數(shù)虛部相減復(fù)數(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);獲取相除結(jié)果的實(shí)部c->img =