鞠 芳，馬 昕，田 嵐

(山東大學(xué)信息科學(xué)與工程學(xué)院，濟南 250100)

在通信與信號處理系統(tǒng)中，乘法器是數(shù)字運算的重要單元，高性能乘法器是完成高性能實時數(shù)據(jù)運算和處理的關(guān)鍵。 隨著 FPGA (Field Programmable Gate Array，現(xiàn)場可編程門陣列)技術(shù)的發(fā)展，F(xiàn)PGA 以其高度的靈活性和正在越來越多地替代ASIC和DSP 用于信號處理的運算［1］，然而常見的FPGA 芯片一般不具有現(xiàn)成的乘法運算單元，因而研究基于FPGA 的數(shù)字乘法器設(shè)計具有非常重要的意義。

針對FPGA 的乘法器設(shè)計，已有前人做了大量的工作，總結(jié)起來主要有陣列法［2］、查找表法、移位相加法［3］和Booth 法［4］，此外，還有以這幾種方法為基礎(chǔ)的改進方法，如有限域乘法器［5］等。實際應(yīng)用中，有時需要乘法運算有較快的速度，有時則需要較少的硬件資源和適中的速度，乘法器的速度和面積優(yōu)化對于整個CPU 的性能來說是非常重要的，因而有必要對乘法器的算法、結(jié)構(gòu)及電路的具體實現(xiàn)做深入的分析并給出性能比較。本文針對查找表法、移位相加法和Booth 法等幾種常用數(shù)字乘法器的設(shè)計方法在ALTERA 公司FPGA 系列進行了設(shè)計，并利用Quartus Ⅱ9.0 對這些設(shè)計進行了綜合和仿真驗證。最后從運算速度和所占用邏輯資源兩方面對數(shù)字乘法器的性能進行了比較。

1 數(shù)字乘法器設(shè)計方法

乘法運算可以利用組合電路或時序電路來實現(xiàn)。組合電路乘法器比時序電路乘法器耗用硬件資源更多，但是運算速度更快。時序電路乘法器則需要幾個時鐘周期才能完成乘法運算，但是耗用的硬件資源較少。常見的組合電路乘法器有陣列乘法器和查找表乘法器，常見的時序電路乘法器有移位相加乘法器和Booth 乘法器，其它的乘法器多為以此為基礎(chǔ)進行組合變形的，如有限域乘法器等。

設(shè)計組合電路乘法器需要根據(jù)乘法運算的原理由邏輯門實現(xiàn)，設(shè)計思路相對簡單，而時序電路乘法器設(shè)計通常需有兩個步驟:(1)選擇數(shù)據(jù)通路結(jié)構(gòu)(2)設(shè)計狀態(tài)機以控制數(shù)據(jù)通路。對于給定的數(shù)據(jù)通路結(jié)構(gòu)，狀態(tài)機必須能生成適當(dāng)?shù)目刂菩盘栃蛄衼砜刂茢?shù)據(jù)的移動以產(chǎn)生乘積［6－8］。下面對陣列乘法器、查找乘法器、移位乘法器以及Booth 乘法器的設(shè)計方法作分析比較。

1.1 陣列乘法器

陣列乘法器是純組合類型的乘法器，完全由邏輯門實現(xiàn)。乘數(shù)、被乘數(shù)和乘積都以并行方式提供［9］。

圖1 給出了4×4 陣列乘法器的一種結(jié)構(gòu)。該結(jié)構(gòu)包括16個與門、8個全加器和4個半加器。在同步操作中，控制乘法器數(shù)據(jù)傳輸?shù)臅r鐘周期必須與電路中的最長路徑相適應(yīng)，該路徑從乘數(shù)的最低位開始，途經(jīng)加法器，到達乘積的最高位。加法器的進位路徑和求和路徑對最長路徑都有影響，應(yīng)將其延時均勻分布。

圖1 陣列乘法器的一種結(jié)構(gòu)

對于現(xiàn)在的FPGA 來講，進位計算執(zhí)行的速度要比和累加的速度快［10］，因此圖2所示的結(jié)構(gòu)對于FPGA 來講效率更高。該結(jié)構(gòu)的思想是:第一步將兩個相鄰的部分積相加，使部分積的數(shù)目減半。然后重復(fù)上述過程直到形成最終乘積。通過引入流水線技術(shù)，可以提高陣列乘法器的工作頻率。

