4 第三章信息編碼與數(shù)據(jù)表示wxr.ppt

1、2,第三章 信息編碼與數(shù)據(jù)表示,數(shù)值數(shù)據(jù)的表示,3.1,浮點機(jī)器數(shù)的表示方法,數(shù)據(jù)格式,3.2,定點機(jī)器數(shù)的表示方法,3.3,3.4,非數(shù)值數(shù)據(jù)的表示,3.5,校驗碼,3.6,現(xiàn)代計算機(jī)系統(tǒng)的數(shù)據(jù)表示,3.7,本章小結(jié),3,3.1 數(shù)值數(shù)據(jù)的表示,進(jìn)位計數(shù)制,一,不同數(shù)制之間的相互轉(zhuǎn)換,二,十進(jìn)制數(shù)的編碼,三,4,一、進(jìn)位計數(shù)制,數(shù)制的兩大要素： 基數(shù)R：指在這種進(jìn)位制中允許使用的基本數(shù)碼個數(shù)?；鶖?shù)為R的數(shù)制稱為R進(jìn)制數(shù)。 R進(jìn)制數(shù)的主要特點就是逢R進(jìn)1 。 權(quán)Wi：權(quán)也稱位權(quán)，指某一位i上的數(shù)碼的權(quán)重值，即權(quán)與數(shù)碼所處的位置i有關(guān)。 Wi Ri。 假設(shè)任意數(shù)值N用R進(jìn)制數(shù)來表示，形式為： N

2、=（Dm1Dm-2D0 D-1D-2 D-k ）R 其中，Di為該進(jìn)制的基本符號，Di0，R-1，i = -k， -k+1， ，m-1，m；小數(shù)點在D0和D-1之間。,5,一、進(jìn)位計數(shù)制,則數(shù)值N的實際值為：,例如：R10，即十進(jìn)制數(shù)。它的每一位上的數(shù)碼Di只能取0，1，2，9；各個數(shù)碼的權(quán)為10i，i指示數(shù)碼所處的位置，個位i0，十位i1，百位i2，依此類推。 思考：二進(jìn)制、八進(jìn)制、十六進(jìn)制？,6,一、進(jìn)位計數(shù)制,例1：（2345.459）102103 3102 41015100 410-1 510-2 910-3 例2：（11011.011）2124 123 022121 12-0 02-

3、1 12-2 12-3=（27.375）10 例3：（123.67）8182 281 38068-1 78-2=（83.859375）10,7,二、不同數(shù)制之間的相互轉(zhuǎn)換,常用的幾種數(shù)制的對應(yīng)關(guān)系,1,二、八、十六進(jìn)制轉(zhuǎn)換為十進(jìn)制,2,十進(jìn)制轉(zhuǎn)換為二、八、十六進(jìn)制,3,8,（1）常用的幾種數(shù)制的對應(yīng)關(guān)系,9,（2）二、八、十六進(jìn)制轉(zhuǎn)換為十進(jìn)制,轉(zhuǎn)換方法：加權(quán)求和。(按式41) 例：（5AC.E6）16= 5162 10161 12160 14161 6162 （1452.8984375）10 十進(jìn)制（Decimal）、二進(jìn)制（Binary）、八進(jìn)制（Octal）、十六進(jìn)制（Hexdecimal

4、）數(shù)分別用D、B、Q、H來標(biāo)志。 例如：（1011）2（1011）B1011B1011b （123.45）2（ 123.45 ）D 123.45D 123.45 （2B.D）16=（2B.D）H=（43.8125）10=(53.64)Q,10,（3）十進(jìn)制轉(zhuǎn)換為二、八、十六進(jìn)制,轉(zhuǎn)換方法：可以分為以下兩種方法 直接轉(zhuǎn)換：十進(jìn)制二、八、十六進(jìn)制 間接轉(zhuǎn)換：十進(jìn)制二進(jìn)制 八、十六進(jìn)制 （a）十進(jìn)制轉(zhuǎn)化為R進(jìn)制 （b）二進(jìn)制轉(zhuǎn)化為八、十六進(jìn)制,11,（a）十進(jìn)制轉(zhuǎn)化為R進(jìn)制,轉(zhuǎn)換方法 整數(shù)部分：除以R取余，先得低位，直到商為0。 小數(shù)部分：乘R取整，先得高位，直到積為0或者達(dá)到精度要求為止。 例：（

5、123.75）10=（ ？ ）2 （123.75）10=（ ？ ）8,1111011.11,173.6,12,小數(shù)部分的精度要求,當(dāng)小數(shù)部分不能整除為二進(jìn)制時，則乘以2取整的過程中，積不會為0；或者當(dāng)小數(shù)部分轉(zhuǎn)化為二進(jìn)制位數(shù)很長，這時由精度來決定二進(jìn)制位數(shù)。 例如：（0.35）10（ ？ ）2無法整除 （0.6875）10（ ？ ）2位數(shù)太長 若要求精度大于10，則表示“”左右兩邊的十進(jìn)制值的差的絕對值10。 則我們只需取4位二進(jìn)制小數(shù)即可滿足要求，因為1024。,13,（b）二進(jìn)制轉(zhuǎn)化為八、十六進(jìn)制,二進(jìn)制八進(jìn)制 以小數(shù)點為中心分別向兩邊分組，每三位一組，寫出對應(yīng)的八進(jìn)制數(shù)字。（不夠位數(shù)則在

6、兩邊加0補(bǔ)足3位 ） 二進(jìn)制十六進(jìn)制 以小數(shù)點為中心分別向兩邊分組，每四位一組，寫出對應(yīng)的十六進(jìn)制符號。（不夠位數(shù)則在兩邊加0補(bǔ)足4位 ） 例：（1011111.11）2 =( ? )8=( ? )16,137.6,5F.C,14,思考1：八、十六進(jìn)制如何轉(zhuǎn)化為二進(jìn)制？,八進(jìn)制二進(jìn)制：將每位八進(jìn)制數(shù)展開為3位二進(jìn)制數(shù)，最高位和最低位的0可以略去。 十六進(jìn)制二進(jìn)制：將每位十六進(jìn)制數(shù)展開為4位二進(jìn)制數(shù)，最高位和最低位的0可以略去。 例：（765.23）8= （ ? ）2 例：（765.23）16= （ ? ）2,111 110 101.010 011,111 0110 0101.0010 0011

7、,15,思考2：計算機(jī)中為什么采用二進(jìn)制表示數(shù)據(jù)？,1、具有二值狀態(tài)的物理器件容易實現(xiàn)。 2、二進(jìn)制的運算規(guī)則簡單，硬件實現(xiàn)容易。 3、具有邏輯特性，可代表“真假”、“是非”。,16,三、十進(jìn)制數(shù)的編碼,提出的問題：如何在計算機(jī)內(nèi)使用二進(jìn)制來表示十進(jìn)制數(shù)據(jù)？ （1）二十進(jìn)制碼（BCD碼） （2）十進(jìn)制數(shù)串的表示方法,17,（1）二十進(jìn)制碼（BCD碼）,BCD（Binary Coded Decimal）碼：使用二進(jìn)制來編碼十進(jìn)制數(shù)字09。 編碼方法：一般使用4位二進(jìn)制編碼來表示1位十進(jìn)制數(shù)字，在16個編碼中選用10個來表示數(shù)字09。不同的選擇構(gòu)成不同的BCD碼 。 分類： 有權(quán)碼：編碼的每一位都

