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

booth_Booth算法 -基本內(nèi)容

在上例中，第一次判斷被乘數(shù)0110中的最低位0以及右邊的位(輔助位0)，得00；所以只進(jìn)行移位操作；第二次判斷0110中的低兩位，得10，所以作減法操作并移位，這個減法操作相當(dāng)于減去2a的值；第三次判斷被乘數(shù)的中間兩位，得11，于是只作移位操作；第四次判斷0110中的最高兩位，得01，于是作加法操作和移位，這個加法相當(dāng)于加上8a的值，因為a的值已經(jīng)左移了三次。

一般而言，設(shè)y=y0,yly2…yn為被乘數(shù)，x為乘數(shù)，yi是a中的第i位(當(dāng)前位)。根據(jù)yj與yi+1的值，Booth算法表示如下表所示，其操作流程如下圖所示。在Booth算法中，操作的方式取決于表達(dá)式(yi+1-yi)的值，這個表達(dá)式的值所代表的操作為：

0 無操作

+1 加x

-1 減x

Booth算法操作表示

yi yi+1 操作 說明

0 0 無 處于0串中，不需要操作

0 1 加x 1串的結(jié)尾

1 0 減x 1串的開始

1 1 無 處于1串中，不需要操作

乘法過程中，被乘數(shù)相對于乘積的左移操作可表示為乘以2，每次循環(huán)中的運(yùn)算可表示為對于x(yi+1-yi)2^31-i項的加法運(yùn)算(i=3l，30，…，1，0)。這樣，Booth算法所計算的結(jié)果 可表示為：

x×(0-y31)×2^0

+x×(y31-y30)×2^1

+x×(y30-y29)×2^2

…

+x×(y1-y0)×2^31

=x×(-y0×231 +y1×2^30 +y2×2^29+y31×2^0)

=x×y

例：用Booth算法計算2×(-3)。

解：補(bǔ)=0010， [-3]補(bǔ)=1101，在乘法開始之前，R0和R1中的初始值為0000和1101，R2中的值為0010。

在乘法的第一個循環(huán)中，判斷R1的最低位和輔助位為10，所以進(jìn)入步驟1c，將R0的值減去R2的值，結(jié)果1110送人R0，然后進(jìn)入第二步，將R0和Rl右移一位，R0和R1的結(jié)果為11110110，輔助位為l。

在第二個循環(huán)中，首先判斷Rl的最低位和輔助位為0l，所以進(jìn)入步驟1b，作加法，R0+R2=1111+0010，結(jié)果0001送入R0，這時R0R1的內(nèi)容為0001 0110，在第二步右移后變?yōu)?000 1011，輔助位為0。

在第三次循環(huán)中，判斷位為10，進(jìn)入步驟lc，R0減去R2，結(jié)果1110送入R0，R1不變；步驟2移位后R0和R1的內(nèi)容為1111 01011，輔助位為1。

第四次循環(huán)時，因兩個判斷位為11，所以不作加減運(yùn)算，向右移位后的結(jié)果為1111 1010，這就是運(yùn)算結(jié)果(―6)。

這個乘法的過程描述如下表所示，表中乘積一欄表示的是R0、R1的內(nèi)容以及一個輔助位P，黑體字表示對兩個判斷位的判斷。

用Booth補(bǔ)碼一位乘法計算2 ×(-3)的過程

循環(huán)

步驟

乘積（R0,R1, P）

0

初始值

0000 1101 0

第一次循環(huán)

1c：減0010

1110 1101 0

2：右移1位

1111 0110 1

第二次循環(huán)

1b：加0010

0001 0110 1

2：右移1位

0000 1011 0

第三次循環(huán)

1c：減0010

1110 1011 0

2：右移1位

1111 0101 1

第四次循環(huán)

1a：無操作

1111 0101 1

2：右移1位

1111 1010 1

4．補(bǔ)碼兩位乘

補(bǔ)碼兩位乘運(yùn)算規(guī)則是根據(jù)補(bǔ)碼一位乘的規(guī)則，把比較yiyi+1的狀態(tài)應(yīng)執(zhí)行的操作和比較yi-1yi 的狀態(tài)應(yīng)執(zhí)行的操作合并成一步，便可得出補(bǔ)碼兩位乘的運(yùn)算方法。

補(bǔ)碼兩位乘法運(yùn)算規(guī)則如下