圖2 FPGA 的快速陣列乘法器

1.2 查找表乘法器

查找表乘法器是將乘積直接存儲在存儲器中，將乘數(shù)和被乘數(shù)作為地址訪問存儲器，得到的輸出數(shù)據(jù)就是乘法運算的結(jié)果。圖3 給出了查找表乘法器的原理。查找表乘法器的速度只局限于所使用的存儲器的存取速度，但是查找表的規(guī)模隨著操作數(shù)位數(shù)的增加迅速增大。因此，查找表乘法器不適合位數(shù)較高的乘法。當(dāng)乘數(shù)位數(shù)較高時可以將乘數(shù)分成幾個部分，然后用低位數(shù)的查找表實現(xiàn)乘法運算。

圖3 查找表乘法器原理圖

1.3 移位相加乘法器

圖4 給出了4×4 移位相加乘法器控制器的ASMD 圖表:控制器初始狀態(tài)為S_idle，復(fù)位完成后Ready 信號有效，表示時序乘法器空閑，可以接收數(shù)據(jù)。然后控制器等待外部輸入Start 信號。Start 信號成立時，如果輸入數(shù)據(jù)全0，則清空乘積寄存器并保持在狀態(tài)S_idle，否則控制器應(yīng)撤銷Ready 信號，輸出Load_words 信號并進入狀態(tài)S_running。在狀態(tài)S_running 判斷計數(shù)器的值，如果計數(shù)器的值為操作數(shù)字節(jié)長度，控制器進入狀態(tài)S_idle，乘法運算完成，否則判斷乘積寄存器的最低位，如果乘積寄存器最低位為1，輸出Add_shift 信號，如果乘積寄存器最低位為0 則輸出Shift 信號。此間控制器運行在狀態(tài)S_running，直到計數(shù)器的值等于操作數(shù)字節(jié)長度［10］。

圖4 移位相加乘法器的控制器方框圖和ASMD 圖表

圖5 給出了4×4 移位相加乘法器的數(shù)據(jù)通路結(jié)構(gòu):該數(shù)據(jù)通路結(jié)構(gòu)由存儲被乘數(shù)的寄存器、一個加法器、一個存儲乘數(shù)和乘積的移位寄存器組成。該結(jié)構(gòu)把被乘數(shù)寄存器通過硬件連線與加法器相連，并作為乘積寄存器最左邊的5 位。乘數(shù)的值最初存儲在乘積寄存器最右邊的4 位。所求得的部分積放在乘積寄存器的最左邊，并將乘積寄存器的內(nèi)容右移。在每一步中，由乘積寄存器的最低位決定是否將被乘數(shù)與乘積寄存器相加，直到乘數(shù)的所有位被移出乘積寄存器為止，最后留在乘積寄存器中的內(nèi)容就是乘法運算的結(jié)果。

圖5 移位相加乘法器的結(jié)構(gòu)單元

移位相加乘法器的控制器產(chǎn)生的控制信號對數(shù)據(jù)通道的作用為:Flush 清空乘積寄存器Load_words控制數(shù)據(jù)通路將乘數(shù)和被乘數(shù)裝入寄存器同時將計數(shù)器清零;Shift 控制乘積寄存器的移位;Add_shift控制被乘數(shù)和部分積的相加以及乘積寄存器的移位;Increment 控制計數(shù)器計數(shù)。

1.4 Booth 乘法器

使用Booth 算法的乘法器對乘數(shù)的位進行重新編碼以減少完成乘法運算周期所需的加法運算次數(shù)。Booth 算法可以應(yīng)用于以2 補形式表示的有符號數(shù)。因此使用Booth 重編碼的硬件乘法器不需要修改就可以使用于負數(shù)運算［11－12］。

Booth 算法的關(guān)鍵在于它跳過了乘數(shù)中全1 的字符串，而將一系列加法運算用一次加法和一次減法來替代。例如，二進制數(shù)11110000 等于(28－1)－(24－1)=28－24=240。Booth 編碼方案將檢測乘數(shù)的全1 字符串，并用加減法運算得到的有符號數(shù)來取代它們，以對乘數(shù)重新進行編碼。

