除法器的实现（恢复余数、不恢复余数、级数展开、Newton-Raphson）

参考《基于FPGA的数字信号处理（第二版）》，对其中的除法器算法进行仿真。

1 基于恢复余数（Restoring）算法的除法器

Restoring 算法无法直接用于与有符号数，对于有符号数需要先转换为无符号数。然后根据除数与被除数的符号判断商与余数的符号。

1.1 原理

被除数（Dividend）5621 / 除数（Divisor）3 = 商（Quotient）1873 … 余数（Remainder）2

       1873
     _______
  3 |  5621
    /  3000
       ____
       2621
       2400  
       ____
        221
        210
        ___
         11
          9
          _
          2

r i = r i + 1 − q i ⋅ D ⋅ 1 0 i r_i = r_{i+1}-q_i·D·10^i ri​=ri+1​−qi​⋅D⋅10i

q i q_i qi​通过部分余数的正负确定，如果余数为负表示 q i q_i qi​较大，需要将其恢复到部分余数为正以获取正确的 q i q_i qi​，这便是“恢复”的含义。

用恢复余数算法表示上式计算过程：

q i q_i qi​余数是否恢复 q 3 = 1 q_3=1 q3​=15621-3×10^3×1=2621 q 3 = 2 q_3=2 q3​=25621-3×10^3×2=-379 q 3 q_3 q3​恢复为1，余2621 q 2 = 1 q_2=1 q2​=12621-3×10^2×1=2321 q 2 = 2 q_2=2 q2​=22621-3×10^2×2=2021………… q 2 = 8 q_2=8 q2​=82621-3×10^2×8=221 q 2 = 9 q_2=9 q2​=92621-3×10^2×9=-79 q 2 q_2 q2​恢复为8，余221………… q 1 = 7 q_1=7 q1​=7221-3×10^1×7=11 q 1 = 8 q_1=8 q1​=8221-3×10^1×8=-19 q 1 q_1 q1​恢复为7，余11………… q 0 = 3 q_0=3 q0​=311-3×10^0×3=2 q 0 = 4 q_0=4 q0​=411-3×10^0×4=-1 q 0 q_0 q0​恢复为3，余2

得 q 3 q 2 q 1 q 0 {q_3q_2q_1q_0} q3​q2​q1​q0​ = 1873，R=2。

以上是十进制算法，对于二进制：

r i = r i + 1 − q i ⋅ D ⋅ 2 i r_i = r_{i+1}-q_i·D·2^i ri​=ri+1​−qi​⋅D⋅2i

q i q_i qi​只能取0或1，所以每位只需一次运算即可判断是否恢复。

此外还需确定各参数的字长：假定除数D为 nbit，商Q为 nbit，则 Q ≤ 2 n − 1 Q\le2^n-1 Q≤2n−1。由于R