于龍洋，段文偉，李署堅

（北京航空航天大學電子信息工程學院，北京100191）

一種精簡結構的浮點蝶形運算單元設計?

于龍洋，段文偉，李署堅

（北京航空航天大學電子信息工程學院，北京100191）

論述了一種結構精簡且高效的浮點數蝶形運算單元設計，單元內部模塊的使用效率接近100%。采用串行全流水線結構設計，與并行結構相比節(jié)省了75%的硬件資源消耗。利用按時間抽取（DIT）的快速傅里葉變換（FFT）算法，通過VHDL編程實現(xiàn)了以該蝶形單元為基礎的1 024點浮點FFT處理器。QUARTUS II中的仿真結果證明了設計的正確性。該設計已成功應用于一種音頻信號分析儀的信號處理部分。

信號處理；蝶形運算單元；浮點數；快速傅里葉變換；流水線；按時間抽取

1 引言

硬件FFT實現(xiàn)相對于軟件實現(xiàn)最大的特點就是速度優(yōu)勢，為了更充分地發(fā)掘FPGA在這方面的潛能，該方面的研究大都集中在如何進一步提高處理速度上，例如文獻［1］通過采用基-16算法提高并行度，文獻［2］通過優(yōu)化設計使其最高工作頻率達到200MHz。這些設計都注重提高并行度和工作頻率以提高處理速度，但是對硬件資源的要求都很高。在很多對資源和成本要求嚴格的領域，硬件FFT處理器得不到應用，改善這種情況的根本措施在于盡量壓縮其最小計算單位——蝶形運算單元的硬件開銷。

本文設計在保證流水線正常工作前提下，最大限度地減少了蝶形單元內運算模塊數量，并且蝶形單元內模塊的利用率基本達到100%。最終在不影響運算精度和效率的情況下對一般的蝶形單元進行了結構上的壓縮。為了驗證這種設計的可靠性，采用按時間抽取的FFT算法設計實現(xiàn)了1 024點的浮點數FFT運算。在QUARTUS II中的仿真結果表明，采用這種方案設計的蝶形運算單元不會影響到浮點FFT處理器的精度和運算效率，并且極大地降低了FFT處理器的最小資源需求，使其具有更廣泛的適用范圍，具有很強的實用意義。

2 FFT算法

FFT算法基本上可以分為兩大類，即按時間抽選（Decimation-in-time，DIT）法和按頻率抽選（Decimation-in-frequency，DIF）法。兩種算法具有相同的運算量和復雜度，且都可以作原位運算，只不過DIT是先作復乘后作加減，而DIF的復數乘法只出現(xiàn)在減法之后［3］。所以嚴格來說兩種算法沒有優(yōu)劣之分，但由于DIT算法更加直觀［2］，所以采用DIT算法。

根據選取的基數的不同，DIT又可分成基-2、基-4和分裂基算法。分裂基算法比較復雜，不易在高速電路中實現(xiàn)。其它兩種算法相比來說，基-2算法具有程序簡單、效率高、使用方便等特點，所以應用范圍最廣。基-4算法比基-2算法具有更高的運算效率，但由于復雜度高，實現(xiàn)起來不僅困難，而且硬件開銷大。由于設計的原則就是壓縮蝶形單元的硬件開銷，所以最后選擇基-2 DIT算法來設計蝶形運算單元。

3 基-2 DIT的蝶形運算

基-2 DIT蝶形運算結構如圖1所示［3］。

圖1 基-2 DIT蝶形運算結構Fig.1 Structure of radix-2 DIT butterfly operation

由圖1可知，每一次蝶形運算完成如下迭代運算：

將上式中的變量寫成實部和虛部構成的復數形式，即：

將這些復數形式代入上面的兩個等式并令實部等于實部，虛部等于虛部，分別可得如下4個等式：

