Booth編碼在補(bǔ)碼乘法中的應(yīng)用

王超

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

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

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

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

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

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

1 基和4基Booth編碼

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

…………（1）

可以改寫成以下形式：

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

其中，。

由此可得：

…………………（3）

因?yàn)楹椭荒苋≈?/1，故可以獲得如表1所示的碼表，稱為2基的Booth編碼表：

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

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

……………（4）

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

因此，

……（5）

因?yàn)椤⒑椭荒苋≈?/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進(jìn)行移位相加得到，這就是4基Booth編碼，共產(chǎn)生[n/2]個(gè)部分積（[*]表示向上取整運(yùn)算）。

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

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

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

3 結(jié)語

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

參考文獻(xiàn)

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

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