8、有固定的權(quán)值，加權(quán)求和的值即是表示的十進(jìn)制數(shù)字。如8421碼、2421碼、5211碼、4311碼、84 -2-1碼等。 無權(quán)碼：編碼的每一位并沒有固定的權(quán)，主要包括格雷碼、余3碼等。,18,（1）二十進(jìn)制碼（BCD碼）,19,幾種常見的BCD碼,8421碼： 特點：4位二進(jìn)制數(shù)位的權(quán)從高到低依次是8、4、2、1；8421碼實際上就是十進(jìn)制數(shù)字09的二進(jìn)制編碼本身。 是最常用的一種BCD碼，在沒有特別指出的一般情況下，所提到的BCD碼通常就是指8421碼。 格雷碼： 特點：又叫循環(huán)碼，它的任何相鄰的兩個編碼（例如2和3、7和8、9和0等）之間只有一位二進(jìn)制位不同。 優(yōu)點：是用它構(gòu)成計數(shù)器時，在從

9、一個編碼變到下一個編碼時，只有一個觸發(fā)器翻轉(zhuǎn)即可，波形更完美、可靠。 格雷碼的編碼方案有許多種。 余3碼：對應(yīng)的8421碼加上0011構(gòu)成的。,20,（2）十進(jìn)制數(shù)串的表示方法,字符串形式：用ASCII碼來表示十進(jìn)制數(shù)字或符號位，即1個字節(jié)存放1位十進(jìn)制數(shù)字或符號位。 壓縮的十進(jìn)制數(shù)串形式：用BCD碼來表示十進(jìn)制數(shù)字，即1個字節(jié)存放2個十進(jìn)制的數(shù)字；符號位放在最低位數(shù)字位之后，一般用C（12）表示正號，用D（13）表示負(fù)號。 例如 258被表示成258CH，占用兩個字節(jié)，-34被表示為034DH，也占用兩個字節(jié)。 共同點：必須給出它在主存中的首地址和位長。,21,（2）十進(jìn)制數(shù)串的表示方法,采

10、用十進(jìn)制表示數(shù)據(jù)的優(yōu)點是： 對于需要大量地進(jìn)行輸入輸出數(shù)據(jù)而運算簡單的場合，大大減少了十二和二十轉(zhuǎn)換，提高了機(jī)器的運行效率； 十進(jìn)制數(shù)串的位長可變，許多機(jī)器中規(guī)定該長度從0到31，有的甚至更長。不受定點數(shù)和浮點數(shù)統(tǒng)一格式的約束，從而提高了數(shù)據(jù)的表示范圍和運算精度。,22,3.2 數(shù)據(jù)格式,計算機(jī)中參與運算的數(shù)據(jù)有兩種： 無符號數(shù)據(jù)（ Unsigned ）：所有的二進(jìn)制數(shù)據(jù)位數(shù)均用來表示數(shù)值本身，沒有正負(fù)之分。 帶符號數(shù)據(jù)（ Signed）：則其二進(jìn)制數(shù)據(jù)位，包括符號位和數(shù)值位。計算機(jī)中的帶符號數(shù)據(jù)又稱為機(jī)器數(shù)。 1、機(jī)器數(shù)與真值 機(jī)器數(shù)：把“+”、“-”符號代碼化，并保存在計算機(jī)中的數(shù)據(jù)。 真

11、值：是指機(jī)器數(shù)所真正表示的數(shù)值，用數(shù)值并冠以“+”、“-”符號的方法來表示。 機(jī)器數(shù)的編碼方法：原碼、反碼、補(bǔ)碼、移碼。,23,3.2 數(shù)據(jù)格式,計算機(jī)硬件如何區(qū)分它們是無符號數(shù)據(jù)還是帶符號數(shù)據(jù)的呢？ 例： （Intel X86系列CPU） 假設(shè)AX（1111111111111111）2，BX（0000000000000001）2，那么執(zhí)行下面兩段程序時，計算機(jī)硬件將把AX和BX中的數(shù)據(jù)看成是不同的數(shù)據(jù)。 程序A CMPAX,BX; 結(jié)果影響標(biāo)志位 JLL1;有符號數(shù)小于轉(zhuǎn)移 執(zhí)行JL指令時，操作數(shù)AX和BX被當(dāng)作有符號數(shù)據(jù)，AX（1）10，BX（1）10，所以執(zhí)行結(jié)果是轉(zhuǎn)移到L1標(biāo)號處執(zhí)行。

12、 程序B CMPAX,BX JBL1;無符號數(shù)小于轉(zhuǎn)移 執(zhí)行JB指令時，操作數(shù)AX和BX被當(dāng)作無符號數(shù)據(jù)，AX（65535）10，BX（1）10，所以執(zhí)行結(jié)果是不轉(zhuǎn)移，順序執(zhí)行。,24,3.2 數(shù)據(jù)格式,2、小數(shù)點的表示方法 在機(jī)器數(shù)中，小數(shù)點及其位置是隱含規(guī)定的；有兩種隱含方式： 定點數(shù)：小數(shù)點的位置是固定不變的 浮點數(shù)：小數(shù)點的位置是浮動的 定點機(jī)器數(shù)分為定點小數(shù)、定點整數(shù)兩種。 浮點機(jī)器數(shù)中小數(shù)點的位置由階碼規(guī)定，因此是浮動的。,25,3.2 數(shù)據(jù)格式,（a） 定點整數(shù)格式,（c）浮點數(shù)格式,（b）定點小數(shù)格式,26,3.3 定點機(jī)器數(shù)的表示方法,定點機(jī)器數(shù)的小數(shù)點的位置是固定不變的，可

13、以分為兩種： 定點小數(shù)：用于表示純小數(shù)，小數(shù)點隱含固定在最高數(shù)據(jù)位的左邊，整數(shù)位則用于表示符號位。 定點整數(shù)：用于表示純整數(shù)，小數(shù)點位置隱含固定在最低位之后，最高位為符號位。 1、原碼表示法3、反碼表示法 2、補(bǔ)碼表示法4、移碼表示法 5、定點機(jī)器數(shù)轉(zhuǎn)換,27,1、原碼表示法,（1）表示方法：最高位表示數(shù)的符號，其他位表示數(shù)值位。 符號位：0正數(shù)，1負(fù)數(shù)。 數(shù)值位：與絕對值相同。 對于定點整數(shù)： 若X=+X1X2Xn，則X原= 0,X1X2Xn ； 若X=- X1X2Xn ，則X原= 1,X1X2Xn 。 對于定點小數(shù)： 若X=+0. X1X2Xn ，則X原= 0.X1X2Xn ； 若X=-

14、0.X1X2Xn ，則X原= 1.X1X2Xn 。,“,”和“.”只用于助記，在計算機(jī)中并無專用部件來表示,28,1、原碼表示法,例1：X=1011，Y1011，則： X原 ；Y原 ； 例2：X=0.1101，Y- 0.1101，則： X原 ；Y原 ； 例3： X=1011， Y- 0.1101，求X和Y的8位原碼機(jī)器數(shù)。 X原 ；Y原 ； 例4：0原？,0,1011,1,1011,0.1101,1.1101,0,0001011,1. 1101000,29,1、原碼表示法,（2）0 的表示：0 的原碼表示有兩種形式，即分別按照正數(shù)和負(fù)數(shù)表示。 +0原 000 -0原 100 （3）表示范圍：對

