基4-FFT算法編程

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

2、LAB。四、操作方法和試驗步驟參見“二、試驗內容和步驟五、試驗數(shù)據記錄和處理5.1基4-FFT算法思路、流圖結構簡述如下5.1.1. 算法思路：在時域上按n的特點對序列x(n)進行不斷的以4為基數(shù)的分組以及位序調整，進而通過逐級的蝶形復合處理，間接地完成高點數(shù)DFT的計算，由此到達降低運算量以及節(jié)省存儲空間的目的。令序列x(n)的N點DFT結果為Xk，且有N=4m，按(n)4的結果對序列x(n)分組如下：x0n=x4n X0k=DFT4m-1x0(n)x1n=x(4n+1)X1k=DFT4m-1x1(n)x2n=x(4n+2)X2k=DFT4m-1x2(n)x3n=x(4n+3) X3k=DF

3、T4m-1x3(n)0nN4-10kN-1=4m-1那么有：Xk=X0k+WNkX1k+WN2kX2k+WN3kX3kXk+4m-1=X0k-jWNkX1k-WN2kX2k+jWN3kX3kXk+2×4m-1=X0k-WNkX1k+WN2kX2k-WN3kX3kXk+3×4m-1=X0k+jWNkX1k-WN2kX2k-jWN3kX3k5.1.2蝶形圖如下： 對于N/4個點連續(xù)進行分組和蝶形復合處理，由原序列x(n)動身，完成位序調整后，經過m級蝶形復合便可求得序列X(k)?？傮w過程如以下圖：5.2 16點基4-FFT算法的流圖繪出如下后面省略了系數(shù)-1，-j，j，具體系數(shù)

4、對應項見上一蝶形圖-j-1j-1-1j-1-j5.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');axis(0 17 0 10);figure(2)stem(n,X,'filled');title('Output Sequence');axis(0 17 -20 60)

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

6、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);end5.4用自己的學號構成的輸入序列為列出數(shù)值，插入圖形x1=1,9,9,5,0,3,2,5,3,0,1,0,4,7,2,3;5.5對應的輸出頻譜序列為列出數(shù)值，插入圖形X = 54.0000 + 0.0000i 13

7、.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六、試驗結果與分析1. 基4-FFT計算結果與matlab自帶fft函數(shù)計算結果比照以下是matlab自帶fft函數(shù)的計算結果由上述序列和圖像比較可以