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

,*,计算机组成原理,Principles of,Computer Organization,广义双语教学课程,http:/211.64.192.109/skyclass25/,青岛理工大学,校级精品课程,http:/,jx,.,qtech,.,edu,.,cn,/,ec,/C84/,1,第3章 运算方法和运算部件,( 3 ),A binary multiplier is an electronic circuit used in digital electronics, such as a computer, to multiply two binary numbers. It is built using binary adders.,Until the late 1970s, most minicomputers did not have a multiply instruction, and so programmers used a multiply routine” which repeatedly shifts and accumulates partial results, often written using loop unwinding. Early microprocessors also had no multiply instruction.,原码一位乘法,补码一位乘法,补码两位乘法,原码两位乘法,Unsigned Binary Multiplication,无符号数乘法,两个尾数为,n,位的数相乘，乘积的尾数为2,n,位,。,手算乘法的过程：,1011 被乘数, 1101 乘数,1011,0000,1011,1011,10001111,位积,乘积,需要,n,个寄存器保存位积,对应于乘数的位，将被乘数逐次左移一位加在左下方。,最后将,n,个位积相加，得到乘积。,计算机不能照搬手算的算法。,运算器一次只能完成两数的求和操作。,需要2,n,位的加法器,3. 3 二进制乘法运算,Binary Multiplication,Binary (Fixed-Point) Multiplication Arithmetic,被乘数左移，根据乘数每个位做不同运算，都不便于计算机实现,计算机的算法：,只能把每一个新位积与部分积（部分积的初值为零）相加，总共做,n,次加法（累加）。,部分积与位积相加时，只有,n,位与位积相加，其余部分并不参加运算。因此用,n,位的加法器就可完成乘法了。,被乘数左移一位的操作改为部分积右移一位后与被乘数相加,。,只需用1个,n,位的寄存器存放部分积的高位，部分积的低位与乘数共用一个,n,位的寄存器，在乘数右移一位（计算该位位积后自动丢失）的同时将部分积最低一位移入。,乘法完成后，原来存放乘数的寄存器中是乘积的低,n,位，乘数全部丢失，而硬件则节省了一个寄存器。,被乘数1011,1101 乘数,0000,部分积,+,1011,1011,+,0000,0101,1,+,1011,0101,1 110 右移一位,0010,11 11 右移一位,设计乘法逻辑,&,&,计数器,A,部分积,AF,BF,F/2A,Cd,C,乘数,B,被乘数,F,加法器,移位电路,C/2C,无符号数乘法逻辑原理图,运算前，先将被乘数送寄存器,B，,乘数送寄存器,C，,计数器的初值为,N，,部分积寄存器,A,清零。若乘数末位,Y,i,1，,部分积与被乘数在加法器相加。若乘数末位,Y,i,0，,则加法器输出的是部分积与0的和。寄存器,A,和,C,中的部分积和乘数都右移一位形成新的部分积，部分积的最低位移入,C,空出的最高位。如此重复,N,次，乘法计算完毕。乘积的高,N,位在,A,中，低,N,位在,C,中，原来在,C,中的乘数在移位中丢失。,CPA,例1,X+0.1011B，Y0.1101B，,解：,乘积的符号位,用原码一位乘法计算,XY,X,原,=,|X|=,Y,原,=,|Y|=,0.1011,1.1101,0.,1011,0.1101,原码运算，必须把符号位与数值部分分开进行。,符号位做异或运算，数值部分做无符号数相乘。,Most computers use a shift and add algorithm for multiplying small integers.,|X|= 0.1011， |Y|= 0.1101,高位部分积,0 0 0 0 0,低位部分积 /,乘数,1 1 0 1,初始状态,|XY|=0.10001111,右移 0 1 0 0 0 1 1 1 1,1 0 0 0 1 1 1 1,1,右移 0 0 1 1 0 1 1 1,1,0 1 1 0 1 1 1,1 1,+) 0 1 0 1 1,右移 0 0 0 1 0 1 1,1 1,0 0 1 0 1 1,1 1 0,+) 0 0 0 0 0,右移 0 0 1 0 1 1,1 1 0,0 1 0 1 1,1 1 0 1,+) 0 1 0 1 1,+) 0 1 0 1 1,XY0.10001111B,XY,原,=1.10001111,乘数最低位为1，加|,X|,乘数最低位为0，加0,乘数最低位为1，加|,X|,乘数最低位为1，加|,X|,原码一位乘法流程图,Y,Y,开始,结束,A0，,Cd,n,BX，CY,Cn,=1?,A(A)+(B),(,A),(C),右移一位,Cd,(,Cd,)1,Cd,=0?,N,N,Flowchart,如果乘数的数值部分是,N,位，则共需做,N,次加法，,N,次右移。乘积的数值部分是2,N,位。,原码乘法做的是绝对值相乘，相当于无符号数相乘。,右移按逻辑右移进行。,缺点：需做,N,次加法，,N,次右移，时间太长。,计数器,乘数,被乘数,部分积,乘积的符号位,原码运算，必须把符号位与数值部分分开进行。,符号位做异或运算，数值部分做无符号数相乘。,两个原码表示的数（无论小数或整数）相乘，乘积的值是两数绝对值之积，符号是相乘两数符号位的异或值。两个尾数为,n,位的数相乘，乘积的尾数为2,n,位。,The second problem is that the basic school method handles the sign with a separate rule (+ with + yields +, + with - yields -, etc.).,This method is mathematically correct, but it has two serious engineering problems. The first is that it involves 32 intermediate additions in a 32-bit computer, or 64 intermediate additions in a 64-bit computer. These additions take a lot of time.,原码两位乘法,按照乘数每两位的情况，一次求出对应于该2位的部分积。增加少量逻辑电路，可使乘法的速度提高一倍。,乘数,的相邻,两位,Y,i,-1,Y,i,有4种状态组合，分别对应一种操作：,Y,i,-1,Y,i,操 作,0 0,0 1,1 0,1 1,相当于0,X,相当于1,X,相当于2,X,相当于3,X,部分积,P,i,+0,后右移2位,部分积,P,i,+X,后右移2位,部分积,P,i,+2X,后右移2位,部分积,P,i,+3X,后右移2位,加2,X,很容易实现,。,把,X,左移一位,，,或者把,X,向左,斜传,送一位。,加3,X,一般不能一次完成,。,分两次（3,X=X+2X）,又降低了速度,。,如果令 3,X=4XX,，,形式上看好象需要2次,。,实际上可以这样,：,本次运算只做,减,X,，,用一个,欠帐触发器,C,记下欠加4,X,，,下一步操作时补上。,由于本次累加后,，,部分积要右移2位,，,相当于乘数相对左移2位,。,此时做+,X,相当于前一步+4,X,。,所以,，,3,X=4XX,只需要做一次,。,欠帐触发器,C,的初值为0。,Y,i,-1,Y,i,操 作,0 0,0 1,1 0,1 1,相当于0,X,相当于1,X,相当于2,X,相当于3,X,部分积,P,i,+0,后右移2位,部分积,P,i,+X,后右移2位,部分积,P,i,+2X,后右移2位,部分积,P,i,+3X,后右移2位,原码二位乘法的运算规则：,当欠帐触发器,C=0,时，,Y,i,-1,Y,i,C,0,0 0,0 1 0,1,0 0,1 1 0,操 作,部分积,P,i,+0,后右移2位,部分积,P,i,+X,后右移2位,部分积,P,i,+2X,后右移2位,部分积,P,i,X,后右移2位,0,C,0C,0C,1C,当欠帐触发器,C=1,时，,Y,i,-1,Y,i,C,0,0 1,0 1 1,1,0 1,1 1 1,操 作,部分积,P,i,+X,后右移2位,部分积,P,i,+2X,后右移2位,部分积,P,i,+-X,补,后右移2位,部分积,P,i,+0,后右移2位,0,C,0C,1C,1C,减,X,用加-,X,补,实现。,右移按补码右移规则进行。,当乘数的数值部分是,N,位（,N,必须是偶数,），则共需做,N/2,次加法和,N/2,次右移。最后如果还有,欠帐，再做一次+,X。,欠帐触发器,C,的初值为0。,由于在运算中有+2|,X|，,产生的进位可能侵占符号位，所以被乘数和部分积应该取3符号位。,例2：,X= -0.111111，Y= +0.111001，,用原码二位乘法计算,X*Y,符号位单独处理,，,乘数,的数值部分,必须是偶数位,。,相乘的是两,数的,绝对值。,原码二位乘法的运算规则：,解：,X,原,=,1.111111,乘积的符号位,|,X,|=0.111111,|,2,X,|=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. 0 0 0 0 0 0,乘数,欠帐触发器,C,1 1 1 0,0 1,0,初始状态,000. 1 1 1 0 0 0,0 0 0 1 1 1,111. 1 1 1 0 0 1,0 0 0 1 1 1,1,右移,2位,111. 1 0 0 1 0 0,+ 111. 0 0 0 0 0 1,000. 1 0 0 0 1 1,0 1 1 1,1 1,0,右移,2位,010. 0 0 1 1 0 1,+ 001. 1 1 1 1 1 0,000. 0 0 1 1 1 1,1 1 1 1,1 0,0,右移,2位,000. 1 1 1 1 1 1,+ 000. 1 1 1 1 1 1,+ 000. 1 1 1 1 1 1,Y,i,-1,Y,i,C010,，,加|,X|,0C,Y,i,-1,Y,i,C100,，,加|2,X| ,0C,Y,i,-1,Y,i,C,110，,加-|,X|,补,1,C,C1，,加|,X|,X*Y,原,=1. 111000000111,X*Y= -0.111000000111,|X*Y|,= 0. 111000000111,在计算机系统内,，,由于电路故障或电磁干扰等原因,，,数据在存取或传送过程中可能产生错误,。,为了能发现或纠正这类错误,，,常采用具有能发现某些错误,，,或具有能确定错误的性质和准确的出错位置乃至能自动纠正错误的能力的编码方法,，,即数据校验码,。,Most codes are ,systematic,: the transmitter sends a fixed number of original data bits, followed by fixed number of check bits (usually referred to as redundancy in the literature) which are derived from the data bits by some,deterministic algorithm,.,其实现原理是在合法的数据编码之间加进一些不允许出现的非法编码，使合法编码的码距增大。当合法的数据编码出现错误时，就变成非法编码。这就可以用检测编码的合法性来发现错误。,The receiver applies the same algorithm to the received data bits and compares its output to the received check bits; if the values do not match, an error has occurred at some point during the transmission.,3.7,数据校验码,由若干位代码组成的一个字叫“,码字,”，一种码制是若干种码字的组合。将,两个码字逐位比较,，,有几个二进制位不同,称为这,两个码字间的距离,。,只有一位不同,的，称其,码距为,1,。例如，,3,位二进制代码有,8,种状态，若一种码制用到全部,8,种码字，其码距为,1,。就是说，任何一个合法码字的一位或几位出错时，就变成另一个合法码字。,一种码制中各码字间的最小距离称为该码制的“,码距,”,。,000,111,101,001,110,010,011,100,一种码制中各码字间的最小距离称为该码制的“码距”,。,若增大编码的,冗余度,，设计该码制时用,4,个二进制位来表示,8,个合法码字。由于只利用了全部,16,种状态中的,8,种来表示合法码，就可以把其余,8,种状态作为非法码，则码距可能增大到,2,。当一个合法码的一位出错时，将变成一个非法码而被发现。,所增加的一位称为,校验位,。,数据,000,001,010,011,100,101,110,111,编码,000,0,001,1,010,1,011,0,100,1,101,0,110,0,111,1,非法码,0010,0001,0111,0100,1011,1000,1110,1101,出错,合理的安排非法编码的数量和编码规则，增大合法码的码距就可以提高发现错误的能力，甚至能自动纠正错误；但表示一定数量的合法码所使用的二进制位数也增多，使数据存储和传送的数量增大，硬件开销也相应增大。,常用的数据校验码有：,奇偶校验码,、,海明校验码,和,循环冗余校验码,等。,根据纠错理论，编码的最小距离与编码的检测、纠错能力的关系为：,L1 = C+D,其中：,L,是,编码,的,最小距,离，,D,是,可以检测错误代码,的,位数,，,C,是,可以纠正错误代码,的,位数,，,DC。,当,L=3,时，可,检测出,2,个错误,，或者,可检测并纠正,1,位错误,。,当,L=4,时,，,可,检测,出,3,个错误,，,或者可,检测,出,2,位并纠正,1,位错误,。,奇偶校验码,Parity Check Code,奇偶校验码的编码方法是给,n,位的合法编码增加一个,奇偶校验位,，使其,码距增加到,2,。任何,一位出错,（包括,校验,位）都会使,代码,的,奇偶性,改变,，从而被发现。,校验位可以放在最高数据位的左边，或最低数据位的右边。,若,n+1,位的奇偶校验码中,“,1,”,的个数为奇数,称为,奇校验,，“,1,”,的个数为偶数,称为,偶校验。,当,n,位信息代码中有偶数个,1,，则,偶校验附加的校验位为,0,，而,奇校验的校验位为,1,。例如：,数据代码,奇校验码,偶校验码,101010,101010,0,101010,1,011011,011011,1,011011,0,A,parity bit,is an error detection mechanism that can only detect an odd number of errors.,设校验位在最右边,交叉奇偶校验,奇偶校验码广泛应用于存储器读写检查，数据传输过程中的检查等。,对数据块的横向和纵向都有奇偶校验位。例如：,A,7,A,6,A,5,A,4,A,3,A,2,A,1,A,0,横向校验位,第,1,字节,1 1 0 0 1 0 1 1,1,第2,字节,0 1 1 1 1 1 0 0,1,第3,字节,1 0 0 1 1 0 1 0,0,第4,字节,1 0 0 1 0 1 0 1,0, ,纵向校验位,1 0 1 1 1 0 0 0,交叉奇偶校验能够发现两个位同时出错。,奇偶校验能发现,1,位或者奇数个位同时出错，但不能发现偶数个位同时出错，也没有纠错能力。,计算机组成原理设计性作业,课题1 定点运算器设计,设计一个简单的16位定点运算器逻辑结构。,画出逻辑图，说明所设计的定点运算器是怎样进行定点补码加法运算、减法运算和逻辑运算的。,列出运算器做不同运算时的控制信号。,在基本的定点运算器基础上，如果要求计算机还能做定点乘法、除法运算，可以怎样设计？,实验课题1,ALU,设计,实验内容：,按照题目要求设计一个16位,ALU,的逻辑，决定外部的端口（名称、有效电平）和内部各元件的连接，画出系统框图和逻辑图，设计仿真数据，用,VHDL,编程和仿真。,一、主要元件设计,14位并行进位加法器,功能要求：能完成两个4位二进制数（补码和无符号数）的加法和逻辑加运算。内部有并行进位链。可以扩展成多位组。,2组间并行进位链逻辑,功能要求：4个4位小组的组间并行进位链逻辑。,将组间并行进位链逻辑与4个4位超前进位加法器连接可以构成16位超前进位加法器。可参考74182的逻辑函数。,（4学时）,实验课题1,ALU,设计,实验内容：,按照题目要求设计一个16位,ALU,的逻辑，决定外部的端口（名称、有效电平）和内部各元件的连接，画出系统框图和逻辑图，设计仿真数据，用,VHDL,编程和仿真。,一、主要元件设计,3函数发生器,功能要求：能把输入的两个16位二进制数进行变换，与后面的16位超前进位加法器配合完成两个16位二进制数（补码和无符号数）的8种算术运算（有些运算考虑低位来的进位）和8种逻辑运算。,提示：,ALU,的功能参考数字逻辑课程的“多功能加法器”实验。,实验课题1,ALU,设计,二、顶层设计,用层次结构设计的方法设计一个16位,ALU。,内部包括4个,4位并行进位加法器,、,组间并行进位链、16位函数发生器,等。,功能要求：能完成两个16位二进制数以及低位来的进位的8种算术运算和8种逻辑运算。,可参考74181。,三、仿真,设计仿真波形数据，要考虑到所有可能的情况。在实验报告中必须清楚说明仿真波形数据是怎样设计的。,四、深入的课题,上面设计的,ALU,还没有标志寄存器，如果想为,ALU,增加标志寄存器，应该怎样设计？标志位是怎样产生的？,Homework,3 - 16，17，20，23, 25,When thinking of multiplication as repeated addition, the number to be multiplied is called the multiplicand, while the number of multiples is called the multiplier”（,乘数,）.,The result of a multiplication is called a product.,The numbers to be multiplied are generally called the factors or multiplicands”（,被乘数,）.,斜传电路,