補(bǔ)碼一位乘法的證明

二.

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

i=1當(dāng)x<0時(shí)，x0=1,[x]補(bǔ)=1.x1x2…xn=2+x所以nx=1.x1x2…xn-2=-1+0.x1x2…xn=-1+xi2-i

i=1補(bǔ)碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第1頁!故得出

nx=-x0+xi2-i

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

i=1補(bǔ)碼一位乘法的證明共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寫成補(bǔ)碼形式，即得[1/2x]補(bǔ)=x0.x0x1x2…xn如果要得[2-ix]補(bǔ)，只要將[x]補(bǔ)連同符號(hào)右移i位即可.3．補(bǔ)碼乘法規(guī)則設(shè)被乘數(shù)[x]補(bǔ)=x0.x1x2…xn和乘數(shù)[y]補(bǔ)=y0.y1y2…yn均為任意符號(hào)，則有補(bǔ)碼乘法算式n[x?y]補(bǔ)=[x]補(bǔ)?(-y0+yi2-i)(2.31)i=1

補(bǔ)碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第3頁!（2）被乘數(shù)x符號(hào)任意，乘數(shù)y符號(hào)為負(fù)[x]補(bǔ)=x0.x1x2…xn[y]補(bǔ)=1.y1y2…yn=2+y(mod2)由此y=[y]補(bǔ)-2=0.y1y2…yn-1所以x?y=x(0.y1y2…yn)-x[x?y]補(bǔ)=[x(0.y1y2…yn)]補(bǔ)+[-x]補(bǔ)又(0.y1y2…yn)>0，根據(jù)式（2.31a）有[x(0.y1y2…yn)]補(bǔ)=[x]補(bǔ)(0.y1y2…yn)所以[x?y]補(bǔ)=[x]補(bǔ)(0.y1y2…yn)+[-x]補(bǔ)(2.31b)（3）被乘數(shù)x和乘數(shù)y符號(hào)都任意.將式（231a）和武（2.31b）兩種情況綜合起來，即得補(bǔ)碼乘法的統(tǒng)一算式，即[x?y]補(bǔ)=[x]補(bǔ)(0.y1y2…yn)-[x]補(bǔ)?y0=[x]補(bǔ)(-y0+0.y1y2…yn)n=[x]補(bǔ)?(-yo+Σyi2-i)i=1證畢.補(bǔ)碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第4頁!開始時(shí)，部分積為0，即[z0]補(bǔ)=0．然后每一步都是在前次部分積的基礎(chǔ)上，由（yi+1-yi)（i=0,1,2,…,n）決定對(duì)[x]補(bǔ)的操作，再右移一位，得到新的部分積.如此重復(fù)n+1步，最后一步不移位，便得到[x?y]補(bǔ)，這就是有名的布斯公式.實(shí)現(xiàn)這種補(bǔ)碼乘法規(guī)則時(shí)，在乘數(shù)最末位yn后面要增加一位補(bǔ)充位yn+1。開始時(shí)yn+1=0,由ynyn+1判斷步該怎么操作；然后再由yn-1yn判斷第二步該怎么操作。但因?yàn)槊孔饕徊揭乙埔晃唬首魍瓴胶螅瑈n-1yn正好移到原來ynyn+1的位置上。依此類推，所以每步都用ynyn+1位置進(jìn)行判斷.我們將此兩位稱為判斷位.如果判斷位ynyn+1=01，則yi+1-yi=1，做加[x]補(bǔ)操作.如果ynyn+1=10，則yi+1–yi=-1,做減法,即做加[-x]補(bǔ)操作；如果ynyn+1=11或00，則yi+1–yi=0，［zi］加0，即保持不變.補(bǔ)碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第5頁![例][x]補(bǔ)=0.1101，[y]補(bǔ)=0.1011,求[x·y]補(bǔ).解：部分積乘數(shù)說明00.00000.10110yn+1=0+11.0011ynyn+1=10,+[-x]補(bǔ)11.0011

11.10011010

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

右移1位+00.1101

ynyn+1=01,+[x]補(bǔ)00.100100.0100111010

右移1位+11.0011

ynyn+1=10,+[-x]補(bǔ)11.011111.1011111101

右移1位+00.1101

ynyn+1=01,+[x]補(bǔ)00.1000111101最后一步不移位實(shí)現(xiàn)一位補(bǔ)碼乘法的邏輯原理圖與一位原碼乘法的邏輯結(jié)構(gòu)非常類似，所不同的有以下幾點(diǎn):補(bǔ)碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第6頁!證明如下:（1）被乘數(shù)x符號(hào)任意，乘數(shù)y符號(hào)為正.根據(jù)補(bǔ)碼定義，可得[x]補(bǔ)=2+x=2n+1+x(mod2)[y]補(bǔ)=y所以[x]補(bǔ)?[y]補(bǔ)=2n+1?y+x?y=2(y1y2…yn)+x?y其中（y1y2…yn）是大于0的正整數(shù)，根據(jù)模運(yùn)算性質(zhì)有2（y1y2…yn）=2（mod2）所以[x]補(bǔ)?[y]補(bǔ)=2+x?y=[x?y]補(bǔ)(mod2)即[x?y]補(bǔ)=[x]補(bǔ)?[y]補(bǔ)=[x]補(bǔ)?y(2.31a)

補(bǔ)碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第7頁!為了推出串行邏輯實(shí)現(xiàn)的分步算法，將上式展開加以變換:[x?y]補(bǔ)=[x]補(bǔ)?[-y0+y12-1+y22-2+…+yn2-n]=[x]補(bǔ)?[-y0+(y1-y12-1)+(y22-1-y22-2)+…+(yn2-(n-1)-yn2-n)]=[x]補(bǔ)?[(y1-y0)+(y2-y1)2-1+…+(yn-yn-1)2-(n-1)+(0-yn)2-n]n=[x]補(bǔ)?(yi+1-yi)2-i

i=1寫成遞推公式如下[z0]補(bǔ)=0[z1]補(bǔ)=2-1{[z0]補(bǔ)+(yn+1-yn)[x]補(bǔ)}(yn+1=0)[z2]補(bǔ)=2-1{[z1]補(bǔ)+(yn-yn-1)[x]補(bǔ)}┇[zi]補(bǔ)=2-1{[zi-1]補(bǔ)+(yn-i+2-yn-i+1)[x]補(bǔ)}┇[zn]補(bǔ)=2-1{[zn-1]補(bǔ)+(y2-y1)[x]補(bǔ)}[zn+1]補(bǔ)=[zn]補(bǔ)+(y1-y0)[x]補(bǔ)=[x?y]補(bǔ)補(bǔ)碼一位乘法的證明共10頁，您現(xiàn)在瀏覽的是第8頁!補(bǔ)碼一位乘法的運(yùn)算規(guī)則如下（開始時(shí)yn+1=0）:(1)如果yn=yn+1,部分積［Zi］加0，再右移1位；（2）如果ynyn+1=01,部分積加[x]補(bǔ)，再右移1位；（3）如果ynyn+1=10,部分積加［-x]補(bǔ)，再右移1位.這樣重復(fù)進(jìn)行n＋1步，但最后一步不移位.包括一位符號(hào)位，所得乘積為2n＋1位，其中n為尾數(shù)數(shù)位.補(bǔ)碼