計算機組成原理第2章

1、1 第二章第二章 數(shù)據(jù)的表示和運算數(shù)據(jù)的表示和運算 2 2.1 2.1 數(shù)據(jù)的編碼數(shù)據(jù)的編碼 一、數(shù)制及其轉(zhuǎn)換一、數(shù)制及其轉(zhuǎn)換 1 1、進位記數(shù)制進位記數(shù)制 * *進位記數(shù)制進位記數(shù)制：又稱進制或數(shù)制，是用一組固定的符號和統(tǒng)一又稱進制或數(shù)制，是用一組固定的符號和統(tǒng)一 的規(guī)則來表示數(shù)值的方法的規(guī)則來表示數(shù)值的方法。參數(shù)參數(shù)有數(shù)碼、基數(shù)和位權(quán)有數(shù)碼、基數(shù)和位權(quán) * *常用的常用的4 4種進制種進制： 二進制二進制八進制八進制十進制十進制十六進制十六進制 數(shù)碼數(shù)碼0,10,10,1,70,1,70,1,90,1,90,1,9,0,1,9,A,B,FA,B,F 基數(shù)基數(shù)2 28 810101616 位

2、權(quán)位權(quán)2 2i8 8i1010i1616i 書寫形式書寫形式B BO OD DH H * *R進制數(shù)表示：進制數(shù)表示：( (N N ) )R=(=(kn-1 -1 k1 1k0 0. .k-1 -1k-2-2 k- -m m) )R= 其中，其中，ki0,1,(0,1,(R-1)-1) 1n- mi i i Rk 3 2 2、R進制數(shù)進制數(shù)十進制數(shù)轉(zhuǎn)換十進制數(shù)轉(zhuǎn)換 例例11( (101.01101.01) )2 2 =( =(1 12 22 2+ +1 12 20 0+ +1 12 2-2 -2) )10 10=( =(5.25)5.25)10 10 ( (3A.C3A.C) )16 16 =

3、( =(3 316161 1+ +101016160 0+ +12121616-1 -1) )10 10=(58.75) =(58.75)10 10 3 3、十進制數(shù)十進制數(shù)R進制進制數(shù)轉(zhuǎn)換數(shù)轉(zhuǎn)換 (1)(1)十進制整數(shù)十進制整數(shù)R進進制整數(shù)轉(zhuǎn)換制整數(shù)轉(zhuǎn)換 例例22 余數(shù)余數(shù) 2 19 2 19 1 (1 (最低位最低位) ) 2 9 2 9 1 1 2 4 2 4 0 0 2 2 2 2 0 0 2 1 2 1 1 (1 (最高位最高位) ) 0 0 (19) (19)10 10=( =(1001110011) )2 2 余數(shù)余數(shù) 8 19 8 19 3 (3 (最低位最低位) ) 8 2

4、8 2 2 (2 (最高位最高位) ) 0 0 (19) (19)10 10=( =(2323) )8 8 * *轉(zhuǎn)換規(guī)則：轉(zhuǎn)換規(guī)則：按位權(quán)展開按位權(quán)展開 * *整數(shù)轉(zhuǎn)換規(guī)則：整數(shù)轉(zhuǎn)換規(guī)則：除基取余除基取余、上右下左上右下左 4 (2)(2)十進制小數(shù)十進制小數(shù)R進進制小數(shù)轉(zhuǎn)換制小數(shù)轉(zhuǎn)換 整數(shù)部分整數(shù)部分 0.68750.68752 = 2 = 1 1.375 .375 1 (1 (最高位最高位) ) 0.375 0.375 2 = 2 = 0 0.75 .75 0 0 0.75 0.75 2 = 2 = 1 1.5 .5 1 1 0.5 0.5 2 = 2 = 1 1.0 .0 1 (1 (

5、最低位最低位) ) (0.6875) (0.6875)10 10 = (0. = (0.10111011) )2 2 整數(shù)部分整數(shù)部分 0.68750.68758 = 8 = 5 5.5 .5 5 (5 (最高位最高位) ) 0.5 0.5 8 = 8 = 4 4.0 .0 4 4 ( (最低位最低位) ) (0.6875)(0.6875)10 10 = (0. = (0.5454) )8 8 例例33將將(0.6875)(0.6875)10 10分別轉(zhuǎn)換成二、八進制數(shù) 分別轉(zhuǎn)換成二、八進制數(shù) (3)(3)十進制數(shù)十進制數(shù)R進制進制數(shù)轉(zhuǎn)換數(shù)轉(zhuǎn)換 * *轉(zhuǎn)換規(guī)則：轉(zhuǎn)換規(guī)則：整數(shù)部分、小數(shù)部分整數(shù)

