第二章數(shù)據(jù)在計算機中的表示2015(1)

1、第二章第二章 數(shù)據(jù)在計算機中的表示數(shù)據(jù)在計算機中的表示n概述概述n字符編碼字符編碼n中文編碼中文編碼n邏輯數(shù)據(jù)邏輯數(shù)據(jù)n數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù)n校驗碼校驗碼 概述概述q計算機中最重要的功能是處理信息，如：數(shù)值、文字、符號、語言和圖象等。計算機內(nèi)部，各種信息都必須采用數(shù)字化編碼的形式被傳送、存儲、加工。因此掌握信息編碼的概念與處理技術(shù)是至關(guān)重要的。q所謂編碼，就是用少量簡單的基本符號，選用一定的組合規(guī)則，以表示出大量復雜多樣的信息。概述概述n常用的信息分為： 定點數(shù)(fixed-point) 數(shù)值信息 浮點數(shù)(floating-point) 字符(character) 非數(shù)值信息 漢字(Chinese

2、 character) 邏輯數(shù)據(jù)(logical data)2.1 字符編碼字符編碼n用一定位數(shù)的二進制數(shù)“0”和“1”進行編碼給出。n常用的字符編碼ASCII碼。nASCII （American Standard Code for Information Interchange)2.1 字符編碼字符編碼碼是美國信息交換標準代碼。碼是美國信息交換標準代碼。( ( merican tandard ode for nformation nterchange) )包括包括0- -9十個數(shù)字，大小寫英文字母十個數(shù)字，大小寫英文字母及專用符號等及專用符號等95種可打印字符。另有種可打印字符。另有3333

3、不可不可打印字符，被用于控制碼。打印字符，被用于控制碼。1000011 1101111 11011011110000 1110101 11101001100101 11100107 6 5 4 3 2 12.2 中文編碼中文編碼n漢字輸入碼：為便于漢字進行輸入時的編碼，漢字輸入碼：為便于漢字進行輸入時的編碼，將漢字代碼化。將漢字代碼化。n漢字機內(nèi)碼：用于漢字信息的存儲、交換、漢字機內(nèi)碼：用于漢字信息的存儲、交換、檢索等操作的機內(nèi)代碼。一般用兩個字節(jié)表檢索等操作的機內(nèi)代碼。一般用兩個字節(jié)表示。示。n漢字字型碼：漢字輸出時的編碼。用點陣表漢字字型碼：漢字輸出時的編碼。用點陣表示。示。精密型精密型4

4、848 4848288288提高型提高型3232 3232128128普及型普及型2424 24247272簡易型簡易型1616 16163232漢字點陣類型漢字點陣類型點陣點陣占用字節(jié)數(shù)占用字節(jié)數(shù)顯示輸出顯示輸出打印輸出打印輸出機內(nèi)碼向字形碼轉(zhuǎn)換機內(nèi)碼向字形碼轉(zhuǎn)換機內(nèi)碼機內(nèi)碼輸入碼向機內(nèi)碼轉(zhuǎn)換輸入碼向機內(nèi)碼轉(zhuǎn)換2.2 中文編碼中文編碼字符代碼化（輸入）字符代碼化（輸入）數(shù)字碼數(shù)字碼拼音碼拼音碼字形碼字形碼2.3 邏輯數(shù)據(jù)邏輯數(shù)據(jù)邏輯型數(shù)據(jù)只有兩個值：邏輯型數(shù)據(jù)只有兩個值：真真 和和 假假，正好可以用二進制碼的兩個符號分別表示，正好可以用二進制碼的兩個符號分別表示，例如例如 1 表示表示 真真

5、 則則 0 表示表示 假假不必使用另外的編碼規(guī)則。不必使用另外的編碼規(guī)則。對邏輯型數(shù)據(jù)可以執(zhí)行邏輯的對邏輯型數(shù)據(jù)可以執(zhí)行邏輯的 與與 或或 非非等基本等基本邏輯運算。其規(guī)則如下邏輯運算。其規(guī)則如下邏輯數(shù)據(jù)邏輯數(shù)據(jù) 輸入輸入 輸出輸出 x y X與y X或yX的非000010101110010111102.4 數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù) 在選擇計算機的數(shù)的表示方式時，需在選擇計算機的數(shù)的表示方式時，需要考慮以下幾個因素：要考慮以下幾個因素： 1要表示的數(shù)的類型；要表示的數(shù)的類型；2數(shù)值的范圍；數(shù)值的范圍；3數(shù)值的精度；數(shù)值的精度；4數(shù)據(jù)存儲和處理所需要的硬件代價。數(shù)據(jù)存儲和處理所需要的硬件代價。2.4 數(shù)

