DSP課程設(shè)計(jì)-8點(diǎn)基于DIF的FFT的實(shí)現(xiàn)

1、課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名： 專(zhuān)業(yè)班級(jí)： 指導(dǎo)教師： 工作單位： 題 目：8點(diǎn)基于DIF的FFT的實(shí)現(xiàn)初始條件： 具備數(shù)字信號(hào)處理的理論知識(shí)；具備Matlab編程能力；熟悉基于DIF的FFT的實(shí)現(xiàn)原理；提供編程所需要的計(jì)算機(jī)一臺(tái)要求完成的主要任務(wù)：（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）1、獨(dú)立編寫(xiě)一個(gè)8點(diǎn)的基于DIF的FFT實(shí)現(xiàn)程序，不能使用matlab自帶的FFT實(shí)現(xiàn)函數(shù)2、程序運(yùn)行結(jié)果與matlab自帶函數(shù)結(jié)果進(jìn)行對(duì)比3、完成符合學(xué)校要求的設(shè)計(jì)說(shuō)明書(shū)時(shí)間安排：一周，其中3天程序設(shè)計(jì)，2天程序調(diào)試指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日XX大學(xué)數(shù)字信

2、號(hào)處理課程設(shè)計(jì)說(shuō)明書(shū)目錄摘要I1 Matlab軟件簡(jiǎn)介11.1 Matlab語(yǔ)言的歷史11.2 Matlab軟件概況11.3 Matlab的特點(diǎn)12 快速傅里葉變換算法分析32.1 FFT簡(jiǎn)介32.2 按頻率抽選的FFT算法33 程序設(shè)計(jì)63.1 程序設(shè)計(jì)思路63.2 要使用的Matlab函數(shù)64 程序流程圖85 源程序95.1 直接調(diào)用FFT函數(shù)源程序95.2 FFT計(jì)算源程序96 程序運(yùn)行結(jié)果分析116.1 程序運(yùn)行結(jié)果116.2 結(jié)果分析127 課程設(shè)計(jì)心得體會(huì)13參考文獻(xiàn)14致謝15摘要快速傅里葉變換（FFT）是離散傅里葉變換（DFT）的快速算法，F(xiàn)FT算法通過(guò)利用旋轉(zhuǎn)因子的性質(zhì)，將一

3、個(gè)大點(diǎn)數(shù)DFT化成幾個(gè)小點(diǎn)數(shù)DFT，就可以大大減少運(yùn)算量。DIF-FFT是利用頻率抽選的FFT算法，在Matlab中可以通過(guò)三重循環(huán)語(yǔ)句實(shí)現(xiàn)。關(guān)鍵詞：FFT，蝶形運(yùn)算，倒序排列IXX大學(xué)數(shù)字信號(hào)處理課程設(shè)計(jì)說(shuō)明書(shū)1 Matlab軟件簡(jiǎn)介1.1 Matlab語(yǔ)言的歷史70年代后期,身為美國(guó)New Mexico大學(xué)計(jì)算機(jī)系系主任的Cleve Moler發(fā)現(xiàn)學(xué)生用FORTRAN編寫(xiě)接口程序很費(fèi)時(shí)間,于是他開(kāi)始自己動(dòng)手,利用業(yè)余時(shí)間為學(xué)生編寫(xiě)EISPACK和LINPACK的接口程序。Cleve Moler給這個(gè)接口程序取名為Matlab。1984年，為了推廣Matlab在

4、數(shù)值計(jì)算中的應(yīng)用，Cleve Moler、Johon Little等正式成立了Math works公司，從而把Matlab推向市場(chǎng)，并開(kāi)始了對(duì)Matlab工具相等的開(kāi)發(fā)設(shè)計(jì)。 1.2 Matlab軟件概況Matlab是MatrixLaboratory的縮寫(xiě)，意為矩陣實(shí)驗(yàn)室。它具有強(qiáng)大的矩陣處理功能和繪圖功能，進(jìn)還能進(jìn)行文字處理，繪圖，建模仿真等功能。隨著版本的不斷升級(jí)，它在數(shù)值計(jì)算及符號(hào)計(jì)算功能上得到了進(jìn)一步完善。Matlab已經(jīng)發(fā)展成為多學(xué)科、多種工作平臺(tái)的功能強(qiáng)大的大型軟件。在歐美等高校，Matlab已經(jīng)成為線(xiàn)性代數(shù)、自動(dòng)控制理論、概率論及數(shù)理統(tǒng)計(jì)、數(shù)字信號(hào)處理、時(shí)間序列分析、動(dòng)態(tài)系統(tǒng)仿真

