2014年6月11日 星期三

Booth 布斯演算法 (有號數) ---適用於DE2-70

布斯演算法(Booth's Algorithm)的特性,在於比起只用加法和位移的運算,還可以再運用減法來得到乘積而他也剛好可以用在二補數有號數的運算方面。

原理:  布斯演算法檢查乘數的位元,再依照檢查的結果做相對應的動作,它使用一種可執行加法與減法運算的 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
*/

沒有留言:

張貼留言