6、值數(shù)據(jù)數(shù)值數(shù)據(jù)q 定點數(shù)定點數(shù)q 浮點數(shù)浮點數(shù)q 十進制數(shù)串十進制數(shù)串2.4.1 數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù)定點數(shù)的表示方法定點數(shù)的表示方法 定點表示定點表示：約定機器中所有數(shù)據(jù)的小數(shù)點位置是固定不變的。由于約定在固定的位置，小數(shù)點就不再使用記號“.”來表示。通常將數(shù)據(jù)表示成純小數(shù)純小數(shù)或純整數(shù)純整數(shù)。定點數(shù)xx0 x1x2xn 在定點機中表示如下(0為符號位，0代表正號，1代表負號):2.4.1 數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù)定點數(shù)的表示方法定點數(shù)的表示方法純小數(shù)純小數(shù)的表示范圍為(x0 x1x2xn 各位均為0時最??；各位均為1時最大)0|12n 純整數(shù)純整數(shù)的表示范圍為0|2n1 2.4.2 數(shù)值數(shù)據(jù)數(shù)的機器碼

7、表示數(shù)的機器碼表示 在計算機中對數(shù)據(jù)進行運算操作時，在計算機中對數(shù)據(jù)進行運算操作時，符號位如何表示呢？是否也同數(shù)值位一符號位如何表示呢？是否也同數(shù)值位一道參加運算操作呢？為了妥善的處理好道參加運算操作呢？為了妥善的處理好這些問題，就產(chǎn)生了把符號位和數(shù)字位這些問題，就產(chǎn)生了把符號位和數(shù)字位一起編碼來表示相應的數(shù)的各種表示方一起編碼來表示相應的數(shù)的各種表示方法，如原碼、補碼、反碼、移碼等。通法，如原碼、補碼、反碼、移碼等。通常將前者稱為常將前者稱為真值真值，后者稱為，后者稱為機器數(shù)機器數(shù)或或機器碼機器碼。 1.原碼表示法原碼表示法 定點小數(shù)定點小數(shù)X表示表示: Ns. N: Ns. N1 1 N

8、N2 2 Nn Nn 定義定義: X 原原 = 定點整數(shù)定點整數(shù)X表示表示：Ns N1 N2 Nn 定義定義: X 原原 =X, 0 X 11-X, -1 X 0X, 0 X 2n 2n-X, - 2n X 01.原碼表示法原碼表示法n實例實例：X1 = 0.10110 -0.10110 0.0000 X 原原= 0.10110 1.10110 0.0000 1.0000 n實例實例：X1 = 10110 -10110 0000 X 原原= 010110 110110 00000 10000 1.原碼表示法原碼表示法性質(zhì): 原碼為符號位加上數(shù)的絕對值，0正1負 原碼零有兩個編碼，+0和 -0編

9、碼不同 原碼難以用于加減運算，但乘除方便 N+1位二進制原碼所表示的范圍為：小數(shù)：MAX=1-2-n ，MIN=（ 1-2-n ）整數(shù)：MAX= 2n-1， MIN=（ 2n-1） 1.原碼表示法原碼表示法原碼的優(yōu)點是：簡單易懂。原碼的優(yōu)點是：簡單易懂。 缺點是：難以用于加減運算。原因是：缺點是：難以用于加減運算。原因是：如果是異號相加，則要進行減法運算。首先如果是異號相加，則要進行減法運算。首先要比較絕對值的大小，然后大數(shù)減小數(shù)，最要比較絕對值的大小，然后大數(shù)減小數(shù)，最后確定符號。后確定符號。為了便于加減運算，采用了補碼表示。為了便于加減運算，采用了補碼表示。2. 補碼表示法補碼表示法 補碼