15、于n1位原碼機(jī)器數(shù)X，它所能表示的數(shù)據(jù)范圍為： 定點整數(shù)：（2n1）X 2n1 定點小數(shù)：（12n）X 12n,包括1位符號位，n位數(shù)值位,30,2、補(bǔ)碼表示法,（1）表示方法：最高位為符號位，其他位為數(shù)值位。 符號位：0正數(shù)，1負(fù)數(shù)。 數(shù)值位：正數(shù)時，與絕對值相同；負(fù)數(shù)時，為絕對值取反后，末位加1。,31,2、補(bǔ)碼表示法,例1：X=1011，Y1011，則： X補(bǔ) ；Y補(bǔ) ； 例2：X=0.1101，Y- 0.1101，則： X補(bǔ) ；Y補(bǔ) ； 例3： X=1011， Y- 0.1101，求X和Y的8位補(bǔ)碼機(jī)器數(shù)。 X補(bǔ) ；Y補(bǔ) ； 例4：0補(bǔ)？,0,1011,1,0101,0.1101,1.

16、0011,0,0001011,1. 0011000,32,1.模和同余 模是指一個計量器的容量，可用M表示。例如：一個4位的二進(jìn)制計數(shù)器，當(dāng)計數(shù)器從0計到15之后，再加1，計數(shù)值又變?yōu)?。這個計數(shù)器的容量M=24=16，即模為16。由此可見，純小數(shù)的模為2，一個字長為n+1位的純整數(shù)的模為2n+1。 同余是指兩整數(shù)A、B除以同一正整數(shù)M，所得余數(shù)相同，則稱A、B對M同余，即A、B在以M為模時是相等的，可寫作 A=B (mod M),2、補(bǔ)碼表示法,33,時鐘正撥和倒撥,對鐘表而言，M=12。假設(shè)：時鐘停在8點，而現(xiàn)在正確的時間是6點，這時撥準(zhǔn)時鐘的方法有兩種：正撥和倒撥。 分針倒著旋轉(zhuǎn)2圈，等

17、于分針正著旋轉(zhuǎn)10圈。故有：-2=10 (mod 12) ，即 -2和10同余。 8-2=8+10 (mod 12),倒撥時鐘,正撥時鐘,點擊播放,34,補(bǔ)碼的符號位表示方法與原碼相同，其數(shù)值部分的表示與數(shù)的正負(fù)有關(guān)：對于正數(shù)，數(shù)值部分與真值形式相同；對于負(fù)數(shù)，將真值的數(shù)值部分按位取反，且在最低位上加1。 若真值為純小數(shù)，它的補(bǔ)碼形式為Xs.X1X2Xn，其中Xs表示符號位。 例5：X1=0.0110, X1補(bǔ)=0.0110 X2=-0.0110, X2補(bǔ)=1.1010,2.補(bǔ)碼表示,35,若真值為純整數(shù)，它的補(bǔ)碼形式為XsX1X2Xn，其中Xs表示符號位。 例6：X1=1101， X1補(bǔ)=0

18、1101 X2=-1101， X2補(bǔ)=10011 在補(bǔ)碼表示中，真值0的表示形式是唯一的： +0補(bǔ)=-0補(bǔ)=00000,2.補(bǔ)碼表示（續(xù)）,36,當(dāng)X為正數(shù)時，X補(bǔ)=X原=X 當(dāng)X為負(fù)數(shù)時，由X原轉(zhuǎn)換為X補(bǔ)的方法： X原除掉符號位外的各位取反加“1”。 自低位向高位，尾數(shù)的第一個“1”及其右部的“0”保持不變，左部的各位取反，符號位保持不變。 例7：X原 =1.1110011000 X補(bǔ) =1.0001101000,3.由真值、原碼轉(zhuǎn)換為補(bǔ)碼,37,2、補(bǔ)碼表示法,（2）0 的表示：0 的補(bǔ)碼表示形式是唯一的，即分別按照正數(shù)和負(fù)數(shù)表示均一致，為全零。 +0補(bǔ) 000 -0補(bǔ) 000 （3）表示

19、范圍：對于n1位補(bǔ)碼機(jī)器數(shù)X，它所能表示的數(shù)據(jù)范圍為： 定點整數(shù)：2nX 2n1 定點小數(shù)：1X 12n 計算機(jī)中的整型數(shù)據(jù)（int）均用補(bǔ)碼來表示。,包括1位符號位，n位數(shù)值位,38,3、反碼表示法,（1）表示方法：最高位表示數(shù)的符號，其他位表示數(shù)值位。 符號位：0正數(shù)，1負(fù)數(shù)。 數(shù)值位：正數(shù)時，與絕對值相同；負(fù)數(shù)時，為絕對值取反。,39,3、反碼表示法,例1：X=1011，Y1011，則： X反 ；Y反 ； 例2：X=0.1101，Y- 0.1101，則： X反 ；Y反 ； 例3： X=1011， Y- 0.1101，求X和Y的8位反碼機(jī)器數(shù)。 X反 ；Y反 ； 例4：0反？,0,1011

20、,1,0100,0.1101,1.0010,0,0001011,1. 0010111,40,（2）0 的表示：0 的反碼表示有兩種形式，即分別按照正數(shù)和負(fù)數(shù)表示。 +0反 000 -0反 111 （3）表示范圍：對于n1位反碼機(jī)器數(shù)X，它所能表示的數(shù)據(jù)范圍為： 定點整數(shù)：（2n1）X 2n1 定點小數(shù)：（12n）X 12n,包括1位符號位，n位數(shù)值位,3、反碼表示法,41,4、移碼表示法,（1）表示方法：最高位為符號位，其他位為數(shù)值位。 符號位：1正數(shù)，0負(fù)數(shù)。 數(shù)值位：正數(shù)時，與絕對值相同；負(fù)數(shù)時，為絕對值取反后，末位加1。,移碼表示：即為補(bǔ)碼的符號位取反,42,4、移碼表示法,例1：X=1

21、011，Y1011，則： X移 ；Y移 ； 例2：X=0.1101，Y- 0.1101，則： X移 ；Y移 ； 例3： X=1011， Y- 0.1101，求X和Y的8位移碼機(jī)器數(shù)。 X移 ；Y移 ； 例4：0移？,1,1011,0,0101,1.1101,0.0011,1,0001011,0. 0011000,43,4、移碼表示法,（2）0 的表示：0 的移碼表示形式是唯一的，即分別按照正數(shù)和負(fù)數(shù)表示均一致。 +0移 100 -0移 100 （3）表示范圍：對于n1位移碼機(jī)器數(shù)X，它所能表示的數(shù)據(jù)范圍為： 定點整數(shù)：2n1X 2n1 定點小數(shù)：1X 12n 移碼通常作為浮點數(shù)的階碼。,包括1

22、位符號位，n位數(shù)值位,44,5、定點機(jī)器數(shù)轉(zhuǎn)換,機(jī)器數(shù)轉(zhuǎn)換為真值 四種定點機(jī)器數(shù)轉(zhuǎn)換為真值的方法要點是：首先根據(jù)機(jī)器數(shù)的符號位確定真值的正負(fù)，然后對照機(jī)器數(shù)的定義和表示，反方向求出真值的絕對值 機(jī)器數(shù)之間的相互轉(zhuǎn)換 原碼、補(bǔ)碼、反碼和移碼之間的相互轉(zhuǎn)換，最簡單的方法是先求出它們的真值，然后再轉(zhuǎn)換為另一種表示方法。,45,3.4 浮點機(jī)器數(shù)的表示方法,浮點機(jī)器數(shù)的格式,浮點機(jī)器數(shù)的規(guī)格化表示,浮點數(shù)的表示范圍,46,1、浮點機(jī)器數(shù)的格式,浮點機(jī)器數(shù)用于表示實數(shù)，其小數(shù)點的位置由其中的階碼規(guī)定，因此是浮動的。 浮點數(shù)N的構(gòu)成：,浮點數(shù)的格式：階碼的底是隱含規(guī)定的。,在機(jī)器中，為了方便浮點數(shù)大小的比