6、部分、小數(shù)部分分別轉(zhuǎn)換后再合并分別轉(zhuǎn)換后再合并 練習(xí)練習(xí)11(19.6875)(19.6875)10 10=(X) =(X)2 2=(Y)=(Y)8 8，X=X=？Y=Y=？ * *小數(shù)轉(zhuǎn)換規(guī)則：小數(shù)轉(zhuǎn)換規(guī)則：乘基取整乘基取整、上左下右上左下右 5 4 4、二、八、十六進制數(shù)相互轉(zhuǎn)換、二、八、十六進制數(shù)相互轉(zhuǎn)換 * *數(shù)位長度關(guān)系：數(shù)位長度關(guān)系：1 1個八進制、十六進制數(shù)位個八進制、十六進制數(shù)位3 3 bitbit、4 4 bitbit * *轉(zhuǎn)換規(guī)則轉(zhuǎn)換規(guī)則：從從小數(shù)點向兩邊小數(shù)點向兩邊分別分別轉(zhuǎn)換，轉(zhuǎn)換， 數(shù)位不夠數(shù)位不夠時時補零、無效的零刪除補零、無效的零刪除 例例44(13.724)(

7、13.724)8 8=(=(00001 1 011.111011.111 010010 1 10000) )2 2=(1011.1110101)=(1011.1110101)2 2 (10011.01)(10011.01)2 2=(=(0 01010 011.01011.010 0) )2 2=(23.2)=(23.2)8 8 例例55(2B.E)(2B.E)16 16=( =(00001010 1011.1111011.1110 0) )2 2=(101011.111)=(101011.111)2 2 (11001.11) (11001.11)2 2=(=(0000001 1 1001.11

8、1001.110000) )2 2=(19.C)=(19.C)16 16 練習(xí)練習(xí)22(21.75)(21.75)10 10 (X)(X)2 2(Y)(Y)8 8(Z)(Z)16 16， ，X=X=？Y=Y=？Z=Z=？ (2D.E) (2D.E)16 16 (A)(A)2 2(B)(B)8 8(C)(C)10 10， ，A=A=？B=B=？C=C=？ 6 二、機器數(shù)及其編碼二、機器數(shù)及其編碼 * *數(shù)值數(shù)據(jù)：數(shù)值數(shù)據(jù)：組成組成 符號符號+數(shù)值數(shù)值+小數(shù)點小數(shù)點+ +數(shù)值數(shù)值 運算運算符號與數(shù)值符號與數(shù)值分開運算分開運算，減法減法先先比較大小比較大小 * *機器數(shù)：機器數(shù)：計算機內(nèi)部計算機內(nèi)部

9、編碼表示編碼表示的的數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù) 如如(+101)(+101)2 2(0 0101)101)2 2、(-101)(-101)2 2(1 1101)101)2 2 真值真值數(shù)學(xué)上帶數(shù)學(xué)上帶+/-+/-號的數(shù)值數(shù)據(jù)號的數(shù)值數(shù)據(jù) * *機器數(shù)的編碼方法：機器數(shù)的編碼方法： 運算方法分析運算方法分析采用采用手工運算方法手工運算方法，硬件實現(xiàn)，硬件實現(xiàn)困難困難 采用采用新運算方法新運算方法，以利于以利于硬件實現(xiàn)硬件實現(xiàn) 編碼方法編碼方法原碼、補碼、反碼、移碼原碼、補碼、反碼、移碼等，等， 均用均用二進制二進制表示表示 硬件僅硬件僅0/10/1兩個狀態(tài)兩個狀態(tài) 符號符號/ /數(shù)值一起運算數(shù)值一起運算

10、減法不比較大小減法不比較大小 新的編碼方法新的編碼方法 表示可缺省表示可缺省 7 1 1、原、原碼碼( (Sign-magnitude) )表示法表示法 * *基本思想：基本思想：機器數(shù)機器數(shù)最高位最高位表示真值表示真值的的符號符號(0/1(0/1表示表示+/-)+/-)， 其余位其余位為真值的絕對值為真值的絕對值 * *整數(shù)原碼定義：整數(shù)原碼定義： 設(shè)設(shè)X= =xn-2 n-2 x0 0，則，則 X 原 原= =xn-1n-1xn-2n-2 x0 0， X 原 原 = = X 00X2 2n-1 n-1 2 2n-1 n-1 - - X = = 2 2n-1n-1 +| +|X| -2| -

11、2n-1 n-1 X00 例例11 + +11011101原 原= =0 01101 1101； - -11011101原 原= =1 11101 1101 例例2 2若若 X 原 原= =1 1101 101，則，則X= =- -101101 例例3 3若若 + +X 原 原= =0 0110 110，則，則 - -X 原 原= =1 1110 110 若若 + +Y 原 原= =0 0000 000，則，則 - -Y 原 原= =1 1000 000 +00原 原 -0-0原 原 練習(xí)練習(xí)11若若X=-01000=-01000，則，則 X 原 原= =？ ？ 若若 Y 原 原=101010

12、 =101010，則，則Y= =？ 符號位符號位 數(shù)值位數(shù)值位 8 * *小數(shù)原碼定義：小數(shù)原碼定義： 設(shè)設(shè)X= =0.0.x-1 -1 x-(n-1 -(n-1) )， ，則則 X 原 原= =x0 0. .x-1-1 x-(n-1) -(n-1) X 原 原 = = X 00X1 1 1-1-X=1+|=1+|X| -1| -1X00 例例44 +0+0.1001.1001原 原= =0 0.1001 .1001； -0-0.1001.1001原 原= =1 1.1001 .1001 例例5 5若若 X 原 原= =1 1.01 .01，則，則X= =-0-0.01.01 * *原碼的特性

13、：原碼的特性： X與與 X 原 原關(guān)系 關(guān)系 X 原 原與 與X表示值的范圍相同，表示值的范圍相同， +0+0原 原 -0-0原 原 運算方法運算方法符號與數(shù)值符號與數(shù)值分開運算分開運算( (與手工運算一致與手工運算一致) ) 適合于乘除法，適合于乘除法，加減法較復(fù)雜加減法較復(fù)雜 編碼時編碼時0 0可省略可省略 9 2 2、補碼補碼( (Twos complement) )表示表示法法 * *編碼目標：編碼目標：符號與數(shù)值符號與數(shù)值一起一起運算運算，減法，減法無需比較大小無需比較大小 * *有模運算：有模運算：運算只計量運算只計量小于小于“模?！钡牡牟糠?，多余部分被丟棄部分，多余部分被丟棄 模

14、模計量系統(tǒng)的計數(shù)計量系統(tǒng)的計數(shù)范圍范圍 (1)(1)有模運算與補數(shù)有模運算與補數(shù) 示例示例時針從時針從1010點撥向點撥向7 7點：點：10-3=710-3=7；10+9=7+12=710+9=7+12=7 * *補數(shù)：補數(shù)：若若a、b、M滿足滿足a+ +b= =M，稱，稱a、b互為?；槟的的補數(shù)補數(shù) 同余同余若若A、B、M滿足滿足A=B+kM ( (k為有符號整數(shù)為有符號整數(shù)) )， 則記則記 AB ( (mod M) )，稱，稱B和和A為模為模M的同余的同余 運算特征運算特征c- -a = = c-(-(M- -b) ) = = c+ +b (mod (mod M) )， 即即減去減去

