计算机组成原理第4讲_乘法

计算机组成原理PrinciplesofComputerOrganization广义双语教学课程青岛理工大学校级精品课程第3章运算方法和运算部件(3)Abinarymultiplierisanelectroniccircuitusedindigitalelectronics,suchasacomputer,tomultiplytwobinarynumbers.Itisbuiltusingbinaryadders.Untilthelate1970s,mostminicomputersdidnothaveamultiplyinstruction,andsoprogrammersusedamultiplyroutine”whichrepeatedlyshiftsandaccumulatespartialresults,oftenwrittenusingloopunwinding.Earlymicroprocessorsalsohadnomultiplyinstruction.原码一位乘法补码一位乘法补码两位乘法原码两位乘法UnsignedBinaryMultiplication无符号数乘法两个尾数为n位的数相乘，乘积的尾数为2n位。手算乘法的过程：1011被乘数×1101乘数101100001011101110001111位积乘积需要n个寄存器保存位积对应于乘数的位，将被乘数逐次左移一位加在左下方。最后将n个位积相加，得到乘积。计算机不能照搬手算的算法。运算器一次只能完成两数的求和操作。需要2n位的加法器§3.3二进制乘法运算BinaryMultiplicationBinary(Fixed-Point)MultiplicationArithmetic被乘数左移，根据乘数每个位做不同运算，都不便于计算机实现计算机的算法：只能把每一个新位积与部分积（部分积的初值为零）相加，总共做n次加法（累加）。部分积与位积相加时，只有n位与位积相加，其余部分并不参加运算。因此用n位的加法器就可完成乘法了。被乘数左移一位的操作改为部分积右移一位后与被乘数相加。只需用1个n位的寄存器存放部分积的高位，部分积的低位与乘数共用一个n位的寄存器，在乘数右移一位（计算该位位积后自动丢失）的同时将部分积最低一位移入。乘法完成后，原来存放乘数的寄存器中是乘积的低n位，乘数全部丢失，而硬件则节省了一个寄存器。被乘数10111101乘数0000部分积+10111011+000001011+101101011110右移一位00101111右移一位设计乘法逻辑&&计数器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[例1]X＝+0.1011B，Y＝－0.1101B，解：乘积的符号位110SSYX用原码一位乘法计算X·Y[X]原=|X|=[Y]原=|Y|=0.10111.11010.10110.1101原码运算，必须把符号位与数值部分分开进行。符号位做异或运算，数值部分做无符号数相乘。Mostcomputersuseashiftandaddalgorithmformultiplyingsmallintegers.|X|=0.1011，|Y|=0.1101高位部分积00000低位部分积/乘数1101初始状态|X·Y|=0.10001111右移010001111100011111右移001101111011011111+)01011右移000101111001011110+)00000右移001011110010111101+)01011+)01011X·Y＝－0.10001111B[X·Y]原=1.10001111乘数最低位为1，加|X|乘数最低位为0，加0乘数最低位为1，加|X|乘数最低位为1，加|X|原码一位乘法流程图YY开始结束A←0，Cd←nB←X，C←YCn=1?A←(A)+(B)(A),(C)右移一位Cd←(Cd)—1Cd=0?SSSYXPNNFlowchart如果乘数的数值部分是N位，则共需做N次加法，N次右移。乘积的数值部分是2N位。原码乘法做的是绝对值相乘，相当于无符号数相乘。右移按逻辑右移进行。缺点：需做N次加法，N次右移，时间太长。计数器乘数被乘数部分积乘积的符号位SSYX原码运算，必须把符号位与数值部分分开进行。符号位做异或运算，数值部分做无符号数相乘。两个原码表示的数（无论小数或整数）相乘，乘积的值是两数绝对值之积，符号是相乘两数符号位的异或值。两个尾数为n位的数相乘，乘积的尾数为2n位。Thesecondproblemisthatthebasicschoolmethodhandlesthesignwithaseparaterule(+with+yields+,+with-yields-,etc.).Thismethodismathematicallycorrect,butithastwoseriousengineeringproblems.Thefirstisthatitinvolves32intermediateadditionsina32-bitcomputer,or64intermediateadditionsina64-bitcomputer.Theseadditionstakealotoftime.原码两位乘法按照乘数每两位的情况，一次求出对应于该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位加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位原码二位乘法的运算规则：当欠帐触发器C=0时，Yi-1YiC000010100110操作部分积Pi+0后右移2位部分积Pi+X后右移2位部分积Pi+2X后右移2位部分积Pi—X后右移2位0→C0→C0→C1→C当欠帐触发器C=1时，Yi-1YiC001011101111操作部分积Pi+X后右移2位部分积Pi+2X后右移2位部分积Pi+[-X]补后右移2位部分积Pi+0后右移2位0→C0→C1→C1→C减X用加[-X]补实现。右移按补码右移规则进行。当乘数的数值部分是N位（N必须是偶数），则共需做N/2次加法和N/2次右移。最后如果还有欠帐，再做一次+X。欠帐触发器C的初值为0。由于在运算中有+2|X|，产生的进位可能侵占符号位，所以被乘数和部分积应该取3符号位。例2：X=-0.111111，Y=+0.111001，用原码二位乘法计算X*Y符号位单独处理，000YXP乘数的数值部分必须是偶数位。相乘的是两数的绝对值。原码二位乘法的运算规则：解：[X]原=1.111111乘积的符号位101000YXP|X|=0.111111|2X|=001.111110例2：X=-0.111111，Y=+0.111001，用原码二位乘法计算X*Y[Y]原=0.111001|Y|=0.111001[-|X|]补=1.000001|X|=0.111111,|Y|=0.111001,|2X|=001.111110,[-|X|]补=1.000001高位部分积000.000000乘数欠帐触发器C1110010初始状态000.111000000111111.1110010001111右移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在计算机系统内，由于电路故障或电磁干扰等原因，数据在存取或传送过程中可能产生错误。为了能发现或纠正这类错误，常采用具有能发现某些错误，或具有能确定错误的性质和准确的出错位置乃至能自动纠正错误的能力的编码方法，即数据校验码。Mostcodesaresystematic:thetransmittersendsafixednumberoforiginaldatabits,followedbyfixednumberofcheckbits(usuallyreferredtoasredundancyintheliterature)whicharederivedfromthedatabitsbysomedeterministicalgorithm.其实现原理是在合法的数据编码之间加进一些不允许出现的非法编码，使合法编码的码距增大。当合法的数据编码出现错误时，就变成非法编码。这就可以用检测编码的合法性来发现错误。Thereceiverappliesthesamealgorithmtothereceiveddatabitsandcomparesitsoutputtothereceivedcheckbits;ifthevaluesdonotmatch,anerrorhasoccurredatsomepointduringthetransmission.§3.7数据校验码由若干位代码组成的一个字叫“码字”，一种码制是若干种码字的组合。将两个码字逐位比较，有几个二进制位不同称为这两个码字间的距离。只有一位不同的，称其码距为1。例如，3位二进制代码有8种状态，若一种码制用到全部8种码字，其码距为1。就是说，任何一个合法码字的一位或几位出错时，就变成另一个合法码字。一种码制中各码字间的最小距离称为该码制的“码距”。000111101001110010011100一种码制中各码字间的最小距离称为该码制的“码距”。若增大编码的冗余度，设计该码制时用4个二进制位来表示8个合法码字。由于只利用了全部16种状态中的8种来表示合法码，就可以把其余8种状态作为非法码，则码距可能增大到2。当一个合法码的一位出错时，将变成一个非法码而被发现。所增加的一位称为校验位。数据000001010011100101110111编码00000011010101101001101011001111非法码00100001011101001011100011101101出错合理的安排非法编码的数量和编码规则，增大合法码的码距就可以提高发现错误的能力，甚至能自动纠正错误；但表示一定数量的合法码所使用的二进制位数也增多，使数据存储和传送的数量增大，硬件开销也相应增大。常用的数据校验码有：奇