 上传我的文档
 下载
 收藏
粉丝量：26
该文档贡献者很忙，什么也没留下。
 下载此文档
下载积分：1000
内容提示：练习题
文档格式：DOC|
浏览次数：76|
上传日期： 15:11:39|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1000 积分
下载此文档
该用户还上传了这些文档
关注微信公众号【图文】计算机组成原理第二章 第8讲 定点乘法运算_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
计算机组成原理第二章 第8讲 定点乘法运算
&&计算机组成原理第二章
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢查看: 4436|回复: 2
移位乘法运算
阅读权限200
在计算机中，乘法运算是一种很重要的运算，有的机器由硬件乘法器直接完成乘法运算，有的机器内没有乘法器，但可以按机器作乘法运算的方法，用软件编程实现、因此，学习乘法运算方法不仅有助于乘法器的设计，也有助于乘法编程。
　　下面从分析笔算乘法入手，介绍机器中用到的几种乘法运算方法。
　　(1)分析笔算乘法：
　　设A=0.1101，B=0.1011，求A×B。
　　笔算乘法时乘积的符号由两数符号心算而得：正正得正；其数值部分的运算如下：
　　所以&&A×B=+0.
　　可见，这里包含着被乘数4的多次左移，以及四个位积的相加运算。
　　若计算机完全模仿笔算乘法步骤，将会有两大困难：其一，将四个位积一次相加，机器难以实现；其二，乘积位数增长了一倍，这将造成器材的浪费和运算时间的增加。为此，对笔算乘法做些改进。
　　(2)笔算乘法的改进：
　　将A?B= A?0.1011
　　　　 =0.1A+0.001?A+0.0001?A
　　　　 =0.1A+0.00?A+0.001(A+0.1A）
　　　　 =0.1A+0.01[0?A+0.1(A+0.1A)]
　　　　 =0.1{A+0.1[0?A+0.1(A+0.1A)]}
　　　　 =2-1{A+2-1 [0?A+2-1 (A+2-1A)]}
　　　　 =2-1{A+2-1 [0?A+2-1 (A+2-1(A+0))]}
　　由上式可见，两数相乘的过程，可视作加法和移位(乘2-1相当于做一位右移)两种运算，这对计算机来说是非常容易实现的。
　　从初始值为0开始，对上式作分步运算，则
　　第一步：被乘数加零　　　　　　A+0=0.0=0.1101
　　第二步：右移一位，得新的部分积　　　2-1 (A+0)＝0.01101
　　第三步：被乘数加部分积　A+2-1(A+0)=0.01=1.00111
　　第四步：右移一位，得新的部分积　2-1 A+2-1 (A+0)=0.100111
　　第五步：　　　　　　　　0?A +2-1 [A+2-1 (A+0)] =0.100111
　　第六步：　　　　　　2-1{0?A+2-1 [A+2-1 (A+0)]}=0.0100111
　　第七步：　　　　　　A+2-1{0?A+2-1 [A+2-1 (A+0)]}=1.0001111
　　第八步：　　2-1 {A+2-1[0?A+2-1 (A+2-1 (A+0))]}=0.
　　上述运算过程可归纳为：
　　①乘法运算可用移位和加法来实现，当两个四位数相乘，总共需做四次加法和四次移位。
　　②由乘数的末位值确定被乘数是否与原部分积相加，然后右移一位，形成新的部分积；同时，乘数也右移一位，由次低位作新的末位，空出最高位放部分积的最低位。
　　③每次做加法时，被乘数仅仅与原部分积的高位相加，其低位被移至乘数所空出的高位位置。
　　计算机很容易实现这种运算规则。用一个寄存器存放被乘数，一个寄存器存放乘积的高位，又用一个寄存器存放乘数及乘积的低位，再配上加法器及其他相应电路，就可组成乘法器。又因加法只在部分积的高位进行，故不但节省了器材，而且还缩短了运算时间。
　　1．原码一位乘法
　　由于原码表示与真值极为相似，只差一个符号，而乘积的符号又可通过两数符号的逻辑异或求得，因此，上述讨论的结果可以直接用于原码一位乘，只需加上符号位处理即可。
　　上图是一个32位乘法器的结构框图，其中32位被乘数放在R2中，运算开始时32位乘数放在R1中，运算结束时64位乘积的高位放在R0中，低位放在R1中，R0和R1串联移位。完成这个定点原码一位乘法的运算规则可以用如下图所示的逻辑流程图表示。（32位+32位=64位）
　　在该乘法过程中，每次操作是根据乘数的一位进行操作，对于32位数的乘法，需要循环32次完成一个乘法操作，因此称为一位乘法。
　　例：用原码的乘法方法进行2×3的四位乘法。
　　解：在乘法开始之前，R0和R1中的初始值为，R2中的值为0010。
　　在乘法的第一个循环中，判断R1的最低位为1，所以进入步骤1a，将R0的值加上R2的值，结果0010送人R0，然后进入第二步，将R0和R1右移一位，R0、Rl的结果为，见下表的循环1，表中黑体字的数据位是乘法过程中判断的R1最低位。
　　第二个循环过程中，判断R1的最低位为l，仍进入步骤la，加0010，结果为0011，然后在第二步中将R0和R1右移一位，结果为，见下表的循环2。
　　第三次循环中，因R1的最低位为0，进入步骤lb，R0不变，第二步移位后结果为，见下表的循环3。
　　第四次循环时仍因R1最低位为0，只作移位，结果为，这就是乘法的结果6，见下表的循环4。
001.png (19.51 KB, 下载次数: 0)
19:10 上传
2．原码两位乘法
　　原码两位乘与原码一位乘一样，符号位的运算和数值部分是分开进行的，但原码两位乘是用两位乘数的状态来决定新的部分积如何形成，因此可提高运算速度。
　　两位乘数共有4种状态，对应这4种状态可得下表。
002.png (21.4 KB, 下载次数: 2)
19:03 上传
表中2倍被乘数可通过将被乘数左移一位实现，而3倍被乘数的获得可以分两步来完成，利用3=4-1，第一步先完成减1倍被乘数的操作，第二步完成加4倍被乘数的操作。而加4倍被乘数的操作实际上是由比“11”高的两位乘数代替完成的，可以看作是在高两位乘数上加“1”。这个“1”可暂时存在Cj触发器中。机器完成置“1” Cj即意味着对高两位乘数加1，也即要求高两位乘数代替本两位乘数“11”来完成加4倍被乘数的操作。由此可得原码两位乘的运算规则如下表所示。
003.png (23.21 KB, 下载次数: 4)
19:03 上传
表中z表示原有部分积，x*表示被乘数的绝对值，y*表示乘数的绝对值，→2表示右移两位，当作-x*运算时，一般采用加[-x*]补来实现。这样，参与原码两位乘运算的操作数是绝对值的补码，因此运算中右移两位的操作也必须按补码右移规则完成。尤其应注意的是，乘法过程中可能要加2倍被乘数，即+[2x*]补，使部分积的绝对值大于2。为此，只有对部分积取三位符号位，且以最高符号位作为真正的符号位，才能保证运算过程正确无误。
　　此外，为了统一用两位乘数和一位Cj共同配合管理全部操作，与原码一位乘不同的是，需在乘数（当乘数位数为偶数时）的最高位前增加两个0。这样，当乘数最高两个有效位出现“11”时， Cj需置“1”，再与所添补的两个0结合呈001状态，以完成加x*的操作（此步不必移位）。
例：设x=0.111111，y=-0.111001，用原码两位乘求[x? y]原。
　　解：①数值部分的运算如下表所示，其中x*=0.111111, [-x*]补=1.x*=1.111110, y*=0.111001。
004.png (29.06 KB, 下载次数: 1)
19:10 上传
②乘积的符号为&&
　　故[x? y]原=1.。
　　不难理解，当乘数为偶数时，需作n/2次移位，最多作n/2+1次加法。当乘数为奇数时，乘数高位前可只增加一个“0”，此时需作n/2+1次加法，n/2+1次移位（最后一步移一位）。
　　虽然两位乘法可提高乘法速度，但它仍基于重复相加和移位的思想，而且随着乘数位数的增加，重复次数增多，仍然影响乘法速度的进一步提高t采用并行阵列乘法器可大大提高乘法速度。
　　原码乘法实现比较容易，但由于机器都采用补码作加减运算，倘若做乘法前再将补码转换成原码，相乘之后又要将负积的原码变为补码形式，这样增添了许多操作步骤，反而使运算复杂。为此，有不少机器直接用补码相乘，机器里配置实现补码乘法的乘法器，避免了码制的转换，提高了机器效率。
　　3．补码一位乘法
　　一种比较好的带符号数乘法的方法是布斯(Booth)算法。它采用相加和相减的操作计算补码数据的乘积。Booth算法对乘数从低位开始判断，根据两个数据位的情况决定进行加法、减法还是仅仅移位操作。判断的两个数据位为当前位及其右边的位(初始时需要增加一个辅助位0)，移位操作是向右移动。在上例中，第一次判断被乘数0110中的最低位0以及右边的位(辅助位0)，得00；所以只进行移位操作；第二次判断0110中的低两位，得10，所以作减法操作并移位，这个减法操作相当于减去2a的值；第三次判断被乘数的中间两位，得11，于是只作移位操作；第四次判断0110中的最高两位，得01，于是作加法操作和移位，这个加法相当于加上8a的值，因为a的值已经左移了三次。
　　一般而言，设y=y0,yly2…yn为被乘数，x为乘数，yi是a中的第i位(当前位)。根据yj与yi+1的值，Booth算法表示如下表所示，其操作流程如下图所示。在Booth算法中，操作的方式取决于表达式(yi+1-yi)的值，这个表达式的值所代表的操作为：
　　　0& & 无操作
　　　+1& & 加x
　　　-1& & 减x
Booth算法操作表示
005.png (15.55 KB, 下载次数: 0)
19:03 上传
实现32位Booth乘法算法的流程图
　　乘法过程中，被乘数相对于乘积的左移操作可表示为乘以2，每次循环中的运算可表示为对于x(yi+1-yi)231-i项的加法运算(i=3l，30，…，1，0)。这样，Booth算法所计算的结果&&可表示为：
　　 x×(0-y31)×20
　　+x×(y31-y30)×21
　　+x×(y30-y29)×22
　　+x×(y1-y0)×231
　　=x×(-y0×231 +y1×230 +y2×229+y31×20)
　　例：用Booth算法计算2×(-3)。
　　解：[2]补=0010，&&[-3]补=1101，在乘法开始之前，R0和R1中的初始值为，R2中的值为0010。
　　在乘法的第一个循环中，判断R1的最低位和辅助位为10，所以进入步骤1c，将R0的值减去R2的值，结果1110送人R0，然后进人第二步，将R0和Rl右移一位，R0和R1的结果为，辅助位为l。
　　在第二个循环中，首先判断Rl的最低位和辅助位为0l，所以进入步骤1b，作加法，R0+R2=，结果0001送入R0，这时R0R1的内容为，在第二步右移后变为，辅助位为0。
　　在第三次循环中，判断位为10，进入步骤lc，R0减去R2，结果1110送入R0，R1不变；步骤2移位后R0和R1的内容为，辅助位为1。
　　第四次循环时，因两个判断位为11，所以不作加减运算，向右移位后的结果为，这就是运算结果(—6)。
　　这个乘法的过程描述如下表所示，表中乘积一栏表示的是R0、R1的内容以及一个辅助位P，黑体字表示对两个判断位的判断。
用Booth补码一位乘法计算2 ×(-3)的过程
006.png (20.01 KB, 下载次数: 0)
19:03 上传
4．补码两位乘
　　补码两位乘运算规则是根据补码一位乘的规则，把比较yiyi+1的状态应执行的操作和比较yi-1yi 的状态应执行的操作合并成一步，便可得出补码两位乘的运算方法。
补码两位乘法运算规则如下
007.png (20.7 KB, 下载次数: 0)
19:03 上传
由上表可见，操作中出现加2[x]补和加2[-x]补，故除右移两位的操作外，还有被乘数左移一位的操作；而加2[x]补和加2[-x]补，都可能因溢出而侵占双符号位，故部分积和被乘数采用三位符号位。
　　例：[x]补=0.0101，[y]补=1.0101 求： [x? y]补。
　　解：求解过程如下表所示。其中乘数取两位符号位即11.0101,[-x]补=1.1011取三符号位为111.1011。
008.png (20.04 KB, 下载次数: 1)
19:03 上传
故[x? y]补=1.
　　可见，与补码一位乘相比，补码两位乘的部分积多取一位符号位（共3位），乘数也多取一位符号位（共2位），这是由于乘数每次右移2位，且用3位判断，故采用双符号位更便于硬件实现。可见，当乘数数值位为偶数时，乘数取2位符号位，共需作n/2次移位，最多作n/2+1次加法，最后一步不移位；当n为奇数时，可补0变为偶数位，以简化逻辑操作。也可对乘数取1位符号位，此时共作n/2+1次加法和n/2+1次移位（最后一步移一位）。
　　对于整数补码乘法，其过程与小数乘法完全相同。为了区别于小数乘法，在书写上可将符号位和数值位中间的“.”改为“，”即可。
文章中涉及到的图片打包下载：
(32.68 KB, 下载次数: 12)
19:52 上传
点击文件名下载附件
下载积分: 驿站币 -2
发帖求助前要善用【】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请编辑帖子并把分类改成【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【驿站币】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限70
银牌会员, 积分 1712, 距离下一级还需 1288 积分
这篇文章是肯定要看的
发帖求助前要善用【】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请编辑帖子并把分类改成【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【驿站币】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
阅读权限70
银牌会员, 积分 2819, 距离下一级还需 181 积分
发帖求助前要善用【】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请编辑帖子并把分类改成【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【热心】和【驿站币】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
站长提醒 /1
对已经录取并在vc驿站上面发表的作品予以奖励，视技术含量不同奖励人民币 50~300元
Powered by Discuz! X3.4[转载]定点乘法运算——原码乘法
2.3.1 原码乘法 　　　　　　　　
1.人工算法与机器算法的同异性
　　在定点计算机中,两个原码表示的数相乘的运算规则是:乘积的符号位由两数的符号位按异或
运算得到,而乘积的数值部分则是两个正数相乘之积。
　　设n位被乘数和乘数用定点小数表示(定点整数也同样适用)
　　　　　　　被乘数 　　[ｘ]原＝ｘf
.ｘn－1…ｘ1ｘ0
　　　　　　　　乘数 　　[ｙ]原＝ｙf
.ｙn－1…ｙ1ｙ0
[ｚ]原＝(ｘf&ｙf)＋(0.ｘn－1…ｘ1ｘ0)(0.ｙn－1…ｙ1ｙ0)
式中,ｘf为被乘数符号,ｙf为乘数符号。
　　乘积符号的运算法则是：同号相乘为正,异号相乘为负。由于被乘数和乘数和符号组合只有
四种情况(ｘfｙf＝00,01,10,11),因此积的符号可按“异或”(按位加)运算得到。
　　数值部分的运算方法与普通的十进制小数乘法类似,不过对于用二进制表达式的数来说,其乘
法规则更为简单一些。
　　设ｘ＝0.1101,ｙ＝0.1011.让我们先用习惯方法求其乘积,其过程如下:
　　运算的过程与十进制乘法相似:从乘数ｙ的最低位开始,若这一位为“1”,则将被乘数ｘ写
下；若这一位为“0”,则写下全0。然后在对乘数ｙ的最高为进行乘法运算,其规则同上,不过这
一位乘数的权与最低位乘数的权不一样,因此被乘数ｘ要左移一位。以此类推,直到乘数个位乘完
为止,最后将它们统统加起来,变得到最后乘积ｚ。
　　如果被乘数和乘数用定点整数表示,我们也会得到同样的结果。
　　人们习惯的算法对机器并不完全适用。原因之一,机器通常只有n位长,两个n位数相乘,乘积可能为2n位。原因之二,只有两个操作数相加的加法器难以胜任将各n位积一次相加起来的运算。早期计算机中为了简化硬件结构,采用串行的1位乘法方案,即多次执行“加法—移位”操作来实现。这种方法并不需要很多器件。然而串行方法毕竟太慢,自从大规模集成电路问世以来,出现了各种形式的流水式阵列乘法器,它们属于并行乘法器。
图2.4 m&n位不带符号的阵列乘法器逻辑图
2.不带符号的阵列乘法器
设有两个不带符号的二进制整数：
A＝am－1…a1a0
B＝bn－1…b1b0
它们的数值分别为a和b,即
m－1　　　　　n－1
a ＝∑ai2i　　b
i＝0　　　　　　j＝0
在二进制乘法中,被乘数A与乘数B相乘,产生m＋n位乘积P：
P＝pm＋n－1…p1p0
乘积P 的数值为
　　　　　　
实现这个乘法过程所需要的操作和人们的习惯方法非常类似：
　　上述过程说明了在m位乘n位不带符号整数的阵列乘法中,“加法—移位”操作的被加数矩
阵。每一个部分乘积项(位积)aibj叫做一个被加数。
这m&n个被加数{aibj|0≤i≤m－1和0≤j≤n－1}
可以用m&n个“与”门并行地产生。显然,设计高速并行乘法器的基本问题,就在于缩短被加数
矩阵中每列所包含的1的加法时间。
5位&5位阵列乘法器的逻辑电路图演示　
　　这种乘法器要实现n位&n位时,需要n(n－1)个全加器和n2个“与”门。该乘法器的总的乘法
时间可以估算如下：
　　令Ta为“与门”的传输延迟时间,Tf为全加器(FA)的进位传输延迟时间,假定用2级“与非”逻辑来实现FA的进位链功能,那么我们就有：
Ta ＝ Tf ＝
　从演示中可知，最坏情况下延迟途径,即是沿着矩阵P4垂直线和最下面的一行。因而得
n位&n位不带符号的阵列乘法器总的乘法时间为：
　　　　tm＝Ta＋(n－1)&6T＋(n－1)&Tf
＝2T＋(n－1)&6T＋(n－1)&2T＝(8n－6)T　　　　　(2.27)　　　　　　　　　　　　　　　　　　　　　　
[例16] 参见上CAI演示,已知两个不带符号的二进制整数A ＝ 11011,B ＝
10101,求每一部分乘
积项aibj的值与p9p8……p0的值。
P＝p9p8p7p6p5p4p3p2p1p0＝
3.带符号的阵列乘法器
(1) 对2求补器电路
　　我们先来看看算术运算部件设计中经常用到的求补电路。一个具有使能控制的二进制对2求补
器电路图演示，其逻辑表达式如下：
C－1＝0,　
Ci＝ai＋Ci－1
ai*＝ai&ECi－1,　　　0≤i≤n
　在对2求补时,要采用按位扫描技术来执行所需要的求补操作。令A＝an…a1a0是给定的(n＋1)为
带符号的数,要求确定它的补码形式。进行求补的方法就是从数的最右端a0开始,,由右向左,直到
找出第一个“1”,例如ai＝1, 0≤i≤n。这样,ai以左的每一个输入位都求反,即1变0,0变1。最右
端的起始链式输入C－1必须永远置成“0”。当控制信号线E为“1”时,启动对2求补的操作。当控
制信号线E为“0”时,输出将和输入相等。显然,我们可以利用符号位来作为控制信号。
　　例如,在一个4位的对2求补器中,,如果输入数为1010,那么输出数应是0110,其中从右算起的
第2位,就是所遇到的第一个“1”的位置。用这种对2求补器来转换一个(n＋1)为带符号的数,所需
的总时间延迟为
　　　　　　　　　　　　　tTC＝n·2T＋5T＝(2n＋5)T　　　　　　　　　　　(2.28)
　其中每个扫描级需2T延迟,而5T则是由于“与”门和“异或”门引起的。
(2) 带符号的阵列乘法器
　　(n＋1)&(n＋1)位带求补器的阵列乘法器逻辑方框图演示　
　　　通常,把包括这些求补级的乘法器又称为符号求补的阵列乘法器。在这种逻辑结构中,共使
用三个求补器。其中两个算前求补器的作用是：将两个操作数A和B在被不带符号的乘法阵列(核心
部件)相乘以前,先变成正整数。而算后求补器的作用则是：当两个输入操作数的符号不一致时,把
运算结果变成带符号的数。
　　设A=anan-1…a1a0和B=bnbn-1…b1b0均为用定点表示的(n＋1)位带符号整数。在必要的求补
操作以后,A和B的码值输送给n&n位不带符号的阵列乘法器,并由此产生2n位真值乘积:
　　　　　　　　　　　　　　　A·B＝P＝p2n－1…p1p0
　　　　　　　　　　　　　　　　　p2n＝an&bn
　　其中P2n为符号位。
　　　上面CAI演示所示的带求补级的阵列乘法器既适用于原码乘法,也适用于间接的补码乘法。不
过在原码乘法中,算前求补和算后求补都不需要,因为输入数据都是立即可用的。而间接的补码阵
列乘法所需要增加的硬件较多。为了完成所必需的乘法操作,时间大约比原码阵列乘法增加1倍。
[例17] 设ｘ＝＋15,ｙ＝－13,用带求补器的原码阵列乘法器求出乘积ｘ·ｙ＝？
　　设最高位为符号位,则输入数据为
　　[ｘ]原 ＝01111　　　 [ｙ]原 ＝ 11101
　　符号位单独考虑,算前求补级后
|ｘ|＝1111,|ｙ|＝1101
　　算后经求补级输出并加上乘积符号位1,则原码乘积值为1<font COLOR="#000011。
　　换算成二进制数真值是
－)2=(-195)10
　　十进制数验证：ｘ&ｙ ＝ 15&
(－13) ＝ －195相等。
[例18] 设ｘ＝＋15,ｙ＝－13,用带求补器的补码阵列乘法器求出乘积ｘ·ｙ＝？
　　设最高位为符号位,则输入数据用补码表示为
　　[ｘ]补 ＝01111　　　 [ｙ]补 ＝ 10011
　　符号位单独运算,x0y0=0+1=1
尾数部分算前求补器输出为: |ｘ|＝1111,|ｙ|＝1101
　　算后求补器输出为<font COLOR="#111101,加符号位1,得
[ｘ·ｙ]补=1<font COLOR="#111101
　　补码二进制数真值是
ｘ·ｙ＝-1&28+1&25+1&24+1&23+1&22+1&20=(-195)10
十进制数验证：&&&&
ｘ&ｙ＝(+15)& (－13) ＝ －195相等。
　 　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。【图文】组成原理课后习题答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
组成原理课后习题答案
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢}