计算机组成原理第讲乘法

第3章运算方法和运算部件(3)Abinarymultiplierisanelectroniccircuitusedindigitalelectronics,suchasacomputer,tomultiplytwobinarynumbers.Itisbuiltusingbinaryadders.Untilthelate1970s,mostminicomputersdidnothaveamultiplyinstruction,andsoprogrammersuseda"multiplyroutine”whichrepeatedlyshiftsandaccumulatespartialresults,oftenwrittenusingloopunwinding.Earlymicroprocessorsalsohadnomultiplyinstruction.原码一位乘法补码一位乘法补码两位乘法原码两位乘法第2页,共24页，2024年2月25日，星期天UnsignedBinaryMultiplication

无符号数乘法两个尾数为n位的数相乘，乘积的尾数为2n位。手算乘法的过程：1011被乘数×1101乘数101100001011101110001111位积乘积需要n个寄存器保存位积对应于乘数的位，将被乘数逐次左移一位加在左下方。最后将n个位积相加，得到乘积。计算机不能照搬手算的算法。运算器一次只能完成两数的求和操作。需要2n位的加法器§3.3二进制乘法运算BinaryMultiplication

Binary(Fixed-Point)MultiplicationArithmetic被乘数左移，根据乘数每个位做不同运算，都不便于计算机实现第3页,共24页，2024年2月25日，星期天计算机的算法：

只能把每一个新位积与部分积（部分积的初值为零）相加，总共做n次加法（累加）。

部分积与位积相加时，只有n位与位积相加，其余部分并不参加运算。因此用n位的加法器就可完成乘法了。被乘数左移一位的操作改为部分积右移一位后与被乘数相加。只需用1个n位的寄存器存放部分积的高位，部分积的低位与乘数共用一个n位的寄存器，在乘数右移一位（计算该位位积后自动丢失）的同时将部分积最低一位移入。乘法完成后，原来存放乘数的寄存器中是乘积的低n位，乘数全部丢失，而硬件则节省了一个寄存器。被乘数10111101乘数0000部分积+10111011+000001011+101101011110右移一位00101111右移一位设计乘法逻辑第4页,共24页，2024年2月25日，星期天&&计数器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第5页,共24页，2024年2月25日，星期天[例1]X＝+0.1011B，Y＝－0.1101B，解：乘积的符号位用原码一位乘法计算X·Y[X]原=|X|=[Y]原=|Y|=0.10111.11010.10110.1101原码运算，必须把符号位与数值部分分开进行。符号位做异或运算，数值部分做无符号数相乘。Mostcomputersusea"shiftandadd"algorithmformultiplyingsmallintegers.第6页,共24页，2024年2月25日，星期天|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|第7页,共24页，2024年2月25日，星期天原码一位乘法流程图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次右移，时间太长。计数器乘数被乘数部分积第8页,共24页，2024年2月25日，星期天乘积的符号位原码运算，必须把符号位与数值部分分开进行。符号位做异或运算，数值部分做无符号数相乘。

两个原码表示的数（无论小数或整数）相乘，乘积的值是两数绝对值之积，符号是相乘两数符号位的异或值。两个尾数为n位的数相乘，乘积的尾数为2n位。Thesecondproblemisthatthebasicschoolmethodhandlesthesignwithaseparaterule("+with+yields+","+with-yields-",etc.).Thismethodismathematicallycorrect,butithastwoseriousengineeringproblems.Thefirstisthatitinvolves32intermediateadditionsina32-bitcomputer,or64intermediateadditionsina64-bitcomputer.Theseadditionstakealotoftime.第9页,共24页，2024年2月25日，星期天原码两位乘法按照乘数每两位的情况，一次求出对应于该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位第10页,共24页，2024年2月25日，星期天加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位第11页,共24页，2024年2月25日，星期天原码二位乘法的运算规则：当欠帐触发器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

第12页,共24页，2024年2月25日，星期天减X用加[-X]补实现。右移按补码右移规则进行。

当乘数的数值部分是N位（N必须是偶数），则共需做N/2次加法和N/2次右移。最后如果还有欠帐，再做一次+X。欠帐触发器C的初值为0。

