原码补码乘除法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,原码一位乘运算,以定点小数为例,0.1 1 0 1,0.1 0 1 1,0.0 0 0,0,1 1 0 1,0.0 0,0,1 1 0 1,0.0 0,0 0 0 0,+,0.0,1 1 0 1,0.1 0 0 0 1 1 1 1,返回,例如：,X=0.1101 Y=-0.1011,笔算乘法过程,机器实现问题：,1.加法器只有两个数据输入端；,2.加法器与运算数据位数相同。,解决方案：,1.改,n,输入数相加过程为两两相加；,2.改2,n,位相加过程为,n,位相加。,X,Y=-0.10001111,原码一位乘运算,返回,基本公式：,设 被乘数,X,原,=,x,f,.,x,1,x,2,x,n,乘 数,Y,原,=,y,f,.,y,1,y,2,y,n,则,X,Y,原,=(,x,f,y,f,),.,(X,*,Y,*,),其中，,X,*,和,Y,*,分别是,X,和,Y,的绝对值,例如：,X=0.1101,Y=-0.1011,X,原,=0,.,1101,Y,原,=1,.,1011,X,*,=0.1101,Y,*,=0.1011,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,手工运算过程,原码一位乘运算,原码一位乘运算,X,*,=0,.,1101 Y,*,=0,.,1011,0.1 1 0 1,.,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,手工运算过程,返回,原码一位乘运算,X,*,=0,.,1101 Y,*,=0,.,1011,0.1 1 0 1,.,1 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,手工运算过程,返回,原码一位乘运算,X,*,=0,.,1101 Y,*,=0,.,1011,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,手工运算过程,再用一步完成两数符号异或求积的符号,结果为-0.10001111,返回,原码一位乘运算规则,原码一位乘运算规则：,1.乘积的符号位由两数符号位“异或”产生，符号,位不参与运算；,2.部分积可采用一位或两位符号位；,3.乘积的数值部分由两数绝对值相乘产生，通过,n,次“加法”和“右移”操作实现。(,n,为乘数整数部分位数),返回,原码一位乘运算实例,部分积 乘数,0,.,0 0 0 0,0,.,1 0 1,1,+0,.,1 1 0 1,0,.,1 1 0 1,0,.,0 1 1 0 1,0 1,0,1,+0,.,1 1 0 1,1,.,0 0 1 1,0,.,1 0 0 1,1,1,0 1,0,0,.,0 1 0 0,1,1 1,0,1,+0,.,1 1 0 1,1,.,0 0 0 1,0,.,1 0 0 0,1,1 1,1,0,返回,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,例如：,X=0.1101 Y=-0.1011,手工运算过程,计算机内运算的实现方法,则,X*=0.1101 Y*=0.1011,X,原,=0,.,1101,Y,原,=1,.,1011,X,Y,原,=1.10001111,补码乘法,运算,原码乘法不难实现，但有,两个问题,:,1.符号位与数值位分别处理，不方便；,2.若数据为补码形式，可能需要多于两次,补,原码变换。,也可以直接用补码完成乘法运算，即从补码开始，直接得到补码的积。,下面看一看补码乘运算的实现算法。,返回,=,(,Y,i+1,-Y,i,),2,-i,设 被乘数 ,X,补,=,x,0,.,x,1,x,2,x,n,乘 数 ,Y,补,=,y,0,.,y,1,y,2,y,n,先复习两个概念:,已知,X,补,=,x,0,.,x,1,x,2,x,n,时,X/2,补,=,x,0,.,x,0,x,1,x,2,x,n,-1,已知,Y,补,=,y,0,.,y,1,y,2,y,n,时,Y =,-y,0,y,i,2,-i,i=1,n,n,i=,0,补码一位乘法的,实现,算法推导,(比较,法),返回,X Y,=X ,-,y,0,y,i,2,-i,补码一位乘法运算,算法推导,(比较法),X Y,补,补,补,?,返回,=,X (,0,.y,1,y,2,y,n,),-,X,y,0,X Y,补,=,X (,0,.y,1,y,2,y,n,)-,X y,0,补,=,X (,0,.y,1,y,2,y,n,),补,-,X y,0,补,=,X,补,(,0.,y,1,y,2,y,n,),-y,0,X,补,=,X,补,Y,n,i=,0,证明,X (,0.y,1,y,2,y,n,),补,=,X,补,(,0.,y,1,y,2,y,n,),(1)当,X,0,时，,X (,0.y,1,y,2,y,n,),补,=,X (,0.y,1,y,2,y,n,),=,X,补,(,0.,y,1,y,2,y,n,),(2)当,X,0,时，,X (,0.y,1,y,2,y,n,),补,=,2+,X (,0.y,1,y,2,y,n,),(mod 2),=,2,n+1,+,X (,0.y,1,y,2,y,n,),(mod 2),=,2,n+1,(,0.y,1,y,2,y,n,),+,X (,0.y,1,y,2,y,n,),(mod 2),=,(2,n+1,+,X)(,0.y,1,y,2,y,n,),(mod 2),=,(2+,X)(,0.y,1,y,2,y,n,),(mod 2),=,X,补,(,0.,y,1,y,2,y,n,),(mod 2),=-y,0,*2,0,+,(y,1,*2,0,-y,1,*2,-1,),+,(y,2,*2,-1,-y,2,*2,-2,),+,补码一位乘法运算,算法推导,(比较法),=,(,y,i,+1,-,y,i,)*2,-i,X Y,补,补,返回,Y,补,Y=（y,0,y,i,*2,-i,),i=1,n,分,解为单项形式,=-y,0,*2,0,+,y,1,*2,-1,+,y,2,*2,-2,+y,n,*2,-n,变每位上的 1为高 1位上的 1个+1加本位上的 1个-1,=(,y,1,-y,0,)*2,0,+(y,2,-y,1,)*2,-1,+(,y,n,+1,-,y,n,)*2,-n,最低1位后再补1位,合并同次幂的项,写成为求累加和形式,i=0,n,令,y,n,+1,=0,补码一位,乘法运算,的,实现,(比较法),补码一位乘公式：,Z,补,=,X Y,补,=,补,（,-,y,0,y,i,2,-i,）,返回,=,补,(,y,i,+1,-,y,i,)2,-i,i=0,n,i=0,n,部分积递推公式：,Z,0,补,=0,Z,1,补,=,2,-1,Z,0,补,+(,y,n,+1,-,y,n,),补,(令,y,n,+1,=0),Z,i,补,=2,-1,Z,i,-1,补,+(,y,n,-i+2,-,y,n,-i+1,),补,Z,n,补,=,2,-1,Z,n-1,补,+(,y,2,-,y,1,),补,Z,n+1,补,=,Z,n,补,+(,y,1,-y,0,),补,=,X Y,补,补码一位,乘法运算的,算法规则,(比较法),y,n,y,n,+1,=00,时，,Z,i,补,=,Z,i,-1,补,+0，右移1位;,y,n,y,n,+1,=01,时，,Z,i,补,=,Z,i,-1,补,+,X,补，,右移1位,；,y,n,y,n,+1,=10,时，,Z,i,补,=,Z,i,-1,补,+-,X,补，,右移1位,；,y,n,y,n,+1,=11,时，,Z,i,补,=,Z,i,-1,补,+0，右移1位；,补码一位乘算法规则：,X、Y,的符号位都参加运算，部分积采用双符号位；,2.乘数最低位之后增加一位附加位,y,n,+1,，,且令,y,n,+1,=0；,3.,每位部分积运算规则如下：,4.重复,n+1,次比较和运算，但只进行,n,次右移，,最后一,次不移位。积符由运算过程自动产生。,补码一位乘法运算实例,已知,:,X,补,=0,.,1101,Y,补,=0,.,1011,部分积 乘数,y,n,y,n,+1,0 0,.,0 0 0 0,0,.,1 0 1,1 0,+1 1,.,0 0 1 1,1 1,.,0 0 1 1,1 1,.,1 0 0 1 1,0 1 0,1 1,1 1,.,1 1 0 0 1 1,0 1,0 1,+0 0,.,1 1 0 1,0 0,.,1 0 0 1,0 0,.,0 1 0 0 1 1 1,0,1 0,+1 1,.,0 0 1 1,1 1,.,0 1 1 1,1 1,.,1 0 1 1 1 1 1 1,0 1,+0 0,.,1 1 0 1,0 0,.,1 0 0 0 1 1 1 1,0,清0,则,-,X,补,=1,.,0011,X,Y,补,=0.10001111,补码,一位,乘,硬件配置,及,实例演示,（比较法,）,补码一位乘综合演示.,swf,设 被乘数,X,补,=,x,0,.,x,1,x,2,x,n,乘 数,Y,补,=,y,0,.,y,1,y,2,y,n,补码两位乘法的,实现,算法推导,(比较法,),返回,由一位乘算法得：,Z,i,+2,补,=2,-1,2,-1,Z,i,补,+(,y,n,-i+1,-,y,n,-i,),补,+(,y,n,-i,-,y,n,-i-1,),补,=,2,-2,Z,i,补,+(,y,n,-i+1,+,y,n,-i,-2,y,n,-i-1,),补,结论：,补码两位乘比较法的部分积运算由乘数相邻的三位比较决定，运算后每次右移两位。,Z,i,+1,补,=2,-1,Z,i,补,+(,y,n,-i+1,-,y,n,-i,),补,补码两位,乘法运算的,算法规则,(比较法),y,n,-1,y,n,y,n,+1,=000,时，,Z,i,+2,补,=,Z,i,补,+0，右移2位;,y,n,-1,y,n,y,n,+1,=001,时，,Z,i,+2,补,=,Z,i,补,+,X,补,，右移2位;,y,n,-1,y,n,y,n,+1,=010,时，,Z,i,+2,补,=,Z,i,补,+,X,补,，右移2位;,y,n,-1,y,n,y,n,+1,=011,时，,Z,i,+2,补,=,Z,i,补,+2,X,补,，右移2位;,y,n,-1,y,n,y,n,+1,=100,时，,Z,i,+2,补,=,Z,i,补,+2-,X,补,，右移2位;,y,n,-1,y,n,y,n,+1,=101,时，,Z,i,+2,补,=,Z,i,补,+-,X,补,，右移2位;,y,n,-1,y,n,y,n,+1,=110,时，,Z,i,+2,补,=,Z,i,补,+-,X,补,，右移2位;,y,n,-1,y,n,y,n,+1,=111,时，,Z,i,+2,补,=,Z,i,补,+0，右移2位;,X、Y,的符号位都参加运算，部分积采用,三位符号位,；,乘数最低位之后增加一位附加位,y,n,+1,，,且令,y,n,+1,=0,；,每位部分积运算规则如下：,补码两位,乘法运算的,算法规则,(续,),(,比较法),4.设乘数数值部分为,n,位，,当,n,为奇数时,，乘数设,1位符号位,，做,(,n+1)/2,次,运算和移位，最后一步,右移,1