點基于DIT的FFT的實現(xiàn)

1、目 錄摘要1 FFT原理與實現(xiàn)11.1引言11.2 DFT計算公式11.3旋轉(zhuǎn)因子WN的特性11.4調(diào)用8點計算16點52 程序代碼62.1 計算8點FFT代碼62.2計算算16點FFT代碼73上機過程83.1編寫8點FFT函數(shù)83.2調(diào)用系統(tǒng)函數(shù)83.3 編寫16點FFT函數(shù)93.4調(diào)用系統(tǒng)函數(shù)94 心得體會10參考文獻11摘 要 FFT，即為快速傅氏變換，是離散傅氏變換的快速算法，它是根據(jù)離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。FFT算法可分為按時間抽取算法和按頻率抽取算法 本文詳細介紹了快速傅里葉算法的原理及推詳細推導過程，并給出了8點fft的蝶形圖及m

2、atlab程序代碼，并通過調(diào)用該函數(shù)就算16點的fft。關鍵詞：matlab；fft；函數(shù)1 FFT原理與實現(xiàn)1.1引言 信號的傅里葉變換或頻譜分析是信號處理中的一個強有力工具。它把信號、線性系統(tǒng)、相關、卷積等概念有機結合在一起。對于數(shù)字系統(tǒng)來說，我們應該把譜分析也離散化，這就是離散傅里葉變換（DFT）。1965年庫利與圖基提出了一種快速計算DFT的方法，很快就得到了廣泛的應用。常見的FFT算法有2大類，一類是按時間抽取的FFT算法（簡稱DIT-FFT),另一類是按頻率抽取的FFT算法（簡稱DIF-FFT)。1.2 DFT計算公式對于N點序列，它的離散傅里葉變換（DFT）為離散傅里葉變換的逆變

3、換（IDFT）為：1.3 旋轉(zhuǎn)因子WN的特性（1） WN的對稱性 （2） （2）WN的周期性 （3） 利用DFT中的周期性和對稱性，使整個DFT的計算變成一系列迭代運算，可大幅度提高運算過程和運算量，這就是FFT的基本思想。（3）WN的可約性 （4)假設采樣序列點數(shù)為N=2L，L為整數(shù)，如果不滿足這個條件可以人為地添加若干個0以使采樣序列點數(shù)滿足這一要求。首先我們將序列x(n)按照奇偶分為兩組如下：X(2r)=x1(r) ,X(2r+1)=x2(r),r=0,1.N/2-1 (5)于是根據(jù)DFT計算公式(1)有： （6）至此，我們將一個N點的DFT轉(zhuǎn)化為了式(6)的形式，此時k的取值為0到N-

4、1,現(xiàn)在分為兩段來討論，當k為0N/2-1的時候，因為x1(r)，x2(r)為N/2點的序列，因此，此時式(6)可以寫為： k=0.N-1 (7)而當 k取值為N/2N-1時，k用k+N/2取代，k取值為0N/2-1。對式(6)化簡可得： （8） 綜合以上推導我們可以得到如下結論：一個N點的DFT變換過程可以用兩個N/2點的DFT變換過程來表示，其具體公式如式(9)所示DFT快速算法的迭代公式：（9）X1(k)X2(k)上式中X'(k)為偶數(shù)項分支的離散傅立葉變換，X''(k)為奇數(shù)項分支的離散傅立葉變換。 式(10)的計算過程可以用圖1-1的蝶形算法流圖直觀地表示出來

5、。 X1(k)+X2(k)X1(k)-X2(k) 圖1-1 時間抽取蝶形運算圖1-2 4點蝶形運算流圖 在圖1中，輸入為兩個N/2點的DFT輸出為一個N點的DFT結果，輸入輸出點數(shù)一致。運用這種表示方法，8點的DFT可以用圖1-2來表示： 根據(jù)公式(10)，一個N點的DFT可以由兩個N/2點的DFT運算構成，再結合圖1-1的蝶形信號流圖可以得到圖2的8點DFT的第一次分解。該分解可以用以下幾個步驟來描述： 1.將N點的輸入序列按奇偶分為2組分別為N/2點的序列 2.分別對1中的每組序列進行DFT變換得到兩組點數(shù)為N/2的DFT變換值X1和X2 3.按照蝶形信號流圖將2的結果組合為一個N點的DF

