【正文】 k(n) || mpym *AR7+,T3,AC0 。AC0+=b2k*wk(n2) macm *(AR3+T1),*AR7+,AC0 。AC0+=b0k*wk(n1) macm *AR3+,*AR7+,AC0 。AC0+=b1k*wk(n) filter_loop mov rnd(hi(AC02)),*AR1+ 。按 Q15格式存放結果sample_loop popboth XAR7 ?；謴?AR7 pop T3 ?；謴?T3 popm ST3_55 ?；謴?ST1,ST2,ST3 popm ST2_55 popm ST1_55 ret .end */圖 711 IIR濾波器系數(shù)和信號緩沖區(qū)配置 快速傅里葉變換 FFTn FFT算法原理n 庫利一圖基算法n FFT算法的實現(xiàn) FFT算法原理l 快速傅里葉變換（ FFT）是離散傅里葉變換（ DFT）的一種快速算法。通過 FFT算法， DFT的計算量大大減少，運算時間縮短 1~2個數(shù)量級。l DFT的變換公式為 其中 為旋轉因子。l FFT之所以減少運算量，主要是利用了旋轉因子的以下 3點特性：u對稱性u周期性u可約性利用這些特性可以使 DFT運算中有些項進行合并，將長序列的DFT分解為短序列的 DFT。DFT從算法上分為按時間抽選（ DIT）和按頻率抽選 (DIF）?；?2的 DIT又被稱為庫利一圖基算法?；?2的 DIF又稱為桑德 —圖基算法。 庫利一圖基算法n 信號流圖n 比特反轉n 蝶形運算1. 信號流圖2．比特反轉l 圖 711的輸入信號的順序是按照比特反轉排列的，輸出序列是按照自然順序的。比特反轉就是將序列下標用二進制表示，然后將二進制數(shù)按照相反的方向排列，即得到這個序列的實際位置。l 按照自然排序的時域信號數(shù)據是 x(0)、 x(1)、 x(2)、x(3)、 x(4)、 x(5)、 x(6)、 x(7)，其序號寫成二進制數(shù)分別為 000b、 001b、 010b、 011b、 100b、101b、 110b、 111b，將這些二進制數(shù)前后倒轉，即得到進行 FFT前數(shù)據所對應的實際二進制數(shù)地址：000b、 100b、 010b、 110b、 001b、 101b、 011b、 111b，對應的十進制數(shù)是： 0、 7。序號為 3的存儲單元，按照自然排序應該存放x(3)，但由于 FFT計算規(guī)則的要求，現(xiàn)在應該存放 x(6)。 l 基 2DIT FFT算法，共由 M級構成，每級計算由 N/2個蝶形運算構成。l 基本運算單元為以下所謂蝶形運算：l 蝶形運算中上下兩個節(jié)點 p、 q的間距為： FFT算法的實現(xiàn)l 為了敘述簡單，本書給出采用 C語言編寫的 FFT程序，相應的匯編程序請讀者自行完成。（ 1）主程序： include include /*包含浮點復數(shù)結構體定義頭文件*/extern void bit_rev(plex *,unsigned int)。/*位反轉函數(shù)聲明 */extern void fft(plex *,unsigned int,plex *,unsigned int)。 /* fft函數(shù)聲明 */例 713，基 2DIT FFT算法的 C語言實現(xiàn)。extern void generator(int *,unsigned int)define N 128 /* FFT的數(shù)據個數(shù) */define M 7 /* M=log2(N) */define PI plex X[N]。 /* 說明輸入信號數(shù)組 ,為復數(shù) */plex W[M]。 /* 說明旋轉因子數(shù)組 e^(j2PI/N),為復數(shù) */ plex temp。 /* 說明臨時復數(shù)變量 */float xin[N]。float spectrum[N]。 /* 說明功率譜信號數(shù)組 ,為實數(shù) */float re1[N],im1[N]。 /* 說明臨時變量數(shù)組 ,為實數(shù) */void main(){ unsigned int i,j,L,LE,LE1。 /* *//* 產生旋轉因子表 */ for (L=1。 L=M。 L++) { LE=1L。 /* 子 FFT中的點數(shù) LE=2^L */ LE1=LE1。 /* 子 FFT中的蝶形運算數(shù)目 */ W[L1].re = cos(PI/LE1)。 W[L1].im = sin(PI/LE1)。 } /* */ generator(xin,N)。 for (。) { for (i=0。 iN。 i++) { /* 構造輸入信號樣本 */ X[i].re =xin[i]。 X[i].im = 0。 /* 復制到參考緩沖器 */ re1[i] = X[i].re。 im1[i] = X[i].im。 } /* 啟動 FFT */ bit_rev(X,M)。 /* 以倒位次序排列 X[] */ fft(X,M,W,1)。 /* 執(zhí)行 FFT */ /* 計算功率譜，驗證 FFT結果 */ for (i=0。 iN。 i++) { = X[i].re*X[i].re。 = X[i].im*X[i].im。 spectrum[i] = ( + )*4。 } }}（ 2）浮點復數(shù)基 2 DIT FFT函數(shù)： include void fft(plex *X,unsigned int M,plex *W,unsigned int SCALE){ plex temp。 /* 復變量臨時存儲器 */ plex U。 /* 旋轉因子 W^k */ unsigned int i,j。 unsigned int id。 /* 蝶形運算中下位節(jié)點的序號 */ unsigned int N=1M。 /* FFT 的點數(shù) */ unsigned int L。 /* FFT 的級序號 */ unsigned int LE。 /* L級子 FFT的點數(shù) */ unsigned int LE1。 /* L級子 FFT蝶形運算的個數(shù) */ float scale。 scale = 。 for(L=1。L=M。L++) { LE=1L。 LE1=LE1。 = 。 = 0.。 for(j=0。jLE1。j++) { for(i=j。iN。i+=LE) /*進行蝶形計算 */ { id=i+LE1。 =(X[id].re*[id].im*)*scale。 =(X[id].im*+X[id].re*)*scale。 X[id].re=X[i].re*。 X[id].im=X[i].im*。 X[i].re=X[i].re*scale+。 X[i].im=X[i].im*scale+。 } /*遞推計算 W^k*/ =*W[L1].*W[L1].im。 =*W[L1].im+*W[L1].re。 =。 } }} （ 3）位反轉函數(shù)： include void bit_rev(plex *X,unsigned int M){ plex temp。 unsigned int i,j,k。 unsigned int N=1M。 /* FFT 的點數(shù) */ unsigned int N2=N1。 for (j=0,i=1。 iN1。 i++) { k=N2。 while(k=j){j=k。 k=1。 } j+=k。 if(ij) { temp=X[j]。 X[j]=X[i]。X[i]=temp。}}}（ 4）信號發(fā)生器函數(shù)： /* 該程序用于產生一組信號樣本 */include define PI= define Fs=8000 。采樣頻率設為 8000Hzdefine T=1/Fs 。采樣時間為 define f1=500 。信號源頻率 1取為 500Hzdefine a1= 。信號源幅度 1取為 define w1=2*PI*f1*T void generator(int *x,unsigned int N){ unsigned int i。 for(i=0。iN。i++) { X[i]=a1*cos((float)w1*i)。}}（ 5）復數(shù)結構定義頭文件： struct cmpx{float re。float im。}。typedef struct cmpx plex。