23、較，通常將數(shù)符放置在浮點數(shù)的首位。,47,1、浮點機(jī)器數(shù)的格式,尾數(shù)M：為定點小數(shù)，尾數(shù)的位數(shù)決定了浮點數(shù)有效數(shù)值的精度，尾數(shù)的符號代表了浮點數(shù)的正負(fù)，因此又稱為數(shù)符。尾數(shù)一般采用原碼和補(bǔ)碼表示。 階碼E：為定點整數(shù)，階碼的數(shù)值大小決定了該浮點數(shù)實際小數(shù)點位置與尾數(shù)的小數(shù)點位置（隱含）之間的偏移量。階碼的位數(shù)多少決定了浮點數(shù)的表示范圍。階碼的符號叫階符。階碼一般采用移碼和補(bǔ)碼表示。 階碼的底R：一般為2、8或16 ，且隱含規(guī)定。,48,1、浮點機(jī)器數(shù)的格式,根據(jù)IEEE 754 國際標(biāo)準(zhǔn)，常用的浮點數(shù)格式有3種，階碼的底隱含為2。 短實數(shù)又稱為單精度浮點數(shù)，長實數(shù)又稱為雙精度浮點數(shù)，臨時實數(shù)主

24、要用于進(jìn)行浮點數(shù)運算時保存臨時的計算結(jié)果。,49,2、浮點機(jī)器數(shù)的規(guī)格化表示,浮點數(shù)的規(guī)格化表示：為了充分利用尾數(shù)的二進(jìn)制數(shù)位來表示更多的有效數(shù)字，將尾數(shù)的絕對值限定在某個范圍之內(nèi)。 例如：R2，則規(guī)格化浮點數(shù)的尾數(shù)M應(yīng)滿足條件：最高有效位為1，即,50,2、浮點機(jī)器數(shù)的規(guī)格化表示,為便于計算機(jī)硬件對尾數(shù)的機(jī)器數(shù)形式的規(guī)格化判斷，通常采用下列方法實現(xiàn)判定： （1）對于原碼表示的尾數(shù)，當(dāng)最高有效位（M1）為1時，浮點數(shù)為規(guī)格化，即尾數(shù)為.1形式； （2）對于補(bǔ)碼表示的尾數(shù)，當(dāng)符號位（MS）與最高有效位（M1）相異時，浮點數(shù)為規(guī)格化，即尾數(shù)為0.1形式或者為1.0形式。,對于非規(guī)格化浮點數(shù)，可以通

25、過修改階碼和左右移尾數(shù)的方法來使其變?yōu)橐?guī)格化浮點數(shù)，這個過程叫做規(guī)格化。,51,2、浮點機(jī)器數(shù)的規(guī)格化表示,若尾數(shù)進(jìn)行右移實現(xiàn)的規(guī)格化，則稱為右規(guī)；若尾數(shù)進(jìn)行左移實現(xiàn)的規(guī)格化，則稱為左規(guī)。 使用規(guī)格化的浮點數(shù)表示數(shù)據(jù)的優(yōu)點： （1）提高了浮點數(shù)據(jù)的精度； （2）使程序能夠更方便地交換浮點數(shù)據(jù)； （3）可以使浮點數(shù)的運算更為簡化。,52,2、浮點機(jī)器數(shù)的規(guī)格化表示,例：一浮點數(shù)的階碼為6位（包括一位階符），尾數(shù)為10位（包括一位數(shù)符），階碼與尾數(shù)均采用補(bǔ)碼表示，階碼的底為2。寫出X與Y的規(guī)格化浮點數(shù)。 （1）X123.25 （2）Y34/128 （1）X（123.25）10 （1111011.0

26、1）2 0. 11110110127,53,2、浮點機(jī)器數(shù)的規(guī)格化表示,EX=+7=(+00111)2，MX=0. 111101101 EX補(bǔ)=000111， MX 補(bǔ)=1. 000010011 則：X浮= 1 000111 000010011 （2）Y（34/128 ） 10 （0.010001）2 0. 1000121 EY=00001，MY=0. 100010000 EY補(bǔ)=111111， MY 補(bǔ)=0. 100010000 則：Y浮= 0 111111 100010000,54,3、浮點數(shù)的表示范圍,在浮點數(shù)的表示范圍中，有兩種情況被稱為機(jī)器零： （1）若浮點數(shù)的尾數(shù)為零，無論階碼為何

27、值； （2）當(dāng)階碼的值遇到比它能表示的最小值還要小時（階碼負(fù)溢出），無論其尾數(shù)為何值,機(jī)器零,55,3、浮點數(shù)的表示范圍,浮點數(shù)的表示范圍通常：最小（負(fù)）數(shù)、最大負(fù)數(shù)、最小正數(shù)、最大（正）數(shù)。 位于最大負(fù)數(shù)和最小正數(shù)之間的數(shù)據(jù)（除0外），機(jī)器無法表示，稱為下溢。對于下溢的處理，計算機(jī)直接將其視為機(jī)器零。 當(dāng)一個數(shù)據(jù)大于最大（正）數(shù)，或者小于最?。ㄘ?fù)）數(shù)時，機(jī)器也無法表示，稱為上溢，上溢又稱溢出。,56,3、浮點數(shù)的表示范圍,寫出例3.10中的浮點數(shù)格式的規(guī)格化和非規(guī)格化表示范圍。 解：（1）規(guī)格化表示范圍： （2）非規(guī)格化表示范圍：,57,3.5 非數(shù)值數(shù)據(jù)的表示,非數(shù)值數(shù)據(jù)：文字和符號（字符

28、）、圖像、聲音等 非數(shù)值數(shù)據(jù)的表示：對其進(jìn)行二進(jìn)制編碼,58,一、字符編碼,字符的表示：采用字符編碼，即用規(guī)定的二進(jìn)制數(shù)表示文字和符號的方法。 ASCII碼：美國標(biāo)準(zhǔn)信息交換碼，為國際標(biāo)準(zhǔn)，在全世界通用 。 常用的7位ASCII碼的每個字符都由7個二進(jìn)制位b6b0 表示，有128個編碼，最多可表示128種字符；其中包括： 10個數(shù)字09：30H39H，順序排列 26個小寫字母az：61H7AH ，順序排列 26個大寫字母AZ：41H5AH ，順序排列 各種運算符號和標(biāo)點符號等。,59,ASCII碼編碼表,60,ASCII碼分類,95個可打印或顯示的字符：稱為圖形字符，有確定的結(jié)構(gòu)形狀，可在打印

29、機(jī)和顯示器等輸出設(shè)備上輸出；而且這些字符均可在計算機(jī)鍵盤上找到相應(yīng)的鍵，按鍵后就可以將相應(yīng)字符的二進(jìn)制編碼送入計算機(jī)內(nèi)。 33個控制字符：不可打印或顯示，分成5類： 10個傳輸類控制字符：用于數(shù)據(jù)傳輸控制； 6個格式類控制字符，用于控制數(shù)據(jù)的位置 4個設(shè)備類控制字符，用于控制輔助設(shè)備； 4個信息分隔類控制字符，用于分隔或限定數(shù)據(jù) 9個其他控制字符、空格字符和刪除字符。,61,基于IBM ProPrinter打印機(jī)的擴(kuò)展ASCII碼,62,二、漢字編碼,對于漢字，計算機(jī)的處理技術(shù)必須解決三個問題：漢字輸入、漢字儲存與交換、漢字輸出，它們分別對應(yīng)著漢字輸入碼、交換碼、內(nèi)碼、字形碼的概念。 1、漢字