6、T變換結果根據(jù)式(10)我們可以對圖2中的4點DFT進一步分解，得到圖1-3的結果，分解步驟和前面一致。最后對2點DFT進一步分解得到最終的8點FFT信號計算流圖：圖1-3 8點蝶形運算流圖從圖2到圖4的過程中關于旋轉(zhuǎn)系數(shù)的變化規(guī)律需要說明一下?？雌饋硭坪跸蚯巴埔患?，在奇數(shù)分組部分的旋轉(zhuǎn)系數(shù)因子增量似乎就要變大，其實不是這樣。事實上奇數(shù)分組部分的旋轉(zhuǎn)因子指數(shù)每次增量固定為1，只是因為每向前推進一次，該分組序列的數(shù)據(jù)個數(shù)變少了，為了統(tǒng)一使用以原數(shù)據(jù)N為基的旋轉(zhuǎn)因子就進行了變換導致的。每一次分組奇數(shù)部分的系數(shù)WN,這里的N均為本次分組前的序列點數(shù)。以上邊的8點DFT為例，第一次分組N=8,第二次分

7、組N為4，為了統(tǒng)一根據(jù)式(4)進行了變換將N變?yōu)榱?，但指數(shù)相應的需要乘以2。1.4調(diào)用8點計算16點先將16點fft拆成兩個8點fft，分別調(diào)用自身8點fft函數(shù)fft8計算，然后再按以下公式計算出16點的fft（10）圖1-4 16點蝶形運算圖2 程序代碼2.1 計算8點FFT代碼function y=fft8(x)%根據(jù)蝶形圖計算8點FFTwn=exp(-j*2*pi/8);%旋轉(zhuǎn)因子x1(1)=x(1)+x(5);%計算蝶形圖第一級x1(2)=x(1)-x(5);x1(3)=x(3)+x(7);x1(4)=x(3)-x(7);x1(5)=x(2)+x(6);x1(6)=x(2)-x(6

8、);x1(7)=x(4)+x(8);x1(8)=x(4)-x(8);x2(1)=x1(1)+x1(3);%計算蝶形圖第二級x2(2)=x1(2)+x1(4)*(wn.2);x2(3)=x1(1)-x1(3);x2(4)=x1(2)-x1(4)*(wn.2);x2(5)=x1(5)+x1(7);x2(6)=x1(6)+x1(8)*(wn.2);x2(7)=x1(5)-x1(7);x2(8)=x1(6)-x1(8)*(wn.2);y(1)=x2(1)+x2(5);%計算蝶形圖輸出y(2)=x2(2)+x2(6)*(wn.1);y(3)=x2(3)+x2(7)*(wn.2);y(4)=x2(4)+x