10、是在“?！焙汀巴唷钡母拍钕聦С龅?。 “?！笔侵敢粋€計量系統(tǒng)的計量范圍，即產(chǎn)生“溢出”的量。 在計算機中，機器能表示的數(shù)據(jù)位數(shù)是一定的，其運算都是有模運算。如果是n位整數(shù)，其模為2n。如果是n位小數(shù)，其模為2。 若運算結(jié)果超出了計算機所能表示的數(shù)值范圍，則只保留它的小于模的低n位的數(shù)值，超過n位的高位部分就自動舍棄了。2. 補碼表示法補碼表示法定義： 任意一個X的補碼為X補，可以用該數(shù)加上其模M來表示。 X補=X+M2. 補碼表示法補碼表示法定點小數(shù)表示: X0. X1 X2 Xn 定義: X 補 = （MOD 2） 定點整數(shù)表示：X0 X1 X2 Xn 定義: X 補 = （MOD 2n+1

11、） X 2+ X0 X 1 -1 X 0 X 2n+1 + X；0 X 2n - 2n X 02. 補碼表示法補碼表示法n由于正數(shù)的補碼就是正數(shù)本身，故著重講解負數(shù)求補碼負數(shù)求補碼的方法。2. 補碼表示法補碼表示法（1）由定義求由定義求例：例：X補=2+X=10+(-0.1101001)=1.00101112. 補碼表示法補碼表示法n例例: X=- 1101001 解解: X補補=27+1+X=100000000+(-1101001)=10010111反過來，由補碼求真值，只要將公式進行交換反過來，由補碼求真值，只要將公式進行交換即可即可。2. 補碼表示法補碼表示法性質(zhì): 0的補碼是唯一的 補

12、碼便于加減運算 n+1位補碼所能表示的數(shù)：小數(shù)：MAX=1-2-n ，MIN=1整數(shù)：MAX= 2n-1， MIN= 2n 2. 補碼表示法補碼表示法n補碼便于加減運算，因為不論正、負數(shù)它只補碼便于加減運算，因為不論正、負數(shù)它只需要做加運算。但負數(shù)的求補需要做一次減需要做加運算。但負數(shù)的求補需要做一次減運算，顯然有不方便，為此又引入了反碼。運算，顯然有不方便，為此又引入了反碼。3.反碼表示法反碼表示法定點小數(shù)表示: Ns. N1 N2 Nn 定義: X 反 =定點整數(shù)表示：Ns N1 N2 Nn 定義: X 反 = X； （2-2-n ）+ X；0 X 1 -1 X 0X； 0 X 2n（ 2

13、n+1 1）+ X； - 2n X 03.反碼表示法反碼表示法n由原碼求反碼，如果由原碼求反碼，如果X為正數(shù)，則為正數(shù)，則X反反=X原原；如果如果X為負數(shù)，為負數(shù)，則將則將X原原除符號位以外，每位都除符號位以外，每位都變反，可得到變反，可得到X反反。n實例實例：X1 = 0.10110 -0.10110 0.0000 X 原原 = 0.10110 1.10110 0.0000 1.0000 X 反反 = 0.01001 1.01001 0.0000 1.1111 3.反碼表示法反碼表示法 X 反反 =2+ X -2-n X 補補 = 2+ X 所以所以當當x的真值為負數(shù)時：的真值為負數(shù)時：有有

14、 X 補補 = X 反反 + 2-n 負數(shù)求補：變反加一負數(shù)求補：變反加一由由-X補補求求X補補，此規(guī)則同此規(guī)則同樣適用樣適用。 由X補求-X補:連符號位一起各位求反，末位加1。例：X補=1.1010101解:X補= 1 1 0 1 0 1 0 1 -X補=0 000111 0+1 0 0 1 0 1 0 1 14.移碼表示法移碼表示法 對于n+1位數(shù)x0 x1 x2 xn 定義: X 移 =2n+x; 由于移碼是在原值X上加一個2n，所以也稱為增碼，因此，符號為1時，表示正數(shù)，符號為0時，表示負數(shù)。例如例如：X=1101010， 則：則：X補補= 01101010 X移移=27+X =111

