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

楊偉才，侯 潔，劉玉坤，包莉娜，郭立煒

（河北科技大學信息科學與工程學院，河北石家莊 050018）

高級信號處理算法和硬件的結(jié)合廣泛應(yīng)用于現(xiàn)實生活中的各個領(lǐng)域［1－3］。1965年，COOLEY 和TUKEY 發(fā)表了一種計算DFT 的快速算法，使得DFT 的計算量大為減少，從而使DFT 得以廣泛應(yīng)用。利用FPGA 靈活的實現(xiàn)方案，產(chǎn)品的低功耗、豐富的邏輯單元、大量的輸入輸出引腳、內(nèi)置大量的RAM 和乘法器資源等特點，在FFT 算法的基礎(chǔ)上提出了基于FPGA 硬件平臺的FFT 處理器設(shè)計［4－8］，設(shè)計中采用8位有符號數(shù)完成256點數(shù)據(jù)處理，通過減少乘法運算以及采用查表法，加快系統(tǒng)運算速度，提出的數(shù)據(jù)處理方式避免了浮點運算為數(shù)據(jù)處理造成的困難，完成了信號處理算法與硬件結(jié)合的高速處理方案。

1 FFT算法

一個長度為N的有限長序列的DFT 運算被定義為

在式中定義W N＝e－j（2π／N）。離散傅里葉反變換為

FFT 算法是建立在可以將一個長度為N的序列的離散傅里葉變換逐次分解為較短的離散傅里葉變換這一基本原理的基礎(chǔ)上。其大致可分為2類：按時間抽取的FFT算法和按頻率抽取的FFT算法。通過研究N為2的整數(shù)冪的特殊情況，可以方便證明該算法的原理，因為N為偶整數(shù)，所以可以將x（r）分解成2個序列，一個由x（r）的偶數(shù)點序列組成，另一個由x（r）的奇數(shù)點組成，對于偶數(shù)，r用r＝2n代替，對于奇數(shù)，r用r＝2n＋1代替，有下式

式（3）相當于將原來的N點分解為2個（N／2）點計算，這樣就可以認為每個（N／2）點的DFT都可以分解為2個（N／4）點的DFT之和，然后再進行組合，對于一般情況，應(yīng)當將式（3）繼續(xù)分解，直到剩下2點為止。利用系數(shù)的對稱性和周期性還可以進一步減少計算量。

這樣，只要求出0 到［（N／2）－1］區(qū)間的所有G（k）和H（k），即可求出所有X（k），從而大量減少運算量。筆者只是針對此次設(shè)計做了簡要論述，關(guān)于更詳細的算法介紹請參閱文獻［9］－文獻［10］。

2 FPGA設(shè)計

2.1 系統(tǒng)總體設(shè)計

本文主要完成了處理器的數(shù)據(jù)讀取、保存、處理和輸出模塊設(shè)計。圖1為設(shè)計的系統(tǒng)原理圖。FFT模塊集成了對數(shù)據(jù)的讀取、保存和處理模塊，其內(nèi)部包括3個部分：fft＿process，preramim，F(xiàn)IFO＿Buff。當處理器接收到開始命令時，系統(tǒng)開始工作。工作時首先運行數(shù)據(jù)輸入模塊，產(chǎn)生讀使能信號和讀數(shù)據(jù)地址，從而控制RAM 將數(shù)據(jù)虛部存儲在preramim 模塊中并將數(shù)據(jù)實部存儲在FIFO＿Buff模塊。當數(shù)據(jù)達到要處理點數(shù)時，時序控制模塊運行，由fft＿process模塊將數(shù)據(jù)分別從preramim 和FIFO＿Buff讀取虛部和實部后進行FFT 運算。開始FFT運算后，啟動蝶形運算單元，產(chǎn)生存放旋轉(zhuǎn)因子的ROM 單元讀信號，經(jīng)過蝶形運算后將數(shù)據(jù)重新寫入RAM 中存儲，同時再次讀取preramim 和FIFO＿Buff中的數(shù)據(jù)，使得整個處理過程得以連續(xù)進行，從而減少了運算時間。經(jīng)過8 級運算后，完成256點FFT 處理，完成后產(chǎn)生輸出控制信號，將數(shù)據(jù)實部存放到asyn＿fifoinst1 模塊中。虛部放到asyn＿fifoinst2模塊中。最后在selectdatamcu 模塊控制下，將實部與虛部結(jié)合，順序輸出數(shù)據(jù)，從而完成處理任務(wù)。