9、2(8)*(wn.3);y(5)=x2(1)-x2(5);y(6)=x2(2)-x2(6)*(wn.1);y(7)=x2(3)-x2(7)*(wn.2);y(8)=x2(4)-x2(8)*(wn.3);2.2計算16點FFT代碼function y=fft16(x)%16點FFTwn=exp(-j*2*pi/16);y1=fft8(x(1:2:16);%計算偶數(shù)組的8點ffty2=fft8(x(2:2:16);%就算奇數(shù)組的8點ffty(1:8)=y1+y2.*(wn.0:7); %計算前八個點y(9:16)=y1-y2.*(wn.0:7);%計算后八個點3上機過程3.1編寫8點FFT函數(shù)運行

10、matlab，新建m文件，進入編輯器輸入程序后保存為fft8，注意文件名與函數(shù)名相同。在matlab命令窗口中輸入fft8（1:8)，按回車，運行結果如下fft8(1:8)ans = Columns 1 through 5 36.0000 -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 Columns 6 through 8 -4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i3.2調(diào)用系統(tǒng)函數(shù)在命令窗口輸入 fft(1:8)后按回車，通過調(diào)用系統(tǒng)函數(shù)fft計算8點

11、fft，計算結果與上面一致，結果如下：>> fft(1:8)ans = Columns 1 through 5 36.0000 -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 Columns 6 through 8 -4.0000 - 1.6569i -4.0000 - 4.0000i -4.0000 - 9.6569i3.3 編寫16點FFT函數(shù)輸入fft16（3:18）>> fft16(3:18)ans = 1.0e+002 * Columns 1 through 5 1.6800 -0.0

12、800 + 0.4022i -0.0800 + 0.1931i -0.0800 + 0.1197i -0.0800 + 0.0800i Columns 6 through 10 -0.0800 + 0.0535i -0.0800 + 0.0331i -0.0800 + 0.0159i -0.0800 -0.0800 - 0.0159i Columns 11 through 15 -0.0800 - 0.0331i -0.0800 - 0.0535i -0.0800 - 0.0800i -0.0800 - 0.1197i -0.0800 - 0.1931i Column 16 -0.0800 -

13、 0.4022i3.4調(diào)用系統(tǒng)函數(shù) 輸入fft（3:18）后按回車，通過調(diào)用系統(tǒng)函數(shù)fft計算16點fft，計算結果與上面一致，結果如下：>> fft(3:18)ans = 1.0e+002 * Columns 1 through 5 1.6800 -0.0800 + 0.4022i -0.0800 + 0.1931i -0.0800 + 0.1197i -0.0800 + 0.0800i Columns 6 through 10 -0.0800 + 0.0535i -0.0800 + 0.0331i -0.0800 + 0.0159i -0.0800 -0.0800 - 0.01

14、59i Columns 11 through 15 -0.0800 - 0.0331i -0.0800 - 0.0535i -0.0800 - 0.0800i -0.0800 - 0.1197i -0.0800 - 0.1931i Column 16 -0.0800 - 0.4022i4 心得體會 經(jīng)過三天的努力，總算把數(shù)字信號處理課程設計做完了。 通過該課程設計，全面系統(tǒng)的理解了數(shù)字信號處理的一般原理和基本實現(xiàn)方法。把死板的課本知識變得生動有趣，激發(fā)了學習的積極性。把學過的數(shù)字信號處理基礎原理的知識強化，能夠把課堂上學的知識通過自己編寫的程序表示出來，加深了對理論知識的理解。 在這次課程設計

15、中，我先是認真閱讀課本上的相關知識，理解透后又翻閱關于matlab的書籍，學習matlab中一些函數(shù)及運算符的用法?？傮w來說,這次課設我學到了很多。在設計過程中,加深了對可內(nèi)知識的理解就,真正懂得了學以致用，熟悉了matlab的使用，了解了matlab在數(shù)字信號處理中的重大應用。做課程設計我體會到了設計的艱辛的同時,更讓我體會到成功的喜悅和快樂. 這次數(shù)字信號處理課程設計,雖然短暫但是讓我得到多方面的提高：首先，提高了我們的對matlab語言的運用能力。matlab語言是以矩陣為基礎的語言，像很多高級語言中需要用循環(huán)結構來描述的算法可以用矩陣或數(shù)組的運算來表示，簡潔明了同時提高了執(zhí)行效率。另外，我們還更加充分的認識到，數(shù)字信號處理這門課程在科學發(fā)展中的至關重要性。其次，查閱參考書的獨立思考的能力以及培養(yǎng)非常重要，我們在設計程序時，遇到很多不理解的東西，有的我們通過查閱參考書弄明白，有的通過網(wǎng)絡查到，但由于時間和資