补码一位乘法的证明

二.

补码一位乘法为了得到补码一位乘法的规律，我们先从补码和真值的转换公式开始讨论.1.补码与真值的转换公式设[x]补=x0.x1x2…xn,当x>=0时,x0=0,n[x]补=0.x1x2…xn=xi2-i=x

i=1当x<0时，x0=1,[x]补=1.x1x2…xn=2+x所以nx=1.x1x2…xn-2=-1+0.x1x2…xn=-1+xi2-i

i=1补码一位乘法的证明共10页，您现在浏览的是第1页!故得出

nx=-x0+xi2-i

i=1等式右边x为真值.这是一个重要公式，说明真值和补码之间的关系.2.补码的右移正数右移一位，相当于乘1／2.负数用补码表示时，右移一位也相当于乘1／2.因此，在补码运算的机器中，一个数不论其正负，连同符号位向右移一位，符号位保持不变，就等于乘1／2.现证明如下:设[x]补=x0.x1x2…xn，因为nx=-x0+xi2-i

i=1补码一位乘法的证明共10页，您现在浏览的是第2页!所以n

1/2x=-1/2x0+1/2x2-ii=1nn=-x0+1/2x0+1/2xi2-i=-x0+1/2xi2-(i+1)i=1i=0写成补码形式，即得[1/2x]补=x0.x0x1x2…xn如果要得[2-ix]补，只要将[x]补连同符号右移i位即可.3．补码乘法规则设被乘数[x]补=x0.x1x2…xn和乘数[y]补=y0.y1y2…yn均为任意符号，则有补码乘法算式n[x•y]补=[x]补•(-y0+yi2-i)(2.31)i=1

补码一位乘法的证明共10页，您现在浏览的是第3页!（2）被乘数x符号任意，乘数y符号为负[x]补=x0.x1x2…xn[y]补=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]补(-y0+0.y1y2…yn)n=[x]补•(-yo+Σyi2-i)i=1证毕.补码一位乘法的证明共10页，您现在浏览的是第4页!开始时，部分积为0，即[z0]补=0．然后每一步都是在前次部分积的基础上，由（yi+1-yi)（i=0,1,2,…,n）决定对[x]补的操作，再右移一位，得到新的部分积.如此重复n+1步，最后一步不移位，便得到[x•y]补，这就是有名的布斯公式.实现这种补码乘法规则时，在乘数最末位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，即保持不变.补码一位乘法的证明共10页，您现在浏览的是第5页![例][x]补=0.1101，[y]补=0.1011,求[x·y]补.解：部分积乘数说明00.00000.10110yn+1=0+11.0011ynyn+1=10,+[-x]补11.0011

11.10011010

11右移1位+00.0000ynyn+1=11,+011.100111.1100110101

右移1位+00.1101

ynyn+1=01,+[x]补00.100100.0100111010

右移1位+11.0011

ynyn+1=10,+[-x]补11.011111.1011111101

右移1位+00.1101

ynyn+1=01,+[x]补00.1000111101最后一步不移位实现一位补码乘法的逻辑原理图与一位原码乘法的逻辑结构非常类似，所不同的有以下几点:补码一位乘法的证明共10页，您现在浏览的是第6页!证明如下:（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)

补码一位乘法的证明共10页，您现在浏览的是第7页!为了推出串行逻辑实现的分步算法，将上式展开加以变换:[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-i

i=1写成递推公式如下[z0]补=0[z1]补=2-1{[z0]补+(yn+1-yn)[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]补补码一位乘法的证明共10页，您现在浏览的是第8页!补码一位乘法的运算规则如下（开始时yn+1=0）:(1)如果yn=yn+1,部分积［Zi］加0，再右移1位；（2）如果ynyn+1=01,部分积加[x]补，再右移1位；（3）如果ynyn+1=10,部分积加［-x]补，再右移1位.这样重复进行n＋1步，但最后一步不移位.包括一位符号位，所得乘积为2n＋1位，其中n为尾数数位.补码