5、等高級(jí)課程的基本教學(xué)工具。1.3 Matlab的特點(diǎn)Matlab有以下一些特點(diǎn)：Matlab的幫助功能很強(qiáng)大，自帶有詳細(xì)的幫助手冊(cè)，基于HTML的完整的幫助功能，也可以用help命令來(lái)得到幫助信息。程序語(yǔ)法與C語(yǔ)言類(lèi)似，設(shè)計(jì)自由度大，方便我們編程。例如在Matlab里，用戶(hù)無(wú)需對(duì)變量預(yù)定義就可使用。大量數(shù)學(xué)函數(shù)已經(jīng)定義好，并且有很強(qiáng)的用戶(hù)自定義函數(shù)的能力。Matlab有高級(jí)的程序環(huán)境，但程序環(huán)境很簡(jiǎn)單易用，有與其它語(yǔ)言編寫(xiě)的程序結(jié)合和輸入輸出格式化數(shù)據(jù)的能力；Matlab既具有結(jié)構(gòu)化的控制語(yǔ)句，又有面向?qū)ο缶幊痰奶匦浴＿€有一個(gè)原因使Matlab受人們歡迎的，那就是Matlab源程序具有很大的開(kāi)

6、放性。除了內(nèi)部函數(shù)以外，所有Matlab的核心文件和工具箱文件都是可讀可改的源文件，用戶(hù)可通過(guò)對(duì)源文件的修改以及加入自己的文件構(gòu)成新的工具箱。Matlab有強(qiáng)大的的圖形繪制功能。在Matlab里，數(shù)據(jù)可視化的操作非常簡(jiǎn)單易用。Matlab還有較強(qiáng)的編輯圖形界面的能力?？梢杂脕?lái)聲成圖解和可視化的二維、三維圖。Matlab還擁有功能強(qiáng)大的各種工具箱。其工具箱分為兩類(lèi)：功能性工具箱和學(xué)科性工具箱。功能性工具箱主要用來(lái)擴(kuò)充其符號(hào)計(jì)算功能，圖示建模仿真功能，文字處理功能以及與硬件實(shí)時(shí)交互功能。功能性工具箱用于多種學(xué)科。而學(xué)科性工具箱是專(zhuān)業(yè)性比較強(qiáng)的，如（control、signal proceessin

7、g 、commumnication） toolbox等。這些工具箱都是由該領(lǐng)域內(nèi)學(xué)術(shù)水平很高的專(zhuān)家編寫(xiě)的，所以用戶(hù)無(wú)需編寫(xiě)自己學(xué)科范圍內(nèi)的基礎(chǔ)程序，而直接進(jìn)行高，精，尖的研究，能極大地促進(jìn)我們的學(xué)習(xí)研究工作。雖然Matlab有很多優(yōu)點(diǎn)，但它也有一些缺點(diǎn)，比如：由于Matlab的程序不用編譯等預(yù)處理，也不生成可執(zhí)行文件，程序?yàn)榻忉寛?zhí)行，所以速度較慢。2 快速傅里葉變換算法分析2.1 FFT簡(jiǎn)介快速傅里葉變換（FFT）是離散傅里葉變換（DFT）的快速算法，他在傅里葉變換理論上并沒(méi)有新的發(fā)現(xiàn)，但是卻極大的減少了離散傅里葉變換的運(yùn)算量?？焖俑道锶~變換是1965年由J.W.庫(kù)利和T.W.圖基提出的。19

8、65年，庫(kù)利和圖基合作在Mathematics of Computation上發(fā)表了論文An Algorithm for the Machine Computation of Complex Fourier Series，提出了按時(shí)抽取的快速傅立葉變換算法，也稱(chēng)庫(kù)利-圖基算法，被視為DSP走向應(yīng)用的開(kāi)端。從此，對(duì)快速傅里葉變換算法的研究便不斷深入，數(shù)字信號(hào)處理這門(mén)新興學(xué)科也隨FFT的出現(xiàn)和發(fā)展而迅速發(fā)展。之所以需要快速傅里葉變換，是因?yàn)殡x散傅里葉變換的運(yùn)算量較大。離散傅里葉變換的公式為：正變換：n=0，1，2，N-1逆變換： n=0，1，2，N-1一般情況下WN，x(n)，X（k）都是復(fù)序列，

