iT邦幫忙

2021 iThome 鐵人賽

DAY 26
1
Software Development

verilog or very lag系列 第 26

【Day26】快速乘法器的實作(Booth演算法)

為什麼要自己寫乘法器?

這篇會來教大家寫一個乘法器,那麼你可能會想:為什麼會需要乘法器呢?像我在 quartus 或 Vivado 裡打乘號也可以有乘法器用啊

那是因為在 EDA tool 裡面已經幫你在你使用乘號時合成出了他們已經寫好的乘法器了,那為什麼有這個不用還要另外設計呢?因為乘法器的種類有很多種,每一種也都有著不同的優缺點,所以通常會根據自己的需求來去設計一個最適合的乘法器,就例如 pipelined 乘法器,雖然把乘法拆成了數個步驟算,但是卻可以增加 throughput。

那麼我們先來看看 Booth 這個演算法


Booth演算法

例如:nbit X nbit(P = a X b):

  • Step1 : 宣告一個 2xn+1 位寬的暫存器 P。
  • Step2 : 一開始先將 b 載入至 P[n:1] 中(其餘 bit 皆為 "0")。
  • Step3 : 判斷最後兩bit
    • 2'b01 : P[2n:n+1] bit 加上 A
    • 2'b10 : P[2n:n+1] bit 減去 A
    • 2'b00 or 2'b11 : P 保持不變
  • Step4 : 右移 1 bit(算術位移)
  • Step5 : 重複 Step3 及 Step4 步驟 n 次
  • Step6 : 拿掉最後 1 bit 即是最後乘法結果

那麼第一步先來宣告狀態吧

定義狀態

/*---------parameter----------*/
localparam IDLE   = 2'd0;
localparam CAL    = 2'd1;
localparam SHIFT  = 2'd2;
localparam FINISH = 2'd3;

定義輸入/輸出
輸入:

  • clkSys
  • rst_n
  • en(狀態機致能)
  • a(被乘數)
  • b(乘數)

輸出:

  • product(乘法結果)
  • done(運算完成訊號)
module booth_multiplier(
  clkSys, 
  rst_n, 
  en, 
  a, 
  b, 
  product, 
  done
);
/*---------ports declarations----------*/
input         clkSys; 
input         rst_n; 
input         en; 
input  [31:0] a; 
input  [31:0] b;
output [63:0] product; 
output        done;
reg    [63:0] product; 
reg           done;

宣告變數

  • aReg(存放 a 以用來往後相加用)
  • sReg(存放 -a 以用來往後相減用)
  • pReg(product register)
  • fstate(狀態變數)
  • times(計數次數)

狀態邏輯

  • reset 後可以回到 IDLE
  • IDLE(收到 en 後往下一個狀態)
  • CAL(停留 1 clk 計算用,再往下個狀態)
  • SHIFT(判斷是否計算夠多次,達到次數後結束計算,否則回到 CAL 繼續計算、移位)
  • FINISH(輸出結果)
