第6章計(jì)算機(jī)中的數(shù)據(jù)表示方法

1、本章的主要內(nèi)容本章的主要內(nèi)容數(shù)據(jù)表示：定點(diǎn)和浮點(diǎn)數(shù)據(jù)表示格式數(shù)據(jù)表示：定點(diǎn)和浮點(diǎn)數(shù)據(jù)表示格式(含浮點(diǎn)規(guī)格化含浮點(diǎn)規(guī)格化)補(bǔ)碼中模的概念及應(yīng)用、補(bǔ)碼與真值之間的關(guān)系補(bǔ)碼中模的概念及應(yīng)用、補(bǔ)碼與真值之間的關(guān)系校驗(yàn)及其原理、作用、實(shí)現(xiàn)方法校驗(yàn)及其原理、作用、實(shí)現(xiàn)方法數(shù)據(jù)信息的校驗(yàn)數(shù)據(jù)信息的校驗(yàn) 第第6章章 計(jì)算機(jī)中的數(shù)據(jù)表示方法計(jì)算機(jī)中的數(shù)據(jù)表示方法1、數(shù)據(jù)格式、數(shù)據(jù)格式 選擇數(shù)據(jù)格式要考慮的因素：選擇數(shù)據(jù)格式要考慮的因素： 數(shù)的類型數(shù)的類型 數(shù)的范圍數(shù)的范圍 數(shù)的精度數(shù)的精度 存儲(chǔ)和處理的代價(jià)存儲(chǔ)和處理的代價(jià) 是否有利于軟件的移植是否有利于軟件的移植一、數(shù)值數(shù)據(jù)與非數(shù)值數(shù)據(jù)的表示方法一、數(shù)值數(shù)據(jù)與

2、非數(shù)值數(shù)據(jù)的表示方法1)定點(diǎn)數(shù)定點(diǎn)數(shù) 可表示定點(diǎn)小數(shù)和整數(shù)可表示定點(diǎn)小數(shù)和整數(shù) 表現(xiàn)形式：表現(xiàn)形式：X0.X1X2X3X4.Xn定點(diǎn)小數(shù)定點(diǎn)整數(shù)定點(diǎn)小數(shù)的表示數(shù)的范圍：定點(diǎn)小數(shù)的表示數(shù)的范圍：1-2n |x| 2-n定點(diǎn)整數(shù)的表示數(shù)的范圍：定點(diǎn)整數(shù)的表示數(shù)的范圍：2n-1 |x| 12、計(jì)算機(jī)中常用的兩種數(shù)值數(shù)據(jù)格式及其表示范圍、計(jì)算機(jī)中常用的兩種數(shù)值數(shù)據(jù)格式及其表示范圍 浮點(diǎn)數(shù)的使用場(chǎng)合浮點(diǎn)數(shù)的使用場(chǎng)合當(dāng)數(shù)的表示范圍超出了定點(diǎn)數(shù)能表示的范圍時(shí)使用。當(dāng)數(shù)的表示范圍超出了定點(diǎn)數(shù)能表示的范圍時(shí)使用。(1)格式格式(一般格式一般格式) ESE1E2E3EnMSM1M2M3M4.Mk階碼：決定數(shù)據(jù)的范

3、圍階碼：決定數(shù)據(jù)的范圍尾數(shù)：決定數(shù)的精度尾數(shù)：決定數(shù)的精度2)浮點(diǎn)數(shù)：把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。浮點(diǎn)數(shù)：把數(shù)的范圍和精度分別表示的一種數(shù)據(jù)表示方法。N=Rem基基(2)IEEE 754格式格式 S8位偏指數(shù)位偏指數(shù)E23位有效尾數(shù)位有效尾數(shù)M單精度單精度11位偏指數(shù)位偏指數(shù)E52位有效尾數(shù)位有效尾數(shù)MS雙精度雙精度 指數(shù)采用偏移值指數(shù)采用偏移值,其中單精度為其中單精度為127,雙精度為雙精度為1023.這樣非負(fù)浮點(diǎn)數(shù)這樣非負(fù)浮點(diǎn)數(shù)能作為整數(shù)對(duì)待進(jìn)行比較運(yùn)算能作為整數(shù)對(duì)待進(jìn)行比較運(yùn)算,便于浮點(diǎn)數(shù)的比較和排序便于浮點(diǎn)數(shù)的比較和排序. (A) 754尾數(shù)形式為尾數(shù)形式為1.XXXX

