【Day27】线性收敛除法器实作

在加减乘除四个基本运算中，其中除法最为困难及复杂，因此除法也是最耗时的运算。

对於一个被除数为 N，除数为 D，商为 Q，余数 R 的除法运算中，我们可以得到这样的算式：

N/D = Q..R，其中|R|<D

当然也可以看成是：

N = D x Q + R

除法运算与乘法很大的不同是：乘法中部分的乘积都可以并行算出来，而除法中商的每一位则要用一种"尝试错误"的方法得出，而大多数的微处理器都是以 N = D x Q + R 的方式作为乘法的逆运算处理，因此假定分子是一个乘法的结果，所以会把分母及商的位宽扩充为两倍当作是分子的位宽，但这样做的结果则会导致必须使用很没有效率的方式来确定我们的商是否会在有效的范围内。

因此我们来做一个有效的假定：
我们假设 N >= Q 以及 |R| < D
也就是我们假定商和分子以及分母和余数的位宽互相相等，如此一来我们就不用再检查商的范围是否有效了。

而会说线性收敛是因为这个除法算法所花的 cycle 数与被除数的 bit 数是一样的，是呈线性关系的。

实作方法

先来假设商（q_out）和分子（dividend）的位宽是 8 bit，而分母（divisor）和余数（r_out）是 6 bit。

接着我们需要两个位宽和的两个变数，一个有号（r）、一个无号（d）。

一开始我们先把 divisor 左移（8-1）次载入到d（如果移 8 次会超出范围，要少一次），而直接将 dividend 存入到 r。

接着将 r 减去 d，如果为负号，代表不够减，我们在商的部分就左移入 "0" 并且将 r 还原为刚刚的值（因为不够减，要保持刚刚的值然後看下一个 bit 够不够减），如果减完为正的代表够减，此时则将商左移入 "1"，而 r 不需要还原，最後要把 d 除以 2（右移一次），再继续接着刚刚的动作连续8次。

最後将 q 及 r 输出则是我们最後的商跟余数了！

宣告状态

/*-------localparam-------*/
localparam IDLE    = 2'd0;
localparam SUB     = 2'd1;
localparam RESTORE = 2'd2;
localparam FINISH  = 2'd3;

宣告输入输出

module divRes(
  clkSys,
  en,
  rst_n,
  dividend,
  divisor,
  r_out,
  q_out,
  done
);
/*-------ports declarations-------*/
input        clkSys;
input        en;
input        rst_n;
input  [7:0] dividend;
input  [5:0] divisor;
output [5:0] r_out;
output [7:0] q_out;
output       done;
reg    [5:0] r_out;
reg    [7:0] q_out;
reg          done;

宣告所需变数

/*-------variables-------*/
reg    [1:0] fstate;
reg    [3:0] count;
reg    [7:0] q;
reg   [13:0] d;
reg signed [13:0] r;

状态逻辑

/*-------fstate state-------*/
always@(posedge clkSys or negedge rst_n)begin
  if(!rst_n)fstate <= IDLE;
  else begin
    case(fstate)
      IDLE:begin
        if(en)fstate <= SUB;
        else  fstate <= IDLE;
      end
      SUB:fstate <= RESTORE;
      RESTORE:begin
        if(count == 4'd8)fstate <= FINISH;
        else             fstate <= SUB;
      end
      FINISH:fstate <= IDLE;
      default:fstate <= IDLE;
    endcase
  end
end

输出逻辑

/*-------fstate output-------*/
always@(posedge clkSys or negedge rst_n)begin
  if(!rst_n)begin
    count <= 4'd0;
    r_out <= 6'd0; 
    q_out <= 8'd0;
    q     <= 8'd0;
    r     <= 14'd0;
    d     <= 14'd0;
    done  <= 1'b0;
  end
  else begin
    case(fstate)
      IDLE:begin
        count <= 4'd0;
        q     <= 8'd0;
        d     <= divisor << 7;//load divisor
        r     <= dividend;//Remainder = dividend
        done  <= 1'b0; 
      end
      SUB:begin
        r     <= r - d;
        count <= count + 4'd1;
      end
      RESTORE:begin
        if(r<0)begin
          r <= r + d;
          q <= q << 1;//left shift and LSB = 0
        end
        else begin
          r <= r;
          q <= {q[6:0], 1'b1};//left shift and LSB = 1
        end
        d <= d >> 1;
      end
      FINISH:begin
        q_out <= q;
        r_out <= r[5:0];
        done  <= 1'b1; 
      end
      default:begin
        count <= 4'd0;
        r_out <= 6'd0; 
        q_out <= 8'd0;
        q     <= 8'd0;
        r     <= 14'd0;
        d     <= 14'd0;
        done  <= 1'b0; 
      end
    endcase
  end
end
endmodule

TestBench

`timescale 1ns/1ns
module tb_divRes();

reg        clkSys;
reg        en;
reg        rst_n;
reg  [7:0] dividend;
reg  [5:0] divisor;
wire [5:0] r_out;
wire [7:0] q_out;
wire       done;

divRes UUT(
  .clkSys(clkSys),
  .en(en),
  .rst_n(rst_n),
  .dividend(dividend),
  .divisor(divisor),
  .r_out(r_out),
  .q_out(q_out),
  .done(done)
);

initial begin
  clkSys = 0;
  rst_n  = 0;
  repeat(2)@(posedge clkSys)rst_n = 0;
  rst_n = 1;
  test(234,50);
  test(196,20);
  test(97 ,15);
  test(200,11);
  test(19 ,50);
  test(192 ,1);
  test(64 ,2);
  #1000 $stop;
end

always #10 clkSys = ~clkSys;

task test;
input [7:0]a;
input [5:0]b;
  begin
    dividend = a;
    divisor  = b;
    #40 en = 1;
    #20 en = 0;

    wait (done == 1);
  end
endtask

endmodule

Wave

商与余的结果也都有符合预期，那麽今天的教学也到这边喽~