圖1 系統(tǒng)原理圖Fig.1 System diagram

2.2 FFT控制模塊設(shè)計

FFT 主控制模塊采用FSM（有限狀態(tài)機）來設(shè)計完成，有限狀態(tài)機是數(shù)字系統(tǒng)中的順序控制電路，在高速運算和控制應(yīng)用中，狀態(tài)機有很大的優(yōu)勢。在設(shè)計時，首先根據(jù)設(shè)計的整體功能要求確定所需的狀態(tài)數(shù)量，從一種狀態(tài)到另一種狀態(tài)的轉(zhuǎn)移條件以及各狀態(tài)的輸出信號，然后畫出狀態(tài)轉(zhuǎn)移圖，從而按照狀態(tài)轉(zhuǎn)移圖編寫Verilog程序來實現(xiàn)整個系統(tǒng)的設(shè)計功能。關(guān)于Verilog語言的學習請參閱文獻［11］。圖2為此次設(shè)計繪制的狀態(tài)轉(zhuǎn)移圖。

圖2 狀態(tài)轉(zhuǎn)移圖Fig.2 State transition diagram

IDLE：fft＿process控制器的初始狀態(tài)，沒有數(shù)據(jù)輸入時，為空閑狀態(tài)，不進行FFT 運算，此狀態(tài)還用于一些控制信號的初始化。

WAIT＿WR＿RAM：當有數(shù)據(jù)輸入時，狀態(tài)機進入wait＿wr＿ram 狀態(tài)。在wait＿wr＿ram 狀態(tài)下，通過時鐘clk＿fpga的驅(qū)動，當FIFO＿Buff的空標志stack＿empty不為0時，從FIFO＿Buff和preramim中將數(shù)據(jù)寫入rama中，數(shù)據(jù)是由8位I／O 數(shù)據(jù)口傳送得到。在此設(shè)計中，F(xiàn)FT 處理器采用了2個時鐘，一個clk＿fpga時鐘和一個外部寫入時鐘。數(shù)據(jù)的傳送接收是以外部時鐘控制寫入FIFO＿Buff中，一上電，F(xiàn)FT 中的FIFO＿Buff接收到第1 個數(shù)據(jù)后，就會啟動讀數(shù)據(jù)。因為讀寫數(shù)據(jù)的速度不一樣，所以采用異步FIFO 設(shè)計，將256個數(shù)據(jù)全部寫入rama中后，狀態(tài)機進入FFT＿PROCESS狀態(tài)。

FFT＿PROCESS：在此狀態(tài)中，將接收得到的數(shù)據(jù)進行處理，數(shù)據(jù)存儲器采用的是雙端口RAM，將256個數(shù)據(jù)的地址分配，前128個數(shù)據(jù)為一組，存放地址為0到127，后128個數(shù)據(jù)為一組，存放地址為128到255，最后將數(shù)據(jù)送入butterfly中進行蝶形運算，要完成整個FFT 處理過程總共需要8 級處理，每一級處理需要調(diào)用128次蝶形運算，在數(shù)據(jù)處理過程中有2 個雙輸入輸出的256 位數(shù)據(jù)存儲器rama和ramb，這2個數(shù)據(jù)存儲器相互交換來存儲數(shù)據(jù)，使設(shè)計不會在存儲時發(fā)生沖突或數(shù)據(jù)重疊，同時還可以提高FFT 的數(shù)據(jù)處理速度。在8級運算中的0，2，4，6級處理時，從rama中讀取數(shù)據(jù)，將處理后的蝶形數(shù)據(jù)依次存儲在ramb中的n和（n＋1）地址中；在1，3，5，7級數(shù)據(jù)處理時，從ramb中讀取數(shù)據(jù)，將處理后的蝶形數(shù)據(jù)再依次存儲在rama中的n和（n＋1）地址中；8級運算完成之后，進入下一狀態(tài)。

READ＿RESULT：讀數(shù)據(jù)狀態(tài)，此次設(shè)計采用基2蝶形運算的最優(yōu)架構(gòu)，計算中采用同址運算，蝶形運算輸出的結(jié)果為倒位序，所以最后讀數(shù)據(jù)時要控制ram 地址，將ram 地址進行倒序排列后即可得到輸出數(shù)據(jù)的正序列。

2.3 蝶形運算單元