4、XX, 其中其中M部分保存的是部分保存的是XXXXXX.這樣這樣可以保留更多的有效數(shù)字位可以保留更多的有效數(shù)字位,進(jìn)一步提高數(shù)據(jù)表示的精確度進(jìn)一步提高數(shù)據(jù)表示的精確度 754的的0特殊處理特殊處理,只要指數(shù)為只要指數(shù)為0,不論尾數(shù)為多少均作為零對(duì)待不論尾數(shù)為多少均作為零對(duì)待(A)計(jì)算機(jī)組成和設(shè)計(jì)計(jì)算機(jī)組成和設(shè)計(jì) 硬件硬件/軟件接口軟件接口 第第2版版 .P211-213.鄭緯民譯鄭緯民譯IEEE754 32位浮點(diǎn)數(shù)與對(duì)應(yīng)真值之間的變換流程位浮點(diǎn)數(shù)與對(duì)應(yīng)真值之間的變換流程例例1：將十進(jìn)制數(shù)：將十進(jìn)制數(shù)20.59375轉(zhuǎn)換成轉(zhuǎn)換成32位位IEEE754格式浮點(diǎn)數(shù)的格式浮點(diǎn)數(shù)的二進(jìn)制格式來存儲(chǔ)二進(jìn)制

5、格式來存儲(chǔ) 。解解:首先分別將整數(shù)和分?jǐn)?shù)部分轉(zhuǎn)換成二進(jìn)制數(shù)：首先分別將整數(shù)和分?jǐn)?shù)部分轉(zhuǎn)換成二進(jìn)制數(shù)：20.59375=10100.10011(0.5+0.25+0.125+0.0625+0.03125) 移動(dòng)小數(shù)點(diǎn)，使其變成移動(dòng)小數(shù)點(diǎn)，使其變成1.M的形式的形式10100.10011=1.01001001124得到：得到：S=0, e = 4，E= 100+01111111 =10000011，M = 010010011最后得到最后得到32位浮點(diǎn)數(shù)的二進(jìn)制存儲(chǔ)格式為：位浮點(diǎn)數(shù)的二進(jìn)制存儲(chǔ)格式為： 0100 0001 1010 0100 1100 0000 0000 0000= (41A4C00

6、0)16例例2： 若某浮點(diǎn)數(shù)若某浮點(diǎn)數(shù)x的二進(jìn)制存儲(chǔ)格式為的二進(jìn)制存儲(chǔ)格式為(41360000)16 ,求與其求與其對(duì)應(yīng)的對(duì)應(yīng)的32位浮點(diǎn)表示的十進(jìn)的值。位浮點(diǎn)表示的十進(jìn)的值。解：解： 將將(41360000)16 = (0 100,0001,0 011,0 110,0 000,0 000,0 000,0 000)2 s=0 e=10000010-01111111=00000011=(3)10 1.M=1.011011 則上述浮點(diǎn)數(shù)對(duì)應(yīng)的真值為則上述浮點(diǎn)數(shù)對(duì)應(yīng)的真值為 X=(-1)0 (1.011011)2 23 =(11.375)10 例例3 假設(shè)由假設(shè)由E、M二個(gè)域組成一個(gè)二個(gè)域組成一個(gè)3

7、2位二進(jìn)制所表示的非位二進(jìn)制所表示的非零規(guī)格化浮點(diǎn)數(shù)零規(guī)格化浮點(diǎn)數(shù)X。若其階碼為。若其階碼為8位，尾數(shù)為位，尾數(shù)為24位。位。 求所求所能表示的規(guī)格化的最大正數(shù)、最小正數(shù)、最大負(fù)數(shù)和最小能表示的規(guī)格化的最大正數(shù)、最小正數(shù)、最大負(fù)數(shù)和最小負(fù)數(shù)分別是多少負(fù)數(shù)分別是多少？解：對(duì)于浮點(diǎn)數(shù)而言，其表示的真值由兩部分構(gòu)成：解：對(duì)于浮點(diǎn)數(shù)而言，其表示的真值由兩部分構(gòu)成： X= 2階碼的值階碼的值 尾數(shù)值尾數(shù)值 (假設(shè)均為補(bǔ)碼表示假設(shè)均為補(bǔ)碼表示) 最大正數(shù)：最大正數(shù)： 階碼正最大階碼正最大&尾數(shù)正最大尾數(shù)正最大 最小正數(shù)：最小正數(shù)： 階碼負(fù)最小階碼負(fù)最小&尾數(shù)正最小尾數(shù)正最小(注意規(guī)格化注意

8、規(guī)格化) 最大負(fù)數(shù)最大負(fù)數(shù): 階碼負(fù)最小階碼負(fù)最小&尾數(shù)負(fù)最大尾數(shù)負(fù)最大(注意規(guī)格化注意規(guī)格化) 最小負(fù)數(shù)最小負(fù)數(shù): 階碼正最大階碼正最大&尾數(shù)負(fù)最小尾數(shù)負(fù)最小 最大正數(shù)：最大正數(shù)： 階碼正最大階碼正最大&尾數(shù)正最大尾數(shù)正最大 ( 01111111 011111111111111111111111)2 =2127 (1-2-23) 最小正數(shù)：最小正數(shù)： 階碼負(fù)最小階碼負(fù)最小&尾數(shù)正最小尾數(shù)正最小(注意規(guī)格化注意規(guī)格化) (10000000 010000000000000000000000)2=2128 21=2129 最大負(fù)數(shù)最大負(fù)數(shù): 階碼負(fù)最小階碼負(fù)最小&a