判斷位yi-1y iyi+1

操作內(nèi)容

000

[zi+1]補(bǔ)=2-2[zi]補(bǔ)

001

[zi+1]補(bǔ)=2-2{[zi]補(bǔ)+[x]補(bǔ)}

010

[zi+1]補(bǔ)=2-2{[zi]補(bǔ)+[x]補(bǔ)}

011

[zi+1]補(bǔ)=2-2{[zi]補(bǔ)+2[x]補(bǔ)}

100

[zi+1]補(bǔ)=2-2{[zi]補(bǔ)+2[-x]補(bǔ)}

101

[zi+1]補(bǔ)=2-2{[zi]補(bǔ)+ [-x]補(bǔ)}

110

[zi+1]補(bǔ)=2-2{[zi]補(bǔ)+-x}補(bǔ)}

111

[zi+1]補(bǔ)=2-2[zi]補(bǔ)

由上表可見，操作中出現(xiàn)加2[x]補(bǔ)和加2[-x]補(bǔ)，故除右移兩位的操作外，還有被乘數(shù)左移一位的操作；而加2[x]補(bǔ)和加2[-x]補(bǔ)，都可能因溢出而侵占雙符號位，故部分積和被乘數(shù)采用三位符號位。

例：[x]補(bǔ)=0.0101，[y]補(bǔ)=1.0101 求： [x? y]補(bǔ)。

解：求解過程如下表所示。其中乘數(shù)取兩位符號位即11.0101,[-x]補(bǔ)=1.1011取三符號位為111.1011。

部分積

乘數(shù)

說 明

000.0000

+ 000.0101

1101010

判斷位為010，加[x]補(bǔ)

000.0101

000.0001

+ 000.0101

0111010

→2位

判斷位為010，加[x]補(bǔ)

000.0110

000.0001

+ 111.1011

01

1001110

→2位

判斷位為110，加[-x]補(bǔ)

111.1100

1001

最后一步不移位，得[x? y]補(bǔ)

故[x? y]補(bǔ)=1.11001001

可見，與補(bǔ)碼一位乘相比，補(bǔ)碼兩位乘的部分積多取一位符號位（共3位），乘數(shù)也多取一位符號位（共2位），這是由于乘數(shù)每次右移2位，且用3位判斷，故采用雙符號位更便于硬件實現(xiàn)。可見，當(dāng)乘數(shù)數(shù)值位為偶數(shù)時，乘數(shù)取2位符號位，共需作n/2次移位，最多作n/2+1次加法，最后一步不移位；當(dāng)n為奇數(shù)時，可補(bǔ)0變?yōu)榕紨?shù)位，以簡化邏輯操作。也可對乘數(shù)取1位符號位，此時共作n/2+1次加法和n/2+1次移位（最后一步移一位）。

對于整數(shù)補(bǔ)碼乘法，其過程與小數(shù)乘法完全相同。為了區(qū)別于小數(shù)乘法，在書寫上可將符號位和數(shù)值位中間的“.”改為“，”即可。

再補(bǔ)充一道例子，增加一下理解。呵呵

例1.37 設(shè)被乘數(shù)M=0111（7），乘數(shù)Q=0011（3），相乘過程如下：(其中的①②……是我自己加上去的)

A Q Q-1

①00000011 0 初始值

②1001 00110 A=A-M

③110010011右移（第1次循環(huán)）

④111001001右移（第2次循環(huán)）

⑤010101001A=A+M

⑥001010100右移（第3次循環(huán)）

⑦000101010右移（第4次循環(huán)）

乘法運(yùn)算結(jié)束后，所得結(jié)果共8位，A寄存器中是乘積的高位部分，Q寄存器中是乘積的低位部分，即乘積=0010101=(21)(十進(jìn)制）

例1.38設(shè)被乘數(shù)M=0111(7),乘數(shù)Q=1101（－3），相乘過程如下：

A QQ－1

000011010初始值

100111010A=A－M

110011101右移（第1次循環(huán)）

001111101A=A+M

000111110右移（第2次循環(huán)）

101011110A=A－M

110101111右移（第3次循環(huán)）

111010111右移（第4次循環(huán)）

乘積=11101011=(-21)(十進(jìn)制)

其中的移位是循環(huán)移位.

被乘數(shù)n位要移位3次.

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/8103490103/114230.html