15、01010 -2n X 2n4.移碼表示法移碼表示法例如例如：X=-1101010， 則：則：X補補=28+X = 10010110 X移移=27+X =00010110 結(jié)論：結(jié)論：由X補求X移：只要將X補的符號位變反，就可得到X移4.移碼表示法移碼表示法 零的移碼是唯一的，即：+0移= -0移= 10000性質(zhì)： 若X1移X2移，則有 X1X2 浮點數(shù)的階碼常用移碼來表示的原因，就浮點數(shù)的階碼常用移碼來表示的原因，就是用到了該性質(zhì)。是用到了該性質(zhì)。用用+4+4和和-3-3兩個數(shù)的補碼和移碼來舉例說明兩個數(shù)的補碼和移碼來舉例說明計算機比較數(shù)據(jù)的大小計算機比較數(shù)據(jù)的大小. . 四種碼制的比較四

16、種碼制的比較1）移碼最高位為“0”表示負數(shù)，最高位為“1”表示正數(shù)。這與原碼、補碼、反碼的符號位正好相反。2）原碼、補碼、反碼對于正數(shù)，它們都等于真值本身，而對于負數(shù)各有不同的表示。3）最高位都表示符號位。補碼、反碼和移碼的符號位可作為數(shù)值位的一部分看待，和數(shù)值位一起參加四種碼制的比較四種碼制的比較 運算，但原碼的符號位不允許和數(shù)值位同等看待，必須分開進行處理。 4）對于真值0，原碼和反碼各有兩種不同的表示形式，而補碼、移碼是唯一的。 教材教材P22 例題例題6、7、8例1 以n+1定點整數(shù)為例,用數(shù)軸形式說明原碼、反碼、補碼表示范圍和可能的數(shù)碼組合情況。例2 將十進制真值(127,1,0,1

17、,127)列表表示成二進制數(shù)及原碼、反碼、補碼、移碼值。 解解:二進制真值及其諸碼值列于下表,其中0在原反中有兩種表示。由表中數(shù)據(jù)可知,補碼值與移碼值差別僅在于符號位不同。 例3設機器字長16位,定點表示,尾數(shù)15位,數(shù)符1位,問： (1)定點原碼整數(shù)表示時,最大正數(shù)是多少?最小負數(shù)是多少? (2)定點原碼小數(shù)表示時,最大正數(shù)是多少?最小負數(shù)是多少?; 解解:例題例題3(1)定點原碼整數(shù)表示 最大正數(shù)值(2151)10(32767)10 0111 1111 1111 1111 最小負數(shù)值(2151)10(32767)10 1111 1111 1111 1111(2)定點原碼小數(shù)表示 最大正數(shù)值

18、(1215)10(0.111.11)2 最小負數(shù)值(1215)10(0.111.11)2 2.4.3 數(shù)值數(shù)據(jù)浮點數(shù)表示法浮點數(shù)表示法定義：任意一個R進制都可以通過移動小數(shù)點的位置寫成N=RE*M式中：R是基數(shù)，可以取2，8，16，一旦定義則不能改變，是隱含的。M是尾數(shù)，為純小數(shù) ，表示數(shù)N的有效數(shù)字位數(shù)。決定了浮點數(shù)的精度。E是階碼，為純整數(shù)，指出小數(shù)點在該數(shù)中的位置。決定了浮點數(shù)的大小。由于階碼可以取不同的數(shù)值，所以，小數(shù)點的位置是不確定的，因而稱之為浮點數(shù)。2.4.3 數(shù)值數(shù)據(jù)浮點數(shù)表示法浮點數(shù)表示法 由于基數(shù)在系統(tǒng)中是隱含約定的，不需要用代碼表示，所以浮點數(shù)只需用一對定點數(shù)（階碼和尾數(shù)

