第二章(數(shù)據(jù)的表示與數(shù)據(jù)校驗(yàn))77

1、第2章數(shù)據(jù)的表示與數(shù)據(jù)校驗(yàn)本章主要內(nèi)容 數(shù)據(jù)表示形式的多樣性 二進(jìn)制數(shù)值數(shù)據(jù)的編碼格式 信息傳輸過(guò)程中的檢錯(cuò)與糾錯(cuò)碼2.1 數(shù)據(jù)表示形式的多樣性 數(shù)值、文字、符號(hào)、語(yǔ)音、圖形、圖像等數(shù)值、文字、符號(hào)、語(yǔ)音、圖形、圖像等統(tǒng)稱數(shù)據(jù)，在計(jì)算機(jī)內(nèi)部，都必須用統(tǒng)稱數(shù)據(jù)，在計(jì)算機(jī)內(nèi)部，都必須用數(shù)字?jǐn)?shù)字化編碼化編碼的形式被的形式被存儲(chǔ)存儲(chǔ)、加工加工 、傳送傳送 。 數(shù)字化編碼數(shù)字化編碼二要素二要素 少量簡(jiǎn)單的基本符號(hào)少量簡(jiǎn)單的基本符號(hào) 一定的組合規(guī)則一定的組合規(guī)則 表示表示大量復(fù)雜多樣大量復(fù)雜多樣的信息的信息2.1.1 適合于人的數(shù)據(jù)表示形式 如時(shí)鐘、十進(jìn)制、語(yǔ)音數(shù)據(jù)、圖形數(shù)據(jù)等。 輸入計(jì)算機(jī)之前的數(shù)據(jù)、計(jì)

2、算機(jī)輸出的數(shù)據(jù)都要力爭(zhēng)符合人的習(xí)慣。2.1.2 適合計(jì)算機(jī)的表示形式-編碼 采用二進(jìn)制的理由 符號(hào)個(gè)數(shù)最少，物理上容易實(shí)現(xiàn)(數(shù)字電路)。用二個(gè)狀態(tài)如導(dǎo)通/截止，高/低電壓等來(lái)表示，比用十個(gè)狀態(tài)方便。 用二進(jìn)制碼表示數(shù)值數(shù)據(jù)運(yùn)算規(guī)則簡(jiǎn)單。加法和乘法各只有4條運(yùn)算規(guī)則。 十進(jìn)制與二進(jìn)制轉(zhuǎn)換簡(jiǎn)單。 與二值邏輯的真、假兩個(gè)值對(duì)應(yīng)簡(jiǎn)單。 高電壓1，低電壓-0。二進(jìn)制無(wú)符號(hào)數(shù)據(jù)算術(shù)運(yùn)算規(guī)則二進(jìn)制無(wú)符號(hào)數(shù)據(jù)算術(shù)運(yùn)算規(guī)則(1) 加法運(yùn)算規(guī)則加法運(yùn)算規(guī)則 0+0=0 例如：例如： 0101 0+1=1 +) 0001 1+0=1 0110 1+1=0 并產(chǎn)生進(jìn)位并產(chǎn)生進(jìn)位(2) 減法運(yùn)算規(guī)則減法運(yùn)算規(guī)則 0-0

3、=0 例如：例如： 1011 0-1=1 并產(chǎn)生借位并產(chǎn)生借位 -) 0101 1-0=1 0110 1-1=0二進(jìn)制數(shù)據(jù)算術(shù)運(yùn)算規(guī)則(3) 乘法運(yùn)算規(guī)則 例如： 1101 0X0=0 X) 0101 0X1=0 1101 1X0=0 1101 1X1=1 1000001(4)除法運(yùn)算規(guī)則 1101 例如： 1110101/1001 1001 1110101 1001 1011 1001 01001 1001 0 0000進(jìn)位記數(shù)法與進(jìn)制轉(zhuǎn)換 進(jìn)位記數(shù)法 任何一個(gè)數(shù)都可以寫成以下算式： N=Di*ri (i=-k,-k+1,.,m-1)N 代表一個(gè)數(shù)值r 是這個(gè)數(shù)制的基(Radix)。r=2,

4、8,10,16,i表示這些符號(hào)排列的位號(hào)Di是位號(hào)為i的位上的一個(gè)符號(hào)ri是位號(hào)為i的位上的一個(gè) 1 代表的值Di*ri是第i位的所代表的實(shí)際值表示m+k位的值求累加和計(jì)算機(jī)中常用的數(shù)制常用數(shù)制基數(shù)r基本符號(hào)第i位的權(quán)值二進(jìn)制20,12i八進(jìn)制80,1,2,3,4,5,6,78i十六進(jìn)制160,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F16i十進(jìn)制100,1,2,3,4,5,6,7,8,910i十-八-十六進(jìn)制數(shù)據(jù)的二進(jìn)制編碼十進(jìn)制數(shù)八進(jìn)制數(shù)十六進(jìn)制數(shù)十進(jìn)制數(shù)八進(jìn)制數(shù)十六進(jìn)制數(shù)0000000081000100100019100120100010A101030110011B101

5、141000100C110051010101D110161100110E111071110111F1111 例(101)2 =(5) 8 =(5)16(101101011)2=(101 101 011) 2 =(5 5 3) 8(101101011)2=(1 0110 1011) 2 =(1 6 B) 16十進(jìn)制數(shù) 二十進(jìn)制編碼(BCD碼)表示法是指用四位二進(jìn)制數(shù)字來(lái)表示一位十進(jìn)制數(shù)字。 多位十進(jìn)制數(shù)字表示為這種編碼的數(shù)串。 由于24=16個(gè)狀態(tài)，而二進(jìn)制只要10個(gè)狀態(tài)，因此需要舍去其中6種狀態(tài)。 根據(jù)舍去狀態(tài)的不同(有多種方案)，BCD碼分為有權(quán)碼和無(wú)權(quán)碼。有權(quán)碼無(wú)權(quán)碼十進(jìn)十進(jìn)制數(shù)制數(shù)842