從上面的4個實數等式中可以看到，一個蝶形運算包含4個實數乘法和8個實數加法，但是這8個實數加法可以通過兩級加法運算化簡成6個加法，所以蝶形運算的流水線設計中包含兩級加法器。

從功能上將整個蝶形運算單元看成一個封閉的系統(tǒng)，其輸入包括參加蝶形運算的兩個節(jié)點的實部和虛部4個數據，分別是x、y、X、Y，和系數WrN的實部和虛部兩個數據（用cos和sin表示），總計6個數據；輸出是這一級蝶形運算的結果，即對應節(jié)點在下一級上的實部和虛部4個數據，分別是x′、y′、X′、Y′，其功能如圖2所示。

圖2 蝶形運算單元功能示意圖Fig.2 Functions of butterfly unit

4 蝶形運算單元的時序

參照圖2，可以明確流水線包括4級，即數據讀入級、乘法運算級、第一級加法運算和第二級加法運算。

遵循盡可能壓縮蝶形單元硬件開銷的原則，每一級流水線功能實現(xiàn)采用串行結構，這樣乘法器和每一級加法器分別只用一個。流水線的每一級功能實現(xiàn)中運算次數的最大值是4，所以此時的蝶形運算周期是4個主時鐘周期。流水線的時序如表1所示。表中的下標n表示蝶形運算序號，當n=1時，所有含有n-1下標項均為無效值。為了書寫方便，表1中直接用cos和sin表示式（3）中的實部和虛部。一個蝶形運算周期包括4個階段，依次記為C1～C4。

表1 蝶形運算單元的流水線時序Table 1 Pipeline sequence of butterfly unit

與文獻［2］和文獻［4］中選用的并行流水線結構對比，該設計方案具有以下優(yōu)點：

（1）采用全流水線結構，充分體現(xiàn)出硬件處理的速度優(yōu)勢；合理地采用局部流水線技術，避免了并行結構引起的硬件資源消耗過多的弊端，因此更好地平衡了時間和硬件代價；

（2）將一次蝶形運算分解成4部分，所以以它為基礎構建的FFT處理器可以把所有的數據放在同一個存儲器中，只需要一個地址產生模塊，所以可以降低后面FFT處理器的設計復雜度，減少硬件資源消耗；

（3）串行結構較并行結構會導致處理時間變長，但是這種劣勢可以通過增加蝶形運算單元數目的方法來平衡，而采用全并行結構后，在資源比時間更為關鍵時卻無能為力，所以本文設計具有更好的靈活性。

5 蝶形運算單元結構

蝶形運算單元的時序確定以后，就可以確定其具體結構了。其內部結構包括運算部分、寄存器部分、時序邏輯部分和多路選擇器。運算部分包括一個浮點數乘法器、兩個浮點數加法器和兩個取反單元用以配合加法器實現(xiàn)減法運算；寄存器部分包括4個輸入數據寄存器、兩個乘法結果寄存器、兩個一級加法結果寄存器、一個最終運算結果寄存器和一個移位寄存器；時序邏輯部分用來產生其它各個單元的工作時鐘以保證整個流水線的正常工作。各個單元的工作時鐘同主時鐘關系的仿真結果如圖3所示。

圖3 時序邏輯單元輸出仿真Fig.3 Output of sequence logic unit

蝶形運算單元內部具體結構如圖4所示。由于浮點數加法運算的復雜性，一個時鐘周期內根本無法完成運算，所以設計了一個多級流水線浮點加法器單元。為了保證整個流水線按照如表1所表示的時序正常工作，在第一級加法運算和第二級加法運算之間要加入必要的延時單元，延時功能通過移位寄存器實現(xiàn)。

圖4 蝶形運算單元結構框圖Fig.4 Structure of butterfly unit

將圖4與文獻［2］中選用的并行流水線結構對比，可以發(fā)現(xiàn)采用串行全流水線結構后只用了并行結構1／4的硬件資源。并且可以將實數加法由8個簡化為6個，提高了25%的加法運算效率。