/*---------state----------*/
always@(posedge clkSys or negedge rst_n)begin
  if(!rst_n)fstate <= IDLE;
  else begin
    case(fstate)
      IDLE:begin
        if(en)fstate <= CAL;
        else  fstate <= IDLE;
      end
      CAL:begin
        fstate <= SHIFT;
      end
      SHIFT:begin
        if(times == 6'd32)fstate <= FINISH;
        else              fstate <= CAL;
      end
      FINISH: fstate <= IDLE;
      default:fstate <= IDLE;
    endcase
  end
end

輸出邏輯

  • IDLE
    • 將 a 存入 aReg
    • 將 a 補數存入 sReg
    • 將 b 載入至 pReg[n:1],其餘 bit 為 "0"
    • 計數器歸零
  • CAL
    • 判斷 pReg 尾兩 bit 來判斷 pReg[2n:n+1 ]是加 a 還是減 a
    • times 在此狀態加 1(因為判斷次數是否足夠是在下個狀態,因此如果在下個狀態內才加一會來不及抓到)
  • SHIFT
    • 將 pReg 算術右移 1 bit
  • FINISH(輸出結果
    • 將 pReg[2n:1] 輸出給 product

註:這裡我是寫 32bit X 32bit 的乘法器

/*---------output----------*/
always@(posedge clkSys or negedge rst_n)begin
  if(!rst_n)begin
    aReg    <= 32'd0;
    sReg    <= 32'd0;
    pReg    <= 65'd0;
    times   <= 6'd0;
    done    <= 1'b0;
    product <= 64'd0;
  end
  else begin
    case(fstate)
      IDLE:begin
        aReg  <= a;
        sReg  <= (~a + 32'd1);
        pReg  <= {32'd0, b, 1'b0};
        done  <= 1'b0;
        times <= 6'd0;
      end
      CAL:begin
        if(pReg[1:0] == 2'b01)     pReg <= {pReg[64:33]+aReg ,pReg[32:0]};//20 bit of MSB add aReg
        else if(pReg[1:0] == 2'b10)pReg <= {pReg[64:33]+sReg ,pReg[32:0]};//20 bit of MSB minus aReg
        else                       pReg <= pReg;
        times <= times + 6'd1;
      end
      SHIFT:begin
        pReg  <= {pReg[64],pReg[64:1]};
      end
      FINISH:begin
        done    <= 1'b1;
        product <= pReg[64:1];
      end
      default:begin
        aReg    <= 32'd0;
        sReg    <= 32'd0;
        pReg    <= 65'd0;
        times   <= 6'd0;
        done    <= 1'b0;
        product <= 64'd0;
      end
    endcase
  end
end
endmodule

TestBench

`timescale 10ns/10ns
module tb_booth();
reg                clk;
reg                rst_n;
reg  signed [31:0] a; 
reg  signed [31:0] b;
reg                en;
wire               done_sig;
wire signed [63:0] product;

booth_multiplier UUT(
  .clkSys(clk), 
  .rst_n(rst_n), 
  .en(en), 
  .a(a), 
  .b(b), 
  .product(product), 
  .done(done_sig)
);
initial begin
  clk = 0;
  rst_n = 0;
  a = 0;
  b = 0;
  en = 0;
  repeat(5)@(posedge clk)rst_n = 0;
  #10 rst_n = 1;
  test(32'd1, -32'd1);
  test(-32'd2, -32'd2);
  test(32'd3, -32'd3);
  test(32'd4, -32'd4);
  test(32'd5, -32'd5);
  test(32'd6, 32'd6);
  test(-32'd7, -32'd7);
  test(32'd8, -32'd8);
  test(32'd9, -32'd9);
  test(32'd10,-32'd10);
  
  test(32'd101, -32'd110);
  test(-32'd299, -32'd289);
  test(32'd330, -32'd3);
  test(32'd4986, -32'd4452);
  test(32'd5243, -32'd575);
  test(32'd2, 32'd67896);
  test(-32'd7, -32'd1334);
  test(32'd812, -32'd802);
  test(32'd0, -32'd9);
  test(32'd1000,-32'd123);
  
  #1000 $stop;
end
always #10 clk = ~clk;

task test;
  input  signed [19:0] in1;
  input  signed [19:0] in2;
  begin
    a = in1;
    b = in2;
    #40 en = 1;
    #20 en = 0;
    wait (done_sig == 1);
  end
endtask

endmodule

像這邊在寫 TestBench 時有很重複性動作時就可以寫成一個 task,可以大大提升效率,而 task 之間總要等電路計算完才給下一筆測試資料嘛,所以在這邊也有用到 wait 語法,讓每一個 task 都收到模組的 done 時才繼續往下。

Wave

可以看到計算結果都完全正確,那麼今天的教學就到這邊~


上一篇
【Day25】One-Wire protocol
下一篇
【Day27】線性收斂除法器實作
系列文
verilog or very lag30

尚未有邦友留言

立即登入留言