DFT與FFT計(jì)算速度比較分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上大神大學(xué)課 程 設(shè) 計(jì) 說 明 書題目： DFT與FFT計(jì)算速度比較分析 系 別： 工業(yè)自動(dòng)化儀表 年級(jí)專業(yè)： 22級(jí)儀表1班 學(xué) 號(hào)： 2 學(xué)生姓名： 儀表小子 指導(dǎo)教師： 林大神 趙大神 教師職稱： 大神 大神 大神大學(xué)課程設(shè)計(jì)（論文）任務(wù)書院（系）： 大神工程學(xué)院 基層教學(xué)單位： 自動(dòng)化儀表系 學(xué) 號(hào)2學(xué)生姓名儀表小子專業(yè)（班級(jí)）22級(jí)儀表1班設(shè)計(jì)題目DFT與FFT計(jì)算速度比較分析設(shè)計(jì)技術(shù)參數(shù) 用MATLAB實(shí)現(xiàn)DFT及FFT對(duì)任意長度的序列進(jìn)行傅里葉變換DFT與FFT的運(yùn)算時(shí)間比較 設(shè)計(jì)要求利用Matlab或者C語言設(shè)計(jì)DFT和FFT程序，比較兩種頻譜分析方法

2、的計(jì)算速度，并與理論值進(jìn)行比較。工作量先對(duì)兩種算法進(jìn)行介紹，包括推導(dǎo)過程及運(yùn)算性質(zhì)，然后用MATLAB實(shí)現(xiàn)兩種算法，再分別對(duì)兩種算法進(jìn)行運(yùn)算時(shí)間對(duì)比，并分析時(shí)間長短的原因。工作計(jì)劃第一周第二周周一 接受任務(wù)并查閱資料周二到周五上午學(xué)習(xí)相關(guān)知識(shí) 下午編寫程序上機(jī)調(diào)試程序周一到周四上午學(xué)習(xí)相關(guān)知識(shí) 下午編寫程序上機(jī)調(diào)試程序編寫 任務(wù)書參考資料1. 謝平、王娜、林洪斌等，信號(hào)處理原理及應(yīng)用。機(jī)械工業(yè)出版社，2008.102. 王宏，MATLAB 6.5 及其在信號(hào)處理中的應(yīng)用。清華大學(xué)出版社，2004.103. Sanjit K.Mitra 著 孫洪、余翔宇等譯，數(shù)字信號(hào)處理實(shí)驗(yàn)指導(dǎo)書。電子工業(yè)出版

3、社 2005.1指導(dǎo)教師簽字林大神 趙大神基層教學(xué)單位主任簽字謝大仙說明：此表一式四份，學(xué)生、指導(dǎo)教師、基層教學(xué)單位、系部各一份。 2011 年 7 月 13 日 大神工程學(xué)院課程設(shè)計(jì)評(píng)審意見表指導(dǎo)教師評(píng)語： 認(rèn)真 正確完善 完善 較為合理 合理工作態(tài)度 較認(rèn)真 理論分析 一般 軟件設(shè)計(jì) 一般 不認(rèn)真 較差 較差平時(shí)成績： 指導(dǎo)教師簽字： 年 月 日?qǐng)D面及其它成績：答辯小組評(píng)語： 清晰 正確 基本掌握 優(yōu)化設(shè)計(jì) 基本正確原理 了解 不正確 不清楚答辯成績： 組長簽字： 年 月 日課程設(shè)計(jì)綜合成績：答辯小組成員簽字： 年 月 日 專心-專注-專業(yè)摘 要時(shí)域分析方法和頻域分析方法是信號(hào)和系統(tǒng)的分析