30、輸入碼 漢字輸入碼也稱外碼，是為了將漢字輸入計算機(jī)而編制的代碼，是代表某一漢字的一串鍵盤符號。 漢字輸入碼種類： 數(shù)字編碼：如區(qū)位碼、國標(biāo)碼、電報碼等。 拼音編碼：如全拼碼、雙拼碼、簡拼碼等。 字形編碼：如王碼五筆、鄭碼、大眾碼等。 音形編碼：如表形碼、錢碼、智能ABC等。,63,二、漢字編碼,漢字交換碼是指不同的具有漢字處理功能的計算機(jī)系統(tǒng)之間在交換漢字信息時所使用的代碼標(biāo)準(zhǔn)。 目前國內(nèi)計算機(jī)系統(tǒng)所采用的標(biāo)準(zhǔn)信息處理交換碼，是基于1980年制定的國家標(biāo)準(zhǔn)信息交換用漢字編碼字符集基本集（GB2312-80）修訂的國標(biāo)碼。 該字符集共收錄了6763個漢字和682個圖形符號。6763個漢字按其使用

31、頻率和用途，又可分為一級常用漢字3755個，二級次常用漢字3008個。其中一級漢字按拼音字母順序排列，二級漢字按偏旁部首排列。 采用兩個字節(jié)對每個漢字進(jìn)行編碼，每個字節(jié)各取七位，這樣可對12812816384個字符進(jìn)行編碼。,64,二、漢字編碼,兩種典型的數(shù)字編碼： 區(qū)位碼：是將國家標(biāo)準(zhǔn)局公布的6763個兩級漢字分為94個區(qū)，每個區(qū)分94位，實際上把漢字表示成二維數(shù)組，每個漢字在數(shù)組中的下標(biāo)就是區(qū)位碼。例如“中”字位于54區(qū)48位，“中”字的區(qū)位碼即為“5448”。 國標(biāo)碼：將區(qū)位碼加2020H，占用兩個字節(jié)。例如“中”字的國標(biāo)碼為區(qū)位碼5448的區(qū)碼和位碼轉(zhuǎn)化為16進(jìn)制，為3630H，再加2

32、020H得國標(biāo)碼5650H。,65,二、漢字編碼,2、漢字內(nèi)碼 漢字內(nèi)碼是用于漢字信息的存儲、交換、檢索等操作的機(jī)內(nèi)代碼，一般采用兩個字節(jié)表示。 漢字可以通過不同的輸入法輸入，但其內(nèi)碼在計算機(jī)中是唯一的。 英文字符的機(jī)內(nèi)代碼是七位的ASCII碼，當(dāng)用一個字節(jié)表示時，最高位為“0”。為了與英文字符能相互區(qū)別，漢字機(jī)內(nèi)代碼中兩個字節(jié)的最高位均規(guī)定為“1”。 機(jī)內(nèi)碼等于漢字國標(biāo)碼加上8080H。例如“中”字的機(jī)內(nèi)碼為D6D0H。,66,二、漢字編碼,3、漢字字形碼 漢字字形碼是將漢字字形經(jīng)過點陣數(shù)字化后形成的一串二進(jìn)制數(shù)，用于漢字的顯示和打印。 根據(jù)漢字輸出的要求不同，點陣有以下幾種： 簡易型漢字：

33、1616， 32字節(jié)/漢字 普通型漢字：2424， 72字節(jié)/漢字 提高型漢字：3232，128字節(jié)/漢字。 漢字字庫：將所有漢字的字模點陣代碼按內(nèi)碼順序集中起來，構(gòu)成了漢字庫。,67,68,漢字的表示,通常用兩個字節(jié)表示一個漢字 為了與西文字符編碼相區(qū)別（西文的ASCII碼的最高一位編碼值為0），表示一個漢字時，把兩個字節(jié)的最高一位的編碼值設(shè)定為1，則該編碼集的最多編碼數(shù)量為128*128。 這種編碼方案與西文傳送中的把ASCII碼的最高一位用作奇偶校驗位有矛盾。,69,漢字信息的數(shù)字化,國標(biāo)碼：國家標(biāo)準(zhǔn)信息交換用漢字編碼。 國標(biāo)碼采用雙字節(jié)的編碼方式,用兩個7位二進(jìn)制編碼表示一個漢字。,國

34、標(biāo)碼收入6763個漢字，682個西文字符、圖符， 構(gòu)成9494的矩陣。 （每一行為“區(qū)”，每一列為“位”：國標(biāo)區(qū)位碼）,機(jī)內(nèi)碼,“啊”：區(qū)位碼“1601” 國標(biāo)碼“3021H”,00110000 00100001,10110000 10100001,“啊”：機(jī)內(nèi)碼“B0A1H”,70,漢字信息的數(shù)字化,外 碼,輸入 程序,內(nèi)碼,字 庫,字符,顯示輸出 打印輸出,輸入,輸出,漢字輸入碼(外碼):將漢字通過鍵盤輸入到計算機(jī)而采用的編碼。 拼音：全拼、雙拼 字型：五筆字型 數(shù)字：區(qū)位碼、電報碼,漢字機(jī)內(nèi)碼：在漢字信息處理中為漢字的存儲、運算與傳輸所編制的代碼,內(nèi)碼與字符一一對應(yīng),71,漢字的輸出（字

35、庫）,72,128,288,72,各種漢字編碼之間的關(guān)系,數(shù)字編碼,字音編碼,字形編碼,內(nèi)碼,字形碼,國標(biāo)碼,顯示漢字,打印漢字,73,3.6 校驗碼,74,3.6 校驗碼,1、校驗碼定義：是一種具有發(fā)現(xiàn)某些錯誤或自動改正錯誤能力的一種數(shù)據(jù)編碼方法。 2、校驗碼目的：用于檢查或糾正在存取、讀寫和傳送數(shù)據(jù)的過程中可能出現(xiàn)的錯誤。 3、校驗碼的基本思想：“冗余校驗”，即通過在有效信息代碼的基礎(chǔ)上，添加一些冗余位來構(gòu)成整個校驗碼。 4、校驗碼的構(gòu)成：有效信息校驗位（由有效信息產(chǎn)生的冗余位）,75,數(shù)據(jù)的檢/糾錯（ErrorDetect/Correct）,為什么要進(jìn)行數(shù)據(jù)的錯誤檢測與校正？ 計算、存取

36、和傳送時，由于元器件故障或噪音干擾等原因會出現(xiàn)差錯。措施： (1) 從計算機(jī)硬件本身的可靠性入手，在電路、電源、布線等各方面采取必要的措施，提高計算機(jī)的抗干擾能力； (2) 采取相應(yīng)的數(shù)據(jù)檢錯和校正措施，自動地發(fā)現(xiàn)并糾正錯誤。 如何進(jìn)行錯誤檢測與校正？ 大多采用“冗余校驗”思想，即除原數(shù)據(jù)信息外，還增加若干位編碼，這些新增的代碼被稱為校驗位。,76,3.6 校驗碼,5、校驗過程：,有效 信息,校驗碼 編碼器,校 驗 碼,校驗位,校 驗 碼,發(fā)送 /寫 /存,接收 /讀 /取,有 效 信 息,校 驗 位,有 效 信 息,校 驗 位,校驗碼 譯碼器,正確,錯誤,輸出,77,數(shù)據(jù)檢/校過程： 數(shù)據(jù)被

