【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