1、一、對FFT的介紹1. FFT （ Fast Fourier Transformation ），即為快速傅里葉變換，是離散 傅里葉變換的快速算法，它是根據離散傅里葉變換的奇、偶、虛、實等 特性，對離散傅里葉變換的算法進行改進獲得的。2. FFT算法的基本原理FFT算法是把長序列的DFT逐次分解為較短序列的 DFT。按照抽取方式的不同可分為 DIT-FFT（按時間抽取）和DIF-FFT（按 頻率抽取）算法。按蝶形運算的構成不同可分為基 2，基4，基8，以及 任意因子的類型。3. 迭代關系冷 -1e2 r ? ! NfjJ =0y / 2 -1N J 2 - 1二 Ze2刃比(2 J)/Nfl j

2、 +y長此（2十：八0J = o.V 2 - 1N2-1二 2e(2 j ) yf 2 j +W KY總j = Q/ = 0二 F /+W疋 jza4、本次程序的基本過程我們這次所研究的是數字信號處理中的FFT算法，我們這次所用的數字信號是復數類型的。(1) 所以首先，我們先定義了一個復數結構體，因為是進行復數的運算，我們又相繼定義復數的加減乘運算的函數。(2) 緊接著，我們定義了進行 FFT計算的fft()快速傅里葉變換函數ini tW()初始化變換核函數即旋轉因子的計算，cha nge()變址函數，output()輸出傅里葉變換的結果的函數。(3) 定義主函數，并調用定義好的相關子函數，利