9、mp;尾數(shù)負(fù)最大尾數(shù)負(fù)最大(注意規(guī)格化注意規(guī)格化) (10000000 110000000000000000000000)2=2128 21= 2129 最小負(fù)數(shù)最小負(fù)數(shù): 階碼正最大階碼正最大&尾數(shù)負(fù)最小尾數(shù)負(fù)最小 (01111111 111111111111111111111111)2= 1 2127= 2127因?yàn)殡A碼為因?yàn)殡A碼為8位，尾數(shù)為位，尾數(shù)為24位，各有一位符號(hào)位位，各有一位符號(hào)位 3、 十進(jìn)制數(shù)的表示方法十進(jìn)制數(shù)的表示方法用二進(jìn)制數(shù)碼表示的十進(jìn)制數(shù)稱為二進(jìn)制編碼的十進(jìn)制數(shù)用二進(jìn)制數(shù)碼表示的十進(jìn)制數(shù)稱為二進(jìn)制編碼的十進(jìn)制數(shù)(BCD碼碼)。1）常見的）常見的BCD碼碼84

10、21碼碼(有權(quán)碼有權(quán)碼)用用4位二進(jìn)制編碼的前位二進(jìn)制編碼的前10個(gè)編碼表示十進(jìn)制數(shù)的個(gè)編碼表示十進(jìn)制數(shù)的10個(gè)數(shù)碼，個(gè)數(shù)碼，10101111為為多余狀態(tài)多余狀態(tài)。4位二進(jìn)制編碼從高到低位的權(quán)分別為位二進(jìn)制編碼從高到低位的權(quán)分別為8、4、2、1。2421碼碼(有權(quán)碼有權(quán)碼)4位二進(jìn)制編碼從高到低位的權(quán)分別為位二進(jìn)制編碼從高到低位的權(quán)分別為2、4、2、1。2421碼選取了碼選取了4位位二進(jìn)制編碼中的前二進(jìn)制編碼中的前5個(gè)和后個(gè)和后5個(gè)，而從個(gè)，而從01011010沒有選用沒有選用(重復(fù)重復(fù))余余3碼碼(無權(quán)碼無權(quán)碼)在在8421編碼的基礎(chǔ)上加編碼的基礎(chǔ)上加0011得到，因此稱為余得到，因此稱為余

11、3碼。如碼。如3的余的余3碼為碼為 0011+0011 = 0110X 1 X 01-X 0 X -14、數(shù)的機(jī)器表、數(shù)的機(jī)器表示示1）真值：符號(hào)用）真值：符號(hào)用“+”、“-”表示的數(shù)據(jù)表示方法。表示的數(shù)據(jù)表示方法。2）機(jī)器數(shù)：符號(hào)用）機(jī)器數(shù)：符號(hào)用0、1表示的數(shù)據(jù)表示的數(shù)據(jù) 表示方法，表示方法，即符號(hào)數(shù)值即符號(hào)數(shù)值化的數(shù)據(jù)表示方法?；臄?shù)據(jù)表示方法。3） 設(shè)定點(diǎn)小數(shù)的形式為設(shè)定點(diǎn)小數(shù)的形式為X0.X1X2X3Xn X原原 = = X 1 X 0 2 -X - 2n 0 X -1X反反X補(bǔ)補(bǔ)=X 1 X 02 + X=2-|X| 0 X 1mod 2例例4 求下列各數(shù)的原碼、補(bǔ)碼和反碼求下列各

12、數(shù)的原碼、補(bǔ)碼和反碼 1) X= 0.1011 X原原= 1.1011 X反反= 1.0100 X補(bǔ)補(bǔ)= 1. 0101 2) X=+0.1011 X原原= X反反= X補(bǔ)補(bǔ)= 0.10110的表示：的表示： +0原原=0.0000 -0原原 =1.0000 +0反反=0.0000 -0反反 =1.1111 +0補(bǔ)補(bǔ)=0.0000=-0補(bǔ)補(bǔ) 原碼：原碼： a)表示簡(jiǎn)單表示簡(jiǎn)單b) 運(yùn)算復(fù)雜：要設(shè)置加法、減法器。（分同號(hào)和異號(hào)）運(yùn)算復(fù)雜：要設(shè)置加法、減法器。（分同號(hào)和異號(hào)） c)0的表示不唯一的表示不唯一 幾種常見機(jī)器數(shù)的特點(diǎn)幾種常見機(jī)器數(shù)的特點(diǎn)反碼：反碼： a)表示相對(duì)原碼復(fù)雜表示相對(duì)原碼復(fù)雜

