王超

摘 要：在數(shù)字信號處理中，乘法器是運算單元的核心部件之一，通過Booth編碼減少部分積的數(shù)量，能提高乘法運算的速度。該文分析了優(yōu)化乘法器的兩種思路，推導(dǎo)了2基Booth編碼及4基Booth編碼，指出在實現(xiàn)乘法器中優(yōu)先考慮4基Booth編碼的原因，闡述了在應(yīng)用Booth編碼時注意的問題，在實際應(yīng)用中驗證了該方案的有效性和穩(wěn)定性。

關(guān)鍵詞：補碼 Booth編碼 乘法器

中圖分類號：TP31 文獻標(biāo)識碼：A 文章編號：1674-098X（2012）12（b）-00-01

在數(shù)字信號處理芯片或一般微處理器芯片中，乘法器是芯片的核心之一，是處理器中進行數(shù)據(jù)處理的關(guān)鍵部件。乘法器完成一次操作的周期基本上決定了處理器的主頻。乘法器的速度和面積優(yōu)化對于整個處理芯片的性能來說是非常重要的。為了加快乘法器的執(zhí)行速度，減少乘法器的面積，有必要對乘法器的算法、結(jié)構(gòu)及電路的具體實現(xiàn)做深入的研究。

乘法器工作的基本原理是首先生成部分積，再將這些部分積相加得到乘積，如對于補碼形式N位有符號數(shù)乘法A×B來說，常規(guī)的乘法運算會產(chǎn)生N個部分積，這和一般手算乘法的過程沒有什么區(qū)別。

從乘法器工作的基本原理可以看出，要提高乘法運算的性能，可以從兩方面入手，一個是減少部分積的數(shù)量，另一個是縮短部分積的相加的運算時間。在節(jié)省部分積相加的運算方面，通常使用3：2CSA（Carry Saved Add）等壓縮編碼方法。而該文就是針對第一方面，就如何減少部分積的數(shù)量，著重推導(dǎo)Booth編碼原理，并簡要分析了Booth編碼的算法實現(xiàn)中的關(guān)鍵點。

1 基和4基Booth編碼

對于某個數(shù)A，采用n Bit的補碼可以表示成以下形式：

…………（1）

可以改寫成以下形式：

…………………………（2）

其中，。

由此可得：

…………………（3）

因為和只能取值0/1，故可以獲得如表1所示的碼表，稱為2基的Booth編碼表：

由（3）式結(jié)合表1可知，A和B的乘積P可以通過B/-B移位相加得到，這就稱為2基Booth編碼，產(chǎn)生n個部分積，共需n次累加，這個在實現(xiàn)上和普通手算乘法沒有區(qū)別。

當(dāng)n是偶數(shù)時，（1）式可以改寫成：

……………（4）

當(dāng)n為奇數(shù)時，對于一個補碼形式的數(shù)，可以直接在A的最高位增加一位與符號位相同的數(shù)，就可以滿足（4）式的表示形式了。

因此，

……（5）

因為、和只能取值0/1，故可以獲得如表 2所示的碼表，稱為4基Booth編碼表。

表1

0 0 0

0 1 B

1 0 -B

1 1 0

表2

0 0 0 0

0 0 1 B

0 1 0 B

0 1 1 2B

1 0 0 -2B

1 0 1 -B

1 1 0 -B

1 1 1 0

通過（5）式可以看出，A和B的乘積P，也可以通過對B/-B進行移位相加得到，這就是4基Booth編碼，共產(chǎn)生[n/2]個部分積（[*]表示向上取整運算）。

從上面的推導(dǎo)過程可以看出，數(shù)A還可以進行其他基的Booth編碼等，但是編碼復(fù)雜度有所增加。另外，主要考慮到在芯片實現(xiàn)時，出現(xiàn)部分積不是的這種情況，使得部分積不是被乘數(shù)左移若干位的情況，這種情況下要在芯片實現(xiàn)增加很多難度。例如，8基的Booth編碼中，將會出現(xiàn)-3B/3B這兩種情況，不是簡單的把B左移一位或者兩位能夠?qū)崿F(xiàn)的。因此，在芯片實現(xiàn)時往往優(yōu)先考慮4基的Booth編碼，使部分積的數(shù)量相對原來減少一半。

2 Booth編碼的應(yīng)用

在補碼形式的兩數(shù)A、B相乘中，不管是2基Booth編碼、4基Booth編碼還是其他基的Booth編碼，都會涉及到一個對“負(fù)”的部分積的進行取反“+1”的問題。處理手法是先取反，把“+1”放到后面的部分積當(dāng)中。當(dāng)然，最后一個部分積也存在是“負(fù)”數(shù)的情況，在這種情況下同樣要取反“+1”，因此，在補碼乘法Booth編碼中，會多一個部分積出現(xiàn)，有區(qū)別于其他表示形式的數(shù)相乘時使用Booth編碼，這點尤其值得注意。當(dāng)兩個相乘的數(shù)位寬不相等時，在設(shè)計中選擇使用位寬較小者進行Booth編碼，也就是對應(yīng)上面的“A”，這樣才能使部分積數(shù)量最少。

3 結(jié)語

該文簡要分析了優(yōu)化乘法器的兩種思路，著重介紹了Booth編碼法減少部分積的數(shù)量，推導(dǎo)了2基Booth編碼及4基Booth編碼，綜合考慮部分積個數(shù)、產(chǎn)生部分積難度兩種因素，指出在實現(xiàn)乘法器中優(yōu)先考慮4基Booth編碼的原因，另外闡述了在應(yīng)用Booth編碼時注意的問題。

參考文獻

[1] 孫航.Xilinx可編程邏輯器件的高級應(yīng)用與設(shè)計技巧[M].北京：電子工業(yè)出版社，2004.

[2] 朱子玉.CPU芯片邏輯設(shè)計技術(shù)[M].北京：清華大學(xué)出版社，2005.