3、用fft()中的蝶形運算以及change()函數來完成從時間域上選取的DIT-FFT。二、FFT中碼位倒置排序1、碼位倒置的實現方法：(1) 簡單的利用按位與、或循環實現(2) 利用公式推導的迭代方法2、為什么要進行碼位倒置因為由于FFT的計算特性，如果按照正常順序輸入，而沒有進行碼位倒置的話，就會以亂序輸出，就不便于我們后續對信號的相關性質進行研究了，所以DIT-FFT算法就是在進行FFT計算之前，進行分奇偶后的碼位倒置運算，即二進制數的倒位。3、倒位序由奇偶分組造成，以 N=8為例，說明如下：Op心樂15卩三、蝶形運算由心（力）：心（疋除示x （k助運算是一種特殊運算1x (疋)=兀 1(

4、£ )+ W x2(k )前一半x (Ar ) = Xj (k )- fF x2(k )后一半(k =(k = 1按照上述公式的規律進行逐級分解，直到2點DFT，如下是N=8時的蝶形算法分析圖：四、FFT算法中蝶形算法的基本思想分析（1）我們知道N點FFT運算可以分成Iog2 （ N ）級，每一級都有N/2 個碟形，FFT的基本思想是用3層循環完成全部運算（N點FFT）。（2）第一層循環：由于 N=2m 需要m級計算，第一層循環對運算的 級數進行控制。（stages）（3）第二層循環：由于第L級有2YL-1）個蝶形因子（乘數），第二層循環根據乘數進行控制，保證對于每一個蝶形因子第三層

5、循環要執行 一次，這樣，第三層循環在第二層循環控制下，每一級要進行2A（L-1）次循環計算.（選擇W）（4）第三層循環：由于第L級共有N/2AL即2A （n-L）個群，并且同一級內不同群的乘數分布相同，當第二層循環確定某一乘數后，第三層循環要將本級中每個群中具有這一乘數的蝶形計算一次，即第三層循環每執行完一次要進行 N/2AL個碟形計算。（執行不同group中具有 相同W的蝶形運算）(5 )可以得出結論：在每一級中，第三層循環完成N/2U 個碟形計算;第二層循環使第三層循環進行2YL-1)次，因此，第二層循環完成時，個碟形計算。實質是：第二、第三層循共進行 2A(L-1) *N/2AL=N/2

6、環完成了第L級的計算。五、用c語言實現的FFT算法如下:<span style="font-size:18px;">#include <stdio.h>#in clude <math.h>#i nclude <stdlib.h>#defi ne N 1000/*定義復數類型*/typedef structdouble real;double img;complex;complex xN, *W; /*輸入序列，變換核*/int size_x=0; /*輸入序列的大小，在本程序中僅限2的次幕*/double PI;/*圓周率*/

7、void fft(); /*快速傅里葉變換*/void ini tW(); /*初始化變換核*/void cha nge(); /*變址*/void add(complex ,complex ,complex *); /*復數加法*/void mul(complex ,complex ,complex *); /*復數乘法*/void sub(complex ,complex ,complex *); /*復數減法*/void output();/*輸出快速傅里葉變換的結果*/int mai n()int i;system("cls");PI=ata n*4; printf

8、("果n");/*輸出結果*/輸岀DIT方法實現的FFT結輸入序列的大小輸入序列的實部和虛部prin tf("Please in put the size of x: n");/ sea nf("%d", &size_x);printf("Please in put the data in xN:n");/ for(i=0;i<size_x;i+)printf(" 請輸入第%d個序列：",i); sea nf("%lf%lf", &xi.real, &a

9、mp;xi.img);printf(“輸岀倒序后的序列n");ini tW();/ 調用變換核fft();/調用快速傅里葉變換printf("輸岀FFT后的結果n");output();/調用輸岀傅里葉變換結果函數return 0;/*快速傅里葉變換*/void fft()int i=O,j=O,k=O,l=O;complex up,dow n,product;eha nge(); / 調用變址函數 for(i=0;i< log(size_x)/log(2) ;i+)/*l=1<<i;for(j=0;j<size_x;j+= 2*l )/*

10、p的蝶形因子乘數不同*/for(k=0;k<l;k+)/*蝶形運算*/一級蝶形運算stage */一組蝶形運算group,每個grou一個蝶形運算每個group內的mul(xj+k+l,Wsize_x*k/2/l,&product); add(xj+k,product，&up);sub(xj+k,product，& dow n);xj+k=up; xj+k+l=dow n;/*初始化變換核，定義一個變換核，相當于旋轉因子WAP*/void ini tW() int i;生成變換核用歐拉公式計算旋轉因子W=(complex *)malloc(sizeof(compl

11、ex) * size_x); / for(i=0;i<size_x;i+)Wi.real=cos(2*PI/size_x*i); / Wi.img=-1*si n(2*PI/size_x*i);/*變址計算，將 x(n)碼位倒置*/void cha nge()complex temp;un sig ned short i=O,j=O,k=O;double t;for(i=0;i<size_x;i+)k=i;j=0;t=(log(size_x)/log (2);while( (t-)>0 ) /利用按位與以及循環實現碼位顛倒j=j<<1;j|=(k & 1)

12、;k=k>>1;if(j>i) /將x(n)的碼位互換temp=xi;xi=xjxj=temp;output();/*輸出傅里葉變換的結果*/void output()int i;printf("The result are as follows: n");for(i=0;i<size_x;i+)prin tf("%.4f',xi.real);if(xi.img>=0.0001)pri ntf("+%.4fjn",xi.img);else if(fabs(xi.img)<0.0001)pr in tf

13、("n"); else prin tf("%.4fjn",xi.img);void add(complex a,complex b,complex *c) / c->real=a.real+b.real; c->img=a.img+b.img;void mul(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.real-b.real; c->img=a.img-b.img;</spa n>六、FFT原理的理解和程序設計中遇到的相關問題及解決方法1、遇到的相關問題:(1)首先一開始不知道什么是 FFT,以及FFT原理是什么不理解FFT中迭代關系的推導以及緣由(3)不理解變址計算的原理(4) 對蝶形運算的推導與原理的理解不透徹(5) 編程過程中對變址計算即對按位與的變換形式的不理解2、解決的方法：(1) 到圖書館借相關的書籍理解相關的原理和過程(2) 到百度收索相關的資料促進理解相