4、的兩種方法，本文介紹離散信號(hào)和系統(tǒng)的頻域分析方法，它和連續(xù)信號(hào)和系統(tǒng)的頻域分析方法有所不同，但也有相似之處。本說明書主要是在介紹兩種用于信號(hào)處理的傅里葉變換算法DFT（離散傅里葉變換）和FFT（快速傅里葉變換），分別介紹了這兩種運(yùn)算的推導(dǎo)過程，并且對(duì)這兩種變換作了簡(jiǎn)要的介紹，分析了各自的性質(zhì)。然后通過MATLAB分別實(shí)現(xiàn)了這兩種傅里葉變換，并對(duì)這兩種變換進(jìn)行了運(yùn)算時(shí)間的比較分別對(duì)同一函數(shù)進(jìn)行DFT和FFT計(jì)算兩者的運(yùn)行時(shí)間，并作圖比較。本說明書的程序部分都是在MATLAB環(huán)境下進(jìn)行的運(yùn)算。MATLAB是矩陣實(shí)驗(yàn)室（Matrix Laboratory）的簡(jiǎn)稱，是美國MathWorks公司出品的商

5、業(yè)數(shù)學(xué)軟件，用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算的高級(jí)技術(shù)計(jì)算語言和交互式環(huán)境，主要包括MATLAB和Simulink兩大部分。MATLAB的基本數(shù)據(jù)單位是矩陣，它的指令表達(dá)式與數(shù)學(xué)、工程中常用的形式十分相似，故用MATLAB來解算問題要比用C，F(xiàn)ORTRAN等語言完成相同的事情簡(jiǎn)捷得多。在新的版本中也加入了對(duì)C，F(xiàn)ORTRAN，C+ ，JAVA的支持，可以直接調(diào)用,用戶也可以將自己編寫的實(shí)用程序?qū)氲組ATLAB函數(shù)庫中方便自己以后調(diào)用。本文介紹了DFT與FFT的原理與Matlab實(shí)現(xiàn)程序，以及DFT與FFT的計(jì)算速度的比較。并用guide函數(shù)親自編寫了一個(gè)界面。 關(guān)鍵詞：DFT、

6、FFT、Matlab、運(yùn)算速度、guide目錄摘 要1第一章 DFT原理與Matlab實(shí)現(xiàn)31.1 DFT的原理31.2 DFT的Matlab實(shí)現(xiàn)4第二章 FFT的原理與Matlab實(shí)現(xiàn)62.1 FFT的原理62.1.1 FFT的基本思想62.1.2 基2 FFT算法72.2 FFT的Matlab實(shí)現(xiàn)9第三章 DFT與FFT計(jì)算速度比較分析123.1 FFT與直接計(jì)算DFT的比較123.2 FFT與DFT運(yùn)算時(shí)間Matlab程序133.2.1隨機(jī)序列的DFT計(jì)算時(shí)間程序133.2.2分析兩者運(yùn)算時(shí)間的差異：16第四章 心得體會(huì)18參考文獻(xiàn)：19第一章 DFT原理與Matlab實(shí)現(xiàn)1.1 DFT

7、的原理傅里葉變換就是在以時(shí)間為自變量的“信號(hào)”與以頻率為自變量的“頻譜”函數(shù)之間的某種變換關(guān)系。隨時(shí)間自變量形式的不同，其傅里葉變換的形式也有不同：周期序列的離散傅里葉級(jí)數(shù)(DFS)和非周期序列的傅里葉變換(DTFT)，其表示式分別為： (1.1.1) (1.1.2)在實(shí)際工作中，當(dāng)用數(shù)字計(jì)算機(jī)對(duì)信號(hào)進(jìn)行頻譜分析時(shí)，要求信號(hào)必須以有限長度的離散值作為輸入，而計(jì)算所得的頻譜值自然也是有限、離散的。上述兩種形式的傅里葉變換中，DFS變換滿足時(shí)、頻域自變量的離散化，但其時(shí)間變量和頻率變量又同時(shí)具有周期性；DTFT變換滿足時(shí)間自變量的有限長度(非周期能量有限信號(hào))，但其頻率變量為連續(xù)形式?？梢姡@兩種