15、一個數(shù)一個數(shù)等價于加上等價于加上這個數(shù)的補數(shù)這個數(shù)的補數(shù) 可將可將減法運算減法運算轉(zhuǎn)化為轉(zhuǎn)化為加法運算加法運算 10 * *減法無需比較大小減法無需比較大小的編碼的編碼思路思路： 負數(shù)負數(shù)用其正補數(shù)表示用其正補數(shù)表示，正數(shù)正數(shù)用其本身表示用其本身表示 示例示例 -48 (mod 12) -48 (mod 12)，+88 (mod 12)+88 (mod 12) 減法減法時，減數(shù)用其取負后編碼表示、進行加法運算時，減數(shù)用其取負后編碼表示、進行加法運算 示例示例9-45 9-45 (mod 12(mod 12) )，4-97 (mod 12)4-97 (mod 12) (2)(2)補碼定義補碼定義

16、 * *基本思想：基本思想：機器數(shù)機器數(shù)最高位最高位表示表示X的的符號符號(0/1(0/1表示表示+/-)+/-)， 其余其余位位為為| |X| |或或| |X| |的補的補數(shù)數(shù) * *整數(shù)補碼定義：整數(shù)補碼定義： 設(shè)設(shè)X= =xn-2 n-2 x0 0，則，則模為模為2 2n n， X 補 補= =xn-1n-1xn-2n-2 x0 0，即，即 X 補 補 = = 2 2n n +X (mod 2 +X (mod 2n n) ) = = X 00X2 2n-1 n-1 2 2n n + +X=2=2n n -|-|X| -2| -2n-1 n-1 X0 0 說明說明為實現(xiàn)為實現(xiàn)“負數(shù)的負數(shù)的

17、xn-1 -1=1 =1”，模須為模須為2 2n n( (不是不是2 2n-1 n-1) ) 11 練習(xí)練習(xí)22若若X=-01000=-01000、Y=+01000=+01000， X 補 補= =？ ？ Y 補 補= =？ ？ 例例77n=5n=5、X00時時， X 補 補最大 最大= =0 011111111，Xmax max=2 =24 4-1=+15-1=+15 X0 0時時， X 補 補最小 最小=1 100000000，Xmin min=-2 =-24 4 =-16 =-16 原碼原碼 無無 1 1111 111 1 1001 001 1 1000000 0 0000 000 0

18、0001 001 0 0111111 補碼補碼 1 1000 000 1 1001 001 1 1111 111 0 0000 000 0 0001 001 0 0111111 真值真值 -2-2n-1 n-1 -(2 -(2n-1 n-1-1) -1) -1 -1 0 0 +1 +(2+1 +(2n-1 n-1-1) -1) +0000 +0000補 補=-0000 =-0000補 補=00000 =00000 數(shù)數(shù)0 0的補碼惟一的補碼惟一 補碼表示數(shù)的個數(shù)比原碼多補碼表示數(shù)的個數(shù)比原碼多1 1個個 例例66+0001+0001補 補=00001 =00001，-0001-0001補 補=

19、 =10 10 00000000+(-0001)=+(-0001)=1111111111 +1111 +1111補 補=01111 =01111，-1111-1111補 補= =10 10 00000000+(-1111)=+(-1111)=1000110001 2 25 5 最高位為最高位為1 1 12 * *小數(shù)補碼定義：小數(shù)補碼定義： 設(shè)設(shè)X= =0.0.x-1 -1 x-(n-1) -(n-1)，則 ，則 X 補 補= =x0 0. .x-1-1 x-(n-1) -(n-1) X 補 補 = = 2+ 2+X (mod 2) (mod 2) = = X 00X1 1 2+2+X=2-|

20、=2-|X| -1| -1X0 0 例例88+0.1011+0.1011補 補=0.1011 =0.1011 -0.1011 -0.1011補 補=2-0.1011= =2-0.1011=1010.0000-0.1011=1.0101.0000-0.1011=1.0101 10 說明說明模為模為2(2(不是不是1 1) )為為實現(xiàn)實現(xiàn)“負數(shù)負數(shù)的的x0 0=1=1” * *符號與數(shù)值一起運算符號與數(shù)值一起運算的原理分析：的原理分析：僅考慮不溢出情況僅考慮不溢出情況 0100(+4) 0100(+4) 1111(-1) 0101(+5) 1011(-5)1111(-1) 0101(+5) 101

21、1(-5) + + 0011(+3)0011(+3) + 1100(-4)+ 1100(-4) + + 1100(-41100(-4) ) + + 0100(+40100(+4) ) 0 0111(+7) 111(+7) 1 1011(-5) 011(-5) 001(+1) 001(+1) 111(-1)111(-1) 結(jié)果正確結(jié)果正確同號加同號加符號不變，符號不變，異號加異號加符號同絕對值較大者符號同絕對值較大者 13 設(shè)設(shè)X= =- -xn-2 n-2 x0 0， Y 補 補= =1 1yn-2n-2 y0 0，xi i及及yi i=0=0或或1 1 則則 X 補 補 = = 2 2n n

22、+ +X = = 2 2n-1 n-1+(2 +(2n-1 n-1-1)+1+ -1)+1+X = 1 0 = 1 0 0 + 10 + 1 1 1 + + 1 = 1 1 = 1 0 0 0 0 - - xn-2 n-2 x0 0 + + xn-2 n-2 x0 0 + 1 + 1 = = 1 1 xn-2 n-2 x0 + + 1 1 (3)(3)補碼的特性補碼的特性 * *X與與 X 補 補的關(guān)系 的關(guān)系：下述方法同樣適用于純小數(shù)下述方法同樣適用于純小數(shù) 設(shè)設(shè)X= =+ +xn-2 n-2 x0 0， Y 補 補= =0 0yn-2n-2 y0 0，xi i及及yi i=0=0或或1 1

