補碼一位乘法的證明

二.

補碼一位乘法為了得到補碼一位乘法的規(guī)律，我們先從補碼和真值的轉(zhuǎn)換公式開始討論.1.補碼與真值的轉(zhuǎn)換公式設(shè)[x]補=x0.x1x2…xn,當(dāng)x>=0時,x0=0,n[x]補=0.x1x2…xn=xi2-i=x

i=1當(dāng)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頁，您現(xiàn)在瀏覽的是第1頁!故得出

nx=-x0+xi2-i

i=1等式右邊x為真值.這是一個重要公式，說明真值和補碼之間的關(guān)系.2.補碼的右移正數(shù)右移一位，相當(dāng)于乘1／2.負數(shù)用補碼表示時，右移一位也相當(dāng)于乘1／2.因此，在補碼運算的機器中，一個數(shù)不論其正負，連同符號位向右移一位，符號位保持不變，就等于乘1／2.現(xiàn)證明如下:設(shè)[x]補=x0.x1x2…xn，因為nx=-x0+xi2-i

i=1補碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第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．補碼乘法規(guī)則設(shè)被乘數(shù)[x]補=x0.x1x2…xn和乘數(shù)[y]補=y0.y1y2…yn均為任意符號，則有補碼乘法算式n[x?y]補=[x]補?(-y0+yi2-i)(2.31)i=1

補碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第3頁!（2）被乘數(shù)x符號任意，乘數(shù)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，根據(jù)式（2.31a）有[x(0.y1y2…yn)]補=[x]補(0.y1y2…yn)所以[x?y]補=[x]補(0.y1y2…yn)+[-x]補(2.31b)（3）被乘數(shù)x和乘數(shù)y符號都任意.將式（231a）和武（2.31b）兩種情況綜合起來，即得補碼乘法的統(tǒng)一算式，即[x?y]補=[x]補(0.y1y2…yn)-[x]補?y0=[x]補(-y0+0.y1y2…yn)n=[x]補?(-yo+Σyi2-i)i=1證畢.補碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第4頁!開始時，部分積為0，即[z0]補=0．然后每一步都是在前次部分積的基礎(chǔ)上，由（yi+1-yi)（i=0,1,2,…,n）決定對[x]補的操作，再右移一位，得到新的部分積.如此重復(fù)n+1步，最后一步不移位，便得到[x?y]補，這就是有名的布斯公式.實現(xiàn)這種補碼乘法規(guī)則時，在乘數(shù)最末位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頁，您現(xiàn)在瀏覽的是第5頁![例][x]補=0.1101，[y]補=0.1011,求[x·y]補.解：部分積乘數(shù)說明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最后一步不移位實現(xiàn)一位補碼乘法的邏輯原理圖與一位原碼乘法的邏輯結(jié)構(gòu)非常類似，所不同的有以下幾點:補碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第6頁!證明如下:（1）被乘數(shù)x符號任意，乘數(shù)y符號為正.根據(jù)補碼定義，可得[x]補=2+x=2n+1+x(mod2)[y]補=y所以[x]補?[y]補=2n+1?y+x?y=2(y1y2…yn)+x?y其中（y1y2…yn）是大于0的正整數(shù)，根據(jù)模運算性質(zhì)有2（y1y2…yn）=2（mod2）所以[x]補?[y]補=2+x?y=[x?y]補(mod2)即[x?y]補=[x]補?[y]補=[x]補?y(2.31a)

補碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第7頁!為了推出串行邏輯實現(xiàn)的分步算法，將上式展開加以變換:[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頁，您現(xiàn)在瀏覽的是第8頁!補碼一位乘法的運算規(guī)則如下（開始時yn+1=0）:(1)如果yn=yn+1,部分積［Zi］加0，再右移1位；（2）如果ynyn+1=01,部分積加[x]補，再右移1位；（3）如果ynyn+1=10,部分積加［-x]補，再右移1位.這樣重復(fù)進行n＋1步，但最后一步不移位.包括一位符號位，所得乘積為2n＋1位，其中n為尾數(shù)數(shù)位.補碼