布斯算法介紹
Booth 的算法檢查有符號(hào)二的補(bǔ)碼表示中 'N'位乘數(shù) Y 的相鄰位對(duì),包括低于最低有效位 y?1 = 0 的隱式位。對(duì)于每個(gè)位 yi,對(duì)于從 0 到 N ? 1 的 i,考慮位 yi 和 yi?1。當(dāng)這兩個(gè)位相等時(shí),乘積累加器P保持不變。其中 yi = 0 且 yi?1 = 1,乘以 2i 添加到 P;其中 yi = 1 且 yi?1 = 0,則從 P 中減去乘以 2i。P 的最終值為有符號(hào)結(jié)果。
未指定乘數(shù)和乘積的表示形式;通常,這些也都在二的補(bǔ)碼表示中,就像乘數(shù)一樣,但是任何支持加法和減法的數(shù)字系統(tǒng)也可以工作。如此處所述,步驟的順序尚未確定。通常,它從LSB到MSB,從i = 0開始;然后乘以2i通常被P累加器在步長(zhǎng)之間向右的增量移位所取代;低位可以移出,然后可以在P的最高N位上進(jìn)行后續(xù)的加法和減法。
該算法通常被描述為將乘數(shù)中 1 的字符串轉(zhuǎn)換為字符串末端的高階 +1 和低階 ?1。當(dāng)字符串通過(guò) MSB 運(yùn)行時(shí),沒(méi)有高階 +1,并且凈效應(yīng)被解釋為相應(yīng)值的負(fù)數(shù)。
計(jì)算步驟
使用的寄存器:A,M,Q,Qres(Qres是Q右移后的殘余位),n(計(jì)數(shù)器)
第1步: 加載寄存器的初始值。
A = 0(累加器),Qres = 0,M = 乘法,Q = 乘法器,n是等于乘法器位數(shù)的計(jì)數(shù)值。
第2步: 檢查 {Q0,Qres} 的值。如果為 00 或 11,請(qǐng)轉(zhuǎn)到步驟 5。如果為01,轉(zhuǎn)到步驟3。如果為 10,轉(zhuǎn)到步驟 4。
第3步: 執(zhí)行 A = A + M,轉(zhuǎn)到步驟 5。
第4步: 執(zhí)行 A = A - M。
第5步: 執(zhí)行 {A,Q,Qres} 的算術(shù)位移和遞減計(jì)數(shù)。
第6步: 檢查計(jì)數(shù)器值 n 是否為零。如果是,請(qǐng)轉(zhuǎn)到下一步。否則轉(zhuǎn)到步驟 2。
第7步: 停止計(jì)算,輸出計(jì)算結(jié)果。
計(jì)算流程圖
以下是布斯計(jì)算的流程圖,從圖中可以清楚的看出計(jì)算的過(guò)程,簡(jiǎn)單的來(lái)說(shuō)就是判定乘數(shù)的最低位和次低位,如果兩位相同則直接執(zhí)行移位操作,如果兩者不同,如為“10”則將原始值減去被乘數(shù),如為“01”則將原始值加上被乘數(shù)。
舉個(gè)栗子
下面就以被乘數(shù)為6,乘數(shù)為-4為例,做一個(gè)計(jì)算過(guò)程的舉例。
- 將所有寄存器初始化,累加器A初始化為0,乘數(shù)加載寄存,最低位移出位設(shè)定為0。
- 判定最低位和移出位為“00”,不進(jìn)行加減操作,將結(jié)果結(jié)果值右移一位。
- 判定最低位和移出位為“00”,不進(jìn)行加減操作,將結(jié)果結(jié)果值右移一位。
- 判定最低位和移出位為“10”,對(duì)累加器減去被乘數(shù),并將結(jié)果結(jié)果值右移一位,注意此時(shí)累加器A為負(fù)數(shù)。
- 判定最低位和移出位為“10”,不進(jìn)行加減操作,將結(jié)果結(jié)果值右移一位,此時(shí)累加器為負(fù)數(shù),因此右移最高位補(bǔ)1。
- 判定最低位和移出位為“10”,不進(jìn)行加減操作,將結(jié)果結(jié)果值右移一位,此時(shí)累加器為負(fù)數(shù),因此右移最高位補(bǔ)1。
- 計(jì)數(shù)器為0表示計(jì)算完成,停止計(jì)算并輸出計(jì)算結(jié)果值。
Verilog 實(shí)現(xiàn)
設(shè)計(jì)思想
總的來(lái)說(shuō)和上面提到的計(jì)算步驟是一致的,利用三段狀態(tài)機(jī)實(shí)現(xiàn),分別為空閑狀態(tài)、計(jì)算狀態(tài)和完成狀態(tài),其中空閑狀態(tài)等待開始計(jì)算信號(hào)的到來(lái),計(jì)算狀態(tài)完成布斯計(jì)算步驟,完成狀態(tài)輸出結(jié)果數(shù)據(jù)以及同步的有效標(biāo)志信號(hào)。
Verilog 代碼
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*Engineer : Linest-5
/*File : booth_multiple.v
/*Create : 2022-08-27 16:40:34
/*Revise : 2022-08-27 16:40:34
/*Module Name : booth_multiple
/*Description : 基于布斯算法的乘法器設(shè)計(jì)
/*Editor : sublime text3, tab size (4)
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
modulebooth_multiple(
inputclk,
inputrst,
inputstart,
inputsigned [3:0] X,
inputsigned [3:0] Y,
outputreg signed [7:0] Z,
outputvalid
);
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*參數(shù)和信號(hào)申明 */
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
parameterIDLE = 3'b001;
parameterCACULATE = 3'b010;
parameterFINISH = 3'b100;
reg[2:0] state;
reg[2:0] next_state;
reg[1:0] q_reg; //右移最后兩位寄存
reg[2:0] cnt; //右移次數(shù)計(jì)數(shù)信號(hào)
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*三段狀態(tài)機(jī) */
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
//狀態(tài)機(jī)第一段,狀態(tài)初始化,時(shí)序邏輯非阻塞賦值
always @(posedge clk or posedge rst) begin
if (rst) begin
state <= IDLE;
end
else begin
state <= next_state;
end
end
//狀態(tài)機(jī)第二段,狀態(tài)跳轉(zhuǎn),組合邏輯阻塞賦值
always @(*) begin
next_state = state;
case(state)
IDLE: begin
if (start) begin
next_state = CACULATE;
end
else begin
next_state = IDLE;
end
end
CACULATE: begin
if (cnt == 'd3) begin
next_state = FINISH;
end
else begin
next_state = CACULATE;
end
end
FINISH: begin
next_state = IDLE;
end
endcase
end
//狀態(tài)機(jī)第三段,結(jié)果輸出,時(shí)序邏輯非阻塞賦值
always @(posedge clk or posedge rst) begin
if (rst) begin
cnt <= 'd0;
q_reg <= 'd0;
Z <= 'd0;
end
else begin
case(state)
IDLE: begin
cnt <= 'd0;
q_reg <= {Y[cnt],1'b0};
Z <= {4'b0000,Y};
end
CACULATE: begin
cnt <= cnt + 'd1;
q_reg <= {Y[cnt+1],Y[cnt]};
case(q_reg)
2'b00,2'b11: begin
Z <= $signed(Z) >> >1;
end
2'b10: begin
Z <= $signed({Z[7:4]-X,Z[3:0]}) >> >1;
end
2'b01: begin
Z <= $signed({Z[7:4]+X,Z[3:0]}) >> >1;
end
endcase
end
FINISH: begin
cnt <= 'd0;
q_reg <= 'd0;
Z <= Z;
end
endcase
end
end
assign valid = (state==FINISH);
endmodule
TestBench 代碼
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/* Engineer : Linest-5
/* File : tb_booth_multiple.v
/* Create : 2022-08-27 19:22:46
/* Revise : 2022-08-27 20:21:49
/* Module Name : tb_booth_multiple
/* Description : 基于布斯算法的乘法器仿真模塊
/* Editor : sublime text3, tab size (4)
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
`timescale 1ns/1ns
module tb_booth_multiple();
reg clk;
reg rst;
reg start;
reg signed [3:0] X;
reg signed [3:0] Y;
wire signed [7:0] Z;
wire valid;
initial begin
clk = 'd0;
rst = 'd1;
#20
rst = 'd0;
end
always #10 clk = ~clk;
initial begin
#20
X = 6;
Y = -4;
start = 'd0;
#50
start = 'd1;
#20
start = 'd0;
#200
X = 7;
Y = -5;
start = 'd1;
#20
start = 'd0;
#200
X = 7;
Y = 5;
start = 'd1;
#20
start = 'd0;
end
booth_multiple inst_booth_multiple (
.clk (clk),
.rst (rst),
.start (start),
.X (X),
.Y (Y),
.Z (Z),
.valid (valid)
);
endmodule
仿真波形
分別進(jìn)行有符號(hào)的乘法,6和-4、7和-5、7和5,可以看到仿真波形中,正確的得到了計(jì)算結(jié)果,并且有效標(biāo)志信號(hào)也同步輸出。
驗(yàn)證成功!
-
寄存器
+關(guān)注
關(guān)注
31文章
5253瀏覽量
119201 -
Verilog
+關(guān)注
關(guān)注
28文章
1333瀏覽量
109713 -
乘法器
+關(guān)注
關(guān)注
8文章
204瀏覽量
36850 -
累加器
+關(guān)注
關(guān)注
0文章
50瀏覽量
9414 -
MSB
+關(guān)注
關(guān)注
0文章
13瀏覽量
8230
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論