23、 則則 X 補 補 = = X = = 0 0 xn-2 n-2 x0 Y = = Y 補 補 = = + + yn-2n-2 y0 0 Y =Y 補 補-2 -2n n = = 1 1yn-2 n-2y0 0-2 -2n-1 n-1+(2 +(2n-1 n-1-1)+1 -1)+1 = = 2 2n-1 n-1-2 -2n-1 n-1 -( -( 1111 - - yn-2 n-2 y0 0 + + 1 1 ) ) = = -(-( yn-2 n-2 y0 0 + + 1 1 ) ) 14 XX 補 補 若若X為為正數(shù)正數(shù)，改符號位為，改符號位為0 0，其余各位不變；，其余各位不變； 若若X

24、為為負數(shù)負數(shù)，改符號位為，改符號位為1 1，其余各位取反、末位加，其余各位取反、末位加1 1 例例99X=+0101=+0101， X 補 補= = X=-0101=-0101， X 補 補= =0 0 01010101； 1 1 1011011 1 X 補 補 X 若若 X 補 補最高位為 最高位為0 0，改其為正號，其余各位不變；改其為正號，其余各位不變； 若若 X 補 補最高位為 最高位為1 1，改其為負號，其余各位取反、末位加改其為負號，其余各位取反、末位加1 1 例例1010 X 補 補=0 =0 01010101，X=+=+ 01010101； X 補 補=1 =1 1011101

25、1，X= = - - 0100101 1 15 X 原 原 X 補 補 若若 X 原 原最高位為 最高位為0 0， X 補 補= =X 原 原； ； 若若 X 原 原最高位為 最高位為1 1， X 補 補= =X 原 原各數(shù)值位 各數(shù)值位取反、末位加取反、末位加1 1 例例1111 X 原 原=0 =0 0101,0101,X 補 補= = 0 0 0101 0101； X 原 原=1 =1 0101,0101,X 補 補= = 1 1 101 1011 1 X 補 補 X 原 原 若若 X 補 補最高位為 最高位為0 0， X 原 原= =X 補 補； ； 若若 X 補 補最高位為 最高位為

26、1 1， X 原 原= =X 補 補各數(shù)值位 各數(shù)值位取反、末位加取反、末位加1 1 例例1212 X 補 補=0 =0 0101,0101,X 原 原= = 0 0 0101 0101； X 補 補=1 =1 0101,0101,X 原 原= = 1 1 101 1011 1 符號位符號位( (最高位最高位) )不變不變 符號位符號位( (最高位最高位) )不變不變 16 * * X 補 補與 與-X 補 補的關(guān)系： 的關(guān)系： 設(shè)設(shè) X 補 補= =xn-1n-1xn-2n-2 x0 0，則，則 當(dāng)當(dāng)X00時時，X = = X 補 補，其中 ，其中xn-1 n-1=0 =0， -X 補 補

27、= = 1 1xn-2n-2 x0 0 +1+1 = = xn-1 n-1xn-2n-2 x0 0 +1+1 X 補 補 -X 補 補 X 補補的各位取反 的各位取反( (含符號位含符號位) )、末位加、末位加1 1 - -X 補 補 X 補 補 -X 補 補的各位取反 的各位取反( (含符號位含符號位) )、末位加、末位加1 1 例例1313 X 補 補=1 =1 01100110，-X 補 補= = 0 0 1001+1 1001+1 = = 0 0 10101010 練習(xí)練習(xí)33若若X=-01001=-01001，-X 補 補= =？ ？ 若若 X 補 補=101010 =101010，

28、-X 補 補= =？ ？- -X= =？ 當(dāng)當(dāng)X0 0時時， X 補 補 = = 2 2n n -| -|X| |，其中，其中xn-1 n-1=1 =1， -X 補 補 =| =|X|=|= 2 2n n -X 補 補= =111 111-X 補 補+1 +1 = = xn-1 n-1xn-2n-2x0 0 +1 +1 17 0 0 0100101001 0 0 0100101001 練習(xí)練習(xí)44 若若X=+01001=+01001， X 原 原= = ， X 補 補= = 若若X=-01010=-01010， X 原 原= = ， X 補 補= = 1 1 0101001010 1 1 10

29、11010110 + + 0101001010 0 0 0101001010 若若 X 原 原=001010 =001010，X= = ， X 補 補= = 若若 X 原 原=101110 =101110，X= = ， X 補 補= = - - 0111001110 1 1 1001010010 + + 0111001110 1 1 1001010010 若若 X 補 補=001110 =001110，X= = ，-X 補 補= = 若若 X 補 補=101110 =101110，X= = ，-X 補 補= = - - 1001010010 0 0 1001010010 0 0 1010110

30、101 0 0 1010110101 若若-X 補 補=101011 =101011， X 補 補= = ， X 原 原= = 若若-X 補 補=001001 =001001， X 補 補= = ， X 原 原= = 1 1 1011110111 1 1 0100101001 714 18 3 3、反碼反碼( (Ones complement) )表示表示法法 * *編碼目標編碼目標：作為原碼與補碼相互轉(zhuǎn)換時的一種作為原碼與補碼相互轉(zhuǎn)換時的一種過渡編碼過渡編碼 * *整數(shù)反碼定義整數(shù)反碼定義：設(shè)設(shè)X= =xn-2 n-2 x0 0，取模，取模=2=2n n-1-1，則，則 X 反 反 = =