19、）表示，其中，符號表示數(shù)的正負，階碼表示小數(shù)點的位置，而尾數(shù)表示有效數(shù)字。2.4.3 數(shù)值數(shù)據(jù)浮點數(shù)表示法浮點數(shù)表示法數(shù)的表示范圍： 設m和n分別表示階碼和尾數(shù)的位數(shù)（均不包含符號位）用原碼表示，則浮點數(shù)的表示范圍是： - 2 2m-1 （1-2-n）N2 2m-1（1-2-n）請問:最小正數(shù)和最大負數(shù)是多少?2.4.3 數(shù)值數(shù)據(jù)浮點數(shù)表示法浮點數(shù)表示法最大正數(shù)為：最小負數(shù)為：最小正數(shù)為：最大負數(shù)為：122)21 (mn12221mn) 12(22mn)12(22mn2.4.3 數(shù)值數(shù)據(jù)浮點數(shù)表示法浮點數(shù)表示法規(guī)格化定義： 所謂規(guī)格化數(shù)，就是非0的尾數(shù)，其絕對值 應大于或等于05。判別方法：

20、原碼規(guī)格化后，正數(shù)為0.1的形式 負數(shù)為1.1的形式 補碼規(guī)格化后，正數(shù)為0.1的形式 負數(shù)為1.0的形式2.4.3 數(shù)值數(shù)據(jù)浮點數(shù)表示法浮點數(shù)表示法規(guī)格化： 存儲在計算機中的浮點數(shù)以及運算結(jié)果的浮點數(shù)都應為規(guī)格化數(shù),如果尾數(shù)不是規(guī)格化數(shù),要用移位方法把他變?yōu)橐?guī)格化數(shù),這種處理過程,稱為規(guī)格化。 例題例題: 設浮點數(shù)字長設浮點數(shù)字長16位，其中階碼位，其中階碼5位（含位（含1位階位階符），尾數(shù)符），尾數(shù)11位（含位（含1位數(shù)符），將十進制數(shù)位數(shù)符），將十進制數(shù)13/128寫成二進制定點數(shù)和浮點數(shù)，并分別寫出寫成二進制定點數(shù)和浮點數(shù)，并分別寫出定點和浮點的機器碼形式。定點和浮點的機器碼形式。解：

21、令解：令x=13/128 則其二進制形式為則其二進制形式為: x=0.0001101000 定點數(shù)表示為定點數(shù)表示為: x=0.0001101000 浮點數(shù)規(guī)格化表示為浮點數(shù)規(guī)格化表示為: x=0.1101000000*2-11 定點機中:x原=x補=x反=0.0001101000浮點機中浮點機中x原=1， 0011；0. 1101000000 x補= 1，1101；0. 1101000000 x反= 1，1100；0. 11010000002.4.3 數(shù)值數(shù)據(jù)浮點數(shù)表示法浮點數(shù)表示法 IEEE754標準(伯克利Willian Kahan教授1987年獲得圖靈獎) IEEE754標準定義了四種

