除法器的原理

1.1 除法器的原理
本设计的要求是设计出一个16位带符号的除法器电路，其时钟频率不低于100MHz。
为了便于理解除法器的原理及实现方式，首先介绍一个通俗的正整数除法例子，如图2-1，尝试将被除数140最左边的数字1除以除数9，结果无法相除；接下来尝试将14除以除数9，此时已可以决定商数的MSB（最高有效位，即左边第一个数字）是1，并且作14-9=5的减法，接着取被除数最后一个数字0形成50，尝试用5作为商数的第二个数字，并且作50-9*5=5的乘减法，此时的余数5小于除数9，可以判断5（商数的第二个数字）就是商数的最低有效位，除法结束，所以最终得到商为15、余数为5。

图1 十进制数字的除法例子
图2-2则是以二进制的数字来描述上述步骤，只是处理的数字只限于0和1。其中A、B、Q和R分别代表图2-1中的被除数、除数、商和余数。

图2 二进制整数的除法例子
下面举一个二进制小数的除法例子，被除数X=0.101001，除数Y=0.111，求X/Y的商和余数。
解：                       [-Y]补 =1.001                     （式2-1）
式中   [-Y]补——除数Y的补码；
具体过程如图2-3所示，

图3 除法步骤
解得
                       Q=q0.q1q2q3=0.101                    （式2-2）
                    R=（0.00r3r4r5r6）=0.00110               （式2-3）
式中   Q——商；
       R——余数；
如图2-3所示，除法转换为移位、比较、加减等一系列步骤，中间运算结果可以用数组存储，如果是有符号的除法，在除法开始之前要去符号，即取除数、被除数的绝对值，在除法结束之前要根据除法规则判断商和余数的符号并修正结果。
1.2 除法器的算法分析
虽然Verilog HDL语言中有除法的运算指令，但除运算符中的除数必须为2的幂，所以无法实现除数是任意整数的除法，一定程度上缩小了它的使用领域。并且在多数综合工具中，除运算指令不能综合出令人满意的结果，有些甚至根本不能综合。对于这种情况，一般使用其他相应的算法来实现除法，分这些算法总的来说为两类：基于乘法操作和基于减法操作的算法。
1.2.1 基于乘法的除法
基于乘法的除法，实质上就是把除法看成是乘法的逆运算。如下面的式子所示:
                                q=x/y=x×(1/y)                 式（2-4）
式中: x为被除数；y为除数；q为商。于是除法器的关键部分就是如何求y的倒数。基于乘法操作的算法有SRT算法（Sweeney,Robreson,Tocher几乎同时发现该除法算法，故以三人名字首字母命名）、牛顿拉普森算法和戈尔德施米特算法等。虽然这类算法是基于乘法的除法，但是除法在很多方面与乘法不同,最重要的区别就是在乘法中所有的部分乘积都可以并行生成,而在除法中每个商的位都是以一种顺序的过程确定的,因此速度较慢。
SRT算法就是在每次迭代中，用除数和固定位数的部分余数查询一张表来确定下一个商位，其较优的除法性能产生于每次循环中的较多的商位移动，SRT除法器的基主要有基2和基4两种，更高的基可以由基2和基4的组合来实现。

图4  基4 SRT算法
SRT算法的每次迭代都执行以下循环：
           式（2-5）
式中，Pj——部分余数。由商位选择函数  决定一个商位，然后产生乘积 ，从中减掉。基4 SRT算法图如图2-4所示。
牛顿拉普森算法的基本思想是构造一个函数f(z),令f(z)=(1/z)-y，利用牛顿迭代公式zk+1= zk -f’(zk)/ f(zk)不断进行迭代，其中f’(zk)是f(zk)的导数，直到最后得到的数值zk+1满足接近于商值的精度要求。
1.2.2  基于减法的除法
基于减法操作的算法有恢复余数除法和不恢复余数除法两种，其中恢复余数法是直接从被除数或者余数中减去除数，若够减，余数为正，上商1；若不够减，余数为负，上商0，这个时候，必须把除数加回去，恢复成原来的余数，这样才能继续计算，所以称为恢复余数法。而不恢复余数法的思想就是当某一次减法执行后的差为负时，不用把它恢复成原来的余数，而是想办法直接用这个负的差值求下一位的商。它们具体的逻辑流程如图5所示。
        
    （a）不恢复余数除法                      (b)恢复余数除法
图5  逻辑框图
为了指明不恢复余数法相比恢复余数法在速度上的优势，下面作简要分析：
设上次余数为Ri ，
当Ri≥0时，商上1，然后继续求下次余数；将余数左移一位变成2Ri ，再减去除数，即 2Ri-Y=Ri+1.
当Ri<0时，商上0，此时如果恢复余数，应做Ri+Y，然后将余数左移一位（成为2Ri+2Y），再减去余数，即2Ri+2Y-Y=2Ri+Y= Ri+1。
显然，如果不使用恢复余数法，而是将余数Ri左移一位得2Ri，再加上除数，结果与恢复余数法一样。但是却去掉了减Y的步骤，也就是去掉了不必要的延时，所以不恢复余数法相比恢复余数法在速度上更有优势，因此不恢复余数法的使用比较广泛，计算机中实际采用的就是不恢复余数法。由于不恢复余数法要根据余数Ri的情况进行加减，所以又称为加减交替法。
不恢复余数法的具体算法如下文：对于16的无符号除法，被除数a除以除数b，他们的商和余数一定不会超过16位。首先将a转换成高16位是0，低16位是a的temp_a。把b转换成高16位是b，低16位是0的temp_b。在每个周期开始时，先将temp_a左移一位，末尾补0，然后与b比较，如果大于b就执行temp_a减去temp_b且加上1，否则继续往下执行。上面的移位、比较和减法（视具体的情况而定）要执行16次，执行结束后temp_a的高16位就是余数，低16位就是商。
对于16位有符号被除数A,先将A转换成无符号数abs_a,然后再转换成高16位是0，低16位是A的数sum_a。在每个周期开始时sum_a向左移动一位, 最后一位补零, 然后判断sum_a的高16位是否大于等于由16位有符号除数B转换成的16位无符号除数abs_b,如是则sum_a的高16位减去低16位是0，高16位是abs_b的32位数sum_b并且加1,得到的新值仍赋给sum_a;如果不是就直接进入下一个步骤。上面的移位、比较、减法(视情况而定)要进行16次,经过16个周期后, 运算结束,所得到的sum_a的高16位为“准”余数,低16位为“准”商，接下来需要判断商和余数的符号是正号还是负号。
令D =A(15)⊕B(15) ,如果D = 0则被除数与除数同为正数或者负数,最终商为正数;如果D = 1说明被除数与除数不同号,最终商值的符号为负，将商值取反加1才是商的最终结果。被除数是负数时余数的符号为负,否则为正。余数的变动根据被除数的符号位进行处理。
    综合上述各类算法的优缺点，我们选用不恢复余数法作为本次设计的除法算法，不恢复余数法过程较为简单，同时相比较其他算法速度更快。
1.3 除法器的基本规则
设计除法器之前，我们应该清楚除法的基本规则，这样才能设计出功能正确的除法器，除法有以下规则：
        除数不能为0；
        对于有符号除法，余数的符号与被除数的符号相同；
        对于有符号除法，商的符号需要根据被除数和除数的符号来判定，如果被除数与除数同为正数或者负数,最终商为正数，如果被除数与除数一个为正、一个为负,最终商为负数。

除法器的原理

除法器原理

除法器的原理