31、(2 (2n n-1)+-1)+X (mod 2 (mod 2n n-1)-1) = = X 00X2 2n-1 n-1 (2(2n n-1)+-1)+X -2 -2n-1 n-1 X00 * *小數(shù)反碼定義小數(shù)反碼定義：設(shè)設(shè)X= =0.0.x-1 -1 x-(n-1) -(n-1)，模 ，模=2-2=2-2-(n-1) -(n-1)，則 ，則 X 反 反 = = (2-2 (2-2-(n-1) -(n-1) ) + + X (mod 2-2 (mod 2-2-(n-1) -(n-1) ) = = X 00X1 1 (2-2(2-2-(n-1) -(n-1)+ )+X -1 -1X00 例例1

32、414+1101+1101反 反=01101 =01101，-1101-1101反 反=10010 =10010 10 例例1515+0.1101+0.1101反 反=0.1101 =0.1101，-0.1101-0.1101反 反=1.0010 =1.0010 * *反碼與補碼關(guān)系反碼與補碼關(guān)系：若若X為為正數(shù)正數(shù)， X 補 補= =X 反 反； ； 若若X為為負數(shù)負數(shù)， X 補 補= =X 反 反+1 +1 19 11 原碼、補碼、反碼比較：原碼、補碼、反碼比較： 機器數(shù)的機器數(shù)的最高位最高位均為符號位均為符號位(0/1(0/1表示正表示正/ /負負) ) 原碼原碼 無無 1 1111 1

33、11 1 1001 001 1 1000000 0 0000 000 0 0001 001 0 0111111 反碼反碼 無無 1 1000 000 1 1110 110 1 1111111 0 0000 000 0 0001 001 0 0111111 補碼補碼 1 1000 000 1 1001 001 1 1111 111 0 0000 000 0 0001 001 0 0111111 真值真值 -2-2n-1 n-1 -(2 -(2n-1 n-1-1) -1) -1 -1 0 0 +1 +(2+1 +(2n-1 n-1-1) -1) +0+0補 補=-0 =-0補 補，補碼比原碼、反碼

34、 ，補碼比原碼、反碼多表示多表示一個負數(shù)一個負數(shù) 若真值若真值X為為正數(shù)正數(shù)， X 原 原= =X 補 補= =X 反 反 若若真值真值X為為負數(shù)負數(shù)， X 補 補= =X 原 原數(shù)值位各位求反、末位 數(shù)值位各位求反、末位+1+1 X 反 反= =X X 原 原數(shù)值位各位求反 數(shù)值位各位求反 移碼移碼 0 0000 000 0 0001 001 0 0111 111 1 1000 000 1 1001 001 1 1111111 20 4 4、移碼表示法、移碼表示法 * *編碼目標：編碼目標：數(shù)數(shù)( (含符號及數(shù)值含符號及數(shù)值) )連續(xù)時，編碼連續(xù)連續(xù)時，編碼連續(xù) * *整數(shù)移碼定義：整數(shù)移碼

35、定義： 設(shè)設(shè)X= =xn-2 n-2 x0 0，取模，取模=2=2n n、偏移量、偏移量=2=2n-1 n-1，則 ，則 X 移 移 = = 2 2n-1 n-1+ +X (mod 2 (mod 2n n) ) = = 2 2n-1 n-1 + + X -2 -2n-1 n-1 X2 2n-1 n-1 例例1616-111-111移 移=0001 =0001，-001-001移 移=0111 =0111， 000000移 移=1000 =1000， +001+001移 移=1001 =1001，+111+111移 移=1111 =1111，-1000-1000移 移=0000 =0000 補碼

36、補碼 1 1000 000 1 1001 001 1 1111 111 0 0000 000 0 0001 001 0 0111111 移碼移碼 0 0000 000 0 0001 001 0 0111 111 1 1000 000 1 1001 001 1 1111111 真值真值 -2-2n-1 n-1 -(2 -(2n-1 n-1-1) -1) -1 -1 0 +1 +(20 +1 +(2n-1 n-1-1) -1) * *移碼的特性：移碼的特性： 數(shù)在數(shù)軸上為數(shù)在數(shù)軸上為連續(xù)編碼連續(xù)編碼( (似無似無符號數(shù)符號數(shù)) )，便于比較，便于比較大小大小 X 移 移= =X 補 補符號位取反、

37、其余各位不變 符號位取反、其余各位不變 21 三、十進制數(shù)編碼三、十進制數(shù)編碼 * *BCDBCD碼碼( (Binary Coded Decimal) )：又稱又稱二二- -十進制編碼十進制編碼，是指，是指 用用4 4位二進制編碼表示位二進制編碼表示1 1位十進制數(shù)位的編碼方式位十進制數(shù)位的編碼方式 * *BCDBCD碼種類：碼種類：分分有權(quán)碼有權(quán)碼和和無權(quán)碼無權(quán)碼兩種，最常用的是兩種，最常用的是84218421碼碼 十進制數(shù)十進制數(shù)0 01 12 23 34 45 56 67 78 89 9 84218421碼碼00000000 00010001 00100010 00110011 0100

38、0100 01010101 01100110 01110111 10001000 10011001 余余3 3碼碼00110011 01000100 01010101 01100110 01110111 10001000 10011001 10101010 10111011 11001100 BCDBCD碼缺省時指碼缺省時指84218421碼碼( (特殊聲明除外特殊聲明除外) )！ * *十進制數(shù)的編碼方法：十進制數(shù)的編碼方法： 對各數(shù)位按序用對各數(shù)位按序用BCDBCD碼編碼，符號編碼放在最后；碼編碼，符號編碼放在最后； 用用特定編碼特定編碼表示符號表示符號( (如如11001100和和110

39、11101表示正和負表示正和負) ) 例例 + +427427表示為表示為0100 0010 0111 0100 0010 0111 11001100 - -123123表示為表示為0001 0010 0011 0001 0010 0011 11011101 22 四、字符及字符串編碼四、字符及字符串編碼 1 1、字符編碼、字符編碼 * *字符編碼：字符編碼：字符在字符在中中惟一惟一的的數(shù)字化數(shù)字化代碼，代碼， 表示字符在字符集中的表示字符在字符集中的序號序號或或特征號特征號 * *字符編碼的類型：字符編碼的類型：有輸入碼、內(nèi)碼、交換碼、字模碼有輸入碼、內(nèi)碼、交換碼、字模碼4 4種種 鍵盤鍵盤

40、 計算機計算機B B 轉(zhuǎn)換轉(zhuǎn)換 處理處理 傳送傳送 字模碼字模碼 內(nèi)內(nèi) 碼碼輸入碼輸入碼 交換碼交換碼 顯示器顯示器 傳送傳送 計算機計算機A A 交換碼交換碼 內(nèi)內(nèi) 碼碼 內(nèi)內(nèi) 碼碼 字符字符 數(shù)據(jù)數(shù)據(jù) 字符字符 字模庫字模庫 MEMMEM 交換碼交換碼 字符字符傳送時傳送時的編碼的編碼( (序號序號),), 僅與字符集大小有關(guān)僅與字符集大小有關(guān) 與輸入法、字與輸入法、字 符集大小有關(guān)符集大小有關(guān) 與字體、字號大小有關(guān)與字體、字號大小有關(guān) 字符字符存儲時存儲時的編碼的編碼( (數(shù)據(jù)數(shù)據(jù)表示表示),), 與字符集大小、存儲器字長有關(guān)與字符集大小、存儲器字長有關(guān) 23 * *有關(guān)字符編碼的有關(guān)字

41、符編碼的： 字符編碼字符編碼均指均指交換碼交換碼的編碼！的編碼！ 字符數(shù)據(jù)字符數(shù)據(jù)均指均指內(nèi)碼內(nèi)碼的編碼！的編碼！ * *常見字符編碼常見字符編碼( (交換碼交換碼) )種類：種類： 編碼種類編碼種類 碼點碼點 數(shù)量數(shù)量 編碼編碼 長度長度 說明說明 ASCIIASCII碼碼1281287 7美國標準信息交換碼，英文，使用最廣泛美國標準信息交換碼，英文，使用最廣泛 EBCDICEBCDIC碼碼2562568 8擴展二擴展二- -十進制交換碼，英文，十進制交換碼，英文，IBMIBM定義定義 UnicodeUnicode碼碼65536655361616統(tǒng)一字符碼，支持各國語言，使用較廣泛統(tǒng)一字符碼

42、，支持各國語言，使用較廣泛 ANSIANSI碼碼2562568 8美國國家標準協(xié)會交換碼，英文，含美國國家標準協(xié)會交換碼，英文，含ASCIIASCII碼碼 GB2312-80GB2312-80744574451414漢字國標碼，中文漢字國標碼，中文 碼點數(shù)量碼點數(shù)量需編碼的信息數(shù)量；需編碼的信息數(shù)量； ( (如交換碼指字符數(shù)，字模碼指字符點陣數(shù)如交換碼指字符數(shù)，字模碼指字符點陣數(shù)) ) 編碼長度編碼長度采用等長編碼，長度采用等長編碼，長度= log= log2 2 碼點數(shù)量碼點數(shù)量 ，UnicodeUnicode可變長可變長 24 2 2、字符串編碼、字符串編碼 * *字符串特性：字符串特性：

43、 由多個字符由多個字符構(gòu)成構(gòu)成 所含字符數(shù)不固定所含字符數(shù)不固定 * *字符串編碼方法：字符串編碼方法： 由各個字符編碼由各個字符編碼組成組成 通過通過特定編碼特定編碼標志字符串的結(jié)束，結(jié)束編碼放在最后標志字符串的結(jié)束，結(jié)束編碼放在最后 字符集必須包含該字符字符集必須包含該字符( (如如ASCIIASCII碼中編碼為碼中編碼為0 0的字符的字符) ) 例例字符串字符串“amam”的的ASCIIASCII編碼編碼為為1100001 1101101 1100001 1101101 00000000000000 作業(yè)一：作業(yè)一：P78P787927927 7 25 * *冗余校驗思想：冗余校驗思想：

44、 用用待發(fā)待發(fā)數(shù)據(jù)數(shù)據(jù)(M)(M)形成形成校驗位校驗位( (P)P)，M M與與P P一起一起傳送傳送 用用接收接收數(shù)據(jù)數(shù)據(jù)(M(M) )形成形成新新校驗位校驗位( (P P”) )，用，用P P及及P P”檢錯檢錯/ /糾錯糾錯 五、校驗碼五、校驗碼 存儲器存儲器 或或 傳輸傳輸 線路線路 M 函數(shù)函數(shù)f P 輸出方輸出方 比較器比較器 P” P 糾正器糾正器 M 函數(shù)函數(shù)f M 輸入方輸入方 狀態(tài)狀態(tài) * *術(shù)語：術(shù)語：校驗碼校驗碼由由數(shù)據(jù)數(shù)據(jù)和和校驗校驗位位組成的組成的信息編碼信息編碼 檢錯檢錯( (檢驗檢驗)檢查檢查數(shù)據(jù)在傳送過程中數(shù)據(jù)在傳送過程中有有/ /無無錯誤錯誤 糾錯糾錯( (

45、校正校正)根據(jù)根據(jù)錯誤位置錯誤位置糾正數(shù)據(jù)糾正數(shù)據(jù) * *常見校驗碼：常見校驗碼：奇偶校驗碼、海明校驗奇偶校驗碼、海明校驗碼，循環(huán)碼，循環(huán)冗余校驗碼冗余校驗碼 26 1 1、奇偶校驗碼、奇偶校驗碼 * *編碼原理：編碼原理：采用采用1 1位校驗位位校驗位，使校驗碼中使校驗碼中 “1 1”的位數(shù)的位數(shù)為奇數(shù)為奇數(shù) 或偶數(shù)個或偶數(shù)個 * *校驗原理：校驗原理：檢測校驗碼中檢測校驗碼中 “1 1”的的個數(shù)特性個數(shù)特性，是否有錯是否有錯 例例11 數(shù)據(jù)數(shù)據(jù) 1010010 1010010 0110100 0110100 1100011 1100011 奇校驗碼奇校驗碼 1010010 1010010

46、0110100 0110100 1100011 1100011 偶校驗碼偶校驗碼 1010010 1010010 0110100 0110100 1100011 1100011 有有奇校驗奇校驗/ /偶偶校驗校驗方法方法為為奇數(shù)奇數(shù)/ /偶數(shù)偶數(shù)個個 * *校驗碼編碼：校驗碼編碼： ( (設(shè)數(shù)據(jù)信息為設(shè)數(shù)據(jù)信息為m mn nm mn-1 n-1m m1 1) ) 校驗碼組成校驗碼組成共共n+1n+1位，位， 數(shù)據(jù)數(shù)據(jù)m mn nm mn-1 n-1mm1 1校驗位校驗位p p1 1 異或與模異或與模2 2加加 a b a b = = a+ba+b (mod 2)(mod 2) 校驗位編碼校驗位

47、編碼奇奇校驗時：校驗時：P=pP=p1 1=m=mn n+m+mn-1 n-1+m +m1 1+1 (mod 2)+1 (mod 2) 偶偶校驗時：校驗時：P=pP=p1 1=m=mn n+m+mn-1 n-1+m +m1 1 (mod 2) (mod 2) 27 * *校驗方法：校驗方法： 故障字故障字S S S=PS=P P P”，其中，其中P P是接收的、是接收的、P P”是形成是形成的的 檢錯檢錯 若若S=0S=0無錯誤，若無錯誤，若S=1S=1有有錯誤錯誤 糾錯糾錯 無此無此能力能力 ( (無法獲得錯誤位置無法獲得錯誤位置) ) 例例22 接收的接收的奇校驗碼奇校驗碼 故障字故障字S

48、 S 錯誤位數(shù)錯誤位數(shù)( (人工人工) ) 發(fā)送碼發(fā)送碼( (參考參考) ) 1 0 1 0 0 1 0 0001 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1?10 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0?10 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0?20 1 1 0 1 1 0 1 * *校驗?zāi)芰Γ盒ｒ災(zāi)芰Γ褐荒軝z測只能檢測奇數(shù)個奇數(shù)個錯誤，無糾錯能力錯誤，無糾錯能力 例例33下列接收的校驗碼下列接收的校驗碼0100101001、1010010100、1001110011中，只中，只 有一個有有一個有奇數(shù)個錯，發(fā)送奇數(shù)個錯，發(fā)送時采用的

49、是奇時采用的是奇校驗還是偶校驗還是偶校驗碼？校驗碼？ * *應(yīng)用：應(yīng)用：應(yīng)用于應(yīng)用于I/OI/O傳輸傳輸?shù)臄?shù)據(jù)校驗的數(shù)據(jù)校驗 25 28 2 2、海明校驗碼、海明校驗碼 * *編碼原理：編碼原理：將數(shù)據(jù)分成將數(shù)據(jù)分成k k個有重疊的組個有重疊的組， 每個組使用一每個組使用一個奇偶校驗位個奇偶校驗位( (共共k k個校驗位個校驗位) ) * *校驗原理：校驗原理：多重奇偶校驗多重奇偶校驗，即，即某位某位錯誤錯誤導(dǎo)致導(dǎo)致多個校驗位變化多個校驗位變化， 從而實現(xiàn)檢錯與糾錯從而實現(xiàn)檢錯與糾錯( (定位定位) ) * *校驗?zāi)芰δ繕耍盒ｒ災(zāi)芰δ繕耍耗苣軝z測并糾正檢測并糾正1 1位錯誤位錯誤 * *校驗方

50、法：校驗方法： ( (能力目標能力目標方法推導(dǎo)方法推導(dǎo)) ) 設(shè)數(shù)據(jù)設(shè)數(shù)據(jù)M=M=m mn nmm1 1，校驗位，校驗位P=P=p pk kpp1 1( (即有即有k k個奇偶檢驗組個奇偶檢驗組) ) 校驗校驗碼的編碼規(guī)則碼的編碼規(guī)則? ?k k的長度的長度? ? 故障字故障字S S S=S=s sk kss1 1，s si i=p=pi i p pi i”=p=pi i + + p pi i” (mod 2)(mod 2) 檢錯檢錯 若若S=0S=0無錯誤，無錯誤，S0S0有有錯誤錯誤 糾錯糾錯 S S值表示錯誤位置值表示錯誤位置( (共有共有n+kn+k種種) )，信息信息取反取反 26

51、校驗碼常稱為校驗碼常稱為單糾單糾 錯碼錯碼SECSEC 29 * *校驗位位數(shù)校驗位位數(shù)k k的確定：的確定： 校驗?zāi)芰δ繕艘笮ｒ災(zāi)芰δ繕艘?2 2k k-1n+k-1n+k，其中其中n+kn+k表示表示1 1位錯誤種類位錯誤種類 n n1 12 24 45 51111 12122626 27275757 5858120120 k(k(最小值最小值) )2 23 34 45 56 67 7 k k的取值的取值 * *校驗碼編碼規(guī)則：校驗碼編碼規(guī)則： ( (以以4 4個校驗組為例個校驗組為例) ) 故障字故障字S S值的約定值的約定S0S0時表示錯誤位置，時表示錯誤位置，S S值有值有n+k

