布斯算法介紹

Booth 的算法檢查有符號二的補(bǔ)碼表示中 'N'位乘數(shù) Y 的相鄰位對，包括低于最低有效位 y?1 = 0 的隱式位。對于每個位 yi，對于從 0 到 N ? 1 的 i，考慮位 yi 和 yi?1。當(dāng)這兩個位相等時，乘積累加器P保持不變。其中 yi = 0 且 yi?1 = 1，乘以 2i 添加到 P;其中 yi = 1 且 yi?1 = 0，則從 P 中減去乘以 2i。P 的最終值為有符號結(jié)果。

未指定乘數(shù)和乘積的表示形式;通常，這些也都在二的補(bǔ)碼表示中，就像乘數(shù)一樣，但是任何支持加法和減法的數(shù)字系統(tǒng)也可以工作。如此處所述，步驟的順序尚未確定。通常，它從LSB到MSB，從i = 0開始;然后乘以2i通常被P累加器在步長之間向右的增量移位所取代;低位可以移出，然后可以在P的最高N位上進(jìn)行后續(xù)的加法和減法。

該算法通常被描述為將乘數(shù)中 1 的字符串轉(zhuǎn)換為字符串末端的高階 +1 和低階 ?1。當(dāng)字符串通過 MSB 運(yùn)行時，沒有高階 +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，請轉(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 是否為零。如果是，請轉(zhuǎn)到下一步。否則轉(zhuǎn)到步驟 2。

第7步： 停止計(jì)算，輸出計(jì)算結(jié)果。

計(jì)算流程圖

以下是布斯計(jì)算的流程圖，從圖中可以清楚的看出計(jì)算的過程，簡單的來說就是判定乘數(shù)的最低位和次低位，如果兩位相同則直接執(zhí)行移位操作，如果兩者不同，如為“10”則將原始值減去被乘數(shù)，如為“01”則將原始值加上被乘數(shù)。

舉個栗子

下面就以被乘數(shù)為6，乘數(shù)為-4為例，做一個計(jì)算過程的舉例。

1. 將所有寄存器初始化，累加器A初始化為0，乘數(shù)加載寄存，最低位移出位設(shè)定為0。
2. 判定最低位和移出位為“00”，不進(jìn)行加減操作，將結(jié)果結(jié)果值右移一位。
3. 判定最低位和移出位為“00”，不進(jìn)行加減操作，將結(jié)果結(jié)果值右移一位。
4. 判定最低位和移出位為“10”，對累加器減去被乘數(shù)，并將結(jié)果結(jié)果值右移一位，注意此時累加器A為負(fù)數(shù)。
5. 判定最低位和移出位為“10”，不進(jìn)行加減操作，將結(jié)果結(jié)果值右移一位，此時累加器為負(fù)數(shù)，因此右移最高位補(bǔ)1。
6. 判定最低位和移出位為“10”，不進(jìn)行加減操作，將結(jié)果結(jié)果值右移一位，此時累加器為負(fù)數(shù)，因此右移最高位補(bǔ)1。
7. 計(jì)數(shù)器為0表示計(jì)算完成，停止計(jì)算并輸出計(jì)算結(jié)果值。

Verilog 實(shí)現(xiàn)

設(shè)計(jì)思想

總的來說和上面提到的計(jì)算步驟是一致的，利用三段狀態(tài)機(jī)實(shí)現(xiàn)，分別為空閑狀態(tài)、計(jì)算狀態(tài)和完成狀態(tài)，其中空閑狀態(tài)等待開始計(jì)算信號的到來，計(jì)算狀態(tài)完成布斯計(jì)算步驟，完成狀態(tài)輸出結(jié)果數(shù)據(jù)以及同步的有效標(biā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ù)和信號申明                                                              */
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
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ù)信號  
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*三段狀態(tài)機(jī)                                                                  */
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
//狀態(tài)機(jī)第一段，狀態(tài)初始化，時序邏輯非阻塞賦值
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é)果輸出，時序邏輯非阻塞賦值
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)行有符號的乘法，6和-4、7和-5、7和5，可以看到仿真波形中，正確的得到了計(jì)算結(jié)果，并且有效標(biāo)志信號也同步輸出。

驗(yàn)證成功！