6、1碼碼2421碼碼5211碼碼4311碼碼00000000000000000100010001000100012001000100011001130011001101010100401000100011110005010110111000011160110110010101011701111101110011008100011101110111091001111111111111十進(jìn)十進(jìn)制數(shù)制數(shù)余余3碼碼格雷碼格雷碼（1）格雷碼格雷碼（2）000110000000010100000101002010100110110301100010001040111011010105100011101011

7、6100110100011710101000000181011110010019110001001000 例如十進(jìn)制數(shù)6578用8421碼表示。65780110 0101 0111 1000hexbinary36353738ASCII(hex)符號(hào)數(shù)據(jù)的表示形式 鍵盤上可以輸入的符號(hào)： 大小寫英文字母：52個(gè) 數(shù)字09：10個(gè) 專用符號(hào) 控制符號(hào) ASCII和EBCDLC碼(略)每個(gè)字符在內(nèi)存中占用一個(gè)字節(jié)。ASCII字符編碼集字符編碼集 b6 b5 b4 000 001 010 011 100 101 110 111 b3 b2 b1 b0 0000 NUL DLE SP 0 P , p 0

8、001 SOH DC1 ! 1 A Q a q 0010 STX DC2 “ 2 B R b r 0011 ETX DC3 # 3 C S c s 0100 EOT DC4 $ 4 D T d t 0101 ENQ NAK % 5 E U e u 0110 ACK SYN & 6 F V f v 0111 BEL ETB 7 G W g w 1000 BS CAN ( 8 H X h x 1001 HT EM ) 9 I Y i y 1010 LF SUB * : J Z j z 1011 VT ESC + ; K k 1100 FF FS , N n 1111 SI US / ? O

9、 _ o 符號(hào)數(shù)據(jù)(字符、漢字)的顯示 字符、漢字等只能以圖形的方式顯示給人看。一般以點(diǎn)陣的形式顯示。如：16*16的漢字點(diǎn)陣8*8的點(diǎn)陣漢字的輸入、存儲(chǔ) 漢字存儲(chǔ)必須遵守國(guó)家標(biāo)準(zhǔn)。 英文符號(hào)采用ASCII碼，1Byte。 常用的漢字有6000多個(gè)，故需要2B來(lái)存儲(chǔ)。為了區(qū)分漢字和英文符號(hào)，所以在機(jī)器中，描述漢字時(shí)每個(gè)字節(jié)的最高位為1。因此漢字編碼有機(jī)內(nèi)碼和機(jī)外碼之分。 機(jī)外碼常用的有國(guó)標(biāo)碼 GB2312。 機(jī)內(nèi)碼與國(guó)標(biāo)碼的關(guān)系 機(jī)內(nèi)碼國(guó)標(biāo)碼8080H 例如國(guó)標(biāo)碼(十六進(jìn)制)二進(jìn)制機(jī)內(nèi)碼機(jī)內(nèi)碼(十六進(jìn)制)3B7A0011 1011 0111 10101011 10111111 1010BBFA

10、 輸入碼 鍵盤輸入。拼音、五筆字型等 語(yǔ)音輸入。 手寫輸入。 掃描輸入。圖形數(shù)據(jù)表示形式 圖形可分為 規(guī)則圖形，如直線，圓、圓弧等。 不規(guī)則圖形，如照片、地圖等。 可以用點(diǎn)陣表示任何圖形，但需要較多的空間。 對(duì)于規(guī)則圖形，可以存儲(chǔ)有關(guān)的特征和規(guī)則即可。 直線,可以存儲(chǔ)起點(diǎn)、終點(diǎn)和線條的類型即可。2.1.3 數(shù)據(jù)格式的相互轉(zhuǎn)換 通過(guò)鍵盤向計(jì)算機(jī)輸入的數(shù)字肯定是用ASCII碼形式表示的十進(jìn)制數(shù)，必須通過(guò)軟件將其轉(zhuǎn)換成二進(jìn)制數(shù)。反之，計(jì)算機(jī)的運(yùn)行結(jié)果輸出時(shí)，常常需要通過(guò)軟件轉(zhuǎn)換成十進(jìn)制數(shù)。 由于二進(jìn)制數(shù)冗長(zhǎng)，讀寫不方便等缺點(diǎn)，常使用八進(jìn)制或十六進(jìn)制來(lái)進(jìn)行書寫等。 需要在不同進(jìn)制數(shù)之間轉(zhuǎn)換。十進(jìn)制轉(zhuǎn)二

11、進(jìn)制整數(shù)部分除2取余 小數(shù)部分乘2取整2 1 1222521011010.625 * 210.25 * 200.5 * 21 0.0 除盡為止 求得位數(shù)滿足要求為止低低高高高高低低(11)10=(1011)2 (0.625)10=(0.101)2(11.625)10=(1011.101)2二進(jìn)制轉(zhuǎn)十進(jìn)制 從二進(jìn)制數(shù)求其十進(jìn)制的值，逐位碼權(quán)累加求和。 (1011.101)2=1*23+0*22+1*21+1*20+ 1*2-1+0*2-2+1*2-3 =8+0+2+1+0.5+0.0+0.125 =11.625二到八或十六進(jìn)制轉(zhuǎn)換二到八 從小數(shù)點(diǎn)向左右三位一分組（10 011 100 . 01)

