Lecture 6 定点乘法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,问题,分析手工乘法运算方法在计算机实现时面临的困难,原码一位乘中，如何把乘法运算转化为加法运算的？,原码一位乘中，需要多次通过加法运算和移位得到部分和，效率低，如何提高乘的效率？,A,=,0.1101,B,=0.1011,A,B,=,0.1 1 0 1,0.1 0 1 1,定点乘法运算,课程结构,计算机系统统计,硬件,运算器,数据表示,数据数据,定点,原码,反码,补码,移码,浮点,一般表示,规格化,IEEE754,非数值数据,字符,汉字,BCD,码,校验码,奇偶校验,海明校验,循环冗余校验,运算方法,定点数补码加减,乘除,原码一位乘,补码一位乘,并行乘法,原码除法,恢复余数,加减交替,浮点数,加减乘除,规格化,溢出判断,运算器,一般运算,快速运算,典型,ALU,存储器,控制器,总线,输入输出,软硬件接口,软件,分析笔算乘法,A,=,0.1101,B,=0.1011,A,B,=,0.10001111,0.1 1 0 1,0.1 0 1 1,1 1 0 1,1 1 0 1,0 0 0 0,1 1 0 1,0.1 0 0 0 1 1 1 1,符号位单独处理,乘数的某一位决定是否加被乘数,4,个位积一起相加,8,位加法,乘积的位数扩大一倍,乘积的符号心算求得,？,笔算乘法改进,A,B,=,A,0.1011,=0.1,A,+0.00,A,+0.001,A,+0.0001,A,=0.1,A,+0.00,A,+,0.001,(,A,+0.1,A,),=0.1,A,+,0.01,0,A,+0.1(,A,+0.1,A,),=,0.1,1,A,+0.1,0,A,+0.1(,1,A,+0.1(,1,A,),=,2,-1,1,A,+2,-1,0,A,+2,-1,(,1,A,+,2,-1,(,1,A,+,0),第一步,0,+,被乘数,A,第二步 右移 一 位，得新的部分积,第八步 右移 一 位，得结果,第三步 部分积,+,被乘数,右移一位,改进后的笔算乘法过程（竖式）,0.0 0 0 0,0.1 1 0 10.1 1 0 1,0.1 1 0 1,0.0 0 0 0,0.1 1 0 1,初态，部分积,=0,乘数为,1,，加被乘数,乘数为,1,，加被乘数,乘数为,0,，加,0,1.0 0 1 1,1,0.1 0 0 1,1 1,1.0 0 0 1,1 1 1,乘数为,1,，加 被乘数,0.1 0 0 0,1 1 1 1,1,，得结果,1 0 1 1,=,0.0 1 1 0,1,，形成新的部分积,1,1 0 1,=,0.1 0 0 1,1,，形成新的部分积,1 1,1 0,=,0.0 1 0 0,1,，形成新的部分积,1 1 1,1,=,部 分 积 乘 数 说 明,笔算小结,被乘数只与部分积的高位相加,由乘数的末位决定被乘数是否与原部分积相加，,然后,1,位形成新的部分积,，同时,乘数,1,位,（末位移丢），空出高位存放部分积的低位。,硬件,3,个寄存器（被乘数、乘数、部分积），具有移位功能,1,个,n,位全加器,乘法,运算可用,加和移位实现,n,=4,，,加,4,次,，,移,4,次,以小数为例,设,x,原,=,x,0,.,x,1,x,2,x,n,y,原,=,y,0,.,y,1,y,2,y,n,=(,x,0,y,0,).,x,*,y,*,x,y,原,=(,x,0,y,0,).(0.,x,1,x,2,x,n,)(0.,y,1,y,2,y,n,),式中,x,*,=0.,x,1,x,2,x,n为,x,的绝对值,y,*,=0,.,y,1,y,2,y,n,为,y,的绝对值,乘积的符号位单独处理,x,0,y,0,数值部分为绝对值相乘,x,*,y,*,原码一位乘,运算规则,x,*,y,*=,x,*(0.,y,1,y,2,y,n,),=,x,*(,y,1,2,-1,+,y,2,2,-2,+,y,n,2,-,n,),=2,-1,(,y,1,x,*+2,-1,(,y,2,x,*+2,-1,(,y,n,x,*+0),z,1,z,n,z,0,=0,z,1,=2,-1,(,y,n,x,*+,z,0,),z,2,=2,-1,(,y,n,-1,x,*+,z,1,),z,n,=2,-1,(,y,1,x,*z,n,-1,),z,0,原码一位乘,递推公式,例,已知,x,=,0.1110,y,=0.1101,求,x,y,原,解：,数值部分的运算,0.0 0 0 0,0.1 1 1 0,0.1 1 1 0,0.0 0 0 0,0.1 1 1 0,0.1 1 1 0,部分积 初态,z,0,=0,部 分 积 乘 数 说 明,0.0 1 1 1,0,1.0 0 0 1,1 0,1.0 1 1 0,1 1 0,0.1 0 1 1,0 1 1 0,1,，,得,z,4,逻辑右移,1 1 0 1,=,0.0 1 1 1,1,，,得,z,1,0,1 1 0,=,0.0 0 1 1,1,，,得,z,2,1 0,1 1,=,0.1 0 0 0,1,，,得,z,3,1 1 0,1,=,逻辑右移,逻辑右移,逻辑右移,+,+,+,+,+,x,*,+0,+,x,*,+,x,*,数值部分按绝对值相乘,乘积的符号位,x,0,y,0,=1 0=1,x,*,y,*=0.1 0 1 1 0 1 1 0,则,x,y,原,=1.1 0 1 1 0 1 1 0,特点,绝对值运算,逻辑移位,结果,用移位的次数判断乘法是否结束,原码一位乘,逻辑实现,(,x,),(,y,)A,的操作流程,原码两位乘,(,自学,),原码乘,符号位,和,数值位,部分,分开运算,两位乘,每次用,乘数的,2,位判断,原部分积,是否加,和,如何加,被乘数,1 1,1 0,0 1,0 0,加“,0”2,加,1,倍的被乘数,2,加,2,倍的被乘数,2,加,3,倍的被乘数,2,3,？,先,减,1,倍,的被乘数,再,加,4,倍,的被乘数,4,1,3,100,01,11,新的部分积,乘数,y,n,-1,y,n,(X+4Y)/4=X/4+Y,部分积加,4,倍的被乘数，然后右移,2,位,等价于,部分积右移两位，然后加被乘数,1,1 1,1,1 0,1,0 1,1,0 0,0,1 1,0,1 0,0,0 1,0,0 0,操 作 内 容,标志位,C,j,乘数判断位,y,n,-1,y,n,z,2,y,*2,C,j,保持,“,0”,z,2,y,*2,C,j,保持,“,1z,x,*2,y,*2,C,j,保持,“,1”,z,+2,x,*2,y,*2,C,j,保持,“,0”,z,+,x,*2,y,*2,C,j,保持,“,0”,共有操作,+,x,*+2,x,*,x,*,2,实际操作,+,x,*,补,+2,x,*,补,+,x,*,补,2,补码移,z,x,*2,y,*2,C,j,置,“,1”,z,+2,x,*2,y,*2,C,j,置,“,0”,z,+,x,*2,y,*2,C,j,置,“,0”,原码两位乘,运算规则,(X+4Y)/4=X/4+Y,部分积加,4,倍的被乘数，然后右移,2,位,等价于,部分积右移两位，然后加被乘数,例,已知,x,=0.111111,y,=,0.111001,求,x,y,原,0 0 0.0 0 0 0 0 0,0 0 0.1 1 1 1 1 1,0 0 0.1 1 1 1 1 1,0 0.1 1 1 0 0 1,0,初态,z,0,=0,+,x,*,，,C,j,=0,0,1 0,.0 0 1 1 0 1,1 1,0 0 0.1 1 1 0 0 0,0 0 0 1 1 1,1,1 1,.1 0 0 1 0 0,0 1 1 1,0 0 1.1 1 1 1 1 0,+2,x,*,，,C,j,=0,1 1 1.0 0 0 0 0 1,x,*,，,C,j,=1,0 0 0.1 1 1 1 1 1,+,x,*,，,C,j,=0,0,0 0 0.0 0 1 1 1 1,1 1,0 0 1 1,1 0,2,0,0 0 0.,1 0,0 0 1 1,0 1 1 1,0 0,1 1,2,1,1 1 1.,1 1,1 0 0 1,0 0 0 1 1 1,0 0,2,C,j,部 分 积 乘 数,说 明,补码右移,补码右移,解：,数值部分的运算,补码右移,+,+,+,+,数值部分的运算,乘积的符号位,x,0,y,0,=0 1=1,x,*,y,*=0.1 1 1 0 0 0 0 0 0 1 1 1,则,x,y,原,=1.1 1 1 0 0 0 0 0 0 1 1 1,结果,特点,绝对值的补码运算,算术移位,用,移位的次数,判断乘法是否结束,原码两位乘和原码一位乘比较,符号位,操作数,移位,移位次数,最多加法次数,x,0,y,0,x,0,y,0,绝对值,绝对值的补码,逻辑右移,算术右移,n,n,n,2,（,n,为偶数）,n,2,+1,（,n,为偶数）,思考,n,为奇数时，原码两位乘,移？次,最多加？次,原码一位乘,原码两位乘,原码两位乘,两个例子,例,X=0.100111,，,Y=0.100111,，则,:-|X|,补,1.011001,部分积 乘数 欠位,C,0,00.000000 00 1001,11 0,1,C,+-X,补,111.011001,111.011001,右移,2,位,111.110110 01 00 10,01 1,0C,+2X 001.001110,001.000100,右移,2,位,000.010001 0001 00,10 0,0,C,+2X 001.001110,001.011111,右移,2,位,000.,010111 110001,00 0,原码两位乘,两个例子,例,X=0.100111,0,，,Y=0.100111,0,，则,:-|X|,补,1.0110010,部分积 乘数 欠位,C,+0 0,00.0000000 00 100111,0,0,0,0,C,右移,2,位,0,00.0000000 00 001001,11 0,1,C,+-X,补,111.0110010,111.0110010,右移,2,位,111.1101100 1000 0010,01 1,0,C,+2X 001.0011100,001.0001000,右移,2,位,000.0100010 001000 00,10 0,0,C,+2X 001.0011100,001.0111110,右移,2,位,000.,0101111 10001000,00 0,原码两位乘,两个例子,X=0.100111,0,，,Y=0.100111,0,，则,:-|X|,补,1.0110010,部分积乘数欠位,C,000 0000000 0 10011,10 0,0,C,+2x 001 0011100,001 0011100,右移,2,位,000 0100111 00,0 100,11 0,1,C,+-|x|,补,111 0110010,111 1011001,右移,2,位,111 1110110 0100 0 1,00 1,0,C,+x 000,1001110,000 1000100,右移,2,位,000 0010001 000100,0 1 0,0,C,+x 000 1001110,000 1011111,右移,1,位,000,0101111 1000100,0,特点：符号 位参与 乘法运算，运算结果用补码表示,补码与真值的关系,设,x,补,x,0,.x,1,x,2,x,n,当真值,x=0,时，,x,0,=0,x,补,x=0x,1,x,2,x,n,=,当真值,x0,时，,x,0,=1,x,补,1.x,1,x,2,x,n,=2+x,x=x,补,2,1.x,1,x,2,x,n,2,=-1,0.x,1,x,2,x,n,-1,综合：,x=-x,0,+,补码一位乘法,设被乘数,X,补,=x,0,.x,1,x,2,x,n,乘数,Y,补,y,0,.y,1,y,2,y,n,，则有,XY,补,=X,补,(-y0+,),证明,：,(1)X,正负任意，,Y,为正数,X,补,=2+X=2,n+1,+X mod 2,Y,补,=Y,则：,X,补,Y,补,2,n+1,Y+X,Y=2+X Y mod 2,所以：,X,补,Y,补,=X,Y,补,X,补,(0.y,1,y,2,y,n,),(2)X,正负任意，,Y,为负数,X,补,=x,0,.x,1,x,2,x,n,，,Y,补,1.y,1,y,2,y,n,=2+Y,Y=0.y,1,y,2,y,n,-1,XY=X(0.y,1,y,2,y,n,)-X,X,Y,补,=X(0.y,1,y,2,y,n,),补,+-X,补,=X,补,(0.y,1,y,2,y,n,)+-X,补,综合：,X,Y,补,=X,补,(-Y,0,+),补码一位乘法,0.xxxx,10.xxxx,10000.xxxx,0.yyyy,yyyy0.0000,设,x,补,=,x,0,.,x,1,x,2,x,n,y,补,=,y,0,.y,1,y,2,y,n,x,y,补,=,x,补,(0.,y,1,y,n,),x,补,y,0,=,x,补,(,y,1,2,-1,+,y,2,2,-2,+,y,n,2,-,n,),x,补,y,0,=,x,补,(,y,0,+,y,1,2,-1,+,y,2,2,-2,+,y,n,2,-,n,),=,x,补,y,0,+,(,y,1,y,1,2,-1,),+,(,y,2,2,-1,y,2,2,-2,),+(,y,n,2,-(,n,-1),y,n,2,-,n,),=,x,补,(,y,1,y,0,)+(,y,2,y,1,)2,-1,+(,y,n,y,n,-1,)2,-(,n,-1),+(0,y,n,)2,-n,),Y,0,2,0,+Y,1,2,-1,+,Y,n,2,-,n,x,补,=+,x,补,2,-1,=2,0,2,-1,2,-2,=2,-1,2,-2,2,-1,2,-2,=,x,补,(,y,1,y,0,)+(,y,2,y,1,)2,-1,+(,y,n,+1,y,n,)2,-,n,附加位,y,n,+1,补码一位乘运算规则（,Booth,算法）,z,0,补,=0,z,1,补,=2,-1,(,y,n,+1,y,n,),x,补,+,z,0,补,y,n,+1,=0,z,n,补,=2,-1,(,y,2,y,1,),x,补,+,z,n,-1,补,x,y,补,=(,y,1,y,0,),x,补,+,z,n,补,最后一步不移位,如何实现,y,i,+1,y,i,?,0 0,0 1,1 0,1 1,1,+,x,补,1,+,x,补,1,1,0,1,-1,0,y,i,y,i,+1,操作,y,i,+1,y,i,补码一位乘运算规则（,Booth,算法）,x,y,补,=(y,1,-y,0,),x,补,+,(y,2,-y,1,),x,补,+(y,3,-y,2,),x,补,+,(y,n,-y,n-1,),x,补,+,(y,n+1,-y,n,),x,补,+0,2,-1,2,-1,2,-1,2,-1,运算规则如下：,符号位参与运算，运算的数均以补码表示。,被乘数取双符号位参加运算，部分积初值为,0,。,乘数取单符号位,乘数末位增设附加位,y,n+1,，且初值为,0,。,按下表进行操作。,(,右移为算术右移,),按照上述算法进行,n+1,步操作，但第,n+1,步不再移位，,补码一位乘运算规则（,Booth,算法）,例,已知,x,=+0.0011,y,=,0.1011,求,x,y,补,解：,0 0.0 0 0 0,1 1.1 1 0 1,1 1.1 1 0 1,0 0.0 0 1 1,1 1.1 1 0 1,0 0.0 0 1 1,1 1.1 1 0 1,1.0 1 0 1,0,0 0.0 0 0 1,1,1 1.1 1 0 1,1 1,0 0.0 0 0 1,1 1 1,1 1.1 1 0 1,1 1 1 1,x,补,=0.0011,y,补,=1.0101,x,补,=1.1101,+,x,补,1 1.,1,1 1 0,1,1 0 1 0,1,1,+,x,补,0 0.,0,0 0 0,1 1,1 0 1,0,1,+,x,补,1 1.,1,1 1 0,1 1 1,1 0,1,1,0 0.,0,0 0 0,1 1 1 1,1,0,1,+,x,补,+,x,补,x,y,补,=1.11011111,最后一步不移位,补码右移,补码右移,补码右移,补码右移,+,+,+,+,+,补码一位乘,Booth,算法的硬件配置,A,、,B,、,Q,均,n,+2,位,移位和加受末两位乘数控制,0,A,部分积,n,+1,n,2,位加法器,控 制 门,0 B,被乘数,n,+1,0 Q,乘数,n,n,+1,移位和加,控制逻辑,计数器,C,G,M,00,11,01,10,右移,补码一位乘,Booth,算法流程,阵列乘法器,不带符号二进制数,a4 a3 a2 a1 a0,b4 b3 b2 b1 b0 0 0 0 0 0,a4b0 a3b0 a2b0 a1b0 a0b0,a4b1 a3b1 a2b1 a1b1 a0b1,a4b2 a3b2 a2b2 a1b2 a0b2,a4b3 a3b3 a2b3 a1b3 a0b3,a4b4 a3b4 a2b4 a1b4 a0b4,+,+,+,+,+,+,+,+,+,+,阵列乘法器,T时刻,6T,时刻,7T,时刻,12T,时刻,13T,时刻,T+(n-1)6T,时刻,T+(n-1)6T-T,时刻,T+(n-1)6T+,2T,时刻,T+(n-1)6T+5T,时刻,T+(n-1)6T+(n-2)2T+T,时刻,最后一次进位：,2T+(n-1)6T+(n-1)2T,时刻,乘法最高位：,2T+(n-1)6T+(n-1)2T+T,时刻,=8(n-1)T+3T=(8n-5)T,为什么不是加,5T,？,如果与门运算需要,2T,，则总时延为,(4n-2)2T,原理：转化为两个正数乘，然后利用不带符号陈列乘法器。结果的符号位单独求，并对结果进行求补。算前求补乘法器算后求补,阵列乘法器,带符号二进制数,E=0,时，输入和输出相等,E=1,时，则从数最右端往左边扫描，直到第一个,1,的时候，该位和右边各位保持不变,0A=A,，左边各数值位按位取反,1A=,乛,A,可以用符号作为,E,的输入,阵列乘法器,带符号的阵列乘法器,(,间接法,),乘法小结,原码乘 符号位,单独处理,补码乘 符号位,自然形成,原码乘去掉符号位运算 即为无符号数乘法,不同的乘法运算需有不同的硬件支持,整数乘法与小数乘法完全相同,可用,逗号,代替小数点,小结,理解并会计算（要求过程）：定点原码一位乘，定点补码一位乘（,Booth,算法,）,了解无符号阵列乘法器的原理,作业,6,6-1.,用原码一位乘计算,0.1001,(-0.1011),（写出详细步骤）,6-2.(,选做）用补码一位乘,(,Booth,算法,),计算,0.1001,(-0.1011),（写出详细步骤）,思考,原码除法中为什么需要恢复余数？在加减交替法中恢复余数的机制是什么？,