鞠 芳，馬 昕，田 嵐

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

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

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

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

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

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

1.1 陣列乘法器

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

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

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

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

圖2 FPGA 的快速陣列乘法器

1.2 查找表乘法器

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

圖3 查找表乘法器原理圖

1.3 移位相加乘法器

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

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

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

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

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

1.4 Booth 乘法器

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

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

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

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

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

圖6 Booth 時(shí)序乘法器的STG

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

4×4 Booth 乘法器的控制器產(chǎn)生的控制信號(hào)對(duì)數(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ì)方法的性能比較

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

［1］馬秀娟，牛進(jìn)鵬，考麗，等.高速數(shù)據(jù)采集系統(tǒng)中的FPGA 的設(shè)計(jì)［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 微處理器的快速乘除法運(yùn)算設(shè)計(jì)與實(shí)現(xiàn)［J］.電子器件，2007，30(1):162－166.

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

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

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

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

［8］Michael D Ciletti 著.張雅綺，李鏘， 等譯.Verilog HDL 高級(jí)數(shù)字設(shè)計(jì)［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.