13、 b)運(yùn)算相對(duì)原碼簡(jiǎn)單：符號(hào)位參加運(yùn)算運(yùn)算相對(duì)原碼簡(jiǎn)單：符號(hào)位參加運(yùn)算, 只需要設(shè)置加法器。只需要設(shè)置加法器。但符號(hào)位的進(jìn)位位需要加到最低位但符號(hào)位的進(jìn)位位需要加到最低位 c) 0的表示不唯一的表示不唯一 補(bǔ)碼：補(bǔ)碼：a)表示相對(duì)復(fù)雜表示相對(duì)復(fù)雜b)運(yùn)算簡(jiǎn)單：運(yùn)算簡(jiǎn)單：只需設(shè)置加法器只需設(shè)置加法器。c)0的表示唯一的表示唯一( 美中不足之處美中不足之處 ) 如如 x反反=0.1101 ， Y反反 = 1.0101 求求 X+YX= 1 0 0 1 0 0 1 1 1 0 1 1 1 0 X補(bǔ)補(bǔ)= 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0基于掃描的求補(bǔ)方法基于掃描的求補(bǔ)方法補(bǔ)碼

14、中模的概念補(bǔ)碼中模的概念 （符號(hào)位的進(jìn)位后所在位的權(quán)值）（符號(hào)位的進(jìn)位后所在位的權(quán)值） X補(bǔ)補(bǔ)= X0.X1X2X3XnX補(bǔ)補(bǔ)=X 1 X 02 + X=2-|X| 0 X 1mod 2X補(bǔ)補(bǔ)=X 2n X 12n+1 + X=2-|X| 0 X 2 n mod 2n+1例例5 整數(shù)整數(shù) 1 用補(bǔ)碼表示，下列哪些用補(bǔ)碼表示，下列哪些(個(gè)個(gè))結(jié)果是正確的？結(jié)果是正確的？ 1) 11 2)111 3)1111 4) 11111 5)111111若設(shè)整數(shù)的補(bǔ)碼形式為若設(shè)整數(shù)的補(bǔ)碼形式為X0X1X2X3X4X5,則則-1的補(bǔ)碼又如何的補(bǔ)碼又如何表示？表示？ 其模是多少？其模是多少？解：依題意知：解：依

15、題意知： 一個(gè)整數(shù)連同符號(hào)位在內(nèi)共有一個(gè)整數(shù)連同符號(hào)位在內(nèi)共有6位位 ， 則則-1補(bǔ)補(bǔ)= 1 11111 根據(jù)補(bǔ)碼的定義，其模為根據(jù)補(bǔ)碼的定義，其模為26 移碼一般用來表示浮點(diǎn)數(shù)的階碼，只有整數(shù)，如移碼一般用來表示浮點(diǎn)數(shù)的階碼，只有整數(shù)，如IEEE754中的階碼就是采用的移碼中的階碼就是采用的移碼。 設(shè)定點(diǎn)整數(shù)的移碼形式為設(shè)定點(diǎn)整數(shù)的移碼形式為X0X1X2X3Xn 則移碼的定義是：則移碼的定義是： X移移= 2n + X 2n X - 2n 具體實(shí)現(xiàn)：具體實(shí)現(xiàn)： 數(shù)值位與數(shù)值位與X的補(bǔ)碼相同，符號(hào)位與補(bǔ)碼相反。的補(bǔ)碼相同，符號(hào)位與補(bǔ)碼相反。 例例6： X=+10101 X補(bǔ)補(bǔ)=010101 X

16、移移=110101 X=10101 X補(bǔ)補(bǔ)=101011 X移移=0010115. 移碼移碼(增碼增碼)表示表示 例例7 將十進(jìn)制值將十進(jìn)制值X(-127，-1，0，1，127)用四種機(jī)器數(shù)表示用四種機(jī)器數(shù)表示x真值真值(二進(jìn)制二進(jìn)制)X原原X反反X補(bǔ)補(bǔ)X移移-127-0111111111111111100000001000000100000001-1-00000001100000011111111011111111011111110 000000001000000010000000000000001000000000000000011111111 0000000100000001000000