8、變換都難以實(shí)際應(yīng)用?？紤]到DFS變換的時(shí)、頻域形式雖是周期序列，但每個(gè)周期卻只有N個(gè)獨(dú)立的復(fù)值，知道其一個(gè)周期的內(nèi)容即可得到其它的內(nèi)容。因此，若從DFS變換的時(shí)、頻域各取出一個(gè)周期，即可構(gòu)造出時(shí)間和頻率自變量皆為離散、有限長度的傅氏變換，這就是離散傅里葉變換(DFT)的引出思想，下面進(jìn)行具體推導(dǎo)。設(shè)是一個(gè)長度為M的有限長序列，由周期序列與有限長序列的本質(zhì)聯(lián)系，可以N()為周期將展開為無重疊的周期序列，即周期延拓為 (1.1.3)再利用式(1.1.1)對(duì)進(jìn)行DFS變換，得到周期離散的頻譜，取的主值序列，代入DFS反變換公式(4-3b)，即 (1.1.4)分析可見：在DFS正變換中，只要把一個(gè)周期

9、內(nèi)的乘以對(duì)應(yīng)的，即可得任意k下的；同理，在DFS反變換中，僅用的一個(gè)周期的值，即可得到任意n下的。如果同時(shí)限制(1.1.1)式中的n和(1.1.4)式中的k，使其都只在區(qū)間內(nèi)取值，就得到了一個(gè)周期的和一個(gè)周期的間的對(duì)應(yīng)關(guān)系 (1.1.5) (1.1.6)式中，N為DFT變換區(qū)間的長度，上兩式即稱為有限長序列的離散傅里葉變換對(duì)。(1.1.5)式稱為離散傅里葉變換，簡(jiǎn)稱DFT；(1.1.6)式稱為離散傅里葉逆變換(Inverse Discrete Fourier Transform)，簡(jiǎn)稱IDFT。1.2 DFT的Matlab實(shí)現(xiàn)程序DFT函數(shù)：functionxk=dft(xn,N)%計(jì)算離散傅

10、里葉變換%-%Xk=dft(xn,N)%Xk=在0<=k<=N-1間的DFT系數(shù)數(shù)組%xn=N點(diǎn)有限長度序列%N=DFT的長度n=0:1:N-1; %n的行向量k=0:1:N-1; %k的行向量WN=exp(-1i*2*pi/N); %Wn因子nk=n'*k; %產(chǎn)生一個(gè)含nk值的N乘N維矩陣WNnk=WN.nk; %DFT矩陣q=xn*WNnk; %DFT系數(shù)的行向量對(duì)一個(gè)單位抽樣序列的DFT變換（N=64）：clear all;N=64;x=zeros(1,N);x(1)=1;xn=0:N-1;subplot(121),stem(xn,x);axis(-1 33 0 1

