基于FPGA的FFT處理器設(shè)計

摘要：在火車車輪的振動式擦傷檢測系統(tǒng)中，經(jīng)常需要對振動信號進行頻譜分析，為實現(xiàn)振動頻譜信號的及時輸出，在此根據(jù)FFT算法中的一種變形運算流圖，提出一種基于FPGA的FFT流水線結(jié)構(gòu)，總結(jié)了利用流水線結(jié)構(gòu)實現(xiàn)這種FFT運算流圖的數(shù)據(jù)存取規(guī)律，并按此結(jié)構(gòu)利用Verilog語言設(shè)計了64點數(shù)據(jù)的6級流水線運算結(jié)構(gòu)。利用振動信號測試數(shù)據(jù)進行仿真實驗，結(jié)果表明該設(shè)計方法的正確可靠。
關(guān)鍵詞：FFT算法；FPGA；流水線結(jié)構(gòu)；蝶形運算；流圖

    在火車車輪的振動式擦傷檢測系統(tǒng)中，根據(jù)車輪與鋼軌接觸時產(chǎn)生的振動信號可以對車輪狀態(tài)進行檢測。有擦傷的車輪與鋼軌接觸時產(chǎn)生的振動信號具有特定的頻譜特征，因此若將檢測設(shè)備采集到的信號變換到頻域進行分析，將有助于判斷車輪是否有擦傷。為實現(xiàn)信號的快速變換，采用FPGA實現(xiàn)的FFT處理器對信號進行變換。
    FFT是離散傅里葉變換(DFT)的一種快速算法，當DFT的計算點數(shù)N很大時，F(xiàn)FT算法相對于直接計算DFT時的運算量會顯著減少，因此其在數(shù)字信號處理領(lǐng)域有著廣泛的應(yīng)用，大大推動了數(shù)字信號處理技術(shù)的發(fā)展。FFT算法可以通過計算機軟件、DSP處理器、FPGA器件和ASIC等方式來實現(xiàn)，目前對各種方式的分析和比較，相關(guān)文獻已有介紹。在此提出的FFT算法，其FPGA結(jié)構(gòu)具有模塊化、流水線、可擴展的特點，因此用它可以提高計算速度，在芯片容量允許的情況下進行多點數(shù)、多級流水線結(jié)構(gòu)的FFT運算。

1 算法原理及分析
1．1 FFT算法原理
    由DFT的定義可知，如果信號為x(n)，則對x(n)做N點DFT的計算表達式為：
    
    FFT算法即是對式(1)的一種快速算法。按抽取方式FFT算法可分為時域抽取(DIT)和頻域抽取(DIF)；按基數(shù)(radix)不同F(xiàn)FT算法又可分為基-2、基-4等算法。在此采用基-2時域抽取法。對式(1)，利用基-2時域抽取法運算，可將x(n)按n的奇偶分成2組后分別求出各組的N／2點DFT，得到X1(k)和X2(k)，并根據(jù)旋轉(zhuǎn)因子的周期性和對稱性，最終得到表達式：
    
    由式(2)可以看出，要計算x(n)的N點DFT，可將x(n)按n的奇偶分成兩組后所求出的N／2點DFT結(jié)果X1(k)和X2(k)，按照式(2)求出全部N點DFT結(jié)果。由式(2)確定的運算即為蝶形運算法，如圖1所示，圖2表示了連續(xù)使用這種分解方法得到最終只有兩點數(shù)據(jù)進行DFT運算的共8點數(shù)據(jù)FFT運算流圖的一種變形形式，這種運算結(jié)構(gòu)在大型數(shù)據(jù)處理系統(tǒng)的FFT算法中采用較多。

