基FFT算法編程

1、實驗報告 課程名稱： 數(shù)字信號處理指導老師：劉英成績： 實驗名稱： 基 4-FFT算法編程 實驗類型：設計 同組學生姓名： _ 一、實驗目的和要求 FFT是快速計算 DFT的一類算法的總稱。 通過序列分解， 用短序列的 DFT代替長序列的 DFT，使得計算量大大下降?；?4-FFT是混合基 FFT的一個特例。 通過編寫基 4-FFT算法程序，加深對 FFT思路、算法結構的理解。 二、實驗內容和步驟 編寫 16 點基 4-FFT算法的 MATLAB程序（ studentname.m 文件）。 產生 16 點輸入序列 x，出生年月日（ 8 位） +自己學號后八位產生 。算出 16 點頻譜序列 X，

2、用 stem（X）顯示頻譜圖形。 三、主要儀器設備 用 MATLAB。 四、操作方法和實驗步驟 （參見 “二、實驗內容和步驟 ”） 五、實驗數(shù)據(jù)記錄和處理 5.1基 4-FFT算法思路、流圖結構簡述如下 5.1.1. 算法思路： 在時域上按 n 的特點對序列 x（n）進行不斷的以 4 為基數(shù)的分組以及位序調整，進而通過 逐級的蝶形復合處理，間接地完成高點數(shù) DFT的計算，由此達到降低運算量以及節(jié)省存儲空 間的目的。 令序列 x(n)的N點DFT結果為 X(k)，且有，按 的結果對序列 x(n)分組如下： 則有： 經過 5.1.2 蝶形圖如下： 對于 N/4 個點繼續(xù)進行分組和蝶形復合處理， 由

3、原序列 x(n)出發(fā)，完成位序調整后， m 級蝶形復合便可求得序列 X(k)。總體過程如下圖： 2 / 6. -1- j j -1j -j 5.2 16點基 4-FFT算法的流圖繪出如下(后面省略了系數(shù) -1，-j，j，具體系數(shù)對應項見上一蝶 形圖) 5.3 16點基 4-FFT算法的 MATLAB程序( studentname.m )列出如下 x=1,9,9,5,0,3,2,5,3,0,1,0,4,7,2,3; X=fft4_16(x); X1=fft(x); n=1:1:16; figure(1) stem(n,x, filled ); title( Input Sequence ); a

4、xis(0 17 0 10); figure(2) stem(n,X, filled ); title( Output Sequence ); axis(0 17 -20 60); figure(3) 3 / 6. stem(n,X1, filled ); title(Output FFT Sequence axis(0 17 -20 60); function X=fft4_16(x) X=zeros(1,16); N=16; ); %初始化輸出的頻譜序列 W4=dftmtx(4); %求出蝶形運算的系數(shù)矩陣 x0=x(1);x(5);x(9);x(13); % 先對原序列進行位序調整 x1

5、=x(2);x(6);x(10);x(14); x2=x(3);x(7);x(11);x(15); x3=x(4);x(8);x(12);x(16); X0=W4*x0; X1=W4*x1; %第一級蝶形運算 X2=W4*x2; X3=W4*x3; for k=0:3 %第二級蝶形運算 t=W4*X0(k+1);(Wk)*X1(k+1);(W(2*k)*X2(k+1);(W(3*k)*X3(k+1); X(k+1)=t(1); X(k+4+1)=t(2); X(k+2*4+1)=t(3); X(k+3*4+1)=t(4); end 5.4 用自己的學號構成的輸入序列為（列出數(shù)值，插入圖形） x

6、1=1,9,9,5,0,3,2,5,3,0,1,0,4,7,2,3; 4 / 6. W=exp(-1j*2*pi/N); 5.5 對應的輸出頻譜序列為（列出數(shù)值，插入圖形） X = 54.0000 + 0.0000i 13.5682 - 6.7903i 1.4142 - 3.1716i -13.2930 -19.4368i -6.0000 - 6.0000i -2.0207 - 0.1231i -1.4142 + 8.8284i -6.2545 - 3.4765i -10.0000 - 0.0000i -6.2545 + 3.4765i -1.4142 - 8.8284i -2.0207 + 0.1231i -6.0000 + 6.0000i -13.2930 +19.4368i 1.4142 + 3.1716i 13.5682 + 6.7903i 六、實驗結果與分析 5 / 6. 1. 基 4-FFT計算結果與 matlab 自帶 fft 函數(shù)計算結果對比 以下是 matlab 自帶 fft 函數(shù)的計算結果 由上述序列和圖像比較可以看到， matlab 自帶的函數(shù) fft 所得結果與我的基