原码一位除法

admin

1．原码一位除法算法设计
除法运算与乘法运算的处理思想相似，也可从手算中得到一些启发。通过分析手工二进制除法的过程,可以发现下列规律：
（1）除法通过减法实现；
（2）上第i位商前，先比较余数与 （即将除数右移i位）之间的大小，然后根据比较的结果决定商上1还是上0。
为便于计算机上实现除法运算,对手工除法算法进行如下改进:
（1）通过减法运算比较数的大小,并作为上商的依据。若余数减去除数大于或等于0则表示够减，若小于零则表示不够减。
（2）将手工运算中每次右移除数改为左移余数,并与上商操作统一起来，使得上商能固定在一个位置上进行。值得注意的是，每左移一次余数，相当于将余数乘以2，在求得n位商后，余数r也就被左移了n次，因此最后正确的余数应为 。
1）原码恢复余数法
由于除法通过减法实现，当商上1时，可将比较数据大小的减法操作与除法操作中的减法操作合并，即商上1后继续后面的除法操作。商上0时表明不够减，不应该直接执行除法运算中的减运算，但因试商时的比较操作已经实施了一次减法，因此，需将余数恢复到试商前的值，这可加除数来是想，这种方法称为恢复余数法除法。
原码恢复余数法的算例如下： 例： ， ，求
解： ，

故 ，余数 。
可以看出运算过程是一个循环过程：比较 →上商（商为0时还需要恢复余数）→左移→再比较，直到商达到规定的位数为止。一般商的位数上到与除数的位数相同即可。
从该算例的运算过程可知，由于可能需要恢复余数，而除法中恢复余数的步数不能在运算前被确定，导致原码恢复余数除法控制复杂，下面将研究改进方法。
2）原码不恢复余数法
不恢复余数法又称加减交替法，是对恢复余数法的改进，其特点是当试商结果为负时不再恢复余数，而是根据所得余数的符号作下列处理：
●当余数为正时，商上1，余数左移一位，减去除数；
●当余数为负时，商上0，余数左移一位，加上除数。
由于没一步都上商，因此运算步数固定，控制简单，提高了运算速度。
原码不恢复余数除法的算例如下：
例： ， ，用不恢复余数法求
解：

即 ，余数 。
算式最左边小方框标识的数字是运算器进位位的值，进一步分析发现，该值与该步所上的商相同,因此,在具体逻辑实现中可用加法器进位位作为上商的控制信号。
2．原码不恢复余数法实现逻辑
实现原码不恢复余数除法的硬件逻辑框图如图3．6所示。

图3．6 原码不恢复余数除法的硬件逻辑框图

寄存器R0在除法开始前存放被除数，运算过程中存放余数；寄存器 存放除数的绝对值或数值位；商存放在 中； 与都具有左移功能。每步的商和下一步的操作根据当前加法器进位位的状态来确定，上商操作固定在 位进行。的值（即每一步所上的商）控制下一步是进行加y还是进行减y操作，当＝1时，下一步加 ，进行减y比较；当＝0时，则下一步进行加y比较。在运算过程中，经过n＋1步后获得n＋1位商，其中n为有效数的位数，最后由 的值来决定商的符号。

二、补码一位除法

鉴于不恢复余数除法的优越性，这里只研究基于不恢复余数法的补码一位除法运算方法。对补码符号位参与运算，因此不能采用原码除法中的方法，需要通过判断余数和除数的符号来进行，具体规则如下：
（1）被除数与除数同号，被除数减去除数；被除数与除数异号，被除数加上除数。
（2）余数与除数同号，商上1，余数左移一位减去除数；余数与除数异号，商上0，余数左移一位加上除数。（注意：余数左移加上或减去除数后就得到了新余数。）
（3）重复（2），直到商的位数满足要求为止。
补码不恢复余数法的算例如下:
例： ， ，求
解：

故 ，余数
实现补码不恢复余数法的逻辑结构与图3．6十分相似，此处不再赘述,请同学们自己设计并组织讨论。

三、阵列除法器

为加快除法的执行速度，也可以采用类似阵列乘法器的思想来设计阵列除法器。为简化运算及阵列除法器的结构，由于除法运算过程中要进行减法运算，需改变传统FA的结构，使其具有可控的加/减功能。详细的结构和工作原理见教材
1．加/减可控单元CAS
图3．7是加减可控单元（CAS）的逻辑结构。

图3．7 CAS阵列除法器组成图

一个CAS单元有8根引线（比FA多3根），分成四个输入端和四个输出端。CAS单元上面一行水平输入和输出线P为加/减操作控制, P =1 时CAS执行加法，否则执行减法；CAS单元下面一行水平输入和输出的是进位/借位输入（输出）信号；斜向输入/输出的Yi为除数,但斜向输出到下一个CAS单元（当由多个CAS单元构成阵列时），相当于手工除法中的右移；垂直输入的是被除数Xi，垂直输出的是商Si。
CAS单元输入与输出的关系可用公式3．3表示：
　　
当 P =0 时,CAS的功能等于FA，而P =1 时,CAS就变成了一位全减器。
2．阵列触发器的逻辑结构
图3．8为字长为3位的阵列除法器的基本结构，其中被除数 （双字长），除数 ，商q=0．q1q2q3,余数 。

图3．8 阵列除法器的基本结构。

理解CAS单元之间的连接方法是掌握阵列触发器工作管理的关键。每行CAS单元的连接中，所有CAS单元的P信号按照相邻关系依次连接，进位/借位信号也依次连接，需要特别注意的有两个地方：
（1）最右边CAS单元的P输出和C输入相连接，要理解这种连接的依据，P=1时CAS做减法，而减法是通过加负数的补码实现，但P=1时，CAS单元只对除数实现了求反码，所以此时要在最低位加1才能变成补码，因此，可用P将1送到最低位CAS的进位输入（即最右边的CAS单元）。当P=0时CAS做加法，与最低CAS的进位位相连刚好满足加法的进位需求。
（2）由原码不恢复余数法可知，新上的商决定了下一步除法的算法，因此，可用上一步的商（各行最左边CAS的进位/借位输出）控制除法阵列中相邻下一行CAS阵列的加/减操作，即商上1，下一步减除数，而商上零，下一步加除数。故将上一步的商与下一行CAS阵列的P输入相连接。