【正文】 n N N L? ? ? ? ? （ 49） 利用 FFT算法可以求得 []xn 和 []yn 的 L 點 DFT，分別是 []Xk 和 []Yk，利用DTFT 卷積性質(zhì)，卷積 [ ]* [ ]x n y n 等于乘積 [ ] [ ]X k Y k 的 L 點 DFT 反變換，這也可以通過 FFT 算法得到。 xlabel(39。 plot(k*gamma,abs(Xapp(1:length(k))),39。 %計算 X(w)近似值 t=0:T:2。為了將存入 X 中的 )( kjX ? 的樣本排列成使 )1( ?KX 就是對于 10 ??? Nk ，在 )2( ???? Nk?? 上求得武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 15 的 CTFT,可用 X=fftshift(tau*fft(x))。利用 MATLAB 可以計算（ CTFT）積分的數(shù)值近似。 已知一個固定的時間間隔 T ，選擇讓 T 足夠小，使得每一個 T秒的間隔( 1)nT t n T? ? ? 內(nèi)， ()xt 的變化很小，則式中積分可近似為 ( 1 )0( ) ( ) ( )nT i w tnTnX e d t x n T?? ? ??? ? ? ( 1 )01[ ] ( )i t t n Tt n Tn e x n Ti??? ? ? ????? ? 01 ()iT i n Tne e x n Ti ? ??? ? ???? ? （ 42） 假設(shè) N 足夠大，對于所有 nN? 的整數(shù)，幅值 ()xnT 很小，則式（ 42）變?yōu)? 101( ) ( )iT N i n TneX e x n Ti ? ?? ?? ? ???? ? （ 43） 當(dāng) 2/k NT??? 時，式（ 42）兩邊的值為 2 / 2 /1 2/02 1 1( ) ( ) [ ]2 / 2 /i k N i k NN i n k Nnk e eX e x n T X kN T i k N T i k N T???? ????? ??????? （ 44） 其中 []Xk 代表抽樣信號 [ ] ( )x n x nT? 的 N 點 DFT 。 還要說明圖 33所示的算法的另一個優(yōu)點。 )(nx 是一個 N 點序列， 1,...,2,1,0 ?? Nn 。下面介紹改進的 Goertzel 算法，這種算法所需的實數(shù)乘法次數(shù)約為直接方法的一半。 )()()( nhnxny kk ?? （ 319） 其中， )(nx 是輸入的 N 點序列，另一個序列被看作濾波器的沖激響應(yīng)序列 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 11 )()( nuWnh knNk ?? 。 Rader 算法提出了利用點數(shù)為 N(N 為質(zhì)數(shù) )的 DFT 進行長度為 N1的回旋折積來表示原本的 DFT，如此就可利用折積用一對基本的 FFT 來計算 DFT。(RaderBrenner 以及 QFT 算法是為了 2 的指數(shù)所設(shè)計的算法，但依然可以適用在可分解的整數(shù)上。計算每個對偶結(jié)點對只需一次乘法，事實上由式（ 38）可得 11( ) ( ) [ ]2 pll lNx i x i i W?? ? ? 211( ) ( ) [ ]22 pl l lllNNx i x i x i W??? ? ? ? （ 310） 式中： lrlr nP ??? ??? 2...2 221 0n ； 0222 2...22 nnP lrlrlr ???? ???? 別為式（ 39）中 1?ln ?。?，１時對應(yīng)的 P值。 次乘法及 N(N1)次復(fù)數(shù)加法。3. 正弦基函數(shù)是微分運算的本征函數(shù) ,從而使得線性微分方程的求解可以轉(zhuǎn)化為常系數(shù)的代數(shù)方程的求解 .在線性時不變雜的卷積運算為簡單的乘積運算 ,從而提供了計算卷積的一種簡單手段 。因此，也可以說，傅立葉變換將原來難以處理的時域信號轉(zhuǎn)換成了易于分析的頻域信號（信號的頻譜），我們可以利用一些專業(yè)工具對這些頻域信號進行加工、處理。承接上面的例子，當(dāng) 1024?時，總的運算次數(shù)就變成了 525312 次，這樣看來，節(jié)省了大約 50%的運算量。 1965 年 , 和 發(fā)現(xiàn)了 DFT 的一種快速算法 ,經(jīng)過后來學(xué)者的進一步改進 , 很快便形成了一套高效的運算方法 ,即現(xiàn)在通用的快速傅里葉變換 , 簡稱 FFT( The Fast Fourier Transform)。 1. 2 課題研究的意義 如上所述，基于對 DSP的快速傅里葉變換算法的研究，從而使 FFT算法能夠有效地在 DSP芯片上實現(xiàn)。應(yīng)當(dāng)指出的是，也是因為當(dāng)時電子數(shù)字計算機的“落后”條件也促成了這個算法的提出。 在信號處理中，離散傅里葉變換（ Discrete Fourier Transform， DFT）是比較常用的變換方法之一，它在各種數(shù)字信號處理系統(tǒng)中扮演著及其重要的角色。它能夠?qū)M足一定條件的某個 函數(shù) 表示成為正弦基 函數(shù) 的線性組合或者積分。 傅里葉變換的理論與方法在“數(shù)理方程”、“線性系統(tǒng)分析”、“信號處理、仿真”等很多學(xué)科領(lǐng)域都有著廣泛應(yīng)用 ,由于計算機只能處理有限長度的離散的序列 ,所以真正在計算機上運算的是一種離散傅里葉變換 . 雖然傅里葉運算在各方面計算中有著重要的作用，但是它的計算過于復(fù)雜，大量的計算對于系統(tǒng)的運算負擔(dān)過于龐大，使得 一些對于耗電量少，運算速度慢的系統(tǒng)對其敬而遠之，然而，快速傅里葉變換的產(chǎn)生，使得傅里葉變換大為簡化，在不犧牲耗電量的條件下提高了系統(tǒng)的運算速度，增強了系統(tǒng)的綜合能力，提高了運算速度，因此快速傅里葉變換在生產(chǎn)和生活中都有著非常重要的作用，對于學(xué)習(xí)掌握都有著非常大的意義。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。 畢業(yè)設(shè)計 (論文 ) 題 目 快速傅里葉變換算法及其在信號處理中的應(yīng)用 專 業(yè) 班 級 學(xué) 號 姓 名 指 導(dǎo) 教 師 學(xué) 院 名 稱 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進行的研究工作及取得的成果。本人完全意識到本聲明的法律后果由本人承擔(dān)。它對傅氏變換的理論并沒有新的發(fā)現(xiàn)，但是對于在計算機系統(tǒng)或者說數(shù)字系統(tǒng)中應(yīng)用離散傅立葉變換，可以說是進了一大步。最后還可以根據(jù)傅立葉反變換將這些頻 域信號轉(zhuǎn)換成原來的時域信號，這是一種特殊的積分變換。因為它本身就具有一系列的優(yōu)點，所以能夠有效地促進工程技術(shù)領(lǐng)域的技術(shù)改造和科學(xué)發(fā)展，應(yīng)用領(lǐng)域也更加地廣泛、深入，越來越受到人們的重視?？焖俑道锶~變換（ Fast Fourier Transform， FFT）并非與離散傅里葉變換完全不同的另一種變換，而是為了減少 DFT 計 算次數(shù)而誕生的一種快速、有效的算法。除了需要普通微處理器所強調(diào)的高速運算和控制能力之外，鑒于實時數(shù)字信號處理的特點，在處理器結(jié)構(gòu)、指令系統(tǒng)、指令流程上做了很大程度上的改進。比如，計算一個 N 點的 DFT ,一般需要2N次復(fù)數(shù)乘法和 N(N1)次復(fù)數(shù)加法運算 .因此 ,當(dāng) N較大或要求對信號進行實時處理時 ,往往很難實現(xiàn)達到所需的運算速度。如此變換以后，總的運算次數(shù)就變成了2/)2/(2 22 NNN ???。該反變換從本質(zhì)上說也就是一種累加處理，這樣便可以將單獨改變的正弦波信號轉(zhuǎn)換成一個信號。2. 傅立葉變換的逆變換容易求出 ,而且形式與正變換非常類似 。10)( )(0 ??? ??? Nne NnkxX NKn k ?? (31) 由 (31)式可知，對每一個 n，計算 X(ｎ )須作 N次復(fù)數(shù)乘法及 N1次復(fù)數(shù)加法，要完成這組變換共需 N2 錯誤 !未找到引用源。將 ()lxi與 ( /2 )llx i n? 稱為第 L個數(shù)組中的對偶結(jié)點對。 Bruun 以及 QFT 算法是不斷的把 DFT 分成許多較小的 DFT 運算。 Winograd 也可以利用剩余值定理來簡化 DFT。 由于 1))(2( ?? ???? kNNjkNN eW 故式（ 316）可化為 )(1010 )()()( mNkNNmkmNNmkNN WmxWmxWkX ??????? ????1,....,2,1,0 ?? Nk （ 317） 定義序列 )(nyk 為 )(10 )()( mnkNNmk Wmxny ?????? （ 318） 可見 )(nyk 是由兩個序列卷積而得到的序列。所以當(dāng) N 不大時，上述算法的效率稍差 [10]。 。在這種較為有效的方案中，仍具有這樣的優(yōu)點，即必須計算和存儲的系數(shù)只有 ))/2cos(( kN? 和 kNW 。當(dāng) , 0 ,1, 2 , , 1k k N? ? ? ? ?時，利用 FFT算法可計算 ()X? 。很多信號都能用（ 41）式連續(xù)時間傅立葉變換（ CTFT）來表示。為了將頻率樣本置于上升的順序，能用函數(shù) fftshift。)。 Xact=exp(i*w)*2*i.*(w.*cos(w)sin(w))./(w.*w)。)。再次運行程序后輸入 N=512， T=，此時 ?? ，得到實際的和近似的傅里葉變換的幅度譜如圖 43 所示。 stem(n,x)。 n=0:15。) subplot(3,1,3)。 xlabel(39。k=0:L1。)。)。 xlabel(39。 xlabel(39。 a) 絕對值最小的 80%系數(shù)為 0 的重構(gòu)信號（ FFT） b) 絕對值最小的 90%系數(shù)為 0 的重構(gòu)信號（ FFT） 圖 46 用 FFT壓縮后的重構(gòu)信號 相關(guān) Matlab 程序如下 : function wc=press(w,r) %壓縮函數(shù) %輸入信號數(shù)據(jù) w,壓縮率 r %輸出壓縮后的信號數(shù)據(jù) if(r0)|(r1) error(39。 wc=(abs(w)=tol).*w。 plot(t,y,39。重構(gòu)信號 39。 a) 絕對值最小的 80%系數(shù)為 0 的重構(gòu)信號（ Harr） b) 絕對值最小的 90%系數(shù)為 0 的重構(gòu)信號（ Harr） 圖 47 用 Harr小波壓縮后的重構(gòu)信號 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 22 相關(guān) Matlab 程序如下 function [unbiased_variance,error]=daubp(t,y,n,r) %利用 Daubechies 系列小波做離散信號壓縮 %輸入時間 t,原信號 y,分解層數(shù) n,以及壓縮率 r %輸出原信號和壓縮后重構(gòu)信號的 圖像 ,以及重構(gòu)均方差和相對 l^2誤差 if(r0)|(r1) error(39。 %調(diào)用壓縮函數(shù) yc=waverec(cc,l,39。 legend(39。 f=t+cos(4*pi*t)+1/2*sin(8*pi*t)。 randn(1,N)。)。%對信號進行 FFT 變換 magY=abs(Y)。 ylabel(39。 plot(f,angY)。)。網(wǎng)址是： 武漢工程大學(xué)畢業(yè)設(shè)計 (論文 )說明書 25 下載后的數(shù)據(jù)存放在文件“ ”中，里面有四列數(shù)據(jù)，第一年是日期，第三列是太陽耀斑的平均數(shù)，第四列平滑后太陽耀斑的平均數(shù)，可以得到從 1749 年到當(dāng)前年月（ 2020 年 4 月）的耀斑數(shù)據(jù)。 grid?？梢酝ㄟ^數(shù)第一個峰值和第二個峰值之間的月份來估計周期的值。ylabel(39。 spd=csvread(39。如果信號 ()xt 是連續(xù)時間形式的，首先還要對其進行抽樣，得到離散時間形式的信號 [ ] ( ) | ( )t n Tx n x t x n T???，根據(jù) Nyquist定理，抽樣間隔 T 應(yīng)滿 max/T ??? ，其中 max? 是 ()xt 中的最大頻率分量。 ylabel(39。N=5