基4-FFT算法編程

1、.實(shí)驗(yàn)報(bào)告課程名稱： 數(shù)字信號處理 指導(dǎo)老師： 劉英 成績：_實(shí)驗(yàn)名稱： 基4-FFT算法編程 實(shí)驗(yàn)類型：_設(shè)計(jì)_ 同組學(xué)生姓名：_一、實(shí)驗(yàn)?zāi)康暮鸵驠FT是快速計(jì)算DFT的一類算法的總稱。通過序列分解，用短序列的DFT代替長序列的DFT，使得計(jì)算量大大下降?；?-FFT是混合基FFT的一個(gè)特例。通過編寫基4-FFT算法程序，加深對FFT思路、算法結(jié)構(gòu)的理解。二、實(shí)驗(yàn)內(nèi)容和步驟編寫16點(diǎn)基4-FFT算法的MATLAB程序（studentname.m文件）。產(chǎn)生16點(diǎn)輸入序列x，出生年月日（8位）+自己學(xué)號后八位產(chǎn)生。算出16點(diǎn)頻譜序列X，用stem(X)顯示頻譜圖形。三、主要儀器設(shè)備用MATL

2、AB。四、操作方法和實(shí)驗(yàn)步驟（參見“二、實(shí)驗(yàn)內(nèi)容和步驟”）五、實(shí)驗(yàn)數(shù)據(jù)記錄和處理5.1基4-FFT算法思路、流圖結(jié)構(gòu)簡述如下5.1.1. 算法思路：在時(shí)域上按n的特點(diǎn)對序列x(n)進(jìn)行不斷的以4為基數(shù)的分組以及位序調(diào)整，進(jìn)而通過逐級的蝶形復(fù)合處理，間接地完成高點(diǎn)數(shù)DFT的計(jì)算，由此達(dá)到降低運(yùn)算量以及節(jié)省存儲(chǔ)空間的目的。令序列x(n)的N點(diǎn)DFT結(jié)果為X（k），且有N=4m，按(n)4的結(jié)果對序列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) X3

3、k=DFT4m-1x3(n)0nN4-10kN-1=4m-1則有：Xk=X0k+WNkX1k+WN2kX2k+WN3kX3kXk+4m-1=X0k-jWNkX1k-WN2kX2k+jWN3kX3kXk+24m-1=X0k-WNkX1k+WN2kX2k-WN3kX3kXk+34m-1=X0k+jWNkX1k-WN2kX2k-jWN3kX3k5.1.2蝶形圖如下： 對于N/4個(gè)點(diǎn)繼續(xù)進(jìn)行分組和蝶形復(fù)合處理，由原序列x(n)出發(fā)，完成位序調(diào)整后，經(jīng)過m級蝶形復(fù)合便可求得序列X(k)?？傮w過程如下圖：5.2 16點(diǎn)基4-FFT算法的流圖繪出如下（后面省略了系數(shù)-1，-j，j，具體系數(shù)對應(yīng)項(xiàng)見上一蝶形圖

4、）-j-1j-1-1j-1-j5.3 16點(diǎn)基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);figure(3)stem(n,X1,filled);title(Output FFT S

5、equence);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); %求出蝶形運(yùn)算的系數(shù)矩陣 x0=x(1);x(5);x(9);x(13); %先對原序列進(jìn)行位序調(diào)整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(16); X0=W4*x0; %第一級蝶形運(yùn)算X1=W4*x1;X2=W4*x2;X3=W4*x3; for k=0:3 %第二級蝶

6、形運(yùn)算 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用自己的學(xué)號構(gòu)成的輸入序列為（列出數(shù)值，插入圖形）x1=1,9,9,5,0,3,2,5,3,0,1,0,4,7,2,3;5.5對應(yīng)的輸出頻譜序列為（列出數(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六、實(shí)驗(yàn)結(jié)果與分析1. 基4-FFT計(jì)算結(jié)果與matlab自帶fft函數(shù)計(jì)算結(jié)果對比以下是matlab自帶fft函數(shù)的計(jì)算結(jié)果由上述序列和圖像比較可以看到，mat