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