补码一位乘法的证明

《补码一位乘法的证明》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二.补码一位乘法为了得到补码一位乘法的规律，我们先从补码和真值的转换公式开始讨论.1.补码与真值的转换公式设[x]补=x0.x1x2…xn,当x>=0时,x0=0,n[x]补=0.x1x2…xn=xi2-i=xi=1当x<0时，x0=1,[x]补=1.x1x2…xn=2+x所以nx=1.x1x2…xn-2=-1+0.x1x2…xn=-1+xi2-ii=1故得出nx=-x0+xi2-ii=1等式右边x为真值.这是一个重要公式，说明真值和补码之间的关系.2.补码的右移正数右移一位，相当于乘1／2.负数用补码表示时，右移一位也相当于乘1／2.因此，

2、在补码运算的机器中，一个数不论其正负，连同符号位向右移一位，符号位保持不变，就等于乘1／2.现证明如下:设[x]补=x0.x1x2…xn，因为nx=-x0+xi2-ii=1所以n1/2x=-1/2x0+1/2x2-ii=1nn=-x0+1/2x0+1/2xi2-i=-x0+1/2xi2-(i+1)i=1i=0写成补码形式，即得[1/2x]补=x0.x0x1x2…xn如果要得[2-ix]补，只要将[x]补连同符号右移i位即可.3．补码乘法规则设被乘数[x]补=x0.x1x2…xn和乘数[y]补=y0.y1y2…yn均为任意符号，则有补码乘法算

3、式n[x•y]补=[x]补•(-y0+yi2-i)(2.31)i=1证明如下:（1）被乘数x符号任意，乘数y符号为正.根据补码定义，可得[x]补=2+x=2n+1+x(mod2)[y]补=y所以[x]补•[y]补=2n+1•y+x•y=2(y1y2…yn)+x•y其中（y1y2…yn）是大于0的正整数，根据模运算性质有2（y1y2…yn）=2（mod2）所以[x]补•[y]补=2+x•y=[x•y]补(mod2)即[x•y]补=[x]补•[y]补=[x]补•y(2.31a)（2）被乘数x符号任意，乘数y符号为负[x]补=x0.x1x2…xn[y]

4、补=1.y1y2…yn=2+y(mod2)由此y=[y]补-2=0.y1y2…yn-1所以x•y=x(0.y1y2…yn)-x[x•y]补=[x(0.y1y2…yn)]补+[-x]补又(0.y1y2…yn)>0，根据式（2.31a）有[x(0.y1y2…yn)]补=[x]补(0.y1y2…yn)所以[x•y]补=[x]补(0.y1y2…yn)+[-x]补(2.31b)（3）被乘数x和乘数y符号都任意.将式（231a）和武（2.31b）两种情况综合起来，即得补码乘法的统一算式，即[x•y]补=[x]补(0.y1y2…yn)-[x]补•y0=[x]补(

5、-y0+0.y1y2…yn)n=[x]补•(-yo+Σyi2-i)i=1证毕.为了推出串行逻辑实现的分步算法，将上式展开加以变换:[x•y]补=[x]补•[-y0+y12-1+y22-2+…+yn2-n]=[x]补•[-y0+(y1-y12-1)+(y22-1-y22-2)+…+(yn2-(n-1)-yn2-n)]=[x]补•[(y1-y0)+(y2-y1)2-1+…+(yn-yn-1)2-(n-1)+(0-yn)2-n]n=[x]补•(yi+1-yi)2-ii=1写成递推公式如下[z0]补=0[z1]补=2-1{[z0]补+(yn+1-yn)[

6、x]补}(yn+1=0)[z2]补=2-1{[z1]补+(yn-yn-1)[x]补}┇[zi]补=2-1{[zi-1]补+(yn-i+2-yn-i+1)[x]补}┇[zn]补=2-1{[zn-1]补+(y2-y1)[x]补}[zn+1]补=[zn]补+(y1-y0)[x]补=[x•y]补开始时，部分积为0，即[z0]补=0．然后每一步都是在前次部分积的基础上，由（yi+1-yi)（i=0,1,2,…,n）决定对[x]补的操作，再右移一位，得到新的部分积.如此重复n+1步，最后一步不移位，便得到[x•y]补，这就是有名的布斯公式.实现这种补码乘法规则

7、时，在乘数最末位yn后面要增加一位补充位yn+1。开始时yn+1=0,由ynyn+1判断第一步该怎么操作；然后再由yn-1yn判断第二步该怎么操作。但因为每作一步要右移一位，故作完第一步后，yn-1yn正好移到原来ynyn+1的位置上。依此类推，所以每步都用ynyn+1位置进行判断.我们将此两位称为判断位.如果判断位ynyn+1=01，则yi+1-yi=1，做加[x]补操作.如果ynyn+1=10，则yi+1–yi=-1,做减法,即做加[-x]补操作；如果ynyn+1=11或00，则yi+1–yi=0，［zi］加0，即保持不变.补码一位乘法的运算规

8、则如下（开始时yn+1=0）:(1)如果yn=yn+1,部分积［Zi］加0，再右移1位；（2）如果ynyn+1=01,部分