11、.1);XK=dft(xn,N);subplot(122);stem(abs(XK);DFT Matlab處理結(jié)果：第二章 FFT的原理與Matlab實(shí)現(xiàn)2.1 FFT的原理DFT在數(shù)字信號(hào)處理中有很重要的作用，如頻譜分析、線性卷積等，但由于直接計(jì)算DFT的計(jì)算量與變換區(qū)間長度N的平方成正比，當(dāng)N較大時(shí)，計(jì)算量太大，所以在快速傅里葉變換(Fast Fourier Transform,簡(jiǎn)稱FFT)出現(xiàn)前，直接用DFT進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。直到1965年庫利(JW Cooley)和圖基(JWTukey)提出了DFT運(yùn)算的一種快速方法以后，情況才發(fā)生了根本的變化。多年來，人們不斷改

12、進(jìn)和完善，形成了一系列新型FFT算法，如基2FFT算法、分裂基FFT算法、N為復(fù)合數(shù)的FFT算法等。必須強(qiáng)調(diào)指出：FFT并不是與DFT不同的另外一種變換，而是為減少DFT計(jì)算次數(shù)的一種快速算法。為了解FFT高效算法的重要及實(shí)現(xiàn)思路，先介紹DFT的運(yùn)算特點(diǎn)，再具體討論高效算法。2.1.1 FFT的基本思想從哪些方面能改進(jìn)DFT的運(yùn)算以減少運(yùn)算工作量呢? 如前所述，DFT的運(yùn)算量是與成正比的。顯然，如果一個(gè)大點(diǎn)數(shù)N的DFT能分解為若干小點(diǎn)數(shù)DFT的組合，則可達(dá)到減少運(yùn)算工作量的效果。充分利用系數(shù)的下列固有周期性和對(duì)稱性，使DFT運(yùn)算中的有些項(xiàng)可以合并，從而使長序列的DFT分解為更小點(diǎn)數(shù)的DFT，提

13、高運(yùn)算效率。的對(duì)稱性 的周期性 快速傅里葉變換算法正是基于上述基本思想而發(fā)展起來的。下面介紹最常用的基2 FFT算法(，庫利一圖基算法)。2.1.2 基2 FFT算法基2 FFT算法主要包括兩類：按時(shí)間抽取(Decimation-in-time，簡(jiǎn)稱DIT)法和按頻率抽取(Decmation-in-Frequence，簡(jiǎn)稱DIF)法，本文只介紹DIT算法。設(shè)是列長為的輸入序列，且，其中為整數(shù)。如果不滿足這個(gè)條件，可以人為地加入若干零點(diǎn)來達(dá)到。將按n的奇偶分成兩個(gè)子序列 (2.1.1)則(1.1.5)式可化為由于，故上式又可表示為 (2.1.2)其中和分別是及的點(diǎn)的DFT (2.1.3) (2.

14、1.4)(2.1.2)式表明了個(gè)N點(diǎn)的DFT被分解為兩個(gè)點(diǎn)的DFT。但是這里有一個(gè)問題，即，的列長為，它們的DFT，的點(diǎn)數(shù)也是，即，而卻有N個(gè)點(diǎn)，所以按(2.1.2)式計(jì)算得到的只是 ()的前一半項(xiàng)數(shù)的結(jié)果，要用來表達(dá)全部的值還必須應(yīng)用W系數(shù)的周期性，即這樣可得同理可得另外又考慮到的對(duì)稱性因此，將上述公式代入(2.1.2)中，又可表達(dá)為 (2.1.5) (2.1.6)圖2.1.1 蝶形運(yùn)算符號(hào)由上分析可見，只要求出區(qū)間內(nèi)各個(gè)整數(shù)k值所對(duì)應(yīng)的和值，即可求出區(qū)間內(nèi)的全部值，這一點(diǎn)恰恰是FFT能大量節(jié)省計(jì)算的關(guān)鍵所在。式(2.1.5)、(2.1.6)的運(yùn)算可用圖2.1.1的信號(hào)流圖符號(hào)表示，根據(jù)其形

15、狀稱之為蝶形運(yùn)算符號(hào)。圖 2.1.2 N點(diǎn)DIT-DFT運(yùn)算流圖（N=8）依此類推得8點(diǎn)的DIT-FFT的運(yùn)算流圖如下：2.2 FFT的Matlab實(shí)現(xiàn)程序FFT函數(shù)：function xn=myfft(x)N=length(x);M=log2(N);xtmp=zeros(1,N);value=zeros(1,M);for i=0:N-1 repr=i; for t=1:1:M repr=bitshift(i,1-t); value(t)=bitand(repr,1); end pos=0; for k=1:1:M pos=pos+value(k)*2(M-k); end xtmp(pos+1

16、)=x(i+1);end for i=1:M deepth=2(i-1); width=2(M-i); for t=1:2i:N for k=1:deepth tmp=xtmp(t+k-1); wn=width*(k-1); xtmp(t+k-1)=tmp+exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1); xtmp(t+k+deepth-1)=tmp-exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1); end endendxn=xtmp;對(duì)一個(gè)單位抽樣序列的FFT變換（N=64）：clear all;N=64;x=zeros(1,N);x(1)

