Verilog – 乘法器Booth算法
@(知識點彙總)
文章目錄
- Verilog -- 乘法器Booth算法
-
- 1. 原理
- 2. 一般化推論
- 3. 實際算法
- 4. Verilog代碼
1. 原理
Booth算法的原理其實國小國中就學過，比如下面這道題：
簡便計算： 8754 × 998 = ? 8754 \times 998 = ? 8754×998=?
随便抓個娃娃來都知道應該這麼算：
8754 × 998 = 8754 × 1000 − 8754 × 2 8754 \times 998 = 8754 \times 1000 - 8754 \times 2 8754×998=8754×1000−8754×2
我們都知道在十進制裡，10的倍數的乘法很容易，就是後面加幾個0的事情，而上面這種簡便計算都有個特點，就是會有999,1001,997,1002這種數，0和9出現的次數很多，這樣就可以通過變為化簡變為簡單的乘法和加減法。
**對于二進制數，這種簡便計算的情況往往更多。**因為計算機中為了計算友善，往往将資料轉換為補碼的形式，而補碼形式在計算時會擴充符号位，比如有符号數補碼5’b10110 = -10，在計算與一個8位數相加時會擴充為8‘b11110110，可以發現，這種數往往會有很多連續的1出現，這跟上面的簡便計算的例子非常相似。比如：
0011110 = 0100000 − 0000010 = 2 5 − 2 1 0011110 = 0100000 - 0000010 = 2^5-2^1 0011110=0100000−0000010=25−21
這就是booth算法分解乘數的基本原理。
2. 一般化推論
假設A和B是乘數和被乘數，且有：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ A &= a_{n-1}a_…
最後的Val(A)的表達式實際上就是補碼A表示的原碼。
3. 實際算法
上面的公式推導了booth乘法對乘數的分解原理，實際上在編碼時隻需要公式3，可以做如下的編碼表：
| a i a_i ai | a i − 1 a_{i-1} ai−1 | a i − 1 − a i a_{i-1}-a_i ai−1−ai | 操作 |
|---|---|---|---|
| 無 | |||
| 1 | -1 | 減B | |
| 1 | 1 | 無 | |
| 1 | 1 | 加B |
舉個栗子：
N = 7 , B = 22 = ( 0010110 ) 2 , A = − 34 = − ( 0100010 ) 2 N=7, B = 22 = (0010110)_2,A=-34=-(0100010)_2 N=7,B=22=(0010110)2,A=−34=−(0100010)2
首先計算-B的補碼(算法中要用到）： − B ‾ = ( 1101010 ) 2 \overline{-B} = (1101010)_2 −B=(1101010)2
以及A的補碼： A ‾ = ( 1011110 ) 2 \overline{A} = (1011110)_2 A=(1011110)2
硬體計算過程如下：
首先初始化p空間: p = 2 N + 1 p=2N+1 p=2N+1.[A]和[Q]是兩個寄存器。其中[Q]是N+1位的。
- 首先将乘數A的補碼放到[Q]的高N位上，Q的最低為預設為0.（這步是為了 i = 0 i=0 i=0時，讓 a − 1 = 0 a_{-1}=0 a−1=0。
- 在Q中檢查 a i − 1 − a i a_{i-1}-a_i ai−1−ai，得00，查表得無操作，直接将[A]和[Q]合起來右移（算數移位）
- 在Q中檢查 a i − 1 − a i a_{i-1}-a_i ai−1−ai，得10，查表得減B,相當于加-B的補碼，在[A]寄存器中加上-B的補碼，之後右移
- …
最後的結果11110100010100就是結果的補碼，也就是：
B × A = 11110100010100 ‾ = ( 10001011101100 ) 原 = − 74 8 10 B\times A = \overline{11110100010100} = (10001011101100)_原 = -748_{10} B×A=11110100010100=(10001011101100)原=−74810
算法跟公式的比對：
實際上，對于公式中的每一項 ( a i − 1 − a i ) × B × 2 i (a_{i-1}-a_i)\times B\times 2^i (ai−1−ai)×B×2i都對應實際算法中的每一步。 ( a i − 1 − a i ) (a_{i-1}-a_i) (ai−1−ai)決定了B的系數，右移操作因為作用在[A][Q]寄存器上，是以實際上是相當于将積右移，等價于B左移，是以這一步對應 × 2 i \times 2^i ×2i操作。加減B的操作都作用在[A]寄存器上，保證了 × 2 i \times 2^i ×2i後的B能夠作用在正确的位上。
4. Verilog代碼
這裡隻放一種狀态機實作的時序邏輯電路，計算過程基本跟上面的算法一樣。
參考了
https://mp.weixin.qq.com/s?__biz=MzU3ODgwMzI5NA==&mid=2247483685&idx=1&sn=d06f3a4ced52b42c48bd978e63e2d1bf&chksm=fd6e8214ca190b023383add3c7b60a2eeffae1f747ea2c1059ebee273e7241116d411384682d&scene=126&sessionid=1589012994&key=826ecc1d344963fb89a1fe763a3a0a3c6d8d706a9ef97ba15b329db58590b56ea54262ec5c331c21ac89e81717147cec8824d56cd54abdbb95c5cf0a5a692b36cc66ac50b6dada9f71b68e893f8cb271&ascene=1&uin=MTk3NDE3MDgyMg%3D%3D&devicetype=Windows+10+x64&version=62090070&lang=zh_CN&exportkey=AQ4%2BwrjRyeNZJrEsZxPofPE%3D&pass_ticket=dkwMmft8fNv1TNAobItN6BuADVUY3SXqwDEWdgd1XXquz3xUPDTVW48UvhGe4gkz
的代碼,提供者fanhu， [email protected]
`timescale 1ns/1ps
module booth_fsm
# (parameter DATAWIDTH = 8)
(
input clk,
input rstn,
input en,
input [DATAWIDTH-1:0] multiplier,
input [DATAWIDTH-1:0] multiplicand,
output reg done,
output reg [2*DATAWIDTH-1:0] product
);
parameter IDLE = 2'b00,
ADD = 2'b01,
SHIFT = 2'b11,
OUTPUT = 2'b10;
reg [1:0] current_state, next_state; // state registers.
reg [2*DATAWIDTH+1:0] a_reg,s_reg,p_reg,sum_reg; // computational values.
reg [DATAWIDTH-1:0] iter_cnt; // iteration count for determining when done.
wire [DATAWIDTH:0] multiplier_neg; // negative value of multiplier
always @(posedge clk or negedge rstn)
if (!rstn) current_state = IDLE;
else current_state <= next_state;
// state transform
always @(*) begin
next_state = 2'bx;
case (current_state)
IDLE : if (en) next_state = ADD;
else next_state = IDLE;
ADD : next_state = SHIFT;
SHIFT : if (iter_cnt==DATAWIDTH) next_state = OUTPUT;
else next_state = ADD;
OUTPUT: next_state = IDLE;
endcase
end
// negative value of multiplier.
assign multiplier_neg = -{multiplier[DATAWIDTH-1],multiplier};
// algorithm implemenation details.
always @(posedge clk or negedge rstn) begin
if (!rstn) begin
{a_reg,s_reg,p_reg,iter_cnt,done,sum_reg,product} <= 0;
end else begin
case (current_state)
IDLE : begin
a_reg <= {multiplier[DATAWIDTH-1],multiplier,{(DATAWIDTH+1){1'b0}}};
s_reg <= {multiplier_neg,{(DATAWIDTH+1){1'b0}}};
p_reg <= {{(DATAWIDTH+1){1'b0}},multiplicand,1'b0};
iter_cnt <= 0;
done <= 1'b0;
end
ADD : begin
case (p_reg[1:0])
2'b01 : sum_reg <= p_reg+a_reg; // + multiplier
2'b10 : sum_reg <= p_reg+s_reg; // - multiplier
2'b00,2'b11 : sum_reg <= p_reg; // nop
endcase
iter_cnt <= iter_cnt + 1;
end
SHIFT : begin
p_reg <= {sum_reg[2*DATAWIDTH+1],sum_reg[2*DATAWIDTH+1:1]}; // right shift
end
OUTPUT : begin
product <= p_reg[2*DATAWIDTH:1];
done <= 1'b1;
end
endcase
end
end
endmodule
testbench:
`timescale 1ns/1ps
// Basic exhaustive self checking test bench.
`define TEST_WIDTH 10
module booth_fsm_tb;
reg clk;
reg rstn;
reg en;
integer multiplier1;
integer multiplicand1;
reg [`TEST_WIDTH-1:0] multiplier;
reg [`TEST_WIDTH-1:0] multiplicand;
wire done;
//輸入 ：要定義有符号和符号，輸出：無要求
wire signed [2*`TEST_WIDTH-1:0] product;
wire signed [`TEST_WIDTH-1:0] m1_in;
wire signed [`TEST_WIDTH-1:0] m2_in;
reg signed [2*`TEST_WIDTH-1:0] product_ref;
reg [2*`TEST_WIDTH-1:0] product_ref_u;
assign m1_in = multiplier[`TEST_WIDTH-1:0];
assign m2_in = multiplicand[`TEST_WIDTH-1:0];
booth_fsm #(.DATAWIDTH(`TEST_WIDTH)) booth
(
.clk(clk),
.rstn(rstn),
.en(en),
.multiplier(multiplier),
.multiplicand(multiplicand),
.done (done),
.product(product)
);
always #1 clk = ~clk;
integer num_good;
integer i;
initial begin
clk = 1;
en = 0;
rstn = 1;
#2 rstn = 0; #2 rstn = 1;
num_good = 0;
multiplier=0;
multiplicand=0;
#8;
for(i=0;i<4;i=i+1) begin
en = 1;
multiplier=10'b10000_00000+i;
multiplicand=10'b00000_00010+i;
wait (done == 0);
wait (done == 1);
product_ref=m1_in*m2_in;
product_ref_u=m1_in*m2_in;
if (product_ref !== product)
$display("multiplier = %d multiplicand = %d proudct =%d",m1_in,m2_in,product);
@(posedge clk);
end
$display("sim done. num good = %d",num_good);
end
initial begin
$fsdbDumpvars();
$fsdbDumpMDA();
$dumpvars();
#1000 $finish;
end
endmodule
仿真波形：
