Booth算法

布斯(Booth)算法是比較好的計算帶符號數乘法的方法。它採用相加和相減的操作計算補碼數據的乘積。Booth算法對乘數從低位開始判斷，根據兩個數據位的情況決定進行加法、減法還是僅僅移位操作。判斷的兩個數據位為當前位及其右邊的位(初始時需要增加一個輔助位0)，移位操作是向右移動。

基本介紹

• 中文名：Booth算法
• 外文名：Booth
• 提出者：Booth夫婦
• 套用學科：數學
• 方法：操作計算補碼數據的乘積

用途

對於算術四則運算，加減用補碼方法、乘除用原碼方法無法實現。這樣會使同一運算部件做四則算術運算需要進行碼制轉換，這會非常困難。

原碼乘法中的符號位不能參加運算，需要單獨用一個異或門產生乘積的符號位。故人們自然地思考能否讓符號數位化後也參加乘法運算的問題，補碼乘法就可以實現符號位直接參加運算。

補碼乘除解決符號位參加運算的問題，但過程比較複雜，人們尋求較好的補碼乘法和除法。由Booth(布斯)夫婦首先提出的比較法即Booth算法是一種比較好的帶符號數乘法的方法，目前被廣泛採用。

Booth算法採用相加和相減的操作，計算補碼數據的乘積。Booth算法對乘數從低位開始判斷，根據兩個數據位的情況決定進行加法、減法還是僅僅移位操作。判斷的兩個數據位為當前位及其右邊的位（初始時需要增加一個輔助位0），移位操作是向右移動。

原理

布斯算法將乘數看作從最低位開始的一串二進制數字。從最低位算起，只要這串數字為“0“，就不執行任何操作；當這串數字遇到第一個“1”時執行一次減法，即減被乘數與該位權值的乘積，而對於其後的“1”不執行任何操作；當這串數字再變為“0”時，則遇到第一個“0”時執行一次加法，即加被乘數與該位權值的乘積，而對其後的“0”則不執行任何操作。如此一直進行到最高位。

舉例來說，假設被乘數是5，乘數是7，即進行二進制數00000101與0000011相乘。該算法將7看作為三個“1”後面跟有五個“0”的一串數字。對於第一個”1”，該算法將減去5×2⁰，對於第二和第三個“1”，則不執行任何操作；當遇到第一個“0”時，加5×2³，得到最後結果是35。用算式表示為

計算步驟

Booth算法對乘數從低位開始判斷，根據兩個數據位的情況決定進行加法、減法還是僅僅移位操作。判斷的兩個數據位為當前位及其右邊的位(初始時需要增加一個輔助位0)，移位操作是向右移動。

其中booth算法在操作時，需要遵循一個操作表：

Yn	Yn+1	操作
0	0	+0，右移一位
0	1	+[x]補，右移一位
1	0	+[-x]補，右移一位
1	1	+0，右移一位

具體步驟如下：

1、被乘數X與乘數Y均以補碼的形式參加乘法運算，運算結果是積的補碼。

2、部分積和被乘數X採用雙符號位，乘數Y採用單符號位。

3、初始部分積為0。運算前，在乘數Y的補碼末位添加一位附加位Yn+1，初始值為0。

4、根據Y_nY_n+1的值，按照上表進行累加右移操作，右移時遵循補碼的移位規則。

5、累加n+1次，右移n次，最後一次不右移。

特點

2位Booth編碼可以將部分積的個數減少1/2，3位或4位的Booth編碼可以使部分積的個數減少得更多。但是，在3位或3位以上的Booth編碼中，雖然部分積的個數減少了，但是部分積產生電路變複雜了，部分積的產生需要的時間增加了，在一定程度上抵消了部分積的減少帶來的好處。因此，在實際的乘法器設計中，常被使用的仍然是2位Booth編碼。