17、=1;xn=0:N-1;subplot(121),stem(xn,x);axis(-1 33 0 1.1);XK=fft(xn);subplot(122);stem(abs(XK);FFT Matlab處理結(jié)果 第三章 DFT與FFT計(jì)算速度比較分析3.1 FFT與直接計(jì)算DFT的比較對(duì)于N點(diǎn)的DFT，需要計(jì)算的復(fù)數(shù)乘法和復(fù)數(shù)加法次數(shù)分別是N²和N(N-1)。由前面介紹的按時(shí)間抽取的FFT運(yùn)算流圖可見，每一級(jí)都由個(gè)蝶形運(yùn)算構(gòu)成。因此每一級(jí)運(yùn)算都需要次復(fù)乘和N次復(fù)加(每個(gè)結(jié)加減各一次)。這樣m級(jí)運(yùn)算總共需要復(fù)乘數(shù) 復(fù)加數(shù) FFT計(jì)算量與DFT計(jì)算量比較NDFTFFTDFT的乘法次數(shù)與F

18、FT的乘法次數(shù)之比DFT的加法次數(shù)與FFT加法次數(shù)之比復(fù)數(shù)乘法次數(shù)復(fù)數(shù)加法次數(shù)復(fù)數(shù)乘法次數(shù)復(fù)數(shù)加法次數(shù)2421241416124841.58645612245.32.31625624032648.03.753210249928016012.86.2644096403219238421.310.5128163841625644889636.618.125665536652801024204864.031.951223044608113.856.81024512010240204.8102.320481126422528372.4186.140962457649152682.7341.381925

19、32481260.3630.03.2 FFT與DFT運(yùn)算時(shí)間Matlab程序3.2.1隨機(jī)序列的DFT計(jì)算時(shí)間程序Guide 程序下的主函數(shù)set(handles.TITLE,'string','calculating.');Nmax=str2num(get(handles.N,'string'); axes(handles.FFT_axes) cla; axes(handles.DFT_axes) cla;fft_time=zeros(1,Nmax);for n=1:1:Nmax x=rand(1,n); t=clock; my_fft(x);

20、 fft_time(n)=etime(clock,t);end n=1:1:Nmax; axes(handles.FFT_axes) plot(n,fft_time,'.'); xlabel('N'); ylabel('時(shí)間 (單位:秒)') title('FFT執(zhí)行時(shí)間')my_dft_time=zeros(1,Nmax);for n=1:1:Nmax x=rand(1,n); t=clock; my_dft(x,n); my_dft_time(n)=etime(clock,t);end n=1:1:Nmax; axes(han

21、dles.DFT_axes) plot(n,my_dft_time,'.'); xlabel('N'); ylabel('時(shí)間 (單位:秒) ')title(' DFT執(zhí)行時(shí)間')set(handles.TITLE,'string','DFT_AND_FFT_TIME');3.2.2 Matlab實(shí)驗(yàn)結(jié)果：Guide程序界面運(yùn)行結(jié)果Nmax =128Nmax =512N=1024N=20483.2.2分析兩者運(yùn)算時(shí)間的差異：由前面介紹的按時(shí)間抽取的FFT運(yùn)算流圖可見，每一級(jí)都由個(gè)蝶形運(yùn)算構(gòu)成。因此每

22、一級(jí)運(yùn)算都需要次復(fù)乘和N次復(fù)加(每個(gè)結(jié)加減各一次)。這樣m級(jí)運(yùn)算總共需要復(fù)乘數(shù) (4.3.45)復(fù)加數(shù) (4.3.46)實(shí)際計(jì)算量和這個(gè)數(shù)字稍有出入，因?yàn)橛蛇\(yùn)算流圖可見，這種情況共有次，這幾個(gè)系數(shù)是都不用乘法運(yùn)算的，但這種情況在直接計(jì)算DFT中也是有的，且當(dāng)N較大時(shí)，這些影響也較小。所以為了統(tǒng)一作比較我們不考慮以上特例。綜上所述，可以得出如下結(jié)論；按時(shí)間抽取法所需的復(fù)乘數(shù)和復(fù)加數(shù)都是與成正比的，而直接計(jì)算DFT時(shí)所需的復(fù)乘數(shù)為，復(fù)數(shù)加為N(N-1)次。當(dāng)N>1時(shí)，N2>N2log2N，從而，DIT-FFT算法比直接計(jì)算DFT的運(yùn)算次數(shù)大大減小。例如時(shí)，0641282565121024641282565121024DFT算法FFT算法乘法次數(shù)(×1000)N(取樣點(diǎn)數(shù))圖 3.2.2 FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線這樣，就使運(yùn)算效率提高200多倍。圖4.3