[!--empirenews.page--]
1．2 運算流圖分析
    對于N點的DFT，采用FFT算法可以顯著減小計算量，當N越大，采用FFT算法的優(yōu)勢越明顯。通過計算可得直接計算DFT的復(fù)數(shù)乘法次數(shù)為N2，而采用FFT計算時其次數(shù)僅為(N／2)log2N。在此，采用的流圖為圖2的形式，通過分析圖2可得以下幾點重要結(jié)論，而這些結(jié)論正是進行FPGA結(jié)構(gòu)設(shè)計的依據(jù)。
    (1)輸入數(shù)據(jù)為順序輸入，輸出為倒序輸出；
    (2)對于N點數(shù)據(jù)，可分為M=log2N級蝶形運算；
    (3)在第L級，共有2L-1組蝶形，且每組蝶形的旋轉(zhuǎn)因子相同，各組旋轉(zhuǎn)因子的上標k的順序及取值為數(shù)0，1，2，…，N／2-1倒序排列后的前2L-1個；
    (4)在流水線工作方式下，在第L級的計算中，共N／2個蝶形需要計算，蝶形內(nèi)數(shù)據(jù)間隔為2M-L，蝶形間數(shù)據(jù)間隔為2M-L+1；也即蝶形的兩輸入數(shù)據(jù)間隔為2M-L，計算下一個蝶形時需要跳躍2M-L+1個數(shù)據(jù)，但跳躍超出數(shù)據(jù)總數(shù)時需要特殊處理，這將在FPGA結(jié)構(gòu)設(shè)計中闡述；
    (5)在流水線工作方式下，每級蝶形輸出需要用RAM存儲一半數(shù)據(jù)后再計算。在第L級的存儲中，其存儲尋址方式與第L-1級計算尋址方式相同(即原位計算)；也即每次需要存儲一組上級輸出的兩個數(shù)據(jù)，其數(shù)據(jù)組間間隔為2M-L+2。組內(nèi)數(shù)據(jù)間隔為2M-L+1。

2 FPGA結(jié)構(gòu)設(shè)計
2．1 總體結(jié)構(gòu)設(shè)計
    這里，F(xiàn)PGA結(jié)構(gòu)設(shè)計采用了如圖2所示的流圖結(jié)構(gòu)。分析圖可以發(fā)現(xiàn)，對M級的運算可設(shè)計成流水線處理方式，但需要注意的是對于第L級和第L+1級之間的數(shù)據(jù)連接問題，即第L級的處理結(jié)果到第L+1級時，并不能立即處理，而需要將第L級的結(jié)果緩存一半后，第L+1級才能按一定的尋址方式開始處理數(shù)據(jù)，其尋址方式如1．2節(jié)中(4)，(5)所述。

    通過前面的分析，設(shè)計出的FPGA流水線處理結(jié)構(gòu)如圖3所示。圖3為64點數(shù)據(jù)FFT運算結(jié)構(gòu)，共6級運算單元，每個單元結(jié)構(gòu)相同。各運算單元包括RAM存儲單元、控制與尋址單元、蝶形運算單元和旋轉(zhuǎn)因子表，其中設(shè)計重點即為蝶形運算單元、控制與尋址單元的設(shè)計。圖3所示結(jié)構(gòu)具有良好的擴展性，圖中所示為64點數(shù)據(jù)6級結(jié)構(gòu)，若要計算其他點數(shù)的FFT，則只需要增加運算單元數(shù)，如1 024點可用10級運算單元來實現(xiàn)，而每個運算單元的結(jié)構(gòu)和功能是相似的。數(shù)據(jù)處理流程為通過輸入端口輸入數(shù)據(jù)到第1級RAM緩存一半數(shù)據(jù)(本文中為32個數(shù)據(jù))，然后在尋址和控制單元的控制下開始蝶形運算；第2級再緩存第1級的輸出結(jié)果，然后按相同的處理方式處理數(shù)據(jù)；由圖3可知，最后一級的輸出結(jié)果是倒序存放的，因此在最終數(shù)據(jù)輸出時需通過倒序單元將處理結(jié)果排列為正序數(shù)據(jù)。
2．2 蝶形運算單元設(shè)計
    蝶形運算單元根據(jù)蝶形運算的特點進行設(shè)計。由圖1可知，其運算包括復(fù)數(shù)乘法器和加法器，設(shè)計形成的蝶形運算單元框圖如圖4所示。

    對圖4中需要說明的是復(fù)數(shù)乘法器的實現(xiàn)，相關(guān)文獻中已詳細介紹了其實現(xiàn)方式，在這里需要對輸入／輸出數(shù)據(jù)的格式和表示方法給予特別關(guān)注。現(xiàn)以本文為例，所有數(shù)據(jù)均以有符號16位Q10格式表示，兩輸入數(shù)據(jù)在經(jīng)過乘法器運算后將得到32位Q20格式的數(shù)據(jù)，但為了能與后級數(shù)據(jù)格式兼容，需將32位Q20格式的數(shù)據(jù)處理成16位Q10格式數(shù)據(jù)?？蓪⒊朔ńY(jié)果右移10位后，通過保留原數(shù)據(jù)的符號位和移位后，由數(shù)據(jù)的低15位組成16位Q10格式的最終乘法結(jié)果，但該處理過程會給運算帶來誤差，在后面的實驗中將會看到。
