基于FPGA的FFT處理器設計

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

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

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

1 FFT算法

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

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

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

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

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

2 FPGA設計

2.1 系統總體設計

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

圖1 系統原理圖Fig.1 System diagram

2.2 FFT控制模塊設計

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

圖2 狀態轉移圖Fig.2 State transition diagram

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

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

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

READ＿RESULT：讀數據狀態，此次設計采用基2蝶形運算的最優架構，計算中采用同址運算，蝶形運算輸出的結果為倒位序，所以最后讀數據時要控制ram 地址，將ram 地址進行倒序排列后即可得到輸出數據的正序列。

2.3 蝶形運算單元

在FFT 算法中，蝶形運算單元是最為核心的關鍵部分，從某一級到下一級的計算過程中，基本的計算如圖3所示，即先用前一級的一對數值計算得到該級的結果，其中的系數總是W N的冪，而其指數總是相差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

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

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

3 系統仿真

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

系統各模塊在設計過程中采用quartusⅡ自帶仿真器進行仿真，圖5為蝶形運算模塊仿真圖，從仿真圖中可以看出，完成一次蝶形運算需要4個時鐘周期，仿真中，筆者輸入的數據為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，其中，各數據最高位為符號位，將計算結果代入蝶形計算公式，經計算，X（p）＝cre＿out＋jcim＿out＝00011110＋j11111110，X（q）＝dre＿out＋jdim＿out＝00001100＋j00000010，與仿真結果一致。

圖4 RTL視圖Fig.4 RLL view

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

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

4 結 語

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

圖6 Matlab仿真圖Fig.6 Matlab simulation

／References：

［1］ 劉德亮，王竹林，尉廣軍.基于FPGA 高精度頻率測量儀的設計［J］.河北工業科技，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 的多端口存儲控制器設計［J］.河北工業科技，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 接收機信號處理系統的設計與實現方法［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 處理器的設計［J］.微計算機信息，2012，28（8）：66－67.ZHAON Guanwen，LU Yawei，FU Xinwei，et al.Design of 1024－point FFT processor based on FPGA［J］.Microcomputer Information，2012，28（8）：66－67.

［8］ 唐鴻武.基于FPGA 的感應電機特性分析硬件單元的設計［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］ 程佩青.數字信號處理教程［M］.第3版.北京：清華大學出版社，2007.CHENG Peiqing.Digital Signal Processing Tutorial［M］.3rd ed.Beijing：Tsinghua University Press，2007.

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