9、計(jì)算一個(gè)完整的N點(diǎn)DFT需要N2次復(fù)數(shù)乘法與N-1次復(fù)數(shù)加法，當(dāng)N極大時(shí)運(yùn)算量與N2成正比，運(yùn)算量將過(guò)于巨大，不方便應(yīng)用。而FFT算法通過(guò)利用旋轉(zhuǎn)因子的性質(zhì)，將一個(gè)大點(diǎn)數(shù)DFT化成幾個(gè)小點(diǎn)數(shù)DFT，就可以大大減少運(yùn)算量。2.2 按頻率抽選的FFT算法FFT算法主要有兩種，按時(shí)間抽選的FFT的算法（DIT-FFT）和按頻率抽選的FFT算法（DIF-FFT）。這里主要介紹DIF-FFT。DIF-FFT算法是將輸入序列x（k）分成前后兩個(gè)部分。k為偶數(shù)k為奇數(shù)由于，則所以k為偶數(shù)k為奇數(shù)把k按奇數(shù)和偶數(shù)分， r=0，1，N/2-1將X（k）分為兩部分：令，可得，r=0，1，2，N/2-1由此可得頻率

10、抽選法蝶形運(yùn)算單元，如圖2.1所示圖2.1頻率抽選法蝶形運(yùn)算單元這樣可以把一個(gè)N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT的組合，兩個(gè)N/2點(diǎn)DFT還可以繼續(xù)分解，設(shè)N=2M，則經(jīng)過(guò)M-1次分解，最后可以分解成為N/2個(gè)兩點(diǎn)DFT，可以由一個(gè)蝶形運(yùn)算來(lái)求解。例如8點(diǎn)DIF-FFT蝶形運(yùn)算圖如圖2.2圖2.2 8點(diǎn)DIF-FFT運(yùn)算流圖。輸出序列的排列規(guī)律不是從小到大按順序的，而是按照倒敘規(guī)則排序的，即先將0-7轉(zhuǎn)換為二進(jìn)制數(shù)，然后將二進(jìn)制數(shù)左右倒序，再轉(zhuǎn)為十進(jìn)制就可以得到新的數(shù)列，即：0，4，2，6，1，5，3，7。3 程序設(shè)計(jì)3.1 程序設(shè)計(jì)思路由8點(diǎn)FFT運(yùn)算的蝶形圖可知，F(xiàn)FT運(yùn)算的基本單元是一個(gè)

11、個(gè)蝶形運(yùn)算單元，一個(gè)蝶形運(yùn)算單元可以用幾條語(yǔ)句實(shí)現(xiàn)，然后可以用循環(huán)語(yǔ)句來(lái)進(jìn)行各個(gè)蝶形運(yùn)算單元的計(jì)算。8點(diǎn)FFT的蝶形運(yùn)算有3級(jí)，第1級(jí)有1組，每組4個(gè)蝶形運(yùn)算單元，旋轉(zhuǎn)因子是、；第2級(jí)有2組，每組2個(gè)蝶形運(yùn)算單元，循環(huán)因子是，；第3級(jí)有4組，每組1個(gè)蝶形運(yùn)算單元，旋轉(zhuǎn)因子是?？偨Y(jié)運(yùn)算規(guī)律，來(lái)設(shè)定循環(huán)語(yǔ)句。第一層循環(huán)在1到3級(jí)間循環(huán)，循環(huán)變量mm=1，2，3。旋轉(zhuǎn)因子下標(biāo)Nm=24-mm=8，4，2。第二層循環(huán)在該級(jí)的各組間循環(huán)，每級(jí)有2mm-1組，每組第一行對(duì)應(yīng)的x值為：第1級(jí)是x(0)，第2級(jí)是x(0)，x(4)，第3級(jí)是x(0)，x(2)，x(4)，x(6)。設(shè)第二層循環(huán)變量為p，則在Ma