由于在运算中有+2|X|，产生的进位可能侵占符号位，所以被乘数和部分积应该取3符号位。例2：X=-0.111111，Y=+0.111001，用原码二位乘法计算X*Y符号位单独处理，乘数的数值部分必须是偶数位。相乘的是两数的绝对值。原码二位乘法的运算规则：第13页,共24页，2024年2月25日，星期天解：[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第14页,共24页，2024年2月25日，星期天|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.001111

1111100

右移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第15页,共24页，2024年2月25日，星期天

在计算机系统内，由于电路故障或电磁干扰等原因，数据在存取或传送过程中可能产生错误。为了能发现或纠正这类错误，常采用具有能发现某些错误，或具有能确定错误的性质和准确的出错位置乃至能自动纠正错误的能力的编码方法，即数据校验码。Mostcodesare"systematic":thetransmittersendsafixednumberoforiginaldatabits,followedbyfixednumberofcheckbits(usuallyreferredtoasredundancyintheliterature)whicharederivedfromthedatabitsbysomedeterministicalgorithm.其实现原理是在合法的数据编码之间加进一些不允许出现的非法编码，使合法编码的码距增大。当合法的数据编码出现错误时，就变成非法编码。这就可以用检测编码的合法性来发现错误。Thereceiverappliesthesamealgorithmtothereceiveddatabitsandcomparesitsoutputtothereceivedcheckbits;ifthevaluesdonotmatch,anerrorhasoccurredatsomepointduringthetransmission.§3.7数据校验码第16页,共24页，2024年2月25日，星期天

由若干位代码组成的一个字叫“码字”，一种码制是若干种码字的组合。将两个码字逐位比较，有几个二进制位不同称为这两个码字间的距离。

只有一位不同的，称其码距为1。例如，3位二进制代码有8种状态，若一种码制用到全部8种码字，其码距为1。就是说，任何一个合法码字的一位或几位出错时，就变成另一个合法码字。一种码制中各码字间的最小距离称为该码制的“码距”。000111101001110010011100第17页,共24页，2024年2月25日，星期天一种码制中各码字间的最小距离称为该码制的“码距”。

若增大编码的冗余度，设计该码制时用4个二进制位来表示8个合法码字。由于只利用了全部16种状态中的8种来表示合法码，就可以把其余8种状态作为非法码，则码距可能增大到2。当一个合法码的一位出错时，将变成一个非法码而被发现。所增加的一位称为校验位。数据000001010011100101110111编码00000011010101101001101011001111非法码00100001011101001011100011101101出错第18页,共24页，2024年2月25日，星期天

合理的安排非法编码的数量和编码规则，增大合法码的码距就可以提高发现错误的能力，甚至能自动纠正错误；但表示一定数量的合法码所使用的二进制位数也增多，使数据存储和传送的数量增大，硬件开销也相应增大。常用的数据校验码有：奇偶校验码、海明校验码和循环冗余校验码等。

根据纠错理论，编码的最小距离与编码的检测、纠错能力的关系为：L—1=C+D其中：L是编码的最小距离，D是可以检测错误代码的位数，C是可以纠正错误代码的位数，D≥C。当L=3时，可检测出2个错误，或者可检测并纠正1位错误。当L=4时，可检测出3个错误，或者可检测出2位并纠正1位错误。第19页,共24页，2024年2月25日，星期天奇偶校验码

ParityCheckCode

奇偶校验码的编码方法是给n位的合法编码增加一个奇偶校验位，使其码距增加到2。任何一位出错（包括校验位）都会使代码的奇偶性改变，从而被发现。校验位可以放在最高数据位的左边，或最低数据位的右边。

若n+1位的奇偶校验码中“1”的个数为奇数称为奇校验，“1”的个数为偶数称为偶校验。

当n位信息代码中有偶数个1，则偶校验附加的校验位为0，而奇校验的校验位为1

。例如：数据代码

奇校验码

偶校验码1010101010100101010101101101101110110110Aparitybitisanerrordetectionmechanismthatcanonlydetectanoddnumberoferrors.设校验位在最右边第20页,共24页，2024年2月25日，星期天交叉奇偶校验

奇偶校验码广泛应用于存储器读写检查，数据传输过程中的检查等。对数据块的横向和纵向都有奇偶校验位。例如：A7A6A5A4A3A2A1A0

横向校验位第1字节11001011→1第2字节01111100→1第3字节10011010→0第4字节10010101→0

↓↓↓↓↓↓↓↓纵向校验位10111000交叉奇偶校验能够发现两个位同时出错。

奇偶校验能发现1位或者奇数个位同时出错，但不能发现偶数个位同时出错，也