![计算机组成原理第讲乘法_第1页](http://file4.renrendoc.com/view/92ea47a5f5c57d631224844ef8587ae4/92ea47a5f5c57d631224844ef8587ae41.gif)
![计算机组成原理第讲乘法_第2页](http://file4.renrendoc.com/view/92ea47a5f5c57d631224844ef8587ae4/92ea47a5f5c57d631224844ef8587ae42.gif)
![计算机组成原理第讲乘法_第3页](http://file4.renrendoc.com/view/92ea47a5f5c57d631224844ef8587ae4/92ea47a5f5c57d631224844ef8587ae43.gif)
![计算机组成原理第讲乘法_第4页](http://file4.renrendoc.com/view/92ea47a5f5c57d631224844ef8587ae4/92ea47a5f5c57d631224844ef8587ae44.gif)
![计算机组成原理第讲乘法_第5页](http://file4.renrendoc.com/view/92ea47a5f5c57d631224844ef8587ae4/92ea47a5f5c57d631224844ef8587ae45.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第一页,共二十四页,编辑于2023年,星期一第3章运算方法和运算部件(3)Abinarymultiplierisanelectroniccircuitusedindigitalelectronics,suchasacomputer,tomultiplytwobinarynumbers.Itisbuiltusingbinaryadders.Untilthelate1970s,mostminicomputersdidnothaveamultiplyinstruction,andsoprogrammersuseda"multiplyroutine”whichrepeatedlyshiftsandaccumulatespartialresults,oftenwrittenusingloopunwinding.Earlymicroprocessorsalsohadnomultiplyinstruction.原码一位乘法补码一位乘法补码两位乘法原码两位乘法第二页,共二十四页,编辑于2023年,星期一UnsignedBinaryMultiplication
无符号数乘法两个尾数为n位的数相乘,乘积的尾数为2n位。手算乘法的过程:1011被乘数×1101乘数101100001011101110001111位积乘积需要n个寄存器保存位积对应于乘数的位,将被乘数逐次左移一位加在左下方。最后将n个位积相加,得到乘积。计算机不能照搬手算的算法。运算器一次只能完成两数的求和操作。需要2n位的加法器§3.3二进制乘法运算BinaryMultiplication
Binary(Fixed-Point)MultiplicationArithmetic被乘数左移,根据乘数每个位做不同运算,都不便于计算机实现第三页,共二十四页,编辑于2023年,星期一计算机的算法:
只能把每一个新位积与部分积(部分积的初值为零)相加,总共做n次加法(累加)。
部分积与位积相加时,只有n位与位积相加,其余部分并不参加运算。因此用n位的加法器就可完成乘法了。被乘数左移一位的操作改为部分积右移一位后与被乘数相加。只需用1个n位的寄存器存放部分积的高位,部分积的低位与乘数共用一个n位的寄存器,在乘数右移一位(计算该位位积后自动丢失)的同时将部分积最低一位移入。乘法完成后,原来存放乘数的寄存器中是乘积的低n位,乘数全部丢失,而硬件则节省了一个寄存器。被乘数10111101乘数0000部分积+10111011+000001011+101101011110右移一位00101111右移一位设计乘法逻辑第四页,共二十四页,编辑于2023年,星期一&&计数器A部分积A→FB→FF/2→ACd…C乘数B被乘数F加法器
移位电路C/2→C无符号数乘法逻辑原理图运算前,先将被乘数送寄存器B,乘数送寄存器C,计数器的初值为N,部分积寄存器A清零。若乘数末位Yi=1,部分积与被乘数在加法器相加。若乘数末位Yi=0,则加法器输出的是部分积与0的和。寄存器A和C中的部分积和乘数都右移一位形成新的部分积,部分积的最低位移入C空出的最高位。如此重复N次,乘法计算完毕。乘积的高N位在A中,低N位在C中,原来在C中的乘数在移位中丢失。CPA第五页,共二十四页,编辑于2023年,星期一[例1]X=+0.1011B,Y=-0.1101B,解:乘积的符号位用原码一位乘法计算X·Y[X]原=|X|=[Y]原=|Y|=0.10111.11010.10110.1101原码运算,必须把符号位与数值部分分开进行。符号位做异或运算,数值部分做无符号数相乘。Mostcomputersusea"shiftandadd"algorithmformultiplyingsmallintegers.第六页,共二十四页,编辑于2023年,星期一|X|=0.1011,|Y|=0.1101高位部分积
00000低位部分积/乘数
1101
初始状态|X·Y|=0.10001111右移010001111100011111右移00110111
1011011111+)01011右移000101111001011110+)00000右移001011110010111101+)01011+)01011X·Y=-0.10001111B[X·Y]原=1.10001111乘数最低位为1,加|X|乘数最低位为0,加0乘数最低位为1,加|X|乘数最低位为1,加|X|第七页,共二十四页,编辑于2023年,星期一原码一位乘法流程图YY开始结束A←0,Cd←nB←X,C←YCn=1?A←(A)+(B)(A),(C)右移一位Cd←(Cd)—1Cd=0?NNFlowchart如果乘数的数值部分是N位,则共需做N次加法,N次右移。乘积的数值部分是2N位。原码乘法做的是绝对值相乘,相当于无符号数相乘。右移按逻辑右移进行。缺点:需做N次加法,N次右移,时间太长。计数器乘数被乘数部分积第八页,共二十四页,编辑于2023年,星期一乘积的符号位原码运算,必须把符号位与数值部分分开进行。符号位做异或运算,数值部分做无符号数相乘。
两个原码表示的数(无论小数或整数)相乘,乘积的值是两数绝对值之积,符号是相乘两数符号位的异或值。两个尾数为n位的数相乘,乘积的尾数为2n位。Thesecondproblemisthatthebasicschoolmethodhandlesthesignwithaseparaterule("+with+yields+","+with-yields-",etc.).Thismethodismathematicallycorrect,butithastwoseriousengineeringproblems.Thefirstisthatitinvolves32intermediateadditionsina32-bitcomputer,or64intermediateadditionsina64-bitcomputer.Theseadditionstakealotoftime.第九页,共二十四页,编辑于2023年,星期一原码两位乘法按照乘数每两位的情况,一次求出对应于该2位的部分积。增加少量逻辑电路,可使乘法的速度提高一倍。乘数的相邻两位Yi-1Yi有4种状态组合,分别对应一种操作:Yi-1Yi
操作00011011相当于0·X相当于1·X相当于2·X相当于3·X部分积Pi+0后右移2位部分积Pi+X后右移2位部分积Pi+2X后右移2位部分积Pi+3X后右移2位第十页,共二十四页,编辑于2023年,星期一加2X很容易实现。把X左移一位,或者把X向左斜传送一位。加3X一般不能一次完成。分两次(3X=X+2X)又降低了速度。如果令3X=4X—X,形式上看好象需要2次。实际上可以这样:
本次运算只做减X,用一个欠帐触发器C记下欠加4X,下一步操作时补上。
由于本次累加后,部分积要右移2位,相当于乘数相对左移2位。此时做+X相当于前一步+4X。所以,3X=4X—X只需要做一次。欠帐触发器C的初值为0。Yi-1Yi
操作00011011相当于0·X相当于1·X相当于2·X相当于3·X部分积Pi+0后右移2位部分积Pi+X后右移2位部分积Pi+2X后右移2位部分积Pi+3X后右移2位第十一页,共二十四页,编辑于2023年,星期一原码二位乘法的运算规则:当欠帐触发器C=0时,Yi-1YiC
000 010 100 110 操作
部分积Pi+0后右移2位 部分积Pi+X后右移2位 部分积Pi+2X后右移2位 部分积Pi—X后右移2位
0→C 0→C 0→C 1→C
当欠帐触发器C=1时,Yi-1YiC
001 011 101 111 操作
部分积Pi+X后右移2位 部分积Pi+2X后右移2位 部分积Pi+[-X]补后右移2位 部分积Pi+0后右移2位
0→C 0→C 1→C 1→C
第十二页,共二十四页,编辑于2023年,星期一减X用加[-X]补实现。右移按补码右移规则进行。
当乘数的数值部分是N位(N必须是偶数),则共需做N/2次加法和N/2次右移。最后如果还有欠帐,再做一次+X。欠帐触发器C的初值为0。
由于在运算中有+2|X|,产生的进位可能侵占符号位,所以被乘数和部分积应该取3符号位。例2:X=-0.111111,Y=+0.111001,用原码二位乘法计算X*Y符号位单独处理,乘数的数值部分必须是偶数位。相乘的是两数的绝对值。原码二位乘法的运算规则:第十三页,共二十四页,编辑于2023年,星期一解:[X]
原=1.111111乘积的符号位|X|=0.111111|2X|=001.111110例2:X=-0.111111,Y=+0.111001,用原码二位乘法计算X*Y[Y]
原=0.111001|Y|=0.111001[-|X|]补=1.000001第十四页,共二十四页,编辑于2023年,星期一|X|=0.111111,|Y|=0.111001,
|2X|=001.111110,[-|X|]补=1.000001高位部分积
000.000000乘数欠帐触发器C
1110010
初始状态
000.111000000111111.111001
0001111
右移2位
111.100100+111.000001000.1000110111110
右移2位010.001101+001.111110000.0011111111100
右移2位000.111111+000.111111+000.111111Yi-1YiC=010,加|X|,0→CYi-1YiC=100,加|2X|,0→CYi-1YiC=110,加[-|X|]补,1→CC=1,加|X|[X*Y]原=1.111000000111X*Y=-0.111000000111|X*Y|
=0.111000000111第十五页,共二十四页,编辑于2023年,星期一
在计算机系统内,由于电路故障或电磁干扰等原因,数据在存取或传送过程中可能产生错误。为了能发现或纠正这类错误,常采用具有能发现某些错误,或具有能确定错误的性质和准确的出错位置乃至能自动纠正错误的能力的编码方法,即数据校验码。Mostcodesare"systematic":thetransmittersendsafixednumberoforiginaldatabits,followedbyfixednumberofcheckbits(usuallyreferredtoasredundancyintheliterature)whicharederivedfromthedatabitsbysomedeterministicalgorithm.其实现原理是在合法的数据编码之间加进一些不允许出现的非法编码,使合法编码的码距增大。当合法的数据编码出现错误时,就变成非法编码。这就可以用检测编码的合法性来发现错误。Thereceiverappliesthesamealgorithmtothereceiveddatabitsandcomparesitsoutputtothereceivedcheckbits;ifthevaluesdonotmatch,anerrorhasoccurredatsomepointduringthetransmission.§3.7数据校验码第十六页,共二十四页,编辑于2023年,星期一
由若干位代码组成的一个字叫“码字”,一种码制是若干种码字的组合。将两个码字逐位比较,有几个二进制位不同称为这两个码字间的距离。
只有一位不同的,称其码距为1。例如,3位二进制代码有8种状态,若一种码制用到全部8种码字,其码距为1。就是说,任何一个合法码字的一位或几位出错时,就变成另一个合法码字。一种码制中各码字间的最小距离称为该码制的“码距”。000111101001110010011100第十七页,共二十四页,编辑于2023年,星期一一种码制中各码字间的最小距离称为该码制的“码距”。
若增大编码的冗余度,设计该码制时用4个二进制位来表示8个合法码字。由于只利用了全部16种状态中的8种来表示合法码,就可以把其余8种状态作为非法码,则码距可能增大到2。当一个合法码的一位出错时,将变成一个非法码而被发现。所增加的一位称为校验位。数据000001010011100101110111编码00000011010101101001101011001111非法码00100001011101001011100011101101出错第十八页,共二十四页,编辑于2023年,星期一
合理的安排非法编码的数量和编码规则,增大合法码的码距就可以提高发现错误的能力,甚至能自动纠正错误;但表示一定数量的合法码所使用的二进制位数也增多,使数据存储和传送的数量增大,硬件开销也相应增大。常用的数据校验码有:奇偶校验码、海明校验码和循环冗余校验码等。
根据纠错理论,编码的最小距离与编码的检测、纠错能力的关系为:L—1=C+D其中:L是编码的最小距离,D是可以检测错误代码的位数,C是可以纠正错误代码的位数,D≥C。当L=3时,可检测出2个错误,或者可检测并纠正1位错误。当L=4时,可检测出3个错误,或者可检测出2位并纠正1位错误。第十九页,共二十四页,编辑于2023年,星期一奇偶校验码
ParityCheckCode
奇偶校验码的编码方法是给n位的合法编码增加一个奇偶校验位,使其码距增加到2。任何一位出错(包括校验位)都会使代码的奇偶性改变,从而被发现。校验位可以放在最高数据位的左边,或最低数据位的右边。
若n+1位的奇偶校验码中“1”的个数为奇数称为奇校验,“1”的个数为偶数称为偶校验。
当n位信息代码中有偶数个1,则偶校验附加的校验位为0,而奇校验的校验位为1
。例如:数据代码
奇校验码
偶校验码1010101010100101010101101101101110110110Aparitybitisanerrordetectionmechanismthatcanonlydetectanoddnumberoferrors.设校验位在最右边第二十页,共二十四页,编辑于2023年,星期一交叉奇偶校验
奇偶校验码广泛应用于存储器读写检查,数据传输过程中的检查等。对数据块的横向和纵向都有奇偶校验位。例如:A7A6A5A4A3A2A1A0
横向校验位第1字节11001011→1第2字节01111100→1第3字节10011010→0第4字节10010101→0
↓↓↓↓↓↓↓↓纵向校验位10111000交叉奇偶校验能够发现两个位同时出错。
奇偶校验能发现1位或者奇数个
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高三化学一轮复习 铁 金属材料
- 开学第一课-初三开学第一课
- 石棉项目风险分析和评估报告
- 医疗护理读书汇报
- 从数据中获取商业智能数据挖掘技术与管理
- 离婚孩子送养协议书
- 工地检查计划表
- 编制老师辞职报告(锦集9篇)
- 2024年印铁油墨合作协议书
- 经尿道前列腺电切术后膀胱冲洗的护理-课件
- 部编版(2024版)七年级历史上册第3课《中华文明的起源与形成》精美课件
- 头疗项目合作协议书
- 2025年高考数学一轮复习-7.1.2球的切、接问题【含解析】
- 2024年微信视频号品牌营销与运营服务协议
- 房颤患者护理查房
- 2024-2030年中国大理石行业发展分析及市场竞争格局与发展前景预测研究报告
- 2024-2030年中国保险中介行业市场深度调研及前景趋势与投资研究报告
- 外聘高管合同范本
- 2024秋七年级历史上册 第一单元 史前时期 中国境内人类的活动 第3课 远古的传说教案1 新人教版
- 保险公司与汽车救援公司 合作协议书范本
- 科研伦理与学术规范期末考试1题库
评论
0/150
提交评论