52、+1n+k+1種種 無無 錯錯 誤誤: : 0000 0000 (校驗碼位置序號從校驗碼位置序號從1 1開始編號開始編號) ) 校驗位錯校驗位錯: : 0001(p0001(p1 1) )、0010(p0010(p2 2) )、0100(p0100(p3 3) )、1000(p1000(p4 4) ) 數(shù)據(jù)位錯數(shù)據(jù)位錯: : S S的其余碼值的其余碼值(2(2個個s si i=1)=1) 校驗碼的組成規(guī)則校驗碼的組成規(guī)則按按“S S值錯誤值錯誤位置位置”規(guī)則規(guī)則排列信息排列信息 位置序號位置序號 151514141313 1212 1111 10109 98 87 76 65 54 43 32

53、 21 1 信息排列信息排列m m11 11 m m10 10 m m9 9m m8 8m m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1 校驗位次重要，校驗位次重要，1 1個個s si i=1=1 30 位置及位置及 信息信息 校驗組校驗組 1515141413131212111110109 98 87 76 65 54 43 32 21 1 11111111 11101110 11011101 11001100 10111011 10101010 10011001 10001000 01110111 0110

54、0110 01010101 01000100 00110011 00100010 00010001 m m11 11 m m10 10 m m9 9m m8 8m m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1 第第4 4組組 第第3 3組組 第第2 2組組 第第1 1組組 檢驗位的編碼規(guī)則檢驗位的編碼規(guī)則 ( (缺省為偶校驗方式缺省為偶校驗方式) ) p p4 4m m11 11+m m1010+m m9 9+m m8 8+m m7 7+m m6 6+m m5 5 (mod 2) (mod 2) p p3 3m