綜上所述，本文的設計方案可以極大地壓縮碟形運算單元對硬件資源的消耗。

6 基-2 DIT的FFT結構

為了驗證蝶形運算單元設計的可行性和可靠性，在它的基礎上，通過增加地址產生單元、雙口RAM以及旋轉因子產生單元，設計實現(xiàn)了一個1 024點的基-2 DIT浮點FFT處理器，其結構組成如圖5所示。

圖5 基-2 DIT的FFT處理器結構框圖Fig.5 Block diagram of radix-2 DIT FFT processor

旋轉因子可以通過CORDIC算法迭代得到［5］，也可以采用查找表的方法實現(xiàn)。由于設計目標是減少資源開銷，且面向的主要應用數據處理量不是很大，CORDIC算法的優(yōu)越性得不到體現(xiàn)。相比較而言，查表法不僅設計簡單，還具有線性度好的特點，所以FFT的設計采用查找表的方式獲取旋轉因子WrN。

采用輸入自然序輸出倒位序的算法［3］，由于該算法是原位運算，所以不需要中間存儲器。地址發(fā)生單元負責產生對應級和對應序號的蝶形運算所需的數據和旋轉因子所在的存儲器地址。時鐘及控制信號產生單元負責產生各個單元的工作時鐘和控制信號。倒序輸出控制單元負責產生倒序地址以輸出正常順序的運算結果。

7 設計的實現(xiàn)和仿真結果

7.1 蝶形運算單元和FFT處理器的實現(xiàn)

以Altera的Quartus II為設計工具，根據圖4和圖5所示的結構圖，采取自底向上的設計方式，用VHDL編寫各個模塊，最后得到以設計的蝶形運算單元為基礎的1 024點FFT處理器的邏輯綜合結果如圖6所示。

圖6 1 024點FFT處理器邏輯綜合結果Fig.6 Logic synthesis of1024-point FFT processor

7.2 仿真結果

為了驗證蝶形運算單元和FFT處理器運算結果是否正確，用一個單位幅度、周期為16點的方波信號作為RAM的初始化數據，將FFT處理器的輸出結果與Matlab對相同的方波信號處理的結果進行對比，以驗證設計的功能是否實現(xiàn)。

FFT處理器的仿真結果如圖7所示。選擇5個不為零的數據與Matlab仿真結果進行對比，如表2所示，仿真結果與Matlab的計算結果一致，且精度很高。

表2 計算結果精度比較Table 2 Comparison of precision

圖7 T=25 ns時FFT處理器仿真結果Fig.7 Simulation result of FFT processor when T=25 ns

處理器的工作時鐘周期用T表示，蝶形運算單元的處理周期為4T，1 024點FFT共包括10級蝶形，每級都有512個蝶形運算，加上流水線引起的延時為31T，所以總的處理用時為（31+52×10×4）T，即20 511T。以Altera公司的EP3C40F780C6為目標芯片在Quartus II 9.1中的仿真結果顯示，整個FFT處理器的最高工作頻率可達80 MHz，此時T取12.5 ns，可計算出整個運算用時為256.39μs。仿真結果如圖8所示。

圖8 主時鐘頻率為80 MHz時處理器仿真結果Fig.8 Simulation result of processor when the main clock frequency is80 MHz

8 結束語

將7.2節(jié)的仿真結果與文獻［2］的仿真結果對比，可得到以下結論：

（1）由表2的對比結果可知，本文設計方案可以獲得與文獻［2］中相同的計算精度；

（2）同樣地完成1 024點浮點FFT，采用本蝶形設計的FFT處理器需要的時鐘周期數是文獻［2］中處理器的20511／5520≈3.7倍，由本文第5節(jié)中的論述可知，該蝶形單元的硬件消耗只是其1／4。所以文中的串行全流水線結構設計不但可以大大壓縮蝶形單元的結構，使得FFT處理器有更好的適用性，還可以提高硬件的利用效率。