17、010000000110000001127 0111111101111111011111110111111111111111-128補(bǔ)補(bǔ) = 1 0000000-128移移 = 0 0000000 1)漢字的輸入碼漢字的輸入碼：解決漢字輸入計(jì)算機(jī)的問題：解決漢字輸入計(jì)算機(jī)的問題 數(shù)字編碼：國(guó)際區(qū)位碼，由區(qū)和位兩部分?jǐn)?shù)字構(gòu)數(shù)字編碼：國(guó)際區(qū)位碼，由區(qū)和位兩部分?jǐn)?shù)字構(gòu) 成，如成，如5448為中。無重碼為中。無重碼 拼音碼：拼音碼： 以漢語(yǔ)拼音來輸入漢字，重碼率高。以漢語(yǔ)拼音來輸入漢字，重碼率高。 字型碼：字型碼： 用漢字的形狀編碼。如五筆字型。用漢字的形狀編碼。如五筆字型。2)漢字的內(nèi)碼漢字的內(nèi)碼：

18、用于漢字的存儲(chǔ)、交換、檢索等操：用于漢字的存儲(chǔ)、交換、檢索等操 作的機(jī)內(nèi)代碼。一般用兩個(gè)字節(jié)表作的機(jī)內(nèi)代碼。一般用兩個(gè)字節(jié)表 示且每個(gè)字節(jié)的最高位為示且每個(gè)字節(jié)的最高位為1。6、漢字的表示方法、漢字的表示方法常用的有常用的有 16 16點(diǎn)陣點(diǎn)陣 保存一個(gè)漢字需保存一個(gè)漢字需 16 16/8=32B 24 24點(diǎn)陣點(diǎn)陣 保存一個(gè)漢字需保存一個(gè)漢字需 24 24/8=72B 32 32點(diǎn)陣點(diǎn)陣 保存一個(gè)漢字需保存一個(gè)漢字需 32 32/8=128B點(diǎn)陣數(shù)越大，保存時(shí)所需要的存儲(chǔ)器容量也越大，輸出的點(diǎn)陣數(shù)越大，保存時(shí)所需要的存儲(chǔ)器容量也越大，輸出的字型的質(zhì)量越高，字型的質(zhì)量越高，*明確漢字的輸入碼、

19、機(jī)內(nèi)碼、字模碼的作用明確漢字的輸入碼、機(jī)內(nèi)碼、字模碼的作用3)漢字的字模碼漢字的字模碼：用點(diǎn)陣表示漢字輸出的字型代碼。：用點(diǎn)陣表示漢字輸出的字型代碼。 2) 2)檢驗(yàn)碼的工作原理檢驗(yàn)碼的工作原理 7、數(shù)據(jù)校驗(yàn)、數(shù)據(jù)校驗(yàn)1)問題的提出：?jiǎn)栴}的提出： 檢測(cè)傳輸、處理和存儲(chǔ)中的錯(cuò)誤。檢測(cè)傳輸、處理和存儲(chǔ)中的錯(cuò)誤。檢檢 測(cè)測(cè) 器器編碼器編碼器 x x1 1 x x2 2 x x3 3 x x4 4 1 11 11 11 11 11 10 00 00 00 01 1F FP P發(fā)送端發(fā)送端 接收端接收端 處處理理/傳傳輸輸 3) 3)帶校驗(yàn)信息的數(shù)據(jù)形式帶校驗(yàn)信息的數(shù)據(jù)形式 沒有付出，就不會(huì)有收獲沒有付

20、出，就不會(huì)有收獲 4) 4)碼距的概念碼距的概念 將一組編碼中任何兩個(gè)編碼之間代碼不同的將一組編碼中任何兩個(gè)編碼之間代碼不同的最小最小位數(shù)稱為這位數(shù)稱為這兩個(gè)編碼距離，簡(jiǎn)稱碼距或海明距離兩個(gè)編碼距離，簡(jiǎn)稱碼距或海明距離 . 四位二進(jìn)制編碼四位二進(jìn)制編碼0011與與0001 的碼距為的碼距為1; 而而0011與與0000兩組兩組編碼的距離為編碼的距離為2。 若用四位二進(jìn)制編碼只表示若用四位二進(jìn)制編碼只表示0000、0011、0101、0110、1001、1010、1100、1111等八種編碼等八種編碼,則碼距為則碼距為2。此時(shí)，這。此時(shí)，這8種編碼種編碼中的任何一位發(fā)生改變，如中的任何一位發(fā)生改

