原理： 布斯演算法檢查乘數的位元，再依照檢查的結果做相對應的動作，它使用一種可執行加法與減法運算的 ALU，以 0100*0110 為例，當計算中第一次遇到 1 時，我們可以把乘數中一連串的 1 換成減法運算，當遇到最後一個 1 後面的 0 時，再加上被乘數，如下圖：
布斯演算法的精髓在於它對數字中間部份的1字串進行頭、中、後三段的分段動作。由於0字串無需進行運算所以不必去理會。如果只看兩個位元，那麼我們就可以試著去瞭解這個意義:
以往的舊演算法一次只看乘數的一個位元，然後就決定是否要把被乘 數加進來。但布斯演算法一次看乘數的兩個位元，所以，依據這兩個 位元的值，演算法的新的第一個步驟就有四種狀況出現。假設這兩個 位元稱為＂現行位元＂和它的＂右邊位元＂ (此亦為前一步驟的現行位 元＂)。第二個步驟還是將乘積移位的動作。
所以演算法如下：
依現行位元及其右方位元，分別執行下列的動作：
00：此為 0 字串的中間部份，所以不執行運算。
01：此為 1 字串的結尾，所以將被乘數加到乘積的左半部。
10：此為 1 字串的開頭，所以將乘積的左半部減去被乘數。
11：此為 1 字串的中間部份，所以不執行運算。
做完一步後將乘積暫存器右移 1 位元。
於是我們以圖的乘數和被乘數為例來做運算，首先是視最低有效位元的右邊有一個＂虛構＂的位元，其值為0。
另一個必要條件是:因為我們所處理的數是有號數，所以在將乘積暫存器往右移位的過程中必須保留中間結果的符號，而實際的解決方法就是當乘積移位時，符號也跟著向右延伸。所以，第二次循環的第 二個步驟就是將1110 00110 two 轉換成1111 00011 two，而非原本之
0111 0001 1 two。這種移位就稱為「算數右移」 (arithmetic right shift)， 有別於邏輯右移運算。
另為我們還可以用(ai-1﹣ai)來表示它，其值各代表如下的
動作:
0: 無運算
+1: 加b
-1: 減b
由於被乘數相對於乘積暫存器左移的運算可以想像成是它乘上一個2 的冪次，所
以布斯演算法可以寫為:
(a-1﹣a0) ×b×2^0
＋(a-1﹣a0) ×b×2^1
＋(a-1﹣a0) ×b×2^2
…………
＋(a-1﹣a0) ×b×2^30
＋(a-1﹣a0) ×b×2^31
利用下式來簡化以上的總合;
(-ai× 2^i) ＋ (-ai× 2^i) ＝(-ai+2ai)×2^i＝ (2ai﹣ai) ×2^i ＝ai×2^I
還有，a-1=0，並把b 提出式子外面:
b×((a31×-2^31)+ (a30×-2^30) + (a29×-2^29) + ……..+( a1×-2^1) +
(a0×-2^0))
右邊括號內的公式恰好就是的2 補數表示法。所以，總和可以進一步
簡化為:
b×a
因此，布斯演算法事實上是執行a 和b 的相乘運算的。
module Booth_method( //適用於DE2-70 的程式
input [17:0]SW,
input [3:0] KEY,
input CLOCK_50,
output [17:0] LEDR,
output [8:0] LEDG,
output [6:0] HEX0,
output [6:0] HEX1,
output [6:0] HEX2,
output [6:0] HEX3,
output [6:0] HEX4,
output [6:0] HEX5,
output [6:0] HEX6,
output [6:0] HEX7
);
//assign HEX0=7'b111_1111; //off 7-segment Display
//assign HEX1=7'b111_1111;
//assign HEX2=7'b111_1111;
//assign HEX3=7'b111_1111;
//assign HEX4=7'b111_1111;
assign HEX5=7'b111_1111;
assign HEX6=7'b111_1111;
assign HEX7=7'b111_1111;
wire [15:0] prod ;
wire [3:0]ONES,TENS,HUNDREDS,THOUSAND,TEN_THOU;
assign LEDR[15:0]=prod;
/*booth( iClk, // input clock
iReset_b, // reset signal
iGo, // indicates inputs are ready
oDone, // indicates that the result is ready
iMer, // 8-bit multiplier
iMand, // 8-bit multiplicand
oProduct // 16-bit product
); */
booth(CLOCK_50,KEY[0],1'b1,LEDR[17],SW[15:8],SW[7:0],prod);
binary_to_BCD u0(prod,ONES,TENS,HUNDREDS,THOUSAND,TEN_THOU);
hex_7seg u1(ONES,HEX0);
hex_7seg u2(TENS,HEX1);
hex_7seg u3(HUNDREDS,HEX2);
hex_7seg u4(THOUSAND,HEX3);
hex_7seg u5(TEN_THOU,HEX4);
endmodule
module booth(
iClk, // input clock
iReset_b, // reset signal
iGo, // indicates inputs are ready
oDone, // indicates that the result is ready
iMer, // 8-bit multiplier
iMand, // 8-bit multiplicand
oProduct // 16-bit product
);
input iClk,iReset_b,iGo;
input [7:0] iMer,iMand;
output oDone;
output [15:0] oProduct;
// State names
parameter WaitForGoState = 0,
InitState = 1,
AddShiftState = 2,
DoneState =3;
reg [1:0] PresentState, NextState;
reg [1:0] NumShifts;
reg [18:0] Product;
reg [9:0] Sum;
//-----------------------------------------------------------------------------
// This is the main FSM controller
//-----------------------------------------------------------------------------
always @(iGo,PresentState,NumShifts)
begin : Controller
case (PresentState)
WaitForGoState:
if (iGo)
NextState = InitState;
else
NextState = WaitForGoState;
InitState:
NextState = AddShiftState;
AddShiftState:
if (NumShifts == 2'b00)
NextState = DoneState;
else
NextState = AddShiftState;
DoneState:
NextState = DoneState;
default:
NextState = InitState;
endcase // PresentState
end // Controller;
always @(posedge iClk or negedge iReset_b)
begin // StateRegs
if (!iReset_b)
PresentState <= WaitForGoState;
else
PresentState <= NextState;
end // StateRegs;
//-----------------------------------------------------------------------------
// This does the addition of the appropriate version of the multiplicand
//-----------------------------------------------------------------------------
reg [9:0] Mand1,Mand2;
always @(Product,iMand)
begin // Adder
Mand1 = {iMand[7],iMand[7],iMand}; // sign extend to 10 bits
Mand2 = Mand1<<1;
case (Product[2:0])
3'b000:
Sum = Product[18:9];
3'b001:
Sum = Product[18:9] + Mand1;
3'b010:
Sum = Product[18:9] + Mand1;
3'b011:
Sum = Product[18:9] + Mand2;
3'b100:
Sum = Product[18:9] - Mand2;
3'b101:
Sum = Product[18:9] - Mand1;
3'b110:
Sum = Product[18:9] - Mand1;
default:
Sum = Product[18:9];
endcase // Product[2:0]
end // Adder
//-----------------------------------------------------------------------------
// This is the Product register and counter
//-----------------------------------------------------------------------------
always @(posedge iClk)
begin // ProdReg
case (PresentState)
WaitForGoState:
;
InitState:
begin
Product[18:9] <= 10'b0000000000;
Product[8:1] <= iMer;
Product[0] <= 1'b0;
NumShifts <= 2'b11;
end
AddShiftState:
begin
//---------------------------------------------------------
// This takes the Sum, sign extends it to 12 bits and
// puts that into the top part of the Product register,
// effectively shifting it at the same time. The bottom
// part of the register is loaded with a shifted value of
// the previous contents in that part.
// The counter is also updated here.
//---------------------------------------------------------
Product[18:7] <= {Sum[9],Sum[9],Sum};
Product[6:0] <= Product[8:2];
NumShifts <= NumShifts - 2'b01;
end
DoneState:
;
endcase // PresentState
end //ProdReg;
//-----------------------------------------------------------------------------
// The output product and done signal.
//-----------------------------------------------------------------------------
assign oProduct = Product[16:1];
assign oDone = (PresentState == DoneState) ? 1'b1:1'b0;
endmodule // of booth
module binary_to_BCD(A,ONES,TENS,HUNDREDS,THOUSAND,TEN_THOU);
input [15:0] A;
output reg [3:0] ONES, TENS;
output reg [3:0] HUNDREDS,THOUSAND,TEN_THOU;
integer i;
always@(A)
begin
TEN_THOU=4'd0;
THOUSAND=4'd0;
HUNDREDS=4'd0;
TENS=4'd0;
ONES=4'd0;
for(i=15;i>=0;i=i-1)
begin
//Add 3 to columns >=5
if (TEN_THOU>=5)
TEN_THOU=TEN_THOU+3;
if (THOUSAND >=5)
THOUSAND=THOUSAND+3;
if (HUNDREDS >=5)
HUNDREDS=HUNDREDS+3;
if (TENS >=5)
TENS=TENS+3;
if (ONES >=5)
ONES=ONES+3;
//Shift left one
TEN_THOU=TEN_THOU<<1;
TEN_THOU[0]=THOUSAND[3];
THOUSAND=THOUSAND<<1;
THOUSAND[0]=HUNDREDS[3];
HUNDREDS=HUNDREDS<<1;
HUNDREDS[0]=TENS[3];
TENS=TENS<<1;
TENS[0]=ONES[3];
ONES=ONES<<1;
ONES[0]=A[i];
end
end
endmodule
module hex_7seg(hex_digit,seg);
input [3:0] hex_digit;
output [6:0] seg;
reg [6:0] seg;
// seg = {g,f,e,d,c,b,a};
// 0 is on and 1 is off
always @ (hex_digit)
case (hex_digit)
4'h0: seg = 7'b1000000;
4'h1: seg = 7'b1111001; // ---a----
4'h2: seg = 7'b0100100; // | |
4'h3: seg = 7'b0110000; // f b
4'h4: seg = 7'b0011001; // | |
4'h5: seg = 7'b0010010; // ---g----
4'h6: seg = 7'b0000010; // | |
4'h7: seg = 7'b1111000; // e c
4'h8: seg = 7'b0000000; // | |
4'h9: seg = 7'b0011000; // ---d----
4'ha: seg = 7'b0001000;
4'hb: seg = 7'b0000011;
4'hc: seg = 7'b1000110;
4'hd: seg = 7'b0100001;
4'he: seg = 7'b0000110;
4'hf: seg = 7'b0001110;
endcase
endmodule
module booth(
iClk, // input clock
iReset_b, // reset signal
iGo, // indicates inputs are ready
oDone, // indicates that the result is ready
iMer, // 8-bit multiplier
iMand, // 8-bit multiplicand
oProduct // 16-bit product
);
input iClk,iReset_b,iGo;
input [7:0] iMer,iMand;
output oDone;
output [15:0] oProduct;
// State names
parameter WaitForGoState = 0,
InitState = 1,
AddShiftState = 2,
DoneState =3;
reg [1:0] PresentState, NextState;
reg [1:0] NumShifts;
reg [18:0] Product;
reg [9:0] Sum;
//-----------------------------------------------------------------------------
// This is the main FSM controller
//-----------------------------------------------------------------------------
always @(iGo,PresentState,NumShifts)
begin : Controller
case (PresentState)
WaitForGoState:
if (iGo)
NextState = InitState;
else
NextState = WaitForGoState;
InitState:
NextState = AddShiftState;
AddShiftState:
if (NumShifts == 2'b00)
NextState = DoneState;
else
NextState = AddShiftState;
DoneState:
NextState = DoneState;
default:
NextState = InitState;
endcase // PresentState
end // Controller;
always @(posedge iClk or negedge iReset_b)
begin // StateRegs
if (!iReset_b)
PresentState <= WaitForGoState;
else
PresentState <= NextState;
end // StateRegs;
//-----------------------------------------------------------------------------
// This does the addition of the appropriate version of the multiplicand
//-----------------------------------------------------------------------------
reg [9:0] Mand1,Mand2;
always @(Product,iMand)
begin // Adder
Mand1 = {iMand[7],iMand[7],iMand}; // sign extend to 10 bits
Mand2 = Mand1<<1;
case (Product[2:0])
3'b000:
Sum = Product[18:9];
3'b001:
Sum = Product[18:9] + Mand1;
3'b010:
Sum = Product[18:9] + Mand1;
3'b011:
Sum = Product[18:9] + Mand2;
3'b100:
Sum = Product[18:9] - Mand2;
3'b101:
Sum = Product[18:9] - Mand1;
3'b110:
Sum = Product[18:9] - Mand1;
default:
Sum = Product[18:9];
endcase // Product[2:0]
end // Adder
//-----------------------------------------------------------------------------
// This is the Product register and counter
//-----------------------------------------------------------------------------
always @(posedge iClk)
begin // ProdReg
case (PresentState)
WaitForGoState:
;
InitState:
begin
Product[18:9] <= 10'b0000000000;
Product[8:1] <= iMer;
Product[0] <= 1'b0;
NumShifts <= 2'b11;
end
AddShiftState:
begin
//---------------------------------------------------------
// This takes the Sum, sign extends it to 12 bits and
// puts that into the top part of the Product register,
// effectively shifting it at the same time. The bottom
// part of the register is loaded with a shifted value of
// the previous contents in that part.
// The counter is also updated here.
//---------------------------------------------------------
Product[18:7] <= {Sum[9],Sum[9],Sum};
Product[6:0] <= Product[8:2];
NumShifts <= NumShifts - 2'b01;
end
DoneState:
;
endcase // PresentState
end //ProdReg;
//-----------------------------------------------------------------------------
// The output product and done signal.
//-----------------------------------------------------------------------------
assign oProduct = Product[16:1];
assign oDone = (PresentState == DoneState) ? 1'b1:1'b0;
endmodule // of booth
*/
沒有留言:
張貼留言