于龍洋，段文偉，李署堅

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

一種精簡結(jié)構(gòu)的浮點蝶形運算單元設(shè)計?

于龍洋，段文偉，李署堅

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

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

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

1 引言

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

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

2 FFT算法

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

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

3 基-2 DIT的蝶形運算

基-2 DIT蝶形運算結(jié)構(gòu)如圖1所示［3］。

圖1 基-2 DIT蝶形運算結(jié)構(gòu)Fig.1 Structure of radix-2 DIT butterfly operation

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

將上式中的變量寫成實部和虛部構(gòu)成的復(fù)數(shù)形式，即：

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

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

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

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

4 蝶形運算單元的時序

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

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

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

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

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

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

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

5 蝶形運算單元結(jié)構(gòu)

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

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

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

圖4 蝶形運算單元結(jié)構(gòu)框圖Fig.4 Structure of butterfly unit

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

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

6 基-2 DIT的FFT結(jié)構(gòu)

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

圖5 基-2 DIT的FFT處理器結(jié)構(gòu)框圖Fig.5 Block diagram of radix-2 DIT FFT processor

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

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

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

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

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

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

7.2 仿真結(jié)果

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

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

表2 計算結(jié)果精度比較Table 2 Comparison of precision

圖7 T=25 ns時FFT處理器仿真結(jié)果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為目標(biāo)芯片在Quartus II 9.1中的仿真結(jié)果顯示，整個FFT處理器的最高工作頻率可達(dá)80 MHz，此時T取12.5 ns，可計算出整個運算用時為256.39μs。仿真結(jié)果如圖8所示。

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

8 結(jié)束語

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

（1）由表2的對比結(jié)果可知，本文設(shè)計方案可以獲得與文獻(xiàn)［2］中相同的計算精度；

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

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

［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蝶形運算單元的設(shè)計［J］.東南大學(xué)學(xué)報（自然科學(xué)版），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］程佩青.數(shù)字信號處理教程［M］.北京：清華大學(xué)出版社，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］楊軍，郭躍東，丁俊.一種高速實時浮點蝶形運算單元的設(shè)計與實現(xiàn)［J］.儀器儀表學(xué)報，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年于南京農(nóng)業(yè)大學(xué)獲學(xué)士學(xué)位，現(xiàn)為北京航空航天大學(xué)碩士研究生，主要研究方向為擴頻通信；

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—），男，湖南人，副教授、碩士生導(dǎo)師，主要研究方向為擴頻通信、高動態(tài)GPS信號接收技術(shù)、RFID關(guān)鍵技術(shù)等。

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年于山東大學(xué)獲學(xué)士學(xué)位，現(xiàn)為碩士研究生，主要研究方向為擴頻通信和衛(wèi)星導(dǎo)航；

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

2011-03-30；

2011-05-31