12、2 = ( 234 . 2 )8 010 二到十六 從小數(shù)點(diǎn)向左右四位一分組（1001 1100 . 01)2 = ( 9C . 4 )16 0100 說(shuō)明：整數(shù)部分不足位數(shù)對(duì)轉(zhuǎn)換無(wú)影響， 小數(shù)部分不足位數(shù)要補(bǔ)零湊足,否則出錯(cuò)。八或十六到二進(jìn)制轉(zhuǎn)換 (107.6)8=(001 000 111.110)2 (1E7.6)16=(0001 1110 0111.1100)2下列表格內(nèi)容請(qǐng)記下來(lái)i2ii2i01664127128248256389512416101024532161024*642.2機(jī)器數(shù)的編碼格式 機(jī)器數(shù)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的二進(jìn)制編碼形式（有多種）。 真值是指原來(lái)書寫形式表示的數(shù)(

13、實(shí)際值)。 選擇機(jī)器數(shù)的原則 只照顧機(jī)器(運(yùn)算方便、節(jié)省存儲(chǔ)空間)，不照顧人(是否便于理解) 。 按小數(shù)點(diǎn)位置是否固定，機(jī)器數(shù)分為定點(diǎn)數(shù)和浮點(diǎn)數(shù)(實(shí)數(shù)) 。 為了有效、方便地表示正負(fù)數(shù)，定點(diǎn)數(shù)表示又分為原碼、反碼、補(bǔ)碼、移碼等編碼方案。2.2.1 二進(jìn)制定點(diǎn)數(shù)的原碼表示 二進(jìn)制數(shù)據(jù)編碼方法應(yīng)達(dá)到目標(biāo)：如何能方便地表示正數(shù)、零和負(fù)數(shù)，盡可能地有利于簡(jiǎn)化對(duì)它們實(shí)現(xiàn)算術(shù)運(yùn)算用到的規(guī)則。1、符號(hào)表示數(shù)的符號(hào)只有“+”和“-”，每一位二進(jìn)制信息只有“0”和“1”。可以用“0”表示“+”，“1”表示“-” 。由于符號(hào)是放在最左邊，所以存放數(shù)據(jù)的單元中的最高位用于表示該數(shù)據(jù)的符號(hào)。 例如：N1=+0.101

14、1 N2=-0.1101 則它們?cè)跈C(jī)器中可以表示為：N1 0.1011N2 1.1101符號(hào)數(shù)值部分2、運(yùn)算中符號(hào)處理 運(yùn)算中存在的問(wèn)題：是否與數(shù)值一起參與運(yùn)算，結(jié)果給下一次運(yùn)算帶來(lái)什么影響等。 將符號(hào)位與數(shù)值位一起編碼的方法分為原碼、補(bǔ)碼、反碼、移碼等。 原碼表示法中機(jī)器數(shù)分為符號(hào)和數(shù)值兩部分。符號(hào)用“0”表示該數(shù)為正，“1”表示該數(shù)為負(fù)。數(shù)值部分為真值的絕對(duì)值。符號(hào)數(shù)值部分的絕對(duì)值 例如 X=+0.1011,Y=-0.1101,求X原,Y原。 解 根據(jù)定義得： X原=0.1011Y原=1.11013、原碼表示 用公式表示：對(duì)于小數(shù)X，其原碼表示定義為：X 1X=0X原=1-X 0=X-1

15、性質(zhì)1 真值0的原碼表示。 +0原=0.0000 -0原=1.0000 從上可知，0的原碼表示形式不是唯一的。 性質(zhì)2 若X原=X0.X1X2X3Xn，X0表示原碼機(jī)器數(shù)的符號(hào)位，它滿足： 0 X=0 X0= 1 X=X=0 X原= 2n-X 0=X-2n 優(yōu)點(diǎn)：簡(jiǎn)單，直觀，易懂。 缺點(diǎn)：做加減法時(shí)，需要將符號(hào)位和數(shù)值部分分開處理。 原碼表示進(jìn)行加減運(yùn)算的各種情況。要求操作第一操作數(shù)符 第二操作數(shù)符 實(shí)際操作加法+ +- - - -+ +- -+減法+-+ +- -+ +- -+ + +-2.2.2 二進(jìn)制定點(diǎn)數(shù)的補(bǔ)碼表示 從上表可以看出由于負(fù)數(shù)的原碼表示，在兩操作數(shù)符號(hào)相異時(shí)，應(yīng)作加運(yùn)算實(shí)際

16、上改為減運(yùn)算；本應(yīng)作減運(yùn)算實(shí)際上改為加運(yùn)算。 倘若能找到一種機(jī)器數(shù)的表示法，對(duì)它所表示的正負(fù)數(shù)，要求做加法就作加法，且結(jié)果為正確的機(jī)器數(shù)表示；對(duì)于做減法，減去一個(gè)負(fù)數(shù)等于加上與這個(gè)負(fù)數(shù)值對(duì)應(yīng)的正數(shù)，減去一個(gè)正數(shù)，等于加上與這個(gè)正數(shù)值相等的負(fù)數(shù)。 好處：減法也能轉(zhuǎn)變?yōu)榧臃ā７?hào)位與數(shù)值部分一起參與運(yùn)算簡(jiǎn)化了運(yùn)算規(guī)則 先看兩個(gè)十進(jìn)制數(shù)的運(yùn)算： 79-38=41 79+62=141 如果使用兩位十進(jìn)制數(shù)的運(yùn)算器（如算盤），多余的100因?yàn)槌隽诉\(yùn)算器的位數(shù)和范圍而自動(dòng)丟掉，結(jié)果為41。 在數(shù)學(xué)上可以用同余式表示： 79+(-38)=79+62=41 (mod 100) 進(jìn)一步定義為： -38=62