37、存入存儲器或從源部件傳輸時，對數(shù)據(jù)M進(jìn)行某種運算（用函數(shù)f 表示），以產(chǎn)生相應(yīng)的代碼P= f (M)，這里P就是校驗位。這樣原數(shù)據(jù)信息和相應(yīng)的校驗位一起被存儲或傳送。當(dāng)數(shù)據(jù)被讀出或傳送到終部件時，和數(shù)據(jù)信息一起被存儲或傳送的校驗位也被得到，用于檢錯和糾錯。假定讀出后的數(shù)據(jù)為M，通過同樣的運算f 對M也得到一個新的校驗位P=f (M)，假定原來被存儲的校驗位P取出后其值為P，將校驗位P與新生成的校驗位P進(jìn)行某種比較，根據(jù)其比較結(jié)果確定是否發(fā)生了差錯。 比較的結(jié)果為以下三種情況之一： 沒有檢測到錯誤，得到的數(shù)據(jù)位直接傳送出去。 檢測到差錯，并可以糾錯。數(shù)據(jù)位和比較結(jié)果一起送入糾錯器，將正確數(shù)據(jù)位傳

38、送出去。 檢測到錯誤，但無法確認(rèn)哪位出錯，因而不能進(jìn)行糾錯處理，此時，報告出錯情況。,BACK,78,碼字和碼距,什么叫碼距？ 由若干位代碼組成的一個字叫“碼字” 兩個碼字中具有不同代碼的位的個數(shù)叫做這兩個碼字間的“距離” 一種碼制各碼字間的最小距離稱為“碼距”，它就是這個碼制的距離。 問題：“8421”碼的碼距是幾？ 2（0010）和3（0011）間距離為1，“8421”碼制的碼距為1。 數(shù)據(jù)校驗中的“碼字”是指數(shù)據(jù)位和校驗位按某種規(guī)律排列得到的代碼,79,3.6 校驗碼,6、校驗碼原理：通過判斷代碼的合法性來檢錯的。 只有當(dāng)合法碼之間的碼距d2時，校驗碼才具有檢錯能力，當(dāng)碼距d 3時，校驗

39、碼才具有糾錯能力。 碼距：一種碼制的碼距是指該碼制中所有代碼之間的最小距離。 兩個代碼之間的距離：在一種編碼中，在任何兩個代碼之間逐位比較，對應(yīng)位值不同的個數(shù)。 校驗碼的檢錯糾錯能力與碼距的關(guān)系如下： 若碼距d為奇數(shù)，如果只用來檢查錯誤，則可以發(fā)現(xiàn)d1位錯誤；如果用來糾正錯誤，則能夠糾正 位錯誤。 若碼距d為偶數(shù)，則可以發(fā)現(xiàn) 位錯誤，并能夠糾正（ ）位錯誤。,80,3.6 校驗碼,7、常見校驗碼： 奇偶校驗碼：碼距d=2，檢錯碼，能檢驗奇數(shù)位錯誤；通常用于磁帶或者串行通信中。 海明校驗碼：碼距d=3，糾錯碼，能糾正1位或多位錯誤；通常用于磁盤冗余陣列中。 CRC校驗碼：碼距d=3，糾錯碼，能糾

40、正1位錯誤；通常用于磁盤或數(shù)據(jù)塊的校驗。,81,奇偶校驗碼,基本思想：增加一位奇校驗位（或偶校驗位），然后將原數(shù)據(jù)和得到的校驗位一起進(jìn)行存儲或傳送，對存取后或在傳送的終部件得到的相應(yīng)數(shù)據(jù)和校驗位，再進(jìn)行一次編碼，求出新校驗位，最后根據(jù)得到的這個新校驗位的值，確定是否發(fā)生了錯誤。 實現(xiàn)原理：假設(shè)將數(shù)據(jù)B=bn-1bn-2.b1b0從源部件傳送至終部件。在終部件接收到的數(shù)據(jù)為B=bn-1bn-2.b1b0。 第一步：在源部件求出奇（偶）校驗位P。 若采用奇校驗，則P=bn-1bn-2 .b1b01。 若采用偶校驗，則P=bn-1bn-2 .b1b0。 第二步：在終部件求出奇（偶）校驗位P。 若采用

41、奇校驗，則P= bn-1bn-2 .b1b01。 若采用偶校驗，則P=bn-1bn-2 .b1b0。 第三步：計算最終的校驗位P*，并根據(jù)其值判斷有無奇偶錯。 假定P在終部件接受到的值為P，則P*= PP” 若P*=1，則表示終部件接受的數(shù)據(jù)有奇數(shù)位錯。 若P*=0，則表示終部件接受的數(shù)據(jù)正確或有偶數(shù)個錯。,82,在有效信息位的前面或者后面添加一位奇（偶）校驗位就組成了奇（偶）校驗碼。 奇（偶）校驗碼的編碼和譯碼在硬件上通常采用異或非門（異或門）實現(xiàn)。 1、編碼 奇校驗位的取值應(yīng)該使整個奇校驗碼中“1”的個數(shù)為奇數(shù)，偶校驗位的取值應(yīng)該使整個偶校驗碼中“1”的個數(shù)為偶數(shù)。 假設(shè)在發(fā)送端，要發(fā)送七

42、位ASCII碼（B6 B5 B4 B3 B2 B1 B0），在ASCII碼前面添加一位奇校驗位P奇或偶校驗位P偶變?yōu)橐粋€字節(jié)的奇偶校驗碼，則它們的生成表達(dá)式為,二、奇偶校驗碼,83,2、譯碼 在接收端，必須檢驗接收到的校驗碼信息的奇偶性，對于奇校驗碼，校驗碼中“1”的個數(shù)應(yīng)該為奇數(shù)，否則出錯；對于偶校驗碼，校驗碼中“1”的個數(shù)應(yīng)該為偶數(shù)，否則出錯。設(shè)E奇為奇校驗碼出錯信號，E偶為偶校驗碼出錯信號，為1出錯，為0正確，則它們的表達(dá)式為,奇偶校驗的編碼電路,例如： 字符“A”的ASCII碼為41H，奇校驗碼為C1H，偶校驗碼為41H。,二、奇偶校驗碼,84,二、奇偶校驗碼,85,海明校驗碼,由Ri

43、chard Hamming于1950年提出，目前還被廣泛使用。 主要用于存儲器中數(shù)據(jù)存取校驗。 基本思想：奇偶校驗碼對整個數(shù)據(jù)編碼生成一位校驗位。因此這種校驗碼檢錯能力差，并且沒有糾錯能力。如果將整個數(shù)據(jù)按某種規(guī)律分成若干組，對每組進(jìn)行相應(yīng)的奇偶檢測，就能提供多位檢錯信息，從而對錯誤位置進(jìn)行定位，并將其糾正。 海明校驗碼實質(zhì)上就是一種多重奇偶校驗碼。,每一組一個校驗位，校驗碼位數(shù)等于組數(shù)！,86,奇偶校驗法的特點,特點： 問題：奇偶校驗碼的碼距是幾？為什么？ 碼距d=2。在奇偶校驗碼中，若兩個數(shù)中有奇數(shù)位不同，則它們相應(yīng)的校驗位就不同；若有偶數(shù)位不同，則雖校驗位相同，但至少有兩位數(shù)據(jù)位不同。因