55、 m11 11+m m1010+m m9 9+m m8 8 +m m4 4+m m3 3+m m2 2 (mod 2) (mod 2) p p2 2m m11 11+m m1010 +m m7 7+m m6 6 +m m4 4+m m3 3 +m m1 1 (mod 2) (mod 2) p p1 1m m11 11 +m m9 9 +m m7 7 +m m5 5+m m4 4 +m m2 2+m m1 1 (mod 2) (mod 2) * *應(yīng)用：應(yīng)用：常應(yīng)用于常應(yīng)用于I/OI/O傳輸、傳輸、RAIDRAID存儲等方面的校驗存儲等方面的校驗 28 信息位加入信息位加入校驗組規(guī)則校驗組規(guī)則

56、信息位的位置信息位的位置h hk khh1 1中，中，h hi i=1=1時就時就加入加入第第i i校驗校驗組組 該信息位錯誤時該信息位錯誤時s si i=1=1 31 解：解：2 23 3-1-17+37+3、2 24 4-1-17+4 7+4 校驗位位數(shù)校驗位位數(shù)=4=4位；位； 例例55求字符求字符b b的的ASCIIASCII碼碼(m(m7 7mm1 1=1100010)=1100010)的海明偶校驗碼。的海明偶校驗碼。 例例44若數(shù)據(jù)有若數(shù)據(jù)有1616位，則海明校驗碼的校驗位最少為多少位位，則海明校驗碼的校驗位最少為多少位? ? 解：解：2 2k k-116+k-116+k，k k最

