Booth算法

利用移位和加法，可以實現二進制無符號數的乘法，在無符號數乘法的基礎上，加上適當的符號處理，很容易得到帶符號數的原碼乘法器。但是，在計算機中，帶符號數都以補碼錶示，若採用原碼乘法器進行帶符號數的乘法運算，則首先要將乘數和被乘數轉換成原碼，相乘後再將負的乘積轉換成補碼，致使運算過程比較複雜。

不少處理器直接採用補碼相乘的方法，以避免運算過程中的碼制轉換，提高處理器的工作效率。然而，二進制無符號的乘法並不能直接推廣到補碼的乘法運算，比較普遍採用的是布斯(Booth)補碼相乘算法 ^[3]  。

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

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

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

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

具體步驟如下：

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

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

3、初始部分積為0。運算前，在乘數Y的補碼末位添加一位附加位Y_n+1，初始值為0 ^{[5]  [6]}  。

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

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

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

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

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

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

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