17、(mod 100) 稱-38的補(bǔ)碼(對(duì)模100而言)是62。 結(jié)論：負(fù)數(shù)用補(bǔ)碼表示時(shí)，可以把減法轉(zhuǎn)化為加法。 在計(jì)算機(jī)中，機(jī)器能表示的數(shù)據(jù)位數(shù)是固定的，其運(yùn)算都是有模的運(yùn)算。位數(shù)模數(shù)整數(shù)n2n小數(shù)n2 若運(yùn)算結(jié)果超出了能表示的數(shù)值范圍，則只保留它的低n位，超過(guò)n位的高位部分就自動(dòng)舍棄了(類似于向一個(gè)杯子倒水)。 補(bǔ)碼定義： 對(duì)于n位小數(shù)，其補(bǔ)碼定義為 X 1X=0 X補(bǔ)= (mod 2) 2+X 0=X-1 對(duì)于n位整數(shù)，其補(bǔ)碼定義為 X 2nX=0 X補(bǔ)= (mod 2n+1) 2n+1+X 0=X-2n原碼與補(bǔ)碼之間的轉(zhuǎn)換方法 1、根據(jù)定義進(jìn)行計(jì)算原碼真值補(bǔ)碼 2、原碼直接求補(bǔ)碼規(guī)則對(duì)于正