57、小為最小為5 5位位(2(24 4-1-12020、2 25 5-1-121)21)。 根據(jù)故障字約定，校驗碼排列根據(jù)故障字約定，校驗碼排列m m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1 故偶校驗碼故偶校驗碼=m=m7 7m m6 6m m5 5p p4 4m m4 4m m3 3m m2 2p p3 3m m1 1p p2 2p p1 1=1=1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 根據(jù)檢驗位編碼規(guī)則，得根據(jù)檢驗位編碼規(guī)則，得 （偶校驗方式）（偶校驗方式） p p4 4=

58、m=m7 7 m m6 6 m m5 5 =0 =0 p p3 3= = m m4 4 m m3 3 m m2 2 =1=1 p p2 2=m=m7 7 m m6 6 m m4 4 m m3 3 m m1 1=0=0 p p1 1=m=m7 7 m m5 5 m m4 4 m m2 2 m m1 1=0=0 29 32 例例66續(xù)例續(xù)例5 5，請分析下列接收的海明偶校驗碼是否有錯？錯，請分析下列接收的海明偶校驗碼是否有錯？錯 誤時的位置？誤時的位置？1100001101011000011010、1100000100011000001000、1100100100011001001000 解：解：

59、接收的接收的M M=1100010=1100010、P P=0110=0110，可求得，可求得P P”=0100=0100， S=P S=P+P+P”(mod 2)(mod 2)，即無進位的模，即無進位的模2 2加，得加，得S=0010S=0010， 有錯誤，位置有錯誤，位置2 2錯誤錯誤(p(p2 2位錯位錯) )，數(shù)據(jù)，數(shù)據(jù)M=1100010M=1100010 接收的接收的M M=1100000=1100000、P P=0100=0100，可求得，可求得P P”=0001=0001， S=P S=P+P+P”(mod 2)(mod 2)，得，得S=0101S=0101， 有錯誤，位置有錯誤

60、，位置5 5錯誤錯誤( (數(shù)據(jù)位數(shù)據(jù)位m m2 2錯錯) )，數(shù)據(jù)，數(shù)據(jù)M=11000M=11000 0 0 接收的接收的M M=1101000=1101000、P P=0100=0100，可求得，可求得P P”=0110=0110， S=P S=P+P+P”(mod 2)(mod 2)，得，得S=0010S=0010， 有錯誤，有錯誤，p p2 2錯錯？實際是？實際是m m4 4及及m m2 2位錯位錯(M(M=110=110 0 0 0)0)！ * *校驗?zāi)芰Γ盒ｒ災(zāi)芰Γ篠ECSEC能能檢測并糾正檢測并糾正1 1位錯，最多只可位錯，最多只可發(fā)現(xiàn)發(fā)現(xiàn)2 2位錯！位錯！ 30 33 3 3、循