定点补码一位乘的运算方法.doc

定点补码一位乘的运算方法:按乘数为正、负两种情况讨论:1.被乘数x补符号任意,乘数y 补为正 设x补=x0.x1x2xn y补=y0.y1y2yn根据补码定义可推得: x补=2+x=2n+1+x (MOD2) y补=y=0.y1y2.yn其中x,y为真值.故: x补y补=(2n+1+x)*y=2n+1+xy =21*2n(0.y1y2.yn)+xy =2(y1y2.yn)+xy注意0.y1y2.yn被2n乘已成为正整数.根据模的运算性质有: 2(y1y2.yn)=2 (mod 2)所以 xp*yp=2+x*y=x*y补 (mod 2)即 x*yp=xp*yp=xp*y(因为ys=0为正) =xp* (0.y1y2.yn) (1)当乘数y0,不管x的符号如何,将xp*y=x*yp2.被乘数xp符号任意,乘数y为负 x补=x0.x1x2xn y补=1.y1y2yn =2+y (mod 2)该项得: y=y补-2=1.y1y2yn -2=1+0.y1y2.yn-2=0.y1y2.yn-1 所以 x*y=x*(0.y1y2.yn-1)=x*(0.y1y2.yn)-x将上式两边取补 所以有: x*yp=x(0.y1y2.yn)-xp =x(0.y1y2.yn)p-xp = x(0.y1y2.yn)p+ -xp因为 (0.y1y2.yn)0 正数的补码 = 本身所以 x(0.y1y2.yn)p= xp*(0.y1y2.yn)所以 x*yp= xp*(0.y1y2.yn) -xp (2) 将(1)和(2)综合起来:得统一的算式 x*yp= xp*(0.y1y2.yn) -xp*y0 (3) =xp*(-y0+0.y1y2.yn)分析:右边第二项xp*y0当y为正 y0=0 该项不存在 (1) y为负 y0=1 该项为xp (2)将(3)式展开,推出逻辑实现分步算法: 获得各项部分积的累加形式. x*yp= xp*(0.y1y2.yn) -xp*y0 = xp*(2-1y1+2-2y2+2-nyn) -xp*y0 =xp*-y0+ (y1-2-1y1)+( y22-1-2-2y2)+(2-(n-1)yn-2-nyn) =xp*(y1-y0)+(y2-y1)2-1+(yn-yn-1)2-(n-1)+(yn+1-yn) 2-n说明:(1) 0.y1y2.yn可写成2-1y1+2-2y2+2-nyn (2)提公因式xp将 -y0 提前 (3)去括号重新组合 (4) y1-2-1y1=(20-2-1)y1=(1-1/2) y1=0.5y y22-1-y22-2=(2-1-2-2)*y2=2-2y2x*y补= x补*(0.y1y2.yn) -x补*y0 = x补*(2-1y1+2-2y2+2-nyn) -x补*y0 =x补*-y0+ (y1-2-1y1)+( y22-1-2-2y2)+(2-(n-1)yn-2-nyn) =x补*(y1-y0)+(y2-y1)2-1+(yn-yn-1)2-(n-1)+(yn+1-yn) 2-n将xp乘进去,然后从第2项开始,每次提2-1=(y1-y0)xp+(y2-y1)2-1xp+(yn+1-yn)2-nxp=(y1-y0)xp+2-1(y2-y1)xp+(y3-y2)2-1xp+(y4-y3) 2-2xp+(yn+1-yn) 2-(n-1) xp1=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+(y4-y3)2-1xp+(yn+1-yn) 2-(n-2)xp21=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+2-1(y4-y3)xp+(yn+1-yn) 2-(n-3)xp321=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+2-1(y4-y3)xp+2-1 (yn-yn-1)xp +2-1 (yn+1-yn)xpnnn-1321说明: 式中yn+1是增设的附加位,初始值位0. ai取决于相邻两位乘数的比较结果 显然(4)式就是部分积累加的形式若定义p0补位初始部分积=0. p1补pn补依次位各步求得的累加并右移后的部分积.将(4)改写:更接近于分步运算逻辑实现x*yp=xp*(y1-y0)+(y2-y1)2-1+(yn-yn-1)2-(n-1)+(yn+1-yn) 2-n将xp乘进去,然后再次提2-1=(y1-y0)xp+(y2-y1)2-1xp+(yn+1-yn)2-nxp=(y1-y0)xp+2-1(y2-y1)xp+(y3-y2)2-1xp+(y4-y3) 2-2xp+(yn+1-yn) 2-(n-1) xp1=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+(y4-y3)2-1xp+(yn+1-yn) 2-(n-2)xp21=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+2-1(y4-y3)xp+(yn+1-yn) 2-(n-3)xp321=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+2-1(y4-y3)xp+2-1 (yn-yn-1)xp +2-1 (yn+1-yn)xpnnn-1321y0 x*yp= xp*(0.y1y2.yn) (1)y0 x*yp= xp*(0.y1y2.yn) -xp (2)统一算式: x*yp= xp*(0.y1y2.yn) -xp*y0 (3) =xp*(-y0+0.y1y2.yn)化简: =xp*(y1-y0)+(y2-y1)2-1+(yn-yn-1)2-(n-1)+(yn+1-yn) 2-n (4)将xp乘进去从第二项开始,每次提2-1=(y1-y0)xp+2-1(y2-y1)xp+(y3-y2)2-1xp+(y4-y3) 2-2xp+(yn+1-yn) 2-(n-1) xp1=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+2-1(y4-y3)xp+2-1 (yn-yn-1)xp +2-1 (yn+1-yn)xpnnn-1321=(y1-y0)xp+2-1(y2-y1)xp+2-1(y3-y2)xp+2-1(y4-y3)xp+2-1 (yn+1-yn)xp +P0补nn-1321P1补写成递推公式:P0补=0P1补=2-1(yn+1-yn)xp +P0补n 令yn+1=0P2补=2-1(yn-yn-1)xp +P1补nPi补=2-1(yn-i+2-yn-i+1)xp +Pi-1补nPn补=2-1(y2-y1)xp +Pn-1补n所以: x*y补=Pn+1补= (y1-y0)xp +Pn补 注意:(1)y0 是乘数y的符