基于FPGA的FFT處理器設(shè)計(jì)
摘要:在火車車輪的振動(dòng)式擦傷檢測系統(tǒng)中,經(jīng)常需要對振動(dòng)信號(hào)進(jìn)行頻譜分析,為實(shí)現(xiàn)振動(dòng)頻譜信號(hào)的及時(shí)輸出,在此根據(jù)FFT算法中的一種變形運(yùn)算流圖,提出一種基于FPGA的FFT流水線結(jié)構(gòu),總結(jié)了利用流水線結(jié)構(gòu)實(shí)現(xiàn)這種FFT運(yùn)算流圖的數(shù)據(jù)存取規(guī)律,并按此結(jié)構(gòu)利用Verilog語言設(shè)計(jì)了64點(diǎn)數(shù)據(jù)的6級流水線運(yùn)算結(jié)構(gòu)。利用振動(dòng)信號(hào)測試數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn),結(jié)果表明該設(shè)計(jì)方法的正確可靠。
關(guān)鍵詞:FFT算法;FPGA;流水線結(jié)構(gòu);蝶形運(yùn)算;流圖
在火車車輪的振動(dòng)式擦傷檢測系統(tǒng)中,根據(jù)車輪與鋼軌接觸時(shí)產(chǎn)生的振動(dòng)信號(hào)可以對車輪狀態(tài)進(jìn)行檢測。有擦傷的車輪與鋼軌接觸時(shí)產(chǎn)生的振動(dòng)信號(hào)具有特定的頻譜特征,因此若將檢測設(shè)備采集到的信號(hào)變換到頻域進(jìn)行分析,將有助于判斷車輪是否有擦傷。為實(shí)現(xiàn)信號(hào)的快速變換,采用FPGA實(shí)現(xiàn)的FFT處理器對信號(hào)進(jìn)行變換。
FFT是離散傅里葉變換(DFT)的一種快速算法,當(dāng)DFT的計(jì)算點(diǎn)數(shù)N很大時(shí),F(xiàn)FT算法相對于直接計(jì)算DFT時(shí)的運(yùn)算量會(huì)顯著減少,因此其在數(shù)字信號(hào)處理領(lǐng)域有著廣泛的應(yīng)用,大大推動(dòng)了數(shù)字信號(hào)處理技術(shù)的發(fā)展。FFT算法可以通過計(jì)算機(jī)軟件、DSP處理器、FPGA器件和ASIC等方式來實(shí)現(xiàn),目前對各種方式的分析和比較,相關(guān)文獻(xiàn)已有介紹。在此提出的FFT算法,其FPGA結(jié)構(gòu)具有模塊化、流水線、可擴(kuò)展的特點(diǎn),因此用它可以提高計(jì)算速度,在芯片容量允許的情況下進(jìn)行多點(diǎn)數(shù)、多級流水線結(jié)構(gòu)的FFT運(yùn)算。
1 算法原理及分析
1.1 FFT算法原理
由DFT的定義可知,如果信號(hào)為x(n),則對x(n)做N點(diǎn)DFT的計(jì)算表達(dá)式為:
FFT算法即是對式(1)的一種快速算法。按抽取方式FFT算法可分為時(shí)域抽取(DIT)和頻域抽取(DIF);按基數(shù)(radix)不同F(xiàn)FT算法又可分為基-2、基-4等算法。在此采用基-2時(shí)域抽取法。對式(1),利用基-2時(shí)域抽取法運(yùn)算,可將x(n)按n的奇偶分成2組后分別求出各組的N/2點(diǎn)DFT,得到X1(k)和X2(k),并根據(jù)旋轉(zhuǎn)因子的周期性和對稱性,最終得到表達(dá)式:
由式(2)可以看出,要計(jì)算x(n)的N點(diǎn)DFT,可將x(n)按n的奇偶分成兩組后所求出的N/2點(diǎn)DFT結(jié)果X1(k)和X2(k),按照式(2)求出全部N點(diǎn)DFT結(jié)果。由式(2)確定的運(yùn)算即為蝶形運(yùn)算法,如圖1所示,圖2表示了連續(xù)使用這種分解方法得到最終只有兩點(diǎn)數(shù)據(jù)進(jìn)行DFT運(yùn)算的共8點(diǎn)數(shù)據(jù)FFT運(yùn)算流圖的一種變形形式,這種運(yùn)算結(jié)構(gòu)在大型數(shù)據(jù)處理系統(tǒng)的FFT算法中采用較多。
1.2 運(yùn)算流圖分析
對于N點(diǎn)的DFT,采用FFT算法可以顯著減小計(jì)算量,當(dāng)N越大,采用FFT算法的優(yōu)勢越明顯。通過計(jì)算可得直接計(jì)算DFT的復(fù)數(shù)乘法次數(shù)為N2,而采用FFT計(jì)算時(shí)其次數(shù)僅為(N/2)log2N。在此,采用的流圖為圖2的形式,通過分析圖2可得以下幾點(diǎn)重要結(jié)論,而這些結(jié)論正是進(jìn)行FPGA結(jié)構(gòu)設(shè)計(jì)的依據(jù)。
(1)輸入數(shù)據(jù)為順序輸入,輸出為倒序輸出;
(2)對于N點(diǎn)數(shù)據(jù),可分為M=log2N級蝶形運(yùn)算;
(3)在第L級,共有2L-1組蝶形,且每組蝶形的旋轉(zhuǎn)因子相同,各組旋轉(zhuǎn)因子的上標(biāo)k的順序及取值為數(shù)0,1,2,…,N/2-1倒序排列后的前2L-1個(gè);
(4)在流水線工作方式下,在第L級的計(jì)算中,共N/2個(gè)蝶形需要計(jì)算,蝶形內(nèi)數(shù)據(jù)間隔為2M-L,蝶形間數(shù)據(jù)間隔為2M-L+1;也即蝶形的兩輸入數(shù)據(jù)間隔為2M-L,計(jì)算下一個(gè)蝶形時(shí)需要跳躍2M-L+1個(gè)數(shù)據(jù),但跳躍超出數(shù)據(jù)總數(shù)時(shí)需要特殊處理,這將在FPGA結(jié)構(gòu)設(shè)計(jì)中闡述;
(5)在流水線工作方式下,每級蝶形輸出需要用RAM存儲(chǔ)一半數(shù)據(jù)后再計(jì)算。在第L級的存儲(chǔ)中,其存儲(chǔ)尋址方式與第L-1級計(jì)算尋址方式相同(即原位計(jì)算);也即每次需要存儲(chǔ)一組上級輸出的兩個(gè)數(shù)據(jù),其數(shù)據(jù)組間間隔為2M-L+2。組內(nèi)數(shù)據(jù)間隔為2M-L+1。
2 FPGA結(jié)構(gòu)設(shè)計(jì)
2.1 總體結(jié)構(gòu)設(shè)計(jì)
這里,F(xiàn)PGA結(jié)構(gòu)設(shè)計(jì)采用了如圖2所示的流圖結(jié)構(gòu)。分析圖可以發(fā)現(xiàn),對M級的運(yùn)算可設(shè)計(jì)成流水線處理方式,但需要注意的是對于第L級和第L+1級之間的數(shù)據(jù)連接問題,即第L級的處理結(jié)果到第L+1級時(shí),并不能立即處理,而需要將第L級的結(jié)果緩存一半后,第L+1級才能按一定的尋址方式開始處理數(shù)據(jù),其尋址方式如1.2節(jié)中(4),(5)所述。
通過前面的分析,設(shè)計(jì)出的FPGA流水線處理結(jié)構(gòu)如圖3所示。圖3為64點(diǎn)數(shù)據(jù)FFT運(yùn)算結(jié)構(gòu),共6級運(yùn)算單元,每個(gè)單元結(jié)構(gòu)相同。各運(yùn)算單元包括RAM存儲(chǔ)單元、控制與尋址單元、蝶形運(yùn)算單元和旋轉(zhuǎn)因子表,其中設(shè)計(jì)重點(diǎn)即為蝶形運(yùn)算單元、控制與尋址單元的設(shè)計(jì)。圖3所示結(jié)構(gòu)具有良好的擴(kuò)展性,圖中所示為64點(diǎn)數(shù)據(jù)6級結(jié)構(gòu),若要計(jì)算其他點(diǎn)數(shù)的FFT,則只需要增加運(yùn)算單元數(shù),如1 024點(diǎn)可用10級運(yùn)算單元來實(shí)現(xiàn),而每個(gè)運(yùn)算單元的結(jié)構(gòu)和功能是相似的。數(shù)據(jù)處理流程為通過輸入端口輸入數(shù)據(jù)到第1級RAM緩存一半數(shù)據(jù)(本文中為32個(gè)數(shù)據(jù)),然后在尋址和控制單元的控制下開始蝶形運(yùn)算;第2級再緩存第1級的輸出結(jié)果,然后按相同的處理方式處理數(shù)據(jù);由圖3可知,最后一級的輸出結(jié)果是倒序存放的,因此在最終數(shù)據(jù)輸出時(shí)需通過倒序單元將處理結(jié)果排列為正序數(shù)據(jù)。
2.2 蝶形運(yùn)算單元設(shè)計(jì)
蝶形運(yùn)算單元根據(jù)蝶形運(yùn)算的特點(diǎn)進(jìn)行設(shè)計(jì)。由圖1可知,其運(yùn)算包括復(fù)數(shù)乘法器和加法器,設(shè)計(jì)形成的蝶形運(yùn)算單元框圖如圖4所示。
對圖4中需要說明的是復(fù)數(shù)乘法器的實(shí)現(xiàn),相關(guān)文獻(xiàn)中已詳細(xì)介紹了其實(shí)現(xiàn)方式,在這里需要對輸入/輸出數(shù)據(jù)的格式和表示方法給予特別關(guān)注?,F(xiàn)以本文為例,所有數(shù)據(jù)均以有符號(hào)16位Q10格式表示,兩輸入數(shù)據(jù)在經(jīng)過乘法器運(yùn)算后將得到32位Q20格式的數(shù)據(jù),但為了能與后級數(shù)據(jù)格式兼容,需將32位Q20格式的數(shù)據(jù)處理成16位Q10格式數(shù)據(jù)??蓪⒊朔ńY(jié)果右移10位后,通過保留原數(shù)據(jù)的符號(hào)位和移位后,由數(shù)據(jù)的低15位組成16位Q10格式的最終乘法結(jié)果,但該處理過程會(huì)給運(yùn)算帶來誤差,在后面的實(shí)驗(yàn)中將會(huì)看到。
2.3 數(shù)據(jù)讀取與存儲(chǔ)尋址控制
在1.2節(jié)中第(4),(5)點(diǎn)已對數(shù)據(jù)的讀取和存儲(chǔ)尋址方式進(jìn)行了總結(jié),因此尋址的關(guān)鍵問題在于各級蝶形處理單元的讀取和存儲(chǔ)地址應(yīng)該如何產(chǎn)生。通過圖2和1.2節(jié)中第(5)點(diǎn)可知:
(1)在第1級處理單元中,首先將輸入數(shù)據(jù)依次存到第一級RAM中,當(dāng)數(shù)據(jù)達(dá)到1/2時(shí),則開始按存儲(chǔ)順序依次讀出RAM數(shù)據(jù),并與后半輸入數(shù)據(jù)送到第1級蝶形運(yùn)算單元進(jìn)行處理。
(2)在第L(1<L<7)級處理單元中,首先要將第L-1級輸出數(shù)據(jù)的前半部分存儲(chǔ)到第L級RAM,第L-1級的每次蝶形運(yùn)算將輸出2個(gè)數(shù)據(jù),這兩個(gè)數(shù)據(jù)存儲(chǔ)時(shí)地址間隔為2M-L+1,每次需要跳躍2M-L+2個(gè)數(shù)據(jù)。但當(dāng)跳躍個(gè)數(shù)超出數(shù)據(jù)總數(shù)時(shí),需要特殊處理,這里給出了一種處理方法:地址位數(shù)用M=log2 N位來表示,存儲(chǔ)時(shí)地址從0開始,每次存儲(chǔ)時(shí)地址增加跳躍間隔2M-L+2。若產(chǎn)生進(jìn)位,則將進(jìn)位加到最低位形成下個(gè)地址,如此循環(huán)直到存儲(chǔ)完全部數(shù)據(jù)。
3 仿真實(shí)驗(yàn)
完成了FFT處理器結(jié)構(gòu)設(shè)計(jì)后,需要對其正確性進(jìn)行測試。本實(shí)驗(yàn)采用Verilog語言完成了FFT處理器的FPGA設(shè)計(jì),仿真工具是ModelSim 6.1f。圖5中(a),(b)分別是振動(dòng)信號(hào)及其幅度譜的Matlab繪圖表示,已知擦傷振動(dòng)信號(hào)的振動(dòng)頻率在2.5kHz附近,系統(tǒng)采樣頻率為15kHz。
對振動(dòng)信號(hào)通過ModelSim仿真進(jìn)行測試,由于處理過程為流水線處理,各級將依次處理數(shù)據(jù),且在時(shí)間上可以有重疊,使總的處理時(shí)間減少。如圖6為ModelSim仿真圖。最終得到的數(shù)據(jù)經(jīng)過倒序輸出后在Matlab中進(jìn)行了繪圖表示,圖7(a),圖7(b)分別表示經(jīng)過處理后的FFT變換結(jié)果的實(shí)部和虛部。對處理后數(shù)據(jù)的實(shí)部和虛部進(jìn)行運(yùn)算后得到最終的輸入信號(hào)幅度譜如圖8所示。
4 結(jié)語
通過對比Matlab處理結(jié)果圖5(b)和FPGA仿真結(jié)果圖8可知:
(1)在該實(shí)驗(yàn)中,設(shè)計(jì)方案能夠正確地對64點(diǎn)數(shù)據(jù)進(jìn)行FFT運(yùn)算,幅度譜峰值位于Matlab結(jié)果的第13點(diǎn)和第21點(diǎn)處,它們對應(yīng)的頻率分別是2.8 kHz和4.7 kHz。其中,2.8 kHz可判斷為擦傷信號(hào)頻率,而4.7 kHz可視為高頻噪聲,因而需要濾波器處理;
(2)FPGA處理結(jié)果存在噪聲,這些噪聲的產(chǎn)生原因在2.2節(jié)中已進(jìn)行了初步分析。這是由于用硬件處理數(shù)據(jù)時(shí)由于數(shù)據(jù)的表示位數(shù)有限,且在乘法器的輸出過程中對數(shù)據(jù)進(jìn)行了截?cái)嗵幚硭斐傻?。在此,仿真測試是基于64點(diǎn)數(shù)據(jù)進(jìn)行的,但該設(shè)計(jì)方法可以方便地?cái)U(kuò)展到其他數(shù)據(jù)點(diǎn)數(shù)的處理中去,只需要增減運(yùn)算級數(shù),修改旋轉(zhuǎn)因子表和修正各級控制與尋址參數(shù)即可。