44、而任意兩個碼字之間至少有兩位不同。 根據(jù)碼距和糾/檢錯能力的關(guān)系，它只能發(fā)現(xiàn)奇數(shù)位出錯，不能發(fā)現(xiàn)偶數(shù)位出錯，而且也不能確定發(fā)生錯誤的位置，不具有糾錯能力。 優(yōu)點： 開銷小 適用于校驗一字節(jié)長的代碼，故常被用于存儲器讀寫檢查或按字節(jié)傳輸過程中的數(shù)據(jù)校驗 因為一字節(jié)長的代碼發(fā)生錯誤時，1位出錯的概率較大，兩位以上出錯則很少，所以可用奇偶校驗。,87,三、海明碼,1、編碼 海明碼的編碼步驟如下： （1）計算校驗位的位數(shù) 假設(shè)信息位為k位，增加r位校驗位，構(gòu)成n=k+r位海明碼字。若要求海明碼能糾正一位錯誤，用r位校驗位產(chǎn)生的r位指誤字來區(qū)分無錯狀態(tài)及碼字中n個不同位置的一位錯誤狀態(tài)，則要求r滿足：

45、2 r k + r + 1 計算出k位有效信息時，必須添加的能糾錯一位的海明校驗碼的校驗位的位數(shù)r,88,（2）確定有效信息和校驗位的位置 假設(shè)k位有效信息從高到低為 ，添加的r位校驗位為 ，則它們構(gòu)成n=k+r位的海明碼排列設(shè)為 ，H的下標(biāo)被稱為海明位號，則第i位的校驗位Pi必須位于位號為2i-1的位置，即 ，其中，i=1，2，r；有效信息則在其余的海明碼位置上順序排列。,三、海明碼,89,三、海明碼,（3）分組 由于海明碼是分組進(jìn)行奇偶校驗的，每一組通過一個監(jiān)督表達(dá)式來監(jiān)督有效信息的變化，因此，分組必須使得監(jiān)督表達(dá)式得出的指誤字能夠反映出錯位的位號。分組的原則是：校驗位只參加一組奇偶校驗，

46、有效信息則參加至少兩組的奇偶校驗，若 Di = Hj ，則Di參加那些位號之和等于j的校驗位的分組校驗。,90,三、海明碼,（4）進(jìn)行奇偶校驗，合成海明碼 首先，按照分組和奇偶校驗的規(guī)律將每個校驗位的生成表達(dá)式寫出，然后，再帶入有效信息的值，依次得出校驗位的取值，最后將校驗位按各自的位置插入，與有效信息一起合成海明碼。,91,三、海明碼,2、譯碼 在接收端收到每個海明碼后，也必須按上述分組檢驗每組的奇偶性有無發(fā)生變化，方法是按照監(jiān)督關(guān)系式算出指誤字Sr Sr-1 S2 S1 ，若為全零，則說明各組奇偶性全部無變化，信息正確，將相應(yīng)的有效信息位析取出來使用；否則，指誤字的十進(jìn)制值，就是出錯位的海

47、明位號。,92,處理過程： 最終比較時按位進(jìn)行異或，根據(jù)異或結(jié)果，確定是否有差錯。 這種異或操作所得到的結(jié)果稱為故障字（syndrome word）。顯然，校驗碼和故障字的位數(shù)是相同。,93,校驗碼位數(shù)的確定,假定數(shù)據(jù)位數(shù)為n，校驗碼為k位，則故障字的位數(shù)也為k位。k位故障字所能表示的狀態(tài)最多是2K，每種狀態(tài)可用來說明一種出錯情況。 若只有一位錯，則結(jié)果可能是： 數(shù)據(jù)中某一位錯 (n種可能) 校驗碼中有一位錯 (k種可能) 無錯 ( 1 種可能) 要能對最多一位錯的所有結(jié)果進(jìn)行正確表示，則n和k必須滿足下列關(guān)系： 2K1+n+k， 即：2K-1n+k 有效數(shù)據(jù)位數(shù)和校驗碼位數(shù)間的關(guān)系 從表中可

48、以看出，當(dāng)數(shù)據(jù)有8位時，校驗碼和故障字都應(yīng)有4位。 說明：4位的故障字最多可以表示16種狀態(tài)，而單個位出錯情況最多只有12種可能（8個數(shù)據(jù)位和4個校驗位），再加上無錯的情況，一共有13種。所以，用16種狀態(tài)表示13種情況應(yīng)是足夠了。,94,有效數(shù)據(jù)位數(shù)和校驗碼位數(shù)間的關(guān)系,95,海明碼的分組,基本思想:數(shù)據(jù)位和校驗位按某種方式排列為一個n+k的碼字，將該字中每一位的出錯位置與故障字的數(shù)值建立關(guān)系，通過故障字的值確定該碼字中哪一位發(fā)生了錯誤，并將其取反來糾正。 根據(jù)上述基本思想，按以下規(guī)則來解釋各故障字的值。 規(guī)則1： 若故障字每位全部是0，則表示沒有發(fā)生錯誤。 規(guī)則2：若故障字中有且僅有一位為

49、1，則表示校驗位中有一位出錯，因而不需糾正。 規(guī)則3：若故障字中多位為1，則表示有一個數(shù)據(jù)位出錯，其在碼字中的出錯位置由故障字的數(shù)值來確定。糾正時只要將出錯位取反即可。,96,海明碼的分組,以8位數(shù)據(jù)進(jìn)行單個位檢錯和糾錯為例說明。 假定一個8位數(shù)據(jù)M= M8M7M6M5M4M3M2M1，其相應(yīng)的4位校驗位為P=P4P3P2P1。根據(jù)規(guī)則將數(shù)據(jù)M和校驗位P按一定的規(guī)律排到一個12位碼字中。 據(jù)規(guī)則1，故障字為0000時，表示無錯，因此沒有和位置號0000對應(yīng)的出錯情況，所以位置號從0001開始。 據(jù)規(guī)則2，故障字中有且僅有一位為1時，表示校驗位中有一位出錯，此時，故障字只可能是0001、0010

50、、0100、1000四種情況，我們將這四種狀態(tài)分別代表校驗位中第P1、P2、P3、P4位發(fā)生錯誤的情況，因此，校驗位P1、P2、P3、P4應(yīng)分別位于碼字的第1、2、4、8位。 據(jù)規(guī)則3，將其他多位為1的故障字依次表示數(shù)據(jù)位M1M8發(fā)生錯誤的情況。因此，數(shù)據(jù)位M1M8應(yīng)分別位于碼字的第0011(3)、0101(5)、0110(6)、0111(7)、1001(9)、1010(10)、1011(11)、1100(12)位。即碼字的排列為： M8M7M6M5P4M4M3M2P3M1P2P1 這樣，得到故障字S=S4S3S2S1的各個狀態(tài)和出錯情況的對應(yīng)關(guān)系表，可根據(jù)這種對應(yīng)關(guān)系對整個數(shù)據(jù)進(jìn)行分組。,邏

51、輯上的一個順序，物理上M和P是分開的,97,海明校驗碼分組情況,BACK,根據(jù)故障字S4S3S2S1的值確定哪位出錯，因此，某位出錯一定會影響與之相對應(yīng)的故障字中為1的位所在組的奇偶性。,碼字：M8M7M6M5P4M4M3M2P3M1P2P1,例：若M1出錯，則故障字為0011，所以一定會改變S2和S1所在分組的奇偶性。故M1同時被分到第2(S2)組和第1(S1) 組。,問題：若P1出錯，則如何？若M8出錯，則如何？,P10001，分在第1組 M81100，分在第4組和第3組,98,校驗位的生成和檢錯、糾錯,分組完成后，就可對每組采用相應(yīng)的奇（偶）校驗，以得到相應(yīng)的一個校驗位。 假定采用偶校驗

