點(diǎn)基于DIT的FFT的實(shí)現(xiàn)

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

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

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

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

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

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

7、組N為4，為了統(tǒng)一根據(jù)式(4)進(jìn)行了變換將N變?yōu)榱?，但指數(shù)相應(yīng)的需要乘以2。1.4調(diào)用8點(diǎn)計(jì)算16點(diǎn)先將16點(diǎn)fft拆成兩個(gè)8點(diǎn)fft，分別調(diào)用自身8點(diǎn)fft函數(shù)fft8計(jì)算，然后再按以下公式計(jì)算出16點(diǎn)的fft（10）圖1-4 16點(diǎn)蝶形運(yùn)算圖2 程序代碼2.1 計(jì)算8點(diǎn)FFT代碼function y=fft8(x)%根據(jù)蝶形圖計(jì)算8點(diǎn)FFTwn=exp(-j*2*pi/8);%旋轉(zhuǎn)因子x1(1)=x(1)+x(5);%計(jì)算蝶形圖第一級(jí)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);%計(jì)算蝶形圖第二級(jí)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);%計(jì)算蝶形圖輸出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計(jì)算16點(diǎn)FFT代碼function y=fft16(x)%16點(diǎn)FFTwn=exp(-j*2*pi/16);y1=fft8(x(1:2:16);%計(jì)算偶數(shù)組的8點(diǎn)ffty2=fft8(x(2:2:16);%就算奇數(shù)組的8點(diǎn)ffty(1:8)=y1+y2.*(wn.0:7); %計(jì)算前八個(gè)點(diǎn)y(9:16)=y1-y2.*(wn.0:7);%計(jì)算后八個(gè)點(diǎn)3上機(jī)過(guò)程3.1編寫8點(diǎn)FFT函數(shù)運(yùn)行

10、matlab，新建m文件，進(jìn)入編輯器輸入程序后保存為fft8，注意文件名與函數(shù)名相同。在matlab命令窗口中輸入fft8（1:8)，按回車，運(yùn)行結(jié)果如下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)后按回車，通過(guò)調(diào)用系統(tǒng)函數(shù)fft計(jì)算8點(diǎn)

11、fft，計(jì)算結(jié)果與上面一致，結(jié)果如下：>> 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點(diǎn)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）后按回車，通過(guò)調(diào)用系統(tǒng)函數(shù)fft計(jì)算16點(diǎn)fft，計(jì)算結(jié)果與上面一致，結(jié)果如下：>> 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 心得體會(huì) 經(jīng)過(guò)三天的努力，總算把數(shù)字信號(hào)處理課程設(shè)計(jì)做完了。 通過(guò)該課程設(shè)計(jì)，全面系統(tǒng)的理解了數(shù)字信號(hào)處理的一般原理和基本實(shí)現(xiàn)方法。把死板的課本知識(shí)變得生動(dòng)有趣，激發(fā)了學(xué)習(xí)的積極性。把學(xué)過(guò)的數(shù)字信號(hào)處理基礎(chǔ)原理的知識(shí)強(qiáng)化，能夠把課堂上學(xué)的知識(shí)通過(guò)自己編寫的程序表示出來(lái)，加深了對(duì)理論知識(shí)的理解。 在這次課程設(shè)計(jì)

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