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的中間部份，所以不需要算術運算
在準備好開始之前，將虛構位元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 |
| 乘積暫存器右移 | 0010 | 1111 0110 1 |
| 2 | 01=>乘積暫存器=乘積暫存器+被乘數暫存器 | 0010 | 0001 0110 1 |
| 乘積暫存器右移 | 0010 | 1111 1011 0 |
| 3 | 10=>乘積暫存器=乘積暫存器-被乘數暫存器 | 0010 | 1110 1011 0 |
| 乘積暫存器右移 | 0010 | 1111 0101 1 |
| 4 | 11=>不做任何事 | 0010 | 1111 0101 1 |
| 乘積暫存器右移 | 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