表1 給出了Booth 重編碼規(guī)則，該規(guī)則從最低位到最高位依次讀取，兩個相鄰位(Mi，Mi－1)的值確定了Booth 重編碼乘數(shù)的各個位BRCi，當(dāng)算法讀取兩個相鄰位時可形成BRCi，并用BRCi 來判斷在跳到下一位之前是進行加法運算還是減法運算。該算法第一步放置一個0 到乘數(shù)最低位的右邊，處理過程將遇到的第一個1 編碼為1，跳過任何連續(xù)的1直到出現(xiàn)0，該0 可被編為1 以表示全1 字符串的結(jié)束，然后進行下一步的處理。

表1 補數(shù)的Booth 重編碼規(guī)則

圖6 給出了4×4 Booth 乘法器的狀態(tài)轉(zhuǎn)移圖:控制器初始狀態(tài)為S_idle，復(fù)位完成后Ready 信號有效，表示時序乘法器空閑，可以接收數(shù)據(jù)。然后控制器等待外部輸入Start 信號。Start 信號成立時，控制器撤銷Ready 信號，輸出Load_words 信號并進入狀態(tài)S_1。此后的狀態(tài)轉(zhuǎn)移取決于Booth 重編碼BRCi，如果BRCi為1 則輸出Add_shift 信號并進入下一狀態(tài)，如果BRCi為2 則輸出Sub_shift 信號并進入下一狀態(tài)，如果BRCi為0或3 則輸出Shift 信號并進入下一狀態(tài)。直到進入狀態(tài)S_5，此時控制器將輸出Ready 信號并保持在狀態(tài)S_5，直到外部輸入Start 信號控制器才進入狀態(tài)S_1 并輸出Load_words 信號重新裝載乘數(shù)和被乘數(shù)，開始新一次的乘法運算。圖7 給出了4×4 Booth 乘法器的數(shù)據(jù)通路結(jié)構(gòu):該數(shù)據(jù)通路結(jié)構(gòu)由存儲被乘數(shù)和乘數(shù)的兩個移位寄存器、一個加法器和一個存儲乘積的寄存器組成。

圖6 Booth 時序乘法器的STG

圖7 Booth 乘法器的數(shù)據(jù)通路結(jié)構(gòu)

4×4 Booth 乘法器的控制器產(chǎn)生的控制信號對數(shù)據(jù)通道的作用為:Load_words 控制數(shù)據(jù)通路將乘數(shù)和被乘數(shù)裝入寄存器;Shift 控制乘數(shù)寄存器和被乘數(shù)寄存器的移位;Add_shift 控制部分積和被乘數(shù)的相加以及乘數(shù)寄存器和被乘數(shù)寄存器的移位;Sub_shift 控制部分積和被乘數(shù)的相減以及乘數(shù)寄存器和被乘數(shù)寄存器的移位。

2 各種數(shù)字乘法器設(shè)計方法的性能比較

根據(jù)上述原理分別設(shè)計了4×4 數(shù)字乘法器和16×16 數(shù)字乘法器，利用Quartus Ⅱ9.0 對各種數(shù)字乘法器進行編譯、綜合及功能仿真(目標(biāo)芯片為cyclone Ⅱ系列中的EP2C8Q208C8)。4×4 位數(shù)字乘法器的綜合結(jié)果見表2。16×16 位數(shù)字乘法器的仿真結(jié)果見表3。

表2 4×4 位乘法器的綜合結(jié)果

表3 16×16 位乘法器的綜合結(jié)果

由以上綜合及仿真結(jié)果可知:對于4×4 位乘法器，陣列乘法器通過增加硬件資源耗用提高了運算速度。查找表乘法器運算速度高于陣列乘法器，其硬件資源耗用也高。移位相加乘法器完成一次乘法需要5個時鐘周期，運算時間較長，但其硬件資源的耗用最少。Booth 乘法器速度上與移位相加乘法器差不多，但資源消耗較大，由此可見對于位寬較小時Booth 乘法器結(jié)構(gòu)的性能沒有優(yōu)勢。

