Booth編碼在補碼乘法中的應用

王超

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

關鍵詞：補碼 Booth編碼 乘法器

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

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

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

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

1 基和4基Booth編碼

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

…………（1）

可以改寫成以下形式：

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

其中，。

由此可得：

…………………（3）

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

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

當n是偶數時，（1）式可以改寫成：

……………（4）

當n為奇數時，對于一個補碼形式的數，可以直接在A的最高位增加一位與符號位相同的數，就可以滿足（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編碼，共產生[n/2]個部分積（[*]表示向上取整運算）。

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

2 Booth編碼的應用

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

3 結語

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

參考文獻

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

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