Booth’s Algorithm布斯乘法算法

最後更新於 2021 年 5 月 15 日

Booth’s algorithm 是一種簡潔的有號數字相乘的方法。

一般來說,我們知道的二進位之間的乘法是將乘數與被乘數轉為正數,最後再取補數。而Booth演算法可以做有號數的相乘,不需轉換成正數來計算。

計算方式

以一題計算來示範:

  • 8bit , 2’s , (-7) * 4

1.首先,將 (-7) 與 4 轉為二進制,分別為 1001 與 0100,但題目要求的是8bit,因此要延伸位元變為 1111100100000100*負數補1;正數補0

image 24 Booth's Algorithm布斯乘法算法

2.再來在乘數最右邊補一個0,從右至左相鄰的兩個bit根據右邊表格做運算,會得到 00001(-1)00

image 25 Booth's Algorithm布斯乘法算法

3.再來我們定義N為1001,但題目設定乘數與被乘數皆為8bit,代表相乘結果為16bit,因此我們需要延伸位元至16bit (+補0,-補1),因此N=1111111111111001,而-N則是取2的補數為0000000000000111

4.將11111001與剛剛運算得到的00001(-1)00做相乘,當被乘數為1時將N寫在下方,被乘數為-1時則將-N寫在下方,為0時左移一位,最後相加取得計算結果(只需要運算到16位元)。

20200606045959 Booth's Algorithm布斯乘法算法

5.運算結果的位數過多比較難檢查,建議可以改為16進制會比較好看(不限制)。

線上Booth’s Algorithm計算機:http://www.ecs.umass.edu/ece/koren/arith/simulator/Booth/


如果單純用文字敘述看不懂,也可以在youtube上找解法,我看到最容易理解的是下方這個教學:

4 3 評分數
Article Rating
訂閱
通知
guest

3 Comments
在線反饋
查看所有評論
Kaitou
Kaitou
10 月 前

您好,想請問最後一個計算的部分-1*11111001的地方為什麼會得出00000111呢?

Kaitou
Kaitou
回复  Kaitou
10 月 前

是-1的值就是直接把-N色算出來的答案帶進去嗎?

...
...
8 月 前

…還行