21、變，如0000變成變成1000就從有效編碼變成就從有效編碼變成了無效編碼，容易檢測(cè)到這種錯(cuò)誤。了無效編碼，容易檢測(cè)到這種錯(cuò)誤。 如果用四位二進(jìn)制編十六種狀態(tài)，情況又如何？如果用四位二進(jìn)制編十六種狀態(tài)，情況又如何？ 數(shù)據(jù)校驗(yàn)可數(shù)據(jù)校驗(yàn)可在正常編碼的基礎(chǔ)上，通過增加一些附加的校驗(yàn)位得在正常編碼的基礎(chǔ)上，通過增加一些附加的校驗(yàn)位得到。增加校驗(yàn)的同時(shí)也增加了碼距，當(dāng)碼距增加到一定程度時(shí)，到。增加校驗(yàn)的同時(shí)也增加了碼距，當(dāng)碼距增加到一定程度時(shí)，校驗(yàn)碼不僅具有檢錯(cuò)功能，而且還可具有糾正錯(cuò)誤的能力。校驗(yàn)碼不僅具有檢錯(cuò)功能，而且還可具有糾正錯(cuò)誤的能力。 5) 5)碼距與數(shù)據(jù)校驗(yàn)之間的關(guān)系碼距與數(shù)據(jù)校驗(yàn)之間的關(guān)

22、系 碼距碼距d與校驗(yàn)碼的與校驗(yàn)碼的檢錯(cuò)檢錯(cuò)和和糾錯(cuò)糾錯(cuò)能力的關(guān)系如下：能力的關(guān)系如下：(1)d e+1 :可檢測(cè)可檢測(cè)e個(gè)錯(cuò)誤。個(gè)錯(cuò)誤。(2)d 2t+1 :可糾正可糾正t個(gè)錯(cuò)誤。個(gè)錯(cuò)誤。(3)d e+t+1 :可檢測(cè)可檢測(cè)e個(gè)錯(cuò)誤并糾正個(gè)錯(cuò)誤并糾正t個(gè)錯(cuò)誤個(gè)錯(cuò)誤(e t) 。如如 X=1001101 ，則，則C=1 被傳送的數(shù)據(jù)為：被傳送的數(shù)據(jù)為：10011011 接收方對(duì)接收到的數(shù)字序列進(jìn)行下列運(yùn)算接收方對(duì)接收到的數(shù)字序列進(jìn)行下列運(yùn)算 F= X0 X1 X2 X n-1 C 若若F=1則正確、則正確、 反之則錯(cuò)。反之則錯(cuò)。 即當(dāng)收到的數(shù)字為即當(dāng)收到的數(shù)字為10011011時(shí)時(shí) F=1 當(dāng)收

23、到的數(shù)字為當(dāng)收到的數(shù)字為11011011時(shí)時(shí) F=0 ，出錯(cuò)，要求重發(fā)，出錯(cuò)，要求重發(fā) 1)奇校驗(yàn)奇校驗(yàn)C= X0 X1 X2 X n-1 。 發(fā)送方，通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù)中發(fā)送方，通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù)中(含一位校驗(yàn)含一位校驗(yàn)位位)1的個(gè)數(shù)的個(gè)數(shù) 為奇數(shù)。設(shè)校驗(yàn)位為為奇數(shù)。設(shè)校驗(yàn)位為C，則：，則：8、奇、奇/偶校驗(yàn)偶校驗(yàn) 發(fā)送方發(fā)送方通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù)通過設(shè)置校驗(yàn)位的值，使待傳數(shù)據(jù) 中中(含一位校驗(yàn)位含一位校驗(yàn)位)1的個(gè)數(shù)的個(gè)數(shù) 為偶數(shù)。設(shè)校驗(yàn)位為為偶數(shù)。設(shè)校驗(yàn)位為C，則，則 C= X0 X1 X2 X n-1 如如 X=1001101 則則C=0 被傳送的數(shù)據(jù)

24、為：被傳送的數(shù)據(jù)為：10011010 接收方對(duì)接收到的數(shù)字序列進(jìn)行下列運(yùn)算接收方對(duì)接收到的數(shù)字序列進(jìn)行下列運(yùn)算 F= X0 X1 X2 X n-1 C 若若F=0則正確、則正確、 反之則錯(cuò)。反之則錯(cuò)。 即當(dāng)收到的數(shù)字為即當(dāng)收到的數(shù)字為10011010時(shí)時(shí) F=0 當(dāng)收到的數(shù)字為當(dāng)收到的數(shù)字為11011011時(shí)時(shí) F=1，錯(cuò)，要求重發(fā)，錯(cuò)，要求重發(fā)2)偶校驗(yàn)偶校驗(yàn)簡(jiǎn)單簡(jiǎn)單 碼距為碼距為2(?),不能檢測(cè)出同時(shí)出現(xiàn)偶數(shù)個(gè)位錯(cuò)誤的錯(cuò)誤！不能檢測(cè)出同時(shí)出現(xiàn)偶數(shù)個(gè)位錯(cuò)誤的錯(cuò)誤！如上例中如上例中 偶校驗(yàn)時(shí)發(fā)送偶校驗(yàn)時(shí)發(fā)送10011010 ，當(dāng)接收為當(dāng)接收為10010000時(shí)仍然不能檢測(cè)出傳輸錯(cuò)誤！時(shí)仍然不