12、tlab中，p=0：Nm：7。第三層循環(huán)在該組的各個(gè)蝶形運(yùn)算單元間循環(huán)，每組有Nm/2個(gè)蝶形運(yùn)算單元，則循環(huán)變量k從1到Nm/2，旋轉(zhuǎn)因子是，每次蝶形運(yùn)算跨越的行數(shù)是Nm/2，則參加蝶形運(yùn)算的x值為x(k+p)和x(k+p+Nm/2)。循環(huán)完成后則FFT運(yùn)算完成，再將x序列按倒敘規(guī)律重新排列就可以得到X(k)序列。3.2 要使用的Matlab函數(shù)程序設(shè)計(jì)思路已經(jīng)有了，結(jié)下來(lái)分析如何在Matlab里具體實(shí)現(xiàn)該程序。Matlab的語(yǔ)法并不困難，掌握了所需的函數(shù)后就能很快設(shè)計(jì)出程序了，這里主要介紹一下要用到的函數(shù)。直接用Matlab計(jì)算N點(diǎn)FFT可以用函數(shù)fft(x,N)，在此課設(shè)中用來(lái)和自編程序?qū)?/p>

13、照結(jié)果。還用到一些計(jì)算函數(shù)，如exp(x)計(jì)算e的x次方,abs(x)計(jì)算x絕對(duì)值。倒序運(yùn)算主要用到的函數(shù)有，dec2bin(x,m)，是把十進(jìn)制序列x轉(zhuǎn)換為m位二進(jìn)制數(shù)，bin2dec(x,m)也是類(lèi)似功能。fliplr函數(shù)是將一個(gè)矩陣左右顛倒，則程序中求倒序的語(yǔ)句就是：d=bin2dec(fliplr(dec2bin(0:N-1,m)+1;y=x(d);x是N點(diǎn)序列，執(zhí)行完語(yǔ)句后，y序列就是x序列的倒序排列。計(jì)算完成結(jié)果要繪圖輸出，要用到的函數(shù)是subplot(a,b,c)，功能是讓下面的語(yǔ)句繪制a行b列圖形中的第c個(gè)。繪圖用stem(x,y)函數(shù)，是以x序列為橫軸，y序列為縱軸，繪制離散

14、的圖像。繪完圖可以用title函數(shù)給圖像命名。4 程序流程圖開(kāi)始設(shè)定輸入序列求出蝶形運(yùn)算級(jí)數(shù)m=3循環(huán)mm=1到3級(jí)蝶形運(yùn)算求該級(jí)旋轉(zhuǎn)因子下標(biāo)Nm循環(huán)該級(jí)1到2mm-1組蝶形運(yùn)算循環(huán)該組1到23-mm個(gè)蝶形運(yùn)算計(jì)算一個(gè)蝶形運(yùn)算單元序列倒序后繪圖結(jié)束YYYNNN圖4.1 程序流程圖5 源程序5.1 直接調(diào)用FFT函數(shù)源程序以下是直接調(diào)用Matlab自帶的FFT函數(shù)計(jì)算的源程序，其輸入序列為x=0 2 4 6 0 2 4 6，求出FFT結(jié)果y=X(k)后對(duì)其幅值和原序列進(jìn)行繪圖。N=8;%FFT點(diǎn)數(shù)為8點(diǎn)n=0:N-1;%橫坐標(biāo)序列x=0 2 4 6 0 2 4 6 ;%設(shè)定輸入x(n)序列y=f

15、ft(x,N)%調(diào)用FFT函數(shù)求X(k)序列，y=X(k)mag=abs(y);%求幅值subplot(2,1,1);stem(n,x);%繪制原序列title('輸入序列x(n)');subplot(2,1,2);stem(n,mag);%繪制X(k)序列title('8點(diǎn)調(diào)用FFT函數(shù)計(jì)算結(jié)果')5.2 FFT計(jì)算源程序以下是本次課程設(shè)計(jì)編寫(xiě)的FFT計(jì)算程序，輸入序列和5.1的程序一樣，都是x=0 2 4 6 0 2 4 6，y等于FFT輸出序列X(k)，最后對(duì)y的幅值和原序列進(jìn)行繪圖。N=8;%設(shè)定FFT點(diǎn)數(shù)為8點(diǎn)n=0:N-1;%橫坐標(biāo)序列x=0 2 4

16、 6 0 2 4 6 ;%設(shè)定輸入序列x(n)x1=x;%暫存x序列到x1m=log2(N);%求蝶形運(yùn)算級(jí)數(shù)mfor mm=1:m%循環(huán)mm=1到3級(jí)蝶形運(yùn)算Nm=2(m-mm+1);%求該級(jí)旋轉(zhuǎn)因子下標(biāo)Nm，Nm=8,4,2 for p=0:Nm:N-1 %循環(huán)該級(jí)1到2mm-1組蝶形運(yùn)算 for k=1:Nm/2 %循環(huán)該組1到23-mm個(gè)蝶形運(yùn)算 kp=k+Nm/2+p;%確定蝶形運(yùn)算對(duì)應(yīng)單元下標(biāo) a=x(kp);%暫存x(xp) x(kp)=(x(k+p)-a)*exp(-j*2*pi*(k-1)/Nm); x(k+p)=x(k+p)+a;%進(jìn)行蝶形運(yùn)算 end endendd=bi

17、n2dec(fliplr(dec2bin(0:N-1,m)+1;%把0-7倒序排列y=x(d)%y=x序列的倒序，即y=X(k)mag=abs(y);%求y幅值x=x1;%x恢復(fù)成原序列subplot(2,1,1);stem(n,x);%繪制原序列title('輸入序列x(n)');subplot(2,1,2);stem(n,mag);%繪制X(k)序列title('8點(diǎn)FFT計(jì)算結(jié)果')6 程序運(yùn)行結(jié)果分析6.1 程序運(yùn)行結(jié)果首先在Matlab中輸入源程序，然后保存，選擇Debug菜單中的Run執(zhí)行程序。如圖6.1：圖6.1 Matlab界面首先運(yùn)行程序1，即

18、直接調(diào)用Matlab自帶的FFT函數(shù)計(jì)算。運(yùn)行結(jié)果如圖6.2所示。y序列即X(k)序列為y =24 0 -8+8i 0 -8 0 -8-8i 0。圖6.2調(diào)用FFT函數(shù)運(yùn)行結(jié)果1然后是用自己編寫(xiě)的FFT計(jì)算函數(shù)，運(yùn)行得到如圖6.3所示結(jié)果。y序列即X(k)序列為y =24 0 -8+8i 0 -8 0 -8-8i 0。圖6.3運(yùn)行結(jié)果26.2 結(jié)果分析通過(guò)比較圖6.2和圖6.3可以看出，兩者的FFT結(jié)果完全一樣，可以證明編寫(xiě)的FFT程序正確，達(dá)到了課程設(shè)計(jì)的任務(wù)要求。而且本程序不僅可以計(jì)算8點(diǎn)FFT，也可以計(jì)算N點(diǎn)FFT（N=2m），經(jīng)測(cè)試結(jié)果也是正確的。7 課程設(shè)計(jì)心得體會(huì)通過(guò)Matlab一

19、周以來(lái)的學(xué)習(xí)研究，我對(duì)Matlab有了初步的認(rèn)識(shí)，我掌握了Matlab的基本操作，并學(xué)會(huì)了用Matlab解決一些電路和數(shù)學(xué)上的問(wèn)題，下面是我具體的一些體會(huì)Matlab功能非常強(qiáng)大，幾乎可以計(jì)算我們目前所遇到的任何問(wèn)題，不僅可以計(jì)算數(shù)學(xué)問(wèn)題，也可以用來(lái)解決電路等其他學(xué)科的各種問(wèn)題。而且我們可以自編函數(shù)，從而可以解決更多樣的問(wèn)題。但以目前我們的知識(shí)，只能掌握Matlab的一小部分功能，在以后的學(xué)習(xí)中，我還需要繼續(xù)學(xué)習(xí)Matlab的相關(guān)知識(shí)。Matlab雖然功能非常強(qiáng)大，但其操作卻非常簡(jiǎn)單，它的語(yǔ)法類(lèi)似于我們以前學(xué)過(guò)的C語(yǔ)言，使我很容易上手，而其語(yǔ)法比C語(yǔ)言更為自由，限制更少，語(yǔ)法類(lèi)似于自然語(yǔ)言，簡(jiǎn)潔而智能化，使我可以很容易的編寫(xiě)程序且不容易出錯(cuò)。關(guān)于繪圖的操作則比C語(yǔ)言簡(jiǎn)單得多，用幾條簡(jiǎn)單的語(yǔ)句就可以繪出各種曲線(xiàn)、圖形，使我們的學(xué)習(xí)研究變的非常方便。通過(guò)本次課程設(shè)計(jì)我掌握了FFT的編程方法，對(duì)FFT有了更深刻的了解。我認(rèn)為學(xué)習(xí)Matlab的關(guān)鍵在于函數(shù)，只要掌握了函數(shù)的用法，那么就能很快的編出程序。而Matlab的難點(diǎn)也正是函數(shù)，因?yàn)镸atlab擁有大量