alex9ufo 聰明人求知心切: 8-bit Booth’s Multiplier Booth演算法

2013年12月18日星期三

8-bit Booth’s Multiplier Booth演算法

Booth演算法
到目前為止，我們已經處理完正數的乘法，將這種演算法改成處理有號數字的最簡單方法是：首先將乘數與被乘數轉換成正數然後記住原來的正負號。而一種較簡潔的有號數字相乘的解決方法是Booth's algorithm。其構想來自下面觀察：只要具有加法與減法的能力，計算乘積應該有很多方法。假設我們想要計算(2)10X(6)10或(0010)2X(0110)2：

          (0010)2
  X       (0110)2
______________________
+          0000     移位(乘數是0)
+         0010      相加(乘數是1)
+        0010       相加(乘數是1)
+       0000        移位(乘數是0)
______________________
       00001100

Booth觀察到：能夠執行加法或減法的ALU，可以用一種以上的方法得到相同的結果。如
(6)10=(-2)10+(8)10或(0110)2=(-0010)2+(1000)2
當第一次遇到1時，可以用減法取代一串的1，當遇到最後一個1後面的0時，再加上被乘數，例如：

          (0010)2
  X       (0110)2
______________________
+          0000     移位(乘數是0)
+         0010      相減(乘數的第一個1)
+        0000       移位(字串1的中間)
+       0010        相加(上一步驟是最後一個1)
______________________
       00001100

Booth為了求快而發明了這種解決方法，他將一群的位元分成以1作為開始，中間，結尾：

如果我們局限在只看兩個位元，根據兩個位元的值，我們得到符合前面圖中的狀況：

現行位元	現行位元之右邊位元	解釋	範例
1	0	一群1的開始	000011110002
1	1	一群1的中間	000011110002
0	1	一群1的結束	000011110002
0	0	一群0的中間	000011110002

Booth演算法一次看乘數的兩個位元

依照目前與先前位元的不同，執行下面工作：
- 00：字串0的中間部份，不需要算術運算
- 01：字串1的結尾，所以將被乘數加到乘積的左半部
- 10：字串1的開端，所以從乘積的左半部減去被乘數
- 11：字串1的中間部份，所以不需要算術運算

如同前面的演算法，將乘積暫存器右移1位元

在準備好開始之前，將虛構位元0放在最右邊位元的右邊。將乘積右移時，因為我們是處理有號數字，必須保留中間過程結果的正負符號，所以當乘積向右移時，擴展其符號。因此第一次重覆迴圈的乘積暫存器右移1位元時，將(111001110)2轉換成(111100111)2，不是(011100111)2，這種移位稱為算術右移(arithemetic right shift)，有別於邏輯右移。
例如：以Booth演算法執行負數乘法 (0010)2X(1101)2=(11111010)2或2X(-3)=-6

重覆次數	步驟	被乘數暫存器	乘積暫存器
0	起始值	0010	0000 1101 0
1	10=>乘積暫存器=乘積暫存器-被乘數暫存器	0010	1110 1101 0
1	乘積暫存器右移	0010	1111 0110 1
2	01=>乘積暫存器=乘積暫存器+被乘數暫存器	0010	0001 0110 1
2	乘積暫存器右移	0010	1111 1011 0
3	10=>乘積暫存器=乘積暫存器-被乘數暫存器	0010	1110 1011 0
3	乘積暫存器右移	0010	1111 0101 1
4	11=>不做任何事	0010	1111 0101 1
4	乘積暫存器右移	0010	1111 1010 1

為了得到較快的乘法，可以將Booth演算法一般化，一次檢查多個位元。

TASK 1 : 8-bit Verilog Code for Booth’s Multiplier

module multiplier(prod, busy, mc, mp, clk, start);
output [15:0] prod;
output busy;
input [7:0] mc, mp;
input clk, start;
reg [7:0] A, Q, M;
reg Q_1;
reg [3:0] count;

wire [7:0] sum, difference;

always @(posedge clk)
begin
if (start) begin
A <= 8'b0;
M <= mc;
Q <= mp;
Q_1 <= 1'b0;
count <= 4'b0;
end
else begin
case ({Q[0], Q_1})
2'b0_1 : {A, Q, Q_1} <= {sum[7], sum, Q};
2'b1_0 : {A, Q, Q_1} <= {difference[7], difference, Q};
default: {A, Q, Q_1} <= {A[7], A, Q};
endcase
count <= count + 1'b1;
end
end

alu adder (sum, A, M, 1'b0);
alu subtracter (difference, A, ~M, 1'b1);

assign prod = {A, Q};
assign busy = (count < 8);

endmodule

//The following is an alu.
//It is an adder, but capable of subtraction:
//Recall that subtraction means adding the two's complement--
//a - b = a + (-b) = a + (inverted b + 1)
//The 1 will be coming in as cin (carry-in)
module alu(out, a, b, cin);
output [7:0] out;
input [7:0] a;
input [7:0] b;
input cin;

assign out = a + b + cin;

endmodule
Testbench for Booth’s Multiplier

module testbench;

reg clk, start;
reg [7:0] a, b;

wire [15:0] ab;
wire busy;

multiplier multiplier1(ab, busy, a, b, clk, start);

initial begin
clk = 0;
$display("first example: a = 3 b = 17");
a = 3; b = 17; start = 1; #50 start = 0;
#80 $display("first example done");
$display("second example: a = 7 b = 7");
a = 7; b = 7; start = 1; #50 start = 0;
#80 $display("second example done");
$finish;
end

always #5 clk = !clk;

always @(posedge clk) $strobe("ab: %d busy: %d at time=%t", ab, busy,
$stime);

endmodule