2．3 數(shù)據(jù)讀取與存儲尋址控制
    在1．2節(jié)中第(4)，(5)點已對數(shù)據(jù)的讀取和存儲尋址方式進行了總結(jié)，因此尋址的關(guān)鍵問題在于各級蝶形處理單元的讀取和存儲地址應(yīng)該如何產(chǎn)生。通過圖2和1．2節(jié)中第(5)點可知：
    (1)在第1級處理單元中，首先將輸入數(shù)據(jù)依次存到第一級RAM中，當數(shù)據(jù)達到1／2時，則開始按存儲順序依次讀出RAM數(shù)據(jù)，并與后半輸入數(shù)據(jù)送到第1級蝶形運算單元進行處理。
    (2)在第L(1<L<7)級處理單元中，首先要將第L-1級輸出數(shù)據(jù)的前半部分存儲到第L級RAM，第L-1級的每次蝶形運算將輸出2個數(shù)據(jù)，這兩個數(shù)據(jù)存儲時地址間隔為2M-L+1，每次需要跳躍2M-L+2個數(shù)據(jù)。但當跳躍個數(shù)超出數(shù)據(jù)總數(shù)時，需要特殊處理，這里給出了一種處理方法：地址位數(shù)用M=log2 N位來表示，存儲時地址從0開始，每次存儲時地址增加跳躍間隔2M-L+2。若產(chǎn)生進位，則將進位加到最低位形成下個地址，如此循環(huán)直到存儲完全部數(shù)據(jù)。

[!--empirenews.page--]

3 仿真實驗
    完成了FFT處理器結(jié)構(gòu)設(shè)計后，需要對其正確性進行測試。本實驗采用Verilog語言完成了FFT處理器的FPGA設(shè)計，仿真工具是ModelSim 6.1f。圖5中(a)，(b)分別是振動信號及其幅度譜的Matlab繪圖表示，已知擦傷振動信號的振動頻率在2.5kHz附近，系統(tǒng)采樣頻率為15kHz。

    對振動信號通過ModelSim仿真進行測試，由于處理過程為流水線處理，各級將依次處理數(shù)據(jù)，且在時間上可以有重疊，使總的處理時間減少。如圖6為ModelSim仿真圖。最終得到的數(shù)據(jù)經(jīng)過倒序輸出后在Matlab中進行了繪圖表示，圖7(a)，圖7(b)分別表示經(jīng)過處理后的FFT變換結(jié)果的實部和虛部。對處理后數(shù)據(jù)的實部和虛部進行運算后得到最終的輸入信號幅度譜如圖8所示。

4 結(jié)語
    通過對比Matlab處理結(jié)果圖5(b)和FPGA仿真結(jié)果圖8可知：
    (1)在該實驗中，設(shè)計方案能夠正確地對64點數(shù)據(jù)進行FFT運算，幅度譜峰值位于Matlab結(jié)果的第13點和第21點處，它們對應(yīng)的頻率分別是2．8 kHz和4．7 kHz。其中，2．8 kHz可判斷為擦傷信號頻率，而4．7 kHz可視為高頻噪聲，因而需要濾波器處理；
    (2)FPGA處理結(jié)果存在噪聲，這些噪聲的產(chǎn)生原因在2．2節(jié)中已進行了初步分析。這是由于用硬件處理數(shù)據(jù)時由于數(shù)據(jù)的表示位數(shù)有限，且在乘法器的輸出過程中對數(shù)據(jù)進行了截斷處理所造成的。在此，仿真測試是基于64點數(shù)據(jù)進行的，但該設(shè)計方法可以方便地擴展到其他數(shù)據(jù)點數(shù)的處理中去，只需要增減運算級數(shù)，修改旋轉(zhuǎn)因子表和修正各級控制與尋址參數(shù)即可。