25、能檢測(cè)出傳輸錯(cuò)誤！3)奇偶校驗(yàn)的特點(diǎn)奇偶校驗(yàn)的特點(diǎn)4)奇偶校驗(yàn)的應(yīng)用場(chǎng)合分析奇偶校驗(yàn)的應(yīng)用場(chǎng)合分析 本身穩(wěn)定性不高，本身穩(wěn)定性不高， 近距離近距離 RAID5)交叉奇交叉奇/偶校驗(yàn)偶校驗(yàn)9、海明校驗(yàn)、海明校驗(yàn)(Richard Hamming（理查德（理查德海明海明）1950年提出年提出)1) 奇偶校驗(yàn)的不足奇偶校驗(yàn)的不足: 只能檢測(cè)奇數(shù)個(gè)位錯(cuò)誤只能檢測(cè)奇數(shù)個(gè)位錯(cuò)誤,且不能糾錯(cuò)，且不能糾錯(cuò)， 檢測(cè)得出的無錯(cuò)誤結(jié)果不一定可信。檢測(cè)得出的無錯(cuò)誤結(jié)果不一定可信。2) 海明校驗(yàn)海明校驗(yàn): 具有檢測(cè)和糾正錯(cuò)誤的一種編碼具有檢測(cè)和糾正錯(cuò)誤的一種編碼 ( 多重奇偶校驗(yàn)多重奇偶校驗(yàn)) 基本思想基本思想: 將待傳

26、送的信息將待傳送的信息 , 按照某種規(guī)律分成若干組按照某種規(guī)律分成若干組, 每每組安排一個(gè)校驗(yàn)位組安排一個(gè)校驗(yàn)位 , 用于奇偶測(cè)試用于奇偶測(cè)試, 這樣就提供了多位檢這樣就提供了多位檢錯(cuò)信息錯(cuò)信息, 以指出最大可能是哪一位出錯(cuò)以指出最大可能是哪一位出錯(cuò), 從而糾正從而糾正. 3)具有指出并糾正一位錯(cuò)誤的海明校驗(yàn)需要的位數(shù)具有指出并糾正一位錯(cuò)誤的海明校驗(yàn)需要的位數(shù)設(shè)有設(shè)有r r位校驗(yàn)位，共能表示位校驗(yàn)位，共能表示2 2r r種不同的狀態(tài)，用一種狀態(tài)表種不同的狀態(tài)，用一種狀態(tài)表示無差錯(cuò)，剩余的可以表示示無差錯(cuò)，剩余的可以表示2 2r r -1 -1種錯(cuò)誤，由于差錯(cuò)可能出種錯(cuò)誤，由于差錯(cuò)可能出現(xiàn)在數(shù)據(jù)

27、位和校驗(yàn)位，因此必須滿足：現(xiàn)在數(shù)據(jù)位和校驗(yàn)位，因此必須滿足： 2 2r r - 1 = k + r - 1 = k + r (k (k數(shù)據(jù)位的位數(shù)數(shù)據(jù)位的位數(shù) r r校驗(yàn)位的位數(shù)校驗(yàn)位的位數(shù) ) )校驗(yàn)位在海明碼中的分布規(guī)則：校驗(yàn)位在海明碼中的分布規(guī)則： k+r位海明碼中，校驗(yàn)位位海明碼中，校驗(yàn)位Pi分布在海明碼分布在海明碼的的H H2 2i i-1-1 位上位上,i=1.r,i=1.r4)海明碼的形成方法海明碼的形成方法海明碼位號(hào)海明碼位號(hào) Hj1 2 3 4 5 6 7 8 9 10 11 P和和b的分布的分布P1 P2 b1 P3 b2 b3 b4 P4 b5 b6 b7 a)分組原則：

28、分組原則：確定海明碼每位數(shù)據(jù)位所用的校驗(yàn)位確定海明碼每位數(shù)據(jù)位所用的校驗(yàn)位Hi1234567891011Pi121,241,42,41,2,481,82,81,2,8根據(jù)每個(gè)校驗(yàn)位校驗(yàn)的位分組：根據(jù)每個(gè)校驗(yàn)位校驗(yàn)的位分組：P1: 3,5,7,9,11 P2: 3,6,7,10,11P3: 5,6,7 P4: 9,10,11b)校驗(yàn)位的取值校驗(yàn)位的取值(偶校驗(yàn)為例偶校驗(yàn)為例)-Hi1234567891011Pi121,2/b141,4/b22,4/b31,2,4/b481,8/b52,8/b61,2,8/b7P1=b1 b2 b4 b5 b7 P2=b1 b3 b4 b6 b7P3=b2 b3