18、數(shù)，原碼與補(bǔ)碼相等；對(duì)于負(fù)數(shù)，轉(zhuǎn)換規(guī)則為：符號(hào)位不變，數(shù)值部分求反加1(在最低位)。 補(bǔ)碼直接求原碼的規(guī)則同上。例 X原=0.1011，Y原=1.1101，求X補(bǔ)=？ Y補(bǔ)=？解：X補(bǔ)=0.1011， Y補(bǔ)=1.0010+0.0001=1.0011 由X補(bǔ)求機(jī)器負(fù)數(shù)-X補(bǔ)規(guī)則：連同符號(hào)位一起求反加1(在最低位）例 X補(bǔ)=0.1011，Y補(bǔ)=1.1101，求-X補(bǔ)=？ -Y補(bǔ)=？解：-X補(bǔ)=1.0101， -Y補(bǔ)=0.0010+0.0001=0.0011補(bǔ)碼加法運(yùn)算 可以證明，在無(wú)溢出的情況下， X補(bǔ)+Y補(bǔ)=X+Y補(bǔ)(mod 2) 稱-X補(bǔ)為X補(bǔ)的機(jī)器負(fù)數(shù)。 X-Y補(bǔ)=X+(-Y) 補(bǔ) =X補(bǔ)+

19、-Y補(bǔ) =X補(bǔ)-Y補(bǔ)(mod 2) 即將減法變成加法運(yùn)算。下面再討論一些性質(zhì) (1)0的補(bǔ)碼表示是唯一的 +0補(bǔ)=0.000 -0補(bǔ)=10.00+(-0)=0.000 (mod 2) (2)由性質(zhì)(1)知 X-X補(bǔ)=X補(bǔ)+-X補(bǔ)=0 所以 -X補(bǔ)= -X補(bǔ)即負(fù)號(hào)在括號(hào)內(nèi)外是一樣的。 X-Y補(bǔ)= =X補(bǔ)+-Y補(bǔ) (mod 2) (3)設(shè)X補(bǔ)=X0.X1X2Xn，求X。若 1X=0 則 1X補(bǔ)=X=0 , X0=0； 0=X=-1 則 2=X補(bǔ)=2+X=1 ,X0=1； 所以 0 1X=0 X補(bǔ)=2X0+X 其中 X0= 1 0=X-1X=XX=X補(bǔ)補(bǔ)-2X-2X0 0=X=X0 0.X.X1 1

20、X X2 2X Xn n-2X-2X0 0 =0.X =0.X1 1X X2 2X Xn n-X-X0 0補(bǔ)碼的算術(shù)移位操作 十進(jìn)制的算術(shù)移位設(shè) X=00.X1X2Xn，對(duì) X 執(zhí)行乘以10的運(yùn)算 10*X=0X1.X2Xn0 相當(dāng)于左移1位對(duì) X 執(zhí)行除以10的運(yùn)算 X/10=00.0X1X2Xn 相當(dāng)于右移1位 二進(jìn)制真值的算術(shù)移位設(shè) X=00.X1X2Xn，對(duì) X 執(zhí)行乘以2的運(yùn)算 2*X=0X1.X2Xn0 相當(dāng)于左移1位對(duì) X 執(zhí)行除以2的運(yùn)算 X/2=00.0X1X2Xn 相當(dāng)于右移1位 (4)由X補(bǔ)，求X/2補(bǔ)(即算術(shù)右移,要保持真值不變) 由性質(zhì)(3)知 X=0.X1X2Xn-

21、X0 所以 X/2=0.X1X2Xn/2-X0/2 =0.0X1X2Xn+X0/2-X0 =0.X0X1X2Xn-X0 比較性質(zhì)3中的X和性質(zhì)4中的X/2可得 X/2補(bǔ)=X0.X0X1X2Xn 由X補(bǔ)求X/2補(bǔ)的規(guī)則： 符號(hào)位不變，連同符號(hào)位一起右移一位。 算術(shù)左移1位的操作規(guī)則 符號(hào)位參與向左移位 左移時(shí)最高位丟失，最低位補(bǔ)0 左移時(shí)可能發(fā)生“溢出”現(xiàn)象，判斷“溢出”的規(guī)則與補(bǔ)碼加減法判斷“溢出”相同補(bǔ)碼的演變 模2補(bǔ)碼的修改 對(duì)于上述補(bǔ)碼，其真值范圍為 1X-1，實(shí)際上可擴(kuò)充到 X=-1(為什么?) 因 -1補(bǔ)=2+(-1)=1.000 這樣補(bǔ)碼定義可修改為： X 1X0 X補(bǔ)= (mod

22、 2) 2+X 0X-1 模4補(bǔ)碼變形補(bǔ)碼 由于參與運(yùn)算的數(shù)X滿足 1X-1，所以兩數(shù)相加減時(shí)其結(jié)果有可能超出模2補(bǔ)碼表示的真值范圍。因此提出了模4補(bǔ)碼，其定義如下： X 2X0 X補(bǔ)= (mod 4) 4+X 0X-2 可以證明:若X補(bǔ)=X00X01.X1X2Xn則 X00正好是表示其真值的符號(hào)，即X00=0，表示正數(shù)，X00=1，表示負(fù)數(shù)。 模2補(bǔ)碼的性質(zhì)及碼制之間轉(zhuǎn)換均可用于模4補(bǔ)碼。 模4補(bǔ)碼的真值范圍是模2補(bǔ)碼的一倍。 假若仍表示1X-1的真值（下一個(gè)參加運(yùn)算的數(shù)要求），小數(shù)點(diǎn)左邊就一定相同，所以說(shuō)模4補(bǔ)碼是有兩個(gè)符號(hào)位的補(bǔ)碼稱為變形補(bǔ)碼。 注意：在計(jì)算機(jī)中存儲(chǔ)和傳送數(shù)據(jù)時(shí)用一位符號(hào)

23、位，而在運(yùn)算時(shí)數(shù)據(jù)采用兩位符號(hào)位表示。 利用雙符號(hào)位判斷定點(diǎn)數(shù)溢出結(jié)果范圍雙符號(hào)是否溢出 2X101正溢出1X000無(wú)溢出0X-111無(wú)溢出-1X-210負(fù)溢出2.2.3 二進(jìn)制定點(diǎn)數(shù)的反碼表示 在補(bǔ)碼表示法中已經(jīng)提到補(bǔ)碼可以通過(guò)原碼除符號(hào)位外“求反加1”得到。如果只求反不加1，就得到了反碼表示法。 對(duì)于小數(shù)X，其反碼定義為 X 1X0 X反= (mod 2-2-n) 2-2-n+X 0X-1 其中 n代表小數(shù)的位數(shù)。 性質(zhì) 0的反碼表示 +0反=0.000 -0反=2-2-n+(-0)=1.111 即在反碼表示中，“0”的表示不唯一。 對(duì)于 n位整數(shù)X，其反碼定義為 X 2nX0 X反= (

24、mod 2n-1) 2n+1-1+X 0X-2n8位二進(jìn)制代碼與真值、原碼、補(bǔ)碼、反碼的對(duì)應(yīng)關(guān)系二進(jìn)制代碼無(wú)符號(hào)數(shù)對(duì)應(yīng)的真值原碼對(duì)應(yīng)的真值補(bǔ)碼對(duì)應(yīng)的真值反碼對(duì)應(yīng)的真值0000000000000000000111110111111127-127-127-127-11000000027-0-27-(27-1)1000000127+1-1-(27-1)-(27-2)1111111028-2-(27-2)-2-11111111128-1-(27-1)-1-0真值、原碼、補(bǔ)碼、反碼的對(duì)應(yīng)關(guān)系二進(jìn)制代碼(真值)原碼補(bǔ)碼反碼+0000000000000000000000000000000+000000100

25、0000010000000100000001+1111111011111110111111101111111-0000000100000000000000011111111-0000001100000011111111111111110-11111101111111010000010100000001-11111111111111110000001100000000-10000000Not10000000Not真值、原碼、補(bǔ)碼、反碼關(guān)系 1、三種機(jī)器數(shù)的最高位為符號(hào)位，符號(hào)位和數(shù)值部分之間約定用“.”或“，”分隔。 2、原碼補(bǔ)碼、反碼轉(zhuǎn)換規(guī)則對(duì)于正數(shù)，原碼、補(bǔ)碼、反碼相等；對(duì)于負(fù)數(shù)，轉(zhuǎn)換規(guī)則為

26、：符號(hào)位不變，數(shù)值部分求反，補(bǔ)碼在最低位還加1。 3、補(bǔ)碼、反碼的符號(hào)位參與運(yùn)算。 4、原碼和反碼對(duì)0的表示不唯一。 5、對(duì)于一個(gè)整數(shù)的表示，用多少位二進(jìn)制與所用的模數(shù)有關(guān)。 25都可以證明。定點(diǎn)數(shù)(整數(shù)與小數(shù))表示 按小數(shù)點(diǎn)的位置分： 定點(diǎn)小數(shù) 定點(diǎn)整數(shù) 按數(shù)有無(wú)符號(hào)分： 帶符號(hào)的 不帶符號(hào)的數(shù) 定點(diǎn)小數(shù)： 無(wú)符號(hào)小數(shù): 有符號(hào)小數(shù):dn-1.d2d1d0最高有效位小數(shù)點(diǎn)dn-1.d2d1d0最高有效位小數(shù)點(diǎn) 定點(diǎn)整數(shù)：dN-1.d2d1d0最高有效位小數(shù)點(diǎn) 進(jìn)行算術(shù)操作時(shí)，應(yīng)使用帶符號(hào)的數(shù)；數(shù)據(jù)可用原碼、補(bǔ)碼或反碼表示。 表示邏輯量或某些特征值時(shí)，應(yīng)用不帶符號(hào)的數(shù)。dN-1.d2d1d0最

27、高有效位小數(shù)點(diǎn) 注意：1、小數(shù)點(diǎn)在機(jī)器中是無(wú)法表示的，是人們?cè)诰幊虝r(shí)的一種約定。2、對(duì)于計(jì)算機(jī)來(lái)說(shuō)，符號(hào)位與其它位沒(méi)有什么區(qū)別，這也只是人們的一種約定。 定點(diǎn)數(shù)的長(zhǎng)度(位數(shù))分為固定長(zhǎng)數(shù)據(jù)表示。一般取機(jī)器字長(zhǎng)，參與運(yùn)算的操作數(shù)長(zhǎng)度也是固定的，一般稱作定長(zhǎng)運(yùn)算或定長(zhǎng)操作。多種定長(zhǎng)數(shù)據(jù)表示。對(duì)每種字長(zhǎng)的存儲(chǔ)和單獨(dú)運(yùn)算仍然是定長(zhǎng)的。如X86系列機(jī)，定長(zhǎng)數(shù)據(jù)有：8位，16位，32位，64位。下面再講述幾個(gè)問(wèn)題 1、數(shù)據(jù)表示的范圍-以8位為例十進(jìn)制數(shù)范圍二進(jìn)制形式maxminmaxmin無(wú)符號(hào)整數(shù)28-101111111100000000有符號(hào)整數(shù)原碼27-1-(27-1)011111111111111