該設計已成功應用于一種音頻信號分析儀中，用來對采樣的信號做傅里葉變換。該音頻頻譜儀信號處理速度快，硬件資源消耗低，在性能和資源方面達到了比較好的平衡。

［1］楊靚，黃士坦.一個高效的嵌入式浮點FFT處理器的實現(xiàn)［J］.信號處理，2003，19（2）：161-165. YANG Liang，HUANGShi-tan.Implementation ofa Highly Efficient Embedded Floating FFT Processor［J］.Signal Processing，2003，19（2）：161-165.（in Chinese）

［2］榮瑜，朱恩.一種高性能FFT蝶形運算單元的設計［J］.東南大學學報（自然科學版），2007，37（4）：565-568. RONGYu，ZHU En.Design of high-performance FFT butterfly unit［J］.Journal of Southeast University（Natural Science Edition），2007，37（4）：565-568.（in Chinese）

［3］程佩青.數字信號處理教程［M］.北京：清華大學出版社，2007. CHENG Pei-qing.Digital signal processing tutorial［M］. Beijing：Tsinghua University Press，2007.（in Chinese）

［4］Shaditalab.Self-sorting Radix-2 FFT on FPGAs Using Parallel Pipelined Distributed Arithmetic Blocks［C］／／Proceedings of 1998 IEEE Symposium on FPGAs.Montreal，Canada：IEEE，1998：337-338.

［5］楊軍，郭躍東，丁俊.一種高速實時浮點蝶形運算單元的設計與實現(xiàn)［J］.儀器儀表學報，2010，31（3）：519-524. YANG Jun，GUOYue-dong，DING Jun.Design and implementation ofhigh-speed and real-time floating-pointbutterfly unit［J］.Chinese Journal of Scientific Instrument，2010，21（3）：519-524.（in Chinese）

YU Long-yang was born in Shandong Province，in 1989.He received the B.S.degree from Shandong University in 2010.He is now a graduate student.His research interests include spread spectrum communication and satalite navigation.

Email：sdyly0127＠163.com

段文偉（1987—），女，山東人，2010年于南京農業(yè)大學獲學士學位，現(xiàn)為北京航空航天大學碩士研究生，主要研究方向為擴頻通信；

DUANWen-wei was born in Shandong Province，in 1987. She received the B.S.degree from Nanjing Agricultural University in 2010.She is now a graduate student.Her research direction is spread spectrum communication.

李署堅（1953—），男，湖南人，副教授、碩士生導師，主要研究方向為擴頻通信、高動態(tài)GPS信號接收技術、RFID關鍵技術等。

LIShu-jian was born in Hunan Province，in 1953.He is now an associate professor and also the instructor of graduate students. His research interests include spread spectrum communication，receiving technology of HDR GPS signal，RFID key technology.

Design of a Floating-point Butterfly Unit w ith Sim plified Structure

YU Long-yang，DUANWen-wei，LIShu-jian
（School of Electronic and Information Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100191，China）

This paper presents an efficient design of butterfly unitwith simplified structure.The occupating coefficient of innermodules of the unit is almost100%.This unit uses a full pipeline structure，which saves 75% of the hardware resource consumption compared with the parallel structure.A floating-point FFT processor based on this butterfly unit is realized by using the FFT algorithm of DIT（Decimation-in-time）.The simulation results of QUARTUS IIdemonstrate the correctness of the design.This design has been successfully applied in the signal processing part of an audio signal analyser.

signal processing；butterfly unit；floating-point；FFT；pipeline；DIT

TN911.72

A

10.3969／j.issn.1001-893x.2011.09.015

于龍洋（1989—），男，山東人，2010年于山東大學獲學士學位，現(xiàn)為碩士研究生，主要研究方向為擴頻通信和衛(wèi)星導航；

1001-893X（2011）09-0073-05

2011-03-30；

2011-05-31