在FFT 算法中，蝶形運算單元是最為核心的關(guān)鍵部分，從某一級到下一級的計算過程中，基本的計算如圖3所示，即先用前一級的一對數(shù)值計算得到該級的結(jié)果，其中的系數(shù)總是W N的冪，而其指數(shù)總是相差N／2。由于流圖的形狀像蝴蝶，因此這種運算稱為蝶形運算。式（5）、式（6）為蝶形運算的計算公式。

（cosθ－jsinθ）（C＋jD）項展開式為（Ccosθ＋Dsinθ）＋j（Dcosθ－Csinθ），其中實部為Ccosθ＋Dsinθ＝（C－D）cosθ＋D（cosθ＋sinθ），虛部為Dcosθ－Csinθ＝C（cosθ－sinθ）－（C－D）cosθ。

圖3 蝶形計算流圖Fig.3 Flow of butterfly calcuation

式子經(jīng)變換后實部與虛部有公共項（C－D）cosθ，經(jīng)過上述處理后，可以看到在一次蝶形運算中可以減少兩次乘法操作，在設(shè)計中采用查表法設(shè)計旋轉(zhuǎn)因子，將cosθ，cosθ＋sinθ，cosθ－sinθ數(shù)值計算出來存儲在ROM 中，在計算過程中直接調(diào)用這些數(shù)值來完成相應(yīng)計算，使FFT 處理時間大為減少，提升了系統(tǒng)的工作頻率。

筆者設(shè)計的蝶形運算是由Butterfly 模塊完成，該模塊首先從數(shù)據(jù)存儲器rama中取出2 個數(shù)據(jù)的實部和虛部，將它們分別與ROM 中存儲的旋轉(zhuǎn)因子相乘，將結(jié)果存儲在ramb中，在數(shù)據(jù)處理時，將旋轉(zhuǎn)因子乘以128 之后再存儲在9 位的ROM 中，由于一個9位數(shù)與一個8位數(shù)相乘結(jié)果是17位數(shù)，在計算中，舍棄數(shù)據(jù)的低7位，在取數(shù)的同時將數(shù)據(jù)縮小了128 倍，從而避免了浮點運算帶來的問題。

3 系統(tǒng)仿真

在完成系統(tǒng)整體設(shè)計后，采用Altera 公司的cycloneⅡ系列EP2C8Q208芯片實現(xiàn)系統(tǒng)功能，利用quartusⅡ軟件對設(shè)計進行編譯、綜合以及布局布線，由報告顯示，此次設(shè)計共使用邏輯單元876個，占芯片邏輯單元總數(shù)的11%，使用存儲器36 352位，占芯片存儲器位數(shù)的22%，并使用了3 個嵌入式乘法器。在蝶形運算設(shè)計完成后，用RTL VIEWER 查看綜合后的原理圖如圖4所示。

系統(tǒng)各模塊在設(shè)計過程中采用quartusⅡ自帶仿真器進行仿真，圖5為蝶形運算模塊仿真圖，從仿真圖中可以看出，完成一次蝶形運算需要4個時鐘周期，仿真中，筆者輸入的數(shù)據(jù)為A＝are＿in＝0001＿

0101，B＝aim＿in＝0000＿0000，C＝bre＿in＝0000＿1010，D＝bim＿in＝0000＿0000，ROM 地址為rom＿addr＝00010，查表后得cos＝0111＿1100，cos－sin＝001100011，cos＋sin＝010010101，其中，各數(shù)據(jù)最高位為符號位，將計算結(jié)果代入蝶形計算公式，經(jīng)計算，X（p）＝cre＿out＋jcim＿out＝00011110＋j11111110，X（q）＝dre＿out＋jdim＿out＝00001100＋j00000010，與仿真結(jié)果一致。

圖4 RTL視圖Fig.4 RLL view

圖5 蝶形運算仿真圖Fig.5 Simulation of butterfly operation

對輸入信號y＝50sin（400πt）＋50sin（200πt）進行采樣，將采樣后數(shù)據(jù)進行處理，并將處理后的仿真波形保存為.tbl文件。用Matlab軟件生成頻譜數(shù)據(jù)圖見圖6，此仿真結(jié)果顯示與數(shù)據(jù)處理結(jié)果一致。

4 結(jié) 語