22、浮點數(shù)的基本格式：單精度格式、擴展單精度格式、雙精度格式、擴展雙精度格式。 對于規(guī)格化的浮點數(shù)，IEEE754規(guī)定在小數(shù)點的左邊有一隱含位（作為二進制整數(shù)的個位）。由于該位為1，不需要存儲，在運算時，自動加上該位參加運算。IEEE754標準標準 32浮點數(shù) 一個規(guī)格化的32位浮點數(shù)的真值 E是階碼，用移碼表示 M是尾數(shù)，其所表示的值為1.M，且1為隱含值。1272). 1 (1EMsxIEEE754標準標準 IEEE754單精度浮點格式的幾點說明:1.階碼的偏移值是127而不是128(27),是因為尾數(shù)是1.M ，且1為隱含值。2.隨著E和M取不同的值，IEEE754浮點數(shù)表示不同的意義：E=

23、0,M=0:表示機器零。1E254：X=（-1）s *2E-127 *1.M，表示一個規(guī)格化的浮點數(shù)。 E=255,M=0: 表示一個無窮大的數(shù)。 E=255,M0: 表示一個非數(shù)值。IEEE754標準標準一個規(guī)格化的64位浮點數(shù)真值10232). 1 (1EMsx例4（2012年研究生入學試題）問:IEEE754單精度浮點數(shù)所能表示的最大正整數(shù)是多少?答:X=(-1)0(1.111) 2254-127 =(1+1-2-23) 2127 =2128-2104例5 若浮點數(shù)的IEEE754標準存儲格式為(41360000)16，求其32位浮點數(shù)的十進制值。 解解: 將十六進制數(shù)展開后，可得二進制

24、數(shù)格式為 指數(shù)e階碼1271000001001111111 00000011=(3)10包括隱藏位1的尾數(shù)1.M 1.011 0110 0000 0000 0000 0000 1.011011于是有(1)s1.M2e (1.011011)23 1011.011 (11.375)10 例6 將十進制數(shù)20.59375轉(zhuǎn)換成IEEE754標準的32位浮點數(shù)的二進制格式。 解解: 首先分別將整數(shù)和分數(shù)部分轉(zhuǎn)換成二進制數(shù)：20.5937510100.10011 然后移動小數(shù)點，使其在第1，2位之間 10100.100111.01001001124 e4于是得到：S0，E4127131，M0100100

25、11最后得到32位浮點數(shù)的二進制存儲格式為：0100 0001 1010 0100 1100 0000 0000 0000(41A4C000)16 例例8 若為定點整數(shù)，采用一位符號位，如果寄存器中的內(nèi)容為10000001，當它分別表示原碼、補碼、反碼、移碼和無符號數(shù)時，問對應的真值為多少？ 解： 原碼的真值為： 補碼的真值為： 反碼的真值為： 移碼的真值為：無符號數(shù)的真值為：-1-127-12611292.4.4 十進制數(shù)的二進制編碼十進制數(shù)的二進制編碼1.有權(quán)BCD碼2.無權(quán)BCD碼十進制數(shù)十進制數(shù)8421碼余3碼00000001110001010020010010130011011040

26、10001115010110006011010017011110108100010119100111002.4.5 多字節(jié)數(shù)據(jù)的排列順序多字節(jié)數(shù)據(jù)的排列順序 現(xiàn)代計算機中都采用字節(jié)編址方式，每個地址編號中存放一個字節(jié)數(shù)據(jù)。由多個字節(jié)組成的數(shù)據(jù)，在程序中每個數(shù)據(jù)只給定一個地址，那么數(shù)據(jù)如何存放？ 有兩種方式：大端方式和小端方式。 假定int 型變量i的地址為08 00H，i的機器數(shù)為12 34 56 78H，則這兩種方式的排列如下：0800H0801H0802H 0803H大端大端12345678小端小端785634122.4.5 多字節(jié)數(shù)據(jù)的排列順序多字節(jié)數(shù)據(jù)的排列順序 IBM360/370、

27、Motorola 68k、MIPS、HP PA等機器都采用大端方式。 Intel 80 x86、DEC VAX等機器都采用小端方式。 有些機器如Alpha和Power PC能夠運行在任何一種方式，但要在加電啟動時選擇。 在排列順序不同的計算機之間進行數(shù)據(jù)通信時，需要進行順序轉(zhuǎn)換。 2.5 校驗碼 為了提高計算機的為了提高計算機的可靠性可靠性，除了采取選用，除了采取選用更高可靠性的器件，更好的生產(chǎn)工藝等措施之更高可靠性的器件，更好的生產(chǎn)工藝等措施之外，還可以從數(shù)據(jù)編碼上想一些辦法，即采用外，還可以從數(shù)據(jù)編碼上想一些辦法，即采用一點冗余的線路，在原有數(shù)據(jù)位之外再一點冗余的線路，在原有數(shù)據(jù)位之外再增

28、加一增加一到幾位校驗位到幾位校驗位，使新得到的碼字帶上某種特性使新得到的碼字帶上某種特性，之后則通過之后則通過檢查該碼字是否仍保持有這一特性檢查該碼字是否仍保持有這一特性，來來發(fā)現(xiàn)發(fā)現(xiàn)是否出現(xiàn)了錯誤，甚至于定位錯誤后，是否出現(xiàn)了錯誤，甚至于定位錯誤后，自動改正自動改正這一錯誤，這就是我們這里說的這一錯誤，這就是我們這里說的檢錯檢錯糾錯編碼技術(shù)糾錯編碼技術(shù)。2.5 校驗碼三種常用的檢錯糾錯碼：三種常用的檢錯糾錯碼：1.奇偶檢錯碼奇偶檢錯碼2.海明檢錯與糾錯碼海明檢錯與糾錯碼3.循環(huán)冗余碼循環(huán)冗余碼(CRC)編碼過程編碼過程譯碼過程譯碼過程傳送傳送原始數(shù)據(jù)原始數(shù)據(jù)碼碼 字字結(jié)果數(shù)據(jù)結(jié)果數(shù)據(jù)形成校驗

29、位的值，形成校驗位的值，加進特征加進特征檢查接送的碼字，檢查接送的碼字，發(fā)現(xiàn)發(fā)現(xiàn) / 改正錯誤改正錯誤2.5.1 校驗碼奇偶校驗碼1.簡單的奇偶校驗碼簡單的奇偶校驗碼原理：在原理：在 數(shù)據(jù)碼之外增加數(shù)據(jù)碼之外增加 1 位校驗位。位校驗位。奇校驗:使整個校驗碼中1的個數(shù)為奇數(shù)。設被校驗的信息為x=x1x2xn-1，校驗位為C.C的邏輯表達式為1321nxxxxc2.5.1 校驗碼奇偶校驗碼1.簡單的奇偶校驗碼簡單的奇偶校驗碼原理：在原理：在 數(shù)據(jù)碼之外增加數(shù)據(jù)碼之外增加 1 位校驗位。位校驗位。偶校驗:使整個校驗碼中1的個數(shù)為偶數(shù)。設被校驗的信息為x=x1x2xn-1，校驗位為C.C的邏輯表達式

30、為1321nxxxxc2.5.1 校驗碼奇偶校驗碼n奇偶校驗碼：用于并行碼奇偶校驗碼：用于并行碼檢錯檢錯原理：在原理：在 k 位數(shù)據(jù)碼之外增加位數(shù)據(jù)碼之外增加 1 位校驗位，位校驗位，使使 K+1 位碼字中取值為位碼字中取值為 1 的位數(shù)的位數(shù)總保持總保持為為 偶數(shù)偶數(shù)（偶校驗偶校驗）或）或 奇數(shù)奇數(shù)（奇校驗奇校驗）。）。例如：例如： 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 原有數(shù)字位原有數(shù)字位 兩個新的碼字兩個新的碼字 偶校驗偶校驗奇校驗奇校驗校驗位校驗位2.5.1 校驗碼奇偶校驗碼+n奇偶校驗碼的實現(xiàn)電路n奇校驗奇校驗

31、 偶校驗偶校驗 出錯指示出錯指示+同左側(cè)電路同左側(cè)電路P (校驗位校驗位)八位數(shù)據(jù)位八位數(shù)據(jù)位D7 D6 D5 D4 D3 D2 D1 D0p譯碼電路編碼電路2.5.1 校驗碼奇偶校驗碼2.交叉奇偶校驗交叉奇偶校驗 簡單的奇偶校驗只能檢測簡單的奇偶校驗只能檢測一位一位的錯誤，的錯誤，人們就又提出了交叉奇偶校驗方法，又稱人們就又提出了交叉奇偶校驗方法，又稱為水平為水平/垂直校驗碼垂直校驗碼. 原理：是對多個數(shù)據(jù)塊同時進行橫向原理：是對多個數(shù)據(jù)塊同時進行橫向和縱向的奇偶校驗和縱向的奇偶校驗.2.5.1 校驗碼奇偶校驗碼交叉奇校驗舉例交叉奇校驗舉例D3 D2 D1 D0 CrW3 10101W2 1

32、1100W1 00100W0 11001Cl010112.5.2 校驗碼海明校驗碼 海明校驗碼：是由Richard Hamming于1950年提出的。這種編碼能糾正一位出錯，并能自動恢復出錯位的校驗碼。 1.校驗碼的位數(shù)： 設要發(fā)送的數(shù)據(jù)為k位，則校驗碼的位數(shù)r,應滿足： kr2log2.5.2 校驗碼海明校驗碼2 2.海明碼的編碼規(guī)則：(1) 校驗位與數(shù)據(jù)位之和為m,每個校驗位Pi在海明碼中被分在位號為 的位置，其余各位為數(shù)據(jù)位,并按 從低位向高位逐位依次排列的關(guān)系分配各數(shù)據(jù)位.(2) 海明碼的每一位碼Hi由多個校驗位校驗，其關(guān)系是被校驗的每一個位位號要等于校驗它的各校驗位的位號之和.(3)

33、在增大合法碼的碼距時，使所有碼的碼距盡量均勻的增大,以保證對所有碼的驗錯能力平衡提高.12i2.5.2 校驗碼海明校驗碼n舉例：k=4, r=3，求相應的海明校驗碼海明校驗碼解：（1）根據(jù)規(guī)則1，Pi應放在1，2，4的位置上。即： 位 號： 1 2 3 4 5 6 7Pi占位 ： P1 P2 D1 P3 D2 D3 D4（2）根據(jù)規(guī)則）根據(jù)規(guī)則2： P1 P2 D1 P3 D2 D3 D4海明碼占位海明碼占位 占用的校驗位號占用的校驗位號 備注備注 1 1 1=1 2 2 2=2 3 1、2 3=1+2 4 4 4=4 5 1、4 5=1+4 6 2、4 6=2+4 7 1、2、4 7=1+2

34、+4 2.5.2 校驗碼海明校驗碼 校驗位只與本身有關(guān)，數(shù)據(jù)位則與多個校驗位有關(guān)。例如：D1由P1和P2校驗，D3由P2和P4校驗等。 P1校驗第1、3、5、7位 P2校驗第2、3、6、7位 P3校驗第4、5、6、7位 當某一位數(shù)據(jù)發(fā)生變化時，必將引起一些Pi的變化。2.5.2 校驗碼海明校驗碼4211DDDP4312DDDP4323DDDP按偶校驗寫出求p1、 p2、 p3的公式：如果設D1 D2 D3 D4=1011，則： p1=0， p2 =1， p3 =02.5.2 校驗碼海明校驗碼3.查錯原理： 42111DDDPG43122DDDPG43233DDDPG由G3G2G1就組成了一個指

35、誤字。當G3G2G1 = 000時，說明沒有出錯；當G3G2G1 = i 時， i就是錯誤的位號。2.5.2 校驗碼海明校驗碼 P1 P2 D1 P3 D2 D3 D4例：若發(fā)送的信息為 0 1 1 0 0 1 1 若接收的信息為 0 1 1 0 1 1 1 111101G011112G111103GG3G2G1 =101， 故第5位有錯誤2.5.2 校驗碼海明校驗碼n4。海明校驗碼的邏輯電路實現(xiàn)和查錯糾錯的。海明校驗碼的邏輯電路實現(xiàn)和查錯糾錯的邏輯電路的實現(xiàn)。邏輯電路的實現(xiàn)。 (請同學們自己畫出請同學們自己畫出k=4、r=3時的海時的海明電路編碼和查錯糾錯電路明電路編碼和查錯糾錯電路)2.5

36、.3 校驗碼循環(huán)冗余碼 循環(huán)冗余校驗碼（循環(huán)冗余校驗碼（CRC）是一種基于模）是一種基于模2運算建立編碼規(guī)則的校驗碼。主要用在磁存運算建立編碼規(guī)則的校驗碼。主要用在磁存儲器和計算機通信方面。儲器和計算機通信方面。2.5.3 校驗碼循環(huán)冗余碼n模2四則運算是以2為模，按位相加的運算，在運算中不考慮借位和進位。 加減法：00=0，01=1，10=1，11=0 乘法：按模2加求部分積之和 除法：按模2 減求部分余數(shù) 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 01 0 0 0 01 0 111 0 10 1 000 0 01 0 011 0 10 1商余數(shù)2.5.3 循環(huán)循環(huán)冗余碼循環(huán)碼的編制原理 設待編碼的有效信息以多項式M(x)表示，用約定的一個多項式G(X)去除，一般情況下能得到一個商Q(X)和余數(shù)R(X) M(x)=Q(x)G(x)+R(x) M(x) -R(x)=Q(x)G(x) 顯然，將M(x)減去余數(shù)R(x)就必定