52、 (取校驗位Pi，使對應(yīng)組中有偶數(shù)個1)，則得到校驗位與數(shù)據(jù)位之間存在如下關(guān)系： P1 = M1M2M4M5M7 P2 = M1M3M4M6M7 P3 = M2M3M4M8 P4 = M5M6M7M8,99,海明校驗過程,根據(jù)公式求出每一組對應(yīng)的校驗位Pi (i=1,2,3,4) 數(shù)據(jù)M和校驗位P一起被存儲，根據(jù)讀出數(shù)據(jù)M，得新校驗位P 讀出校驗位P與新校驗位P 按位進(jìn)行異或操作，得故障字 S = S4S3S2S1 根據(jù)S的值確定：無錯、僅校驗位錯、某個數(shù)據(jù)位錯,100,海明碼舉例,假定一個8位數(shù)據(jù)M為：M8M7M6M5M4M3M2M1= 01101010，根據(jù)上述公式求出相應(yīng)的校驗位為： P

53、1 = M1M2M4M5M7 =01101=1 P2 = M1M3M4M6M7 =00111=1 P3 = M2M3M4M8=1010=0 P4 = M5M6M7M8=0110=0 假定12位碼字(M8M7M6M5P4M4M3M2P3M1P2P1)讀出后的結(jié)果是: (1) 數(shù)據(jù)位M=M=01101010，校驗位P=P=0011 (2) 數(shù)據(jù)位M= 01111010，校驗位P=P=0011 (3) 數(shù)據(jù)位M=M=01101010，校驗位P= 1011 要求分別考察每種情況的故障字。 (1) 數(shù)據(jù)位M=M=01101010，校驗位P=P=0011，即：所有位都無錯。這種情況下，因為M=M，所以P=

54、 P， 因此 S = PP=PP = 0000。,101,海明碼舉例,(2) 數(shù)據(jù)位M= 01111010，校驗位P=P=0011，即：數(shù)據(jù)位第5位(M5)錯。 這種情況下，對M生成新的校驗位P為： P1 = M1M2M4M5M7=01111=0 P2 = M1M3M4M6M7 =00111=1 P3 = M2M3M4M8=1010=0 P4 = M5M6M7M8=1110=1 故障字S為： S1= P1 P1= 01=1 S2= P2 P2=11=0 S3= P3 P3=00=0 S4= P4 P4=10=1 根據(jù)故障字的數(shù)值1001，可以判斷出發(fā)生錯誤的位是在12位碼字的第 1001位(即

55、：第9位)，在這一位上排列的是數(shù)據(jù)位M5，所以檢錯正確。 糾錯時，只要將碼字的第9位（即：第5個數(shù)據(jù)位）取反即可。,102,海明碼舉例,(3) 數(shù)據(jù)位M=M=01101010，校驗位P= 1011， 即：校驗碼第4位(P4)錯。 這種情況下，因為M=M，所以P= P，因此故障位S為： S1= P1 P1= 11=0 S2= P2 P2=11=0 S3= P3 P3=00=0 S4= P4 P4=01=1 根據(jù)故障字的數(shù)值1000，可以判斷出發(fā)生錯誤的位是在12位碼字的第1000位(即：第8位)，在這一位上排列的是校驗位P4，所以檢錯正確，不需糾錯。,103,單糾錯和雙檢錯碼,單糾錯碼（SEC）

56、 問題：上述(n=8/k=4)海明碼的碼距是幾？ 碼距d=3。因為，若有一位出錯，則因該位至少要參與兩組校驗位的生成，因而至少引起兩個校驗位的不同。兩個校驗位加一個數(shù)據(jù)位等于3。 根據(jù)碼距與檢錯、糾錯能力的關(guān)系，知：這種碼制能發(fā)現(xiàn)兩位錯，或?qū)蝹€位出錯進(jìn)行定位和糾錯。這種碼稱為單糾錯碼（SEC）。 單糾錯和雙檢錯碼（SEC-DED） 如果校驗碼同時具有發(fā)現(xiàn)兩位錯和糾正一位錯的能力，則稱為單糾錯和雙檢錯碼（SEC-DED）。 一般半導(dǎo)體存儲器都采用這種校驗碼進(jìn)行數(shù)據(jù)校驗。 若要使上述單糾錯碼成為SEC-DED ，則碼距需擴(kuò)大到d= 4。為此，還需要增加一位校驗位P5，將P5排列在碼字的最前面，即

57、：P5M8M7M6M5P4M4M3M2P3M1P2P1，并使得數(shù)據(jù)中的每一位都參與三個校驗位的生成。從表中可看出除了M4 和M7參與了三個校驗位的生成外，其余位都只參與了兩個校驗位的生成。因此P5按下式求值： P5= M1M2M3M5M6M8 當(dāng)任意一個數(shù)據(jù)位發(fā)生錯誤時，必將引起三個校驗位發(fā)生變化，所以碼距為4。,104,SEC-DED的檢錯糾錯規(guī)則,引入P5后，故障字S也增加了一位，即S=S5S4S3S2S1，根據(jù)S5S4S3S2S1的取值情況，可按如下規(guī)則發(fā)現(xiàn)兩位錯并糾正一位錯。 當(dāng)S5S4S3S2S1為00000時，表明無錯。 當(dāng)S5S4S3S2S1中僅一位不為0時，表明由S指定的位置上

58、那個校驗位發(fā)生了錯誤，或是在數(shù)據(jù)和校驗位中有三位同時出錯，但后面這種可能性非常小，所以一般認(rèn)為發(fā)生了前一種情況。 當(dāng)S5S4S3S2S1中有兩位不為0時，表明數(shù)據(jù)和校驗位中有兩位同時出錯，此時只能發(fā)現(xiàn)這種錯誤，但無法確定是哪兩位錯。 當(dāng)S5S4S3S2S1中有三位不為0時，表明有一個數(shù)據(jù)位發(fā)生了錯誤，或是三個校驗位同時出錯，但后面這種可能性非常小，所以一般認(rèn)為發(fā)生了前一種情況。此時，出錯的位置由S4S3S2S1的數(shù)值指定。 當(dāng)S5S4S3S2S1中有四位或五位都不為0時，表明出錯情況嚴(yán)重，系統(tǒng)可能出現(xiàn)故障，應(yīng)檢查系統(tǒng)硬件的正確性。,105,四、循環(huán)冗余碼CRC,循環(huán)冗余校驗碼（Cyclic R

59、edundancy Check），簡稱CRC碼 具很強(qiáng)的檢錯、糾錯能力。 用于大批量數(shù)據(jù)存儲和傳送(如：外存和通信)中的數(shù)據(jù)校驗。 奇偶校驗碼是在每個字符信息后增加一位校驗位進(jìn)行數(shù)據(jù)校驗的，這樣對大批量傳輸數(shù)據(jù)進(jìn)行校驗時，會增加大量的額外開銷，尤其是在網(wǎng)絡(luò)通信中，傳輸?shù)臄?shù)據(jù)信息都是二進(jìn)制比特流，因而沒有必要將數(shù)據(jù)再分解成一個個字符，也就無法采用奇偶校驗碼，因此，通常采用CRC碼進(jìn)行校驗。 通過某種數(shù)學(xué)運算來建立數(shù)據(jù)和校驗位之間的約定關(guān)系。 奇偶校驗碼和海明校驗碼都是以奇偶檢測為手段的。,網(wǎng)絡(luò)或通信課程中會學(xué)到。,106,CRC碼的檢錯方法,基本思想：假設(shè)要進(jìn)行校驗的數(shù)據(jù)信息M(x)為一個n位的二進(jìn)制數(shù)據(jù)，將M(x)左移k位后，用一