此次設(shè)計使用Verilog HDL 語言進行程序設(shè)計，詳細介紹了數(shù)據(jù)從外部輸入經(jīng)過存儲到內(nèi)部處理再到輸出的詳細流程，給出了系統(tǒng)的整體設(shè)計思路以及蝶形運算每一關(guān)鍵點的詳細設(shè)計說明，并在quartusⅡ8.0軟件上進行編譯、綜合和布局布線，最后下載到cycloneⅡ芯片上完成設(shè)計。經(jīng)過仿真驗證，本設(shè)計成功實現(xiàn)了8 位有符號數(shù)的256 點基2FFT的數(shù)據(jù)處理，在采用特殊方法設(shè)計蝶形模塊后，使系統(tǒng)處理速度優(yōu)于一般FFT 處理器，避免了浮點運算為數(shù)據(jù)處理造成的困難，完全符合設(shè)計標準。

圖6 Matlab仿真圖Fig.6 Matlab simulation

／References：

［1］ 劉德亮，王竹林，尉廣軍.基于FPGA 高精度頻率測量儀的設(shè)計［J］.河北工業(yè)科技，2010，27（1）：29－31.LIU Deliang，WANG Zhulin，YU Guangjun.Design of highaccuracy frequency measuring instrument based on FPGA［J］.Hebei Journal of Industrial Science and Technology，2010，27（1）：29－31.

［2］ 張 陽，王中陽，王紅勝，等.基于FPGA 的多端口存儲控制器設(shè)計［J］.河北工業(yè)科技，2010，27（6）：401－405.ZHANG Yang，WANG Zhongyang，WANG Hongsheng，et al.Design of multi－port memory controller based on FPGA［J］.Hebei Journal of Industrial Science and Technology，2010，27（6）：401－405.

［3］ 王曉君，陳 禾，羅躍東.一種EW 接收機信號處理系統(tǒng)的設(shè)計與實現(xiàn)方法［J］.河北科技大學學報，2007，28（2）：142－146.WANG Xiaojun，CHEN He，LUO Yuedong.Design and implementation of signal processing system for electronic warfare receiver［J］.Journal of Hebei University of Science and Technology，2007，28（2）：142－146.

［4］ NIBOUCHE O，BOUSSAKTA S，DARNELL M，et al.Algorithms and pipeline architectures for 2－D FFT and FFT－like transforms［J］.Digital Signal Processing，2010，20（4）：1 072－1 086.

［5］ ZHOU Yuan，NORAS J M，SHEPHERD S J.Novel design of multiplier－less FFT processors［J］.Signal Processing，2007，87（6）：1 402－1 407.

［6］ CABAL－YEPEZ E，CAROZZI T D，ROMERO－TRONCOSO R J，et al.FPGA－based system for frequency detection of the main periodic component in time series information［J］.Digital Signal Processing，2008，18（6）：1 029－1 044.

［7］ 鐘冠文，盧亞偉，付欣瑋，等.基于FPGA 的1024 點高性能FFT 處理器的設(shè)計［J］.微計算機信息，2012，28（8）：66－67.ZHAON Guanwen，LU Yawei，F(xiàn)U Xinwei，et al.Design of 1024－point FFT processor based on FPGA［J］.Microcomputer Information，2012，28（8）：66－67.

［8］ 唐鴻武.基于FPGA 的感應(yīng)電機特性分析硬件單元的設(shè)計［D］.石家莊：河北科技大學，2010.TANG Hongwu.Design of the Hardware Unit Based on FPGA of Characteristic Analysis on Induction Motors ［D］.Shijiazhuang：Hebei University of Science and Technology，2010.

［9］ 奧本海姆A V，謝弗R W，巴克J M.離散時間信號處理［M］.第2版.劉樹棠，黃建國，譯.西安：西安交通大學出版社，2001.OPPENHEIM A V，SCHAFER R W，BUCK J M.Discretetime Signal Processing［M］.2nd ed.Translated by LIU Shutang，HUANG Jianguo.Xi′an：Xi′an Jiaotong University Press，2001.

［10］ 程佩青.數(shù)字信號處理教程［M］.第3版.北京：清華大學出版社，2007.CHENG Peiqing.Digital Signal Processing Tutorial［M］.3rd ed.Beijing：Tsinghua University Press，2007.

［11］ 劉 波.精通Verilog HDL 語言編程［M］.北京：電子工業(yè)出版社，2007.LIU Bo.Proficient in Verilog HDL Language Programming［M］.Beijing：Publishing House of Electronics Industry，2007.