29、b4 P4=b5 b6 b7 假設(shè)假設(shè)b1b2b3b4b5b6b7 = 1011000 則：則：P1= 1 0 1 0 0 = 0 P2 = 1 1 1 0 0=1 P3=0 1 1 = 0 P4=0 0 0 = 0則則H = 0 1 1 0 0 1 1 0 0 0 0c)指錯(cuò)、糾錯(cuò)原理指錯(cuò)、糾錯(cuò)原理 指錯(cuò)字指錯(cuò)字P1= b1 b2 b4 b5 b7 P2= b1 b3 b4 b6 b7P3=b2 b3 b4 P4=b5 b6 b7 則指錯(cuò)字由則指錯(cuò)字由G4G3G2G1組成，其中：組成，其中：G4= P4 b5 b6 b7 G3 = P3 b2 b3 b4 G2= P2 b1 b3 b4 b6

30、 b7G1= P1 b1 b2 b4 b5 b7 上例中上例中 發(fā)送方發(fā)送方H = 0 1 1 0 0 1 1 0 0 0 0如果接收到如果接收到 H = 0 1 1 0 0 1 1 0 0 0 1G4 = 0 0 0 1 = 1 G3 = 0 0 1 1 = 0G2 = 1 1 1 1 0 1 = 1 G1 = 0 1 0 1 0 1 = 1G4G3G2G1= 1011表明表明H11出錯(cuò)，改正該位的錯(cuò)誤即可。出錯(cuò)，改正該位的錯(cuò)誤即可。則錯(cuò)誤字為：則錯(cuò)誤字為：5)海明校驗(yàn)的缺點(diǎn)海明校驗(yàn)的缺點(diǎn) 計(jì)算復(fù)雜計(jì)算復(fù)雜6)關(guān)于擴(kuò)展的海明校驗(yàn)編碼，請(qǐng)查閱相關(guān)資料。關(guān)于擴(kuò)展的海明校驗(yàn)編碼，請(qǐng)查閱相關(guān)資料。1

31、)CRC 是一種基于模是一種基于模2運(yùn)算建立編碼規(guī)則的校驗(yàn)碼運(yùn)算建立編碼規(guī)則的校驗(yàn)碼 ;2)模模2運(yùn)算規(guī)則運(yùn)算規(guī)則:a)加加/減運(yùn)算減運(yùn)算 (異或運(yùn)算，或不帶進(jìn)位的加法，不帶借位的減法異或運(yùn)算，或不帶進(jìn)位的加法，不帶借位的減法) 000，011，101，110b)乘法運(yùn)算：按模乘法運(yùn)算：按模2加求部分積之和加求部分積之和 ，不進(jìn)位，不進(jìn)位c)模模2除法除法 按模按模2減求部分余數(shù)，不借位。減求部分余數(shù)，不借位。 上商原則是：上商原則是：(1)部分余數(shù)首位為部分余數(shù)首位為1時(shí)，商為時(shí)，商為1，減除數(shù)；，減除數(shù)；(2)部分余數(shù)首位為部分余數(shù)首位為0時(shí)，商為時(shí)，商為0，減，減0；(3)當(dāng)部分余數(shù)的位

32、數(shù)小于除數(shù)的位數(shù)時(shí)，該余數(shù)為最后余數(shù)。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時(shí)，該余數(shù)為最后余數(shù)。10、循環(huán)冗余校驗(yàn)、循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check)(1)部分余數(shù)首位為部分余數(shù)首位為1時(shí)，商為時(shí)，商為1，減除數(shù)；，減除數(shù)；(2)部分余數(shù)首位為部分余數(shù)首位為0時(shí)，商為時(shí)，商為0，減，減0；(3)當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時(shí)，該余數(shù)為最后余數(shù)。當(dāng)部分余數(shù)的位數(shù)小于除數(shù)的位數(shù)時(shí)，該余數(shù)為最后余數(shù)。3) CRC編碼方法編碼方法(1)選擇合適的生成多項(xiàng)式選擇合適的生成多項(xiàng)式G(x),其最高位的權(quán)值其最高位的權(quán)值r log2k,其中其中K為被校驗(yàn)信息的位數(shù)；為被校驗(yàn)信息的位數(shù)； 如如K=4位時(shí)，位時(shí)，r=3.(2)將待校驗(yàn)的二進(jìn)制信息將待校驗(yàn)的二進(jìn)制信息Q(X)邏輯左移邏輯左移r位位,得到得到Q(X)(3)用用Q(X) 按模按模2運(yùn)算法則除運(yùn)算法則除G(x)，將得到的，將得到的r位余數(shù)替換位余數(shù)替換Q(X)最后的最后的r位，就得到位，就得到Q(X)的的CRC。解：解： M(x)1100， r3M(x)