對于16×16 位乘法器，陣列乘法器通過增加硬件資源耗用并適當(dāng)?shù)氖褂昧魉€技術(shù)提高了運算速度，而查找表乘法器通過使用存儲單元存儲乘法結(jié)果達到運算速度的提高，但是其速度已明顯低于陣列乘法器，只是其邏輯單元資源的消耗比陣列乘法器少，但卻要占用較多的片內(nèi)存儲器資源。移位相加乘法器完成一次乘法需要17個時鐘周期，運算時間比其他三種乘法器的都長，但硬件資源的耗用最少。Booth 乘法器速度最快，而同時資源消耗僅高于移位相加乘法器，綜合優(yōu)勢明顯，由此可見對于位寬較大時，Booth 乘法器體現(xiàn)出了明顯的性能優(yōu)勢。

組合乘法器的硬件資源耗用隨著乘法器字節(jié)長度增加而大幅度增長，而時序乘法器的硬件資源耗用隨字節(jié)長度增加增長速度較緩，除Booth 乘法器之外，其他三種乘法器同時完成乘法運算所需的時鐘周期將隨字節(jié)長度呈明顯增長趨勢。

3 結(jié)束語

本文應(yīng)用Verilog 語言，設(shè)計了四種數(shù)字乘法器，并對它們的性能進行了比較。從仿真和綜合的結(jié)果看，隨著位寬的變化，方法的相對效果會發(fā)生改變。對于具有較寬數(shù)據(jù)位的乘法器來說，使用Booth乘法器有明顯的優(yōu)勢。而位寬較小時，陣列乘法器的綜合優(yōu)勢明顯。如果僅考慮資源占用，移位相加乘法器是較好的選擇。在實際應(yīng)用中應(yīng)根據(jù)系統(tǒng)的要求選擇合適的乘法器設(shè)計方法。數(shù)字乘法器的結(jié)構(gòu)多種多樣，本文僅針對四種常見乘法器做了分析和比較，實際應(yīng)用時可根據(jù)實際情況選擇合適的乘法器設(shè)計方法。

［1］馬秀娟，牛進鵬，考麗，等.高速數(shù)據(jù)采集系統(tǒng)中的FPGA 的設(shè)計［J］.電子器件，2007，30(4):1372－1379.

［2］Habibi A，Wintz P A.Fast Multipliers［J］.IEEE Transactions on Computers，1970，C－19(2):153－157.

［3］王江，黃秀蓀，陳剛，等.一種RISC 微處理器的快速乘除法運算設(shè)計與實現(xiàn)［J］.電子器件，2007，30(1):162－166.

［4］湯曉慧，楊軍，吳艷，等輝.基于Booth 算法的32×32 乘法器IP核設(shè)計［J］.電子器件，2005，28(1):218－220.

［5］鮑可進，鄭博.基于FPGA 的有限域乘法算法的分析和比較［J］.計算機工程，2008，34(23)247－248.

［6］Donald E Thomas，Philip R Moorby 著.劉明業(yè)，蔣敬旗，刁嵐松等譯.硬 件 描 述 語 言Verilog［M］.北 京:清 華 大 學(xué) 出 版社，2001.

［7］Uwe Meyer-Baese 著.劉凌譯.數(shù)字信號處理的FPGA 實現(xiàn)［M］.北京:清華大學(xué)出版社，2006.

［8］Michael D Ciletti 著.張雅綺，李鏘， 等譯.Verilog HDL 高級數(shù)字設(shè)計［M］.北京:電子工業(yè)出版社，2005.

［9］Amberg P.Pinckney Harris，Parallel N.High-Radix Montgomery Multipliers［C］//proceedings of 42nd Asilomar Conference on Signals，Systems and Computers.Pacific Grove，CA，Oct.26－29，2008:772－776.

［10］Gnanasekaran R.A Fast Serial-Parallel Binary Multiplier［J］.IEEE Transactions on Computers，1985，34(8):741－744.

［11］Booth A D.A Signed Binary Multiplication Technique［J］.Quarterly Journal of Mechanics and Applied Mathematics，1951，4(2):236－240.

［12］Wallace C S.A Suggestion for a Fast Multiplier［J］.IEEE Transactions on Electronic Computers，1964，13(2):14－17.