基于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ù)即可。