28、1有符號(hào)整數(shù)補(bǔ)碼27-1-270111111110000000無(wú)符號(hào)小數(shù)1-2-801111111100000000有符號(hào)小數(shù)原碼1-2-7-(1-2-7)0111111111111111有符號(hào)小數(shù)補(bǔ)碼1-2-7-10111111110000000 2、在按字節(jié)編址的機(jī)器中，16位、32位、64位字長(zhǎng)的地址如何確定。 以16位字長(zhǎng)為例高字節(jié)低字節(jié)字節(jié)地址a地址a+1偶數(shù)(硬件規(guī)定)2.2.4 2.2.4 十進(jìn)制數(shù)的編碼十進(jìn)制數(shù)的編碼 原因商業(yè)統(tǒng)計(jì)等領(lǐng)域，運(yùn)算簡(jiǎn)單，數(shù)據(jù)量大。在輸入/輸出中十進(jìn)制數(shù)二進(jìn)制數(shù)轉(zhuǎn)換所占的時(shí)間比例很大。為提高機(jī)器的效率，最好能直接對(duì)十進(jìn)制數(shù)進(jìn)行運(yùn)算和處理。擴(kuò)大數(shù)據(jù)的表示

29、范圍和提高運(yùn)算精度。 十進(jìn)制數(shù)串有兩種表示形式。 一、字符串形式 指一個(gè)字節(jié)存放一個(gè)十進(jìn)制的數(shù)位或符號(hào)位的ASCII碼。 在主存中，一個(gè)十進(jìn)制數(shù)串占用連續(xù)多個(gè)字節(jié)，故需要給出該數(shù)串在主存中的起始位置和位數(shù)(串的長(zhǎng)度)。 一個(gè)十進(jìn)制數(shù)可表示為： 無(wú)符號(hào)十進(jìn)制數(shù)、有符號(hào)十進(jìn)制數(shù) 有符號(hào)十進(jìn)制數(shù)是讓符號(hào)位占用單獨(dú)一個(gè)字節(jié)，并把符號(hào)位放在數(shù)字位之前。 缺點(diǎn)：高四位的值在進(jìn)行算術(shù)運(yùn)算時(shí)不具有數(shù)值意義。 主要用在非數(shù)值計(jì)算的應(yīng)用領(lǐng)域中。 例如 +543表示如下左圖。 例如 -96865可表示 (4個(gè)字節(jié)/主存單元)如上右圖。33H34H35H2BH圖35H36H38H36H39H30H30H2DH圖符號(hào)

30、ACSII碼+ +2BH- -2DH 二、壓縮十進(jìn)制數(shù)據(jù)串形式一個(gè)字節(jié)存放兩個(gè)十進(jìn)制數(shù)位每位值可用二十編碼(BCD碼)表示符號(hào)位占用半個(gè)字節(jié) 如8421碼，用12(CH)表示正號(hào)，用13(DH)表示負(fù)號(hào)。 優(yōu)點(diǎn)：節(jié)省存儲(chǔ)空間，可直接完成十進(jìn)制數(shù)的算術(shù)運(yùn)算。 例如-78表示如下圖。 問(wèn)題：1、十進(jìn)制數(shù)串如何變成BCD碼?2、BCD碼如何變成二進(jìn)制數(shù)據(jù)?7 8D 0圖字節(jié)字節(jié) 在這種表示中，規(guī)定數(shù)據(jù)位數(shù)加符號(hào)位數(shù)必須為偶數(shù)，當(dāng)不為偶數(shù)時(shí)，應(yīng)補(bǔ)一個(gè)0。7 80 D圖字節(jié)字節(jié)2.3 檢錯(cuò)/糾錯(cuò)碼 提高計(jì)算機(jī)的可靠性辦法：采取選用更高可靠性的器件更好的生產(chǎn)工藝等措施采用檢錯(cuò)糾錯(cuò)編碼技術(shù) 采用一點(diǎn)冗余的線

31、路，在原有數(shù)據(jù)位之外再增加一到幾位校驗(yàn)位，使新得到的碼字帶上某種特性，之后則通過(guò)檢查該碼字是否仍保持有這一特性，來(lái)發(fā)現(xiàn)是否出現(xiàn)了錯(cuò)誤(檢錯(cuò)碼)，甚至于定位錯(cuò)誤后，自動(dòng)改正這一錯(cuò)誤(糾錯(cuò)碼)。非線性碼線性碼卷積碼分組碼非循環(huán)碼循環(huán)碼循環(huán)碼 隨機(jī) 錯(cuò)誤 突發(fā) 錯(cuò)誤糾錯(cuò)碼校驗(yàn)位與信息位 的形成關(guān)系信息位與校驗(yàn)位的約束條件碼字本身的 結(jié)構(gòu)特點(diǎn)信息位與校驗(yàn)位排列位置關(guān)系系統(tǒng)碼非系統(tǒng)碼糾錯(cuò)碼分類幾種常用的檢錯(cuò)糾錯(cuò)碼三種常用的檢錯(cuò)糾錯(cuò)碼：奇偶檢錯(cuò)碼， 用于并行數(shù)據(jù)傳送中海明檢錯(cuò)與糾錯(cuò)碼， 用于并行數(shù)據(jù)傳送中循環(huán)冗余碼， 用于串行數(shù)據(jù)傳送中編碼過(guò)程譯碼過(guò)程傳送原始數(shù)據(jù)碼 字結(jié)果數(shù)據(jù)形成校驗(yàn)位的值，加進(jìn)特征檢查

32、接送的碼字，發(fā)現(xiàn) / 改正錯(cuò)誤2.3.1 奇偶校驗(yàn)碼用于并行碼檢錯(cuò)原理：在 k 位數(shù)據(jù)碼之外增加 1 位校驗(yàn)位，使 K+1 位碼字中取值為 1 的位數(shù)總保持為 偶數(shù)（偶校驗(yàn)）或 奇數(shù)（奇校驗(yàn)）。例如：0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 原有數(shù)字位 兩個(gè)新的碼字 偶校驗(yàn)偶校驗(yàn)奇校驗(yàn)奇校驗(yàn)校驗(yàn)位數(shù)據(jù)編碼、傳送及檢錯(cuò)過(guò)程數(shù)據(jù)編碼、傳送及檢錯(cuò)過(guò)程： 設(shè)原始數(shù)據(jù)為d6 d5 d4 d3 d2 d1 d0 ，增加1個(gè)偶校驗(yàn)位d7，構(gòu)成8位偶校驗(yàn)編碼。d7 = d6 d5 d4 d3 d2 d1 d0 式中 為異或運(yùn)算。 發(fā)送方把8

33、位的偶校驗(yàn)碼d7d6 d5 d4 d3 d2 d1 d0 發(fā)送出去。 接收方收到8位偶校驗(yàn)碼d7d6 d5 d4 d3 d2 d1 d0 。 校驗(yàn)電路用來(lái)檢查8位數(shù)據(jù)中取值1的個(gè)數(shù)是否為偶數(shù)。若是，則沒(méi)有出錯(cuò)，否則，出現(xiàn)了錯(cuò)誤。 check= d7 d6 d5 d4 d3 d2 d1 d0奇偶校驗(yàn)碼的實(shí)現(xiàn)電路+ 奇校驗(yàn) 偶校驗(yàn) 出錯(cuò)指示(check)+同左側(cè)電路編碼電路譯碼電路D7 (校驗(yàn)位)八位數(shù)據(jù)位0 D6 D5 D4 D3 D2 D1 D0p 奇偶校驗(yàn)又分為 垂直校驗(yàn) 水平校驗(yàn) 水平垂直校驗(yàn)1、垂直(縱向)奇偶校驗(yàn) 以七單位碼數(shù)字0-9為例說(shuō)明垂直奇偶校驗(yàn)碼(表2-1)表2-1七單位數(shù)字

34、的垂直奇偶校驗(yàn)碼(偶校驗(yàn)）0123456789B70000000000B61111111111B51111111111B40000000011B30000111100B20011001100B10101010101校驗(yàn)0110100110 2、水平(橫向)奇偶校驗(yàn) 對(duì)一組信息內(nèi)各字符的同一位進(jìn)行奇偶校驗(yàn)時(shí)，稱為水平奇偶校驗(yàn)。 仍以七單位碼為例并用表2-2來(lái)說(shuō)明。 傳送時(shí)是按列傳送字符。表2-2水平奇偶校驗(yàn)（偶校驗(yàn)）0123456789校驗(yàn)B700000000000B611111111110B511111111110B400000000110B300001111000B200110011000B

35、1010101010113、水平垂直奇偶校驗(yàn) 同時(shí)進(jìn)行水平和垂直奇偶校驗(yàn)的方式稱為水平垂直奇偶校驗(yàn)。 仍以七單位碼為例來(lái)說(shuō)明，如表2-3。0123456789校驗(yàn)B700000000000B611111111110B511111111110B400000000110B300001111000B200110011000B101010101011校驗(yàn)01101001101表2-3水平垂直奇偶校驗(yàn) 水平校驗(yàn)碼和垂直校驗(yàn)碼只能發(fā)現(xiàn)奇數(shù)個(gè)錯(cuò)，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)。 水平垂直校驗(yàn)碼具有較強(qiáng)的檢錯(cuò)能力，它不但能發(fā)現(xiàn)所有一位、二位和三位錯(cuò)誤，而且能改正一位錯(cuò)誤。2.4.2 海明校驗(yàn)碼海明校驗(yàn)碼 定義1 對(duì)2個(gè)二進(jìn)

36、制代碼中的每一位進(jìn)行比較，取值不同的位數(shù)稱為這2個(gè)二進(jìn)制代碼的海明距離。 定義2 最小碼距=Min(Xi和Yi之間的海明距離)，其中Xi和Yi( i != j)是某編碼系統(tǒng)中任意2個(gè)合法代碼。 例1 用4位二進(jìn)制代碼表示一個(gè)十六進(jìn)制，由于沒(méi)有任何剩余狀態(tài)未被使用，因而最小 碼距為1。 例2 給例1的編碼增加1個(gè)奇校驗(yàn)位，變成5位二進(jìn)制代碼表示一個(gè)十六進(jìn)制數(shù)，此時(shí)，任何一個(gè)合法碼在某一位上取值的變化，都會(huì)變成非法代碼。于是碼距=2。 海明校驗(yàn)碼的原理 在數(shù)據(jù)中加入幾個(gè)校驗(yàn)位，將數(shù)據(jù)代碼的碼距較均勻地拉大; 把數(shù)據(jù)的每一個(gè)二進(jìn)制位分配在幾個(gè)奇偶校驗(yàn)組中。 當(dāng)某一位出錯(cuò)后，就會(huì)引起有關(guān)幾個(gè)校驗(yàn)位的值

37、發(fā)生變化，這不但可以發(fā)現(xiàn)錯(cuò)誤，還能指出是哪一位出錯(cuò)。 在此介紹糾正一位錯(cuò)誤的編碼。 r=? 校驗(yàn)位的狀態(tài)應(yīng)當(dāng)有m+1種(含無(wú)錯(cuò))，以便能指出m位中的任何一位有錯(cuò)或無(wú)錯(cuò)。所以增添的奇偶校驗(yàn)位數(shù)r應(yīng)滿足： 2rm+1=k+r+1 海明校驗(yàn)碼構(gòu)成K位信息r位校驗(yàn)碼m位 不同位數(shù)的數(shù)據(jù)編成海明碼所需的最小校驗(yàn)位數(shù)，如表2-4。表2-4 不同位數(shù)的數(shù)據(jù)所需海明碼的最小校驗(yàn)位數(shù)kr 133410411255265665119 7 注：書上P430頁(yè)表為再加上一位校驗(yàn)位，對(duì)整個(gè)海明碼進(jìn)行校驗(yàn)。 若海明碼的最高位號(hào)為m，最低位號(hào)為1。 海明碼的編碼規(guī)則： (1)、校驗(yàn)位位數(shù)與數(shù)據(jù)位位數(shù)之和為m，每個(gè)校驗(yàn)位i在

38、海明碼中被分在位號(hào)2i-1的位置，其余各位為數(shù)據(jù)位，從低位向高位依次排列。HmHm-1H2H1位號(hào) (2)、海明碼的每一位Hi(包括數(shù)據(jù)位和校驗(yàn)位本身)由多個(gè)校驗(yàn)位校驗(yàn)，其關(guān)系: 被校驗(yàn)的每一位位號(hào)2i-1 (i=1) (3)、在增大合法碼的碼距時(shí)，使所有碼的碼距盡量均勻地增大，以保證對(duì)所有碼的檢錯(cuò)能力平衡提高。 由編碼規(guī)則(2)，得出如表2-5。 也可以下面公式獲得 Pi= Hi|j&i=iH13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P1 例如對(duì)一個(gè)字節(jié)進(jìn)行海明編碼。 每個(gè)字節(jié)由8個(gè)二進(jìn)制位組成(k=8)，根據(jù)表2-4可

39、知 r=4，再加上一位對(duì)整個(gè)信息的校驗(yàn)位，故海明碼的位數(shù)為13，表示： 表2-5海明碼位號(hào)與校驗(yàn)位的位號(hào)關(guān)系海明碼位號(hào)數(shù)據(jù)位/校驗(yàn)位參與校驗(yàn)的校驗(yàn)位位號(hào)海明碼位號(hào)=位號(hào)之和H1P111=1H2P222=2H3D11,23=1+2H4P344=4H5D21,45=1+4H6D32,46=2+4HD41,2,47=1+2+4H8P488=8H9D51,89=1+8H10D62,810=2+8H11D71,2,811=1+2+8H12D84,812=4+8H13 P51313=13 從表2-5求出Pi值的偶校驗(yàn)的結(jié)果： P1=D1 D2 D4 D5 D7 P2 =D1 D3 D4 D6 D7 P3

40、=D2 D3 D4 D8 P4 =D5 D6 D7 D8 P5=D1 D2 D3 D4 D5 D6 D7 D8 P1 P2 P3 P4 例如對(duì)字符C(8位)進(jìn)行海明校驗(yàn)，其海明碼如下: 從上述公式可知 P1=1 1 0 0 1=1 P2 =1 0 0 0 1 =0 P3 =1 0 0 0 =1 P4 =0 0 1 0 =1 P5=0 海明碼為：0 0100 1 001 1 1 0 1H13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P1P50100P4001P31P2P1 設(shè)其中一位出錯(cuò)，如第八位接收到的編碼為： 校驗(yàn)結(jié)果： S1=P1

41、 D1 D2 D4 D5 D7=0 S2 =P2 D1 D3 D4 D6 D7=0 S3 =P3 D2 D3 D4 D8=0 S4 =P4 D5 D6 D7 D8=1 S5=1H13H12H11H10H9H8H7H6H5H4H3H2H1P5D8D7D6D5P4D4D3D2P3D1P2P10010000011101由于S4-S1不為00000，所以有錯(cuò)，錯(cuò)誤位在S4-S1=01000處。2.3.3 循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼(CRC碼碼) 循環(huán)冗余校驗(yàn)碼主要用于傳輸純二進(jìn)制比特流信息的情況。 循環(huán)冗余校驗(yàn)碼(n位)由信息位(k位)加上校驗(yàn)位(r位)構(gòu)成。即k位信息位r位校驗(yàn)位 應(yīng)用CRC碼的關(guān)

42、鍵是如何從k位信息得到r位校驗(yàn)位，以及如何從k+r位信息碼判斷是否出錯(cuò)。k+r位1、模2四則運(yùn)算 模2運(yùn)算是指按位模2相加為基礎(chǔ)的四則運(yùn)算，運(yùn)算時(shí)不考慮進(jìn)位和借位。 (1) 模2加減法0+0=00+1=11+0=11+1=00-0=0 0-1=1 1-0=1 1-1=0 結(jié)論：減去一個(gè)數(shù)等于加上該數(shù)。 (2) 模2乘法按模2加求部分積。例1011 110 0000 1011 1011 111010 (3) 模2除法按模2減求余數(shù)。例 101 | 10110000 101 010 000 100 101 01余數(shù)2、CRC碼編碼方法 設(shè)待編碼的信息為Ck-1Ck-2C1C0。 將待編碼的k位有效信息位組表示為多項(xiàng)式m(x)； M(x)=Ck-1xk-1+Ck-2xk-2+C1x+C0 由于CRC碼是由信息位(k位)加上校驗(yàn)位(r位)構(gòu)成，故相當(dāng)于將M