【计算机组成原理学习笔记三十七】原码一位除法

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输入相连接。

发表评论

电子邮件地址不会被公开。 必填项已用*标注