原创 小程序大道理---除法器

除法器

是四则运算中最难搞定的，也是在FPGA/ASIC 中最难实现的运算，消耗时间最多的运算，同时消耗资源也是最多的。

以无符号除法为例

最常用的算法是把“手动计算”方法变换到二进制计算：

（是不是感觉很原始呢，没办法，这就是除法的特殊性）

过程：首先调整分母并把分子加载到余数寄存器中，然后从余数中减去调整的分母并将结果存储在余数寄存器中。如果新的余数为正，我们将商的LSB设置为1，否则置0，而且还需要通过加上分的母来还原从前余数值。最后，还要为下一步重新调整商和分母。重新计算从前的余数，这就是为什么叫“还原除法”的原因。（注：摘自《数字信号处理的FPGA实现》）

程序如下：

// Function ：   Nominator = Quotient * Denumerator + Remainder

module div_res(clk, n_in, d_in, r_out, q_out);

  input         clk;
  input  [7:0] n_in;
  input  [5:0] d_in;
  output [5:0] r_out;
  reg    [5:0] r_out;
  output [7:0] q_out;
  reg    [7:0] q_out;

  always @(posedge clk) //-> Divider in behavioral style
  begin : States
    parameter s0=0, s1=1, s2=2, s3=3;
    reg [3:0] count;
    reg [1:0] state;
    reg  [13:0] r, d;        // Double bit width
    reg  [7:0] q;
    case (state)
      s0 : begin         // Initialization step
        state <= s1;
        count = 0;
        q <= 0;           // Reset quotient register
        d <= d_in << 7;   // Load aligned denumerator
        r <= {6'B0, n_in}; // Remainder = nominator
      end                                          
      s1 : begin         // Processing step
        r <= r - d;      // Subtract denumerator
        state <= s2;
      end
      s2 : begin          // Restoring step
        if (r[13] == 1) begin  // Check r < 0
          r <= r + d;     // Restore previous remainder
          q <= q << 1;     // LSB = 0 and SLL
          end
        else
          q <= (q << 1) + 1; // LSB = 1 and SLL
        count = count + 1;
        d <= d >> 1;

        if (count == 8)   // Division ready ?
          state <= s3;
        else            
          state <= s1;
      end
      s3 : begin       // Output of result
        q_out <= q[7:0];
        r_out <= r[5:0];
        state <= s0;   // Start next division
      end
    endcase 
  end

endmodule

上面的过程是通过右移“除数”实现的，通过改进，可以左移“被除数” ：

（转自 http://blog.csdn.net/rill_zhen/article/details/7961937）

算法推导：

假设4bit的两数相除 a/b，商和余数最多只有4位 （假设1101/0010也就是13除以2得6余1）

我们先自己做二进制除法，则首先看a的MSB，若比除数小则看前两位，大则减除数，然后看余数，以此类推直到最后看到LSB；而上述算法道理一 样，a左移进前四位目的就在于从a本身的MSB开始看起，移4次则是看到LSB为止，期间若比除数大，则减去除数，注意减完以后正是此时所剩的余数。而商 呢则加到了这个数的末尾，因为只要比除数大，商就是1，而商0则是直接左移了，因为会自动补0。这里比较巧因为商可以随此时的a继续左移，然后新的商会继 续加到末尾。经过比对会发现移4位后左右两边分别就是余数和商。

经过整理后，如下实现过程

基于减法的除法器的算法：
        对于32的无符号除法，被除数a除以除数b，他们的商和余数一定不会超过32位。首先将a转换成高32位为0，低32位为a的temp_a。把b转换成高 32位为b，低32位为0的temp_b。在每个周期开始时，先将temp_a左移一位，末尾补0，然后与b比较，是否大于b，是则temp_a减去 temp_b将且加上1，否则继续往下执行。上面的移位、比较和减法（视具体情况而定）要执行32次，执行结束后temp_a的高32位即为余数，低32 位即为商。

除法器的实现算法还有 递推的 “牛顿算法” 等等。。。。。