第三章1_信息編碼與數(shù)據(jù)表示

1、2ALUALU功能和設(shè)計功能和設(shè)計v功能功能- -加工數(shù)據(jù)加工數(shù)據(jù) 對操作數(shù)對操作數(shù)A A、B B完成算術(shù)運算和邏完成算術(shù)運算和邏輯運算輯運算v設(shè)計設(shè)計 算術(shù)運算算術(shù)運算 加法器加法器 邏輯運算邏輯運算 與門與門(ADD)(ADD)、或門、或門(OR)(OR)、非門、非門(NOT)(NOT)323232operationresultabALU34本章節(jié)內(nèi)容本章節(jié)內(nèi)容vALUALU數(shù)據(jù)運算功能數(shù)據(jù)運算功能l計算機(jī)中的數(shù)據(jù)類型計算機(jī)中的數(shù)據(jù)類型l在計算機(jī)中的表示在計算機(jī)中的表示l存儲方式存儲方式l完成運算所需算法完成運算所需算法l實現(xiàn)算法的電路實現(xiàn)算法的電路 二進(jìn)制編碼二進(jìn)制編碼數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換定

2、點小數(shù)和整數(shù)的原定點小數(shù)和整數(shù)的原、補(bǔ)、反碼、補(bǔ)、反碼檢錯糾錯碼檢錯糾錯碼定點小數(shù)、整數(shù)、浮定點小數(shù)、整數(shù)、浮點數(shù)在計算機(jī)內(nèi)的表點數(shù)在計算機(jī)內(nèi)的表示示補(bǔ)碼加減法運算補(bǔ)碼加減法運算原碼一位乘除法算法原碼一位乘除法算法和完成算法所運用到和完成算法所運用到的邏輯線路的邏輯線路5數(shù)據(jù)編碼與表示數(shù)據(jù)編碼與表示v計算機(jī)要處理的信息：計算機(jī)要處理的信息：數(shù)值、文字、符號、語音、圖形、圖像和視數(shù)值、文字、符號、語音、圖形、圖像和視頻等頻等用數(shù)字化形式保存、加工和傳送用數(shù)字化形式保存、加工和傳送編碼編碼( (用少量、簡單的基本符號，利用一定的用少量、簡單的基本符號，利用一定的組合規(guī)則，表示大量復(fù)雜多樣的信息組合

3、規(guī)則，表示大量復(fù)雜多樣的信息) )6數(shù)據(jù)編碼與表示數(shù)據(jù)編碼與表示v計算機(jī)中要存儲的數(shù)據(jù)計算機(jī)中要存儲的數(shù)據(jù) 程序、整數(shù)、浮點數(shù)、字符（串）、邏輯值程序、整數(shù)、浮點數(shù)、字符（串）、邏輯值 需要編碼進(jìn)行表示需要編碼進(jìn)行表示v存儲方式存儲方式 用數(shù)字電路的兩個狀態(tài)表示用數(shù)字電路的兩個狀態(tài)表示 由上一層的抽象計算機(jī)來識別不同的內(nèi)容由上一層的抽象計算機(jī)來識別不同的內(nèi)容v編碼原則編碼原則 少量簡單的基本符號少量簡單的基本符號 一定的規(guī)則一定的規(guī)則 表示大量復(fù)雜的信息表示大量復(fù)雜的信息7基二碼（二進(jìn)制碼）只使用兩個基本符號：符號個數(shù)最少，物理上容易實現(xiàn)與二值邏輯的 真假 兩個值對應(yīng)簡單用二進(jìn)制碼表示數(shù)值數(shù)據(jù)

4、運算規(guī)則簡單8數(shù)據(jù)表示v二進(jìn)制位可以表示任何對象二進(jìn)制位可以表示任何對象: :v字符 大/小寫 + 其它符號 = 7 bits (in 8) 世界上其他語言 = 16 bits (unicode)v無符號整數(shù) (0, 1, , 2n-1)v邏輯值 0 - False, 1 = Truev顏色(圖片是由很多像素點構(gòu)成，電腦里存的都是這些像素點的顏色代碼 )v位置 / 地址 / 指令通常來說有三類：邏輯類型數(shù)據(jù)+字符類型數(shù)據(jù)+數(shù)值類型數(shù)據(jù)9邏輯型數(shù)據(jù)表示 邏輯型數(shù)據(jù)只有兩個值：真 和 假，正好可以用二進(jìn)制碼的兩個符號分別表示，例如 1 表示 真 則 0 表示 假不必使用另外的編碼規(guī)則。 對邏輯型數(shù)

5、據(jù)可以執(zhí)行邏輯的 與 或 非等基本邏輯運算。其規(guī)則如下：10邏輯型數(shù)據(jù)基本運算規(guī)則 X X Y Y X X與與Y XY X或或Y XY X的的非非 0 0 0 0 0 0 0 0 1 10 0 1 10 1 0 1 1 11 01 00 1 0 1 0 01 11 11 1 1 1 0 011字符型數(shù)據(jù)的表示v 字符的表示：采用字符編碼，即用規(guī)定的二進(jìn)制數(shù)字符的表示：采用字符編碼，即用規(guī)定的二進(jìn)制數(shù)表示文字和符號的方法。表示文字和符號的方法。 v ASCIIASCII碼：碼：美國標(biāo)準(zhǔn)信息交換碼，為國際標(biāo)準(zhǔn)，在全美國標(biāo)準(zhǔn)信息交換碼，為國際標(biāo)準(zhǔn)，在全世界通用世界通用 。v 常用的常用的7 7位位A

6、SCIIASCII碼碼的每個字符都由的每個字符都由7 7個二進(jìn)制位個二進(jìn)制位b6b6b0 b0 表示，有表示，有128128個編碼，最高一位為個編碼，最高一位為0 0，占用一個字，占用一個字節(jié)的空間。最多可表示節(jié)的空間。最多可表示128128種字符；其中包括：種字符；其中包括： 1010個數(shù)字個數(shù)字0099：30H30H39H39H，順序排列，順序排列 2626個小寫字母個小寫字母aazz：61H61H7AH 7AH ，順序排，順序排列列 2626個大寫字母個大寫字母AAZZ：41H41H5AH 5AH ，順序排，順序排列列 各種運算符號和標(biāo)點符號等。各種運算符號和標(biāo)點符號等。 12ASCII

7、ASCII碼編碼表碼編碼表00000000100101001001101110010010110111011011111100000000NULNULDLEDLESPSP0 0 P Pp p00010001SOHSOHDC1DC1！1 1A AQ Qa aq q00100010STXSTXDC2DC2“2 2B BR Rb br r00110011ETXETXDC3DC3# #3 3C CS Sc cs s01000100EOTEOTDC4DC4￥4 4D DT Td dt t01010101ENQENQNAKNAK% %5 5E EU Ue eu u01100110ACKACKSYNSYN&

8、amp; &6 6F FV Vf fv v01110111BELBELETBETB7 7G GW Wg gw w10001000BSBSCANCAN（8 8H HX Xh hx x10011001HTHTEMEM）9 9I IY Yi iy y10101010LFLFSUBSUB* *：J JZ Zj jz z10111011VTVTESCESC+ +；K K k k 11001100FFFFFSFS，L L、l l| |11011101CRCRGSGS- -= =M M m m 11101110SOSORSRS. .N N n n 11111111SISIUSUS/ /? ?O O_

9、 _o oDELDEL13字符串的表示與存儲v 字符串是指連續(xù)的一串字符，它們占據(jù)主存中連續(xù)的多個字節(jié)，每個字節(jié)存放一個字符，對一個主存字的多個字節(jié)，有按從低位到高位字節(jié)次序存放的，也有按從高位到低位字節(jié)次序存放的。表示字符串?dāng)?shù)據(jù)要給出串存放的主存起始地址和串的長度。例如：IF AB THEN READ(C)就可以有如下不同的存放方式：14漢字編碼漢字編碼v漢字內(nèi)碼是用于漢字信息的存儲、交換、檢漢字內(nèi)碼是用于漢字信息的存儲、交換、檢索等操作的機(jī)內(nèi)代碼索等操作的機(jī)內(nèi)代碼，一般采用，一般采用兩個字節(jié)兩個字節(jié)表表示。示。v漢字可以通過不同的輸入法輸入，但其內(nèi)碼漢字可以通過不同的輸入法輸入，但其內(nèi)碼在

10、計算機(jī)中是唯一的。在計算機(jī)中是唯一的。v英文字符的機(jī)內(nèi)代碼是七位的英文字符的機(jī)內(nèi)代碼是七位的ASCIIASCII碼，當(dāng)用碼，當(dāng)用一個字節(jié)表示時，最高位為一個字節(jié)表示時，最高位為“0”0”。為了與英。為了與英文字符能相互區(qū)別，文字符能相互區(qū)別，漢字機(jī)內(nèi)代碼中兩個字漢字機(jī)內(nèi)代碼中兩個字節(jié)的最高位均規(guī)定為節(jié)的最高位均規(guī)定為“1 1”。v機(jī)內(nèi)碼等于漢字國標(biāo)碼加上機(jī)內(nèi)碼等于漢字國標(biāo)碼加上8080H8080H。例如。例如“中中”字的機(jī)內(nèi)碼為字的機(jī)內(nèi)碼為D6D0HD6D0H。 15數(shù)值數(shù)據(jù)的表示數(shù)值數(shù)據(jù)的表示v概念：表示數(shù)量大小，數(shù)值大小的數(shù)據(jù)。概念：表示數(shù)量大小，數(shù)值大小的數(shù)據(jù)。v二進(jìn)制二進(jìn)制表示整數(shù)、純

11、小數(shù)、浮點數(shù)表示整數(shù)、純小數(shù)、浮點數(shù)( (實數(shù)實數(shù)) )v怎么來表示這些數(shù)呢？用原碼、反碼和補(bǔ)碼怎么來表示這些數(shù)呢？用原碼、反碼和補(bǔ)碼等來統(tǒng)一表示這些正負(fù)數(shù)和等來統(tǒng)一表示這些正負(fù)數(shù)和0.0.v數(shù)值數(shù)據(jù)數(shù)值數(shù)據(jù)- -數(shù)值范圍和數(shù)值精度數(shù)值范圍和數(shù)值精度v掌握：掌握：定點小數(shù)、定點整數(shù)和浮點數(shù)定點小數(shù)、定點整數(shù)和浮點數(shù)用用4 4位二進(jìn)制數(shù)表示一個十進(jìn)制數(shù)位二進(jìn)制數(shù)表示一個十進(jìn)制數(shù)16數(shù)值數(shù)據(jù)的表示數(shù)值數(shù)據(jù)的表示 進(jìn)位計數(shù)制進(jìn)位計數(shù)制一一 不同數(shù)制之間的相互轉(zhuǎn)換不同數(shù)制之間的相互轉(zhuǎn)換二二 十進(jìn)制數(shù)的編碼十進(jìn)制數(shù)的編碼三三17一、進(jìn)位計數(shù)制一、進(jìn)位計數(shù)制v 數(shù)制的兩大要素： 基數(shù)R：指在這種進(jìn)位制中允

12、許使用的基本數(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。v 假設(shè)任意數(shù)值N用R進(jìn)制數(shù)來表示，形式為： N=（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之間。18一、進(jìn)位計數(shù)制一、進(jìn)位計數(shù)制v 則數(shù)值N的實際值為： 1)(mkiiiRDNv 例如：例如：R R1010，即十進(jìn)制數(shù)。它的每一位上的數(shù)碼，即十進(jìn)制數(shù)。它的每一位上的數(shù)碼D Di i只能取只能取0 0，1

13、 1，2 2，9 9；各個數(shù)碼的；各個數(shù)碼的權(quán)為權(quán)為1010i i，i i指指示數(shù)碼所處的位置，個位示數(shù)碼所處的位置，個位i i0 0，十位，十位i i1 1，百位，百位i i2 2，依此類推。，依此類推。v 思考：二進(jìn)制、八進(jìn)制、十六進(jìn)制？思考：二進(jìn)制、八進(jìn)制、十六進(jìn)制？19一、進(jìn)位計數(shù)制一、進(jìn)位計數(shù)制v 例1：（2345.459）102103 3102 41015100 410-1 510-2 910-3v 例2：（11011.011）2124 123 022121 12-0 02-1 12-2 12-3=（27.375）10v 例3：（123.67）8182 281 38068-1 78

14、-2=（83.859375）1020二、不同數(shù)制之間的相互轉(zhuǎn)換二、不同數(shù)制之間的相互轉(zhuǎn)換 常用的幾種數(shù)制的對應(yīng)關(guān)系常用的幾種數(shù)制的對應(yīng)關(guān)系1 1 二、八、十六進(jìn)制轉(zhuǎn)換為十進(jìn)制二、八、十六進(jìn)制轉(zhuǎn)換為十進(jìn)制2 2 十進(jìn)制轉(zhuǎn)換為二、八、十六進(jìn)制十進(jìn)制轉(zhuǎn)換為二、八、十六進(jìn)制3 321（1 1）常用的幾種數(shù)制的對應(yīng)關(guān)系）常用的幾種數(shù)制的對應(yīng)關(guān)系十進(jìn)制十進(jìn)制 二進(jìn)制二進(jìn)制八進(jìn)制八進(jìn)制十六十六進(jìn)制進(jìn)制十進(jìn)制十進(jìn)制 二進(jìn)制二進(jìn)制八進(jìn)制八進(jìn)制十六十六進(jìn)制進(jìn)制0 0000000000 00 08 81000100010108 81 1000100011 11 19 91001100111119 92 200100

15、0102 22 21010101010101212A A3 3001100113 33 31111101110111313B B4 4010001004 44 41212110011001414C C5 5010101015 55 51313110111011515D D6 6011001106 66 61414111011101616E E7 7011101117 77 71515111111111717F F161610000100002020101022（2 2）二、八、十六進(jìn)制轉(zhuǎn)換為十進(jìn)制）二、八、十六進(jìn)制轉(zhuǎn)換為十進(jìn)制v 轉(zhuǎn)換方法：轉(zhuǎn)換方法：加權(quán)求和。加權(quán)求和。( (按式按式4 41)

16、1) 例：（例：（5AC.E65AC.E6）1616= 5= 516162 2 101016161 1 121216160 0 141416161 1 6 616162 2 （1452.89843751452.8984375）1010v 十進(jìn)制（十進(jìn)制（DecimalDecimal）、二進(jìn)制（）、二進(jìn)制（BinaryBinary）、八進(jìn)）、八進(jìn)制（制（OctalOctal）、十六進(jìn)制（）、十六進(jìn)制（HexdecimalHexdecimal）數(shù)分別）數(shù)分別用用D D、B B、Q Q、H H來標(biāo)志。來標(biāo)志。v 例如：（例如：（10111011）2 2（10111011）B B1011B1011b1

17、011B1011b （123.45123.45）2 2（ 123.45 123.45 ）D D 123.45D 123.45D 123.45123.45 （2B.D2B.D）1616= =（2B.D2B.D）H H= =（43.812543.8125）1010=(53.64)=(53.64)Q Q23（3 3）十進(jìn)制轉(zhuǎn)換為二、八、十六進(jìn)制）十進(jìn)制轉(zhuǎn)換為二、八、十六進(jìn)制v轉(zhuǎn)換方法轉(zhuǎn)換方法：可以分為以下兩種方法：可以分為以下兩種方法 直接轉(zhuǎn)換：十進(jìn)制直接轉(zhuǎn)換：十進(jìn)制二、八、十六進(jìn)制二、八、十六進(jìn)制 間接轉(zhuǎn)換：十進(jìn)制間接轉(zhuǎn)換：十進(jìn)制二進(jìn)制二進(jìn)制 八、十六進(jìn)制八、十六進(jìn)制v（a a）十進(jìn)制轉(zhuǎn)化為）十進(jìn)

18、制轉(zhuǎn)化為R R進(jìn)制進(jìn)制v（b b）二進(jìn)制轉(zhuǎn)化為八、十六進(jìn)制）二進(jìn)制轉(zhuǎn)化為八、十六進(jìn)制24十進(jìn)制轉(zhuǎn)二進(jìn)制25（a a）十進(jìn)制轉(zhuǎn)化為）十進(jìn)制轉(zhuǎn)化為R R進(jìn)制進(jìn)制v轉(zhuǎn)換方法轉(zhuǎn)換方法 整數(shù)部分：整數(shù)部分：除以除以R R取余，先得低位取余，先得低位，直到商為，直到商為0 0。 小數(shù)部分：小數(shù)部分：乘乘R R取整，先得高位取整，先得高位，直到積為，直到積為0 0或或者達(dá)到精度要求為止。者達(dá)到精度要求為止。v例：（例：（123.75123.75）1010= =（ ？ ）2 2 （123.75123.75）1010= =（ ？ ）8 81111011.11173.626小數(shù)部分的精度要求小數(shù)部分的精度要求v

19、當(dāng)小數(shù)部分當(dāng)小數(shù)部分不能整除為二進(jìn)制不能整除為二進(jìn)制時，則乘以時，則乘以2 2取整取整的過程中，積不會為的過程中，積不會為0 0；或者；或者當(dāng)小數(shù)部分轉(zhuǎn)化為當(dāng)小數(shù)部分轉(zhuǎn)化為二進(jìn)制位數(shù)很長二進(jìn)制位數(shù)很長，這時由精度來決定二進(jìn)制位，這時由精度來決定二進(jìn)制位數(shù)。數(shù)。v 例如：（例如：（0.350.35）1010（ ？ ）2 2無法整除無法整除 （0.68750.6875）1010（ ？ ）2 2位數(shù)太長位數(shù)太長v 若要求精度大于若要求精度大于1010，則表示，則表示“”左右兩邊左右兩邊的十進(jìn)制值的差的絕對值的十進(jìn)制值的差的絕對值1010。 則我們只需取則我們只需取4 4位二進(jìn)制小數(shù)即可滿足要求，位二

20、進(jìn)制小數(shù)即可滿足要求，因為因為10102d2 2時，校驗碼才具有時，校驗碼才具有檢錯能力檢錯能力，當(dāng)碼距，當(dāng)碼距dd 3 3時，校驗碼才具有時，校驗碼才具有糾錯糾錯能力能力。 碼距：碼距：一種碼制的碼距是指該碼制中所有代碼之一種碼制的碼距是指該碼制中所有代碼之間的最小間的最小距離距離。 兩個代碼之間的距離兩個代碼之間的距離：在一種編碼中，在任何兩：在一種編碼中，在任何兩個代碼之間逐位比較，對應(yīng)位值不同的個數(shù)。個代碼之間逐位比較，對應(yīng)位值不同的個數(shù)。 校驗碼的檢錯糾錯能力與碼距的關(guān)系如下：校驗碼的檢錯糾錯能力與碼距的關(guān)系如下： 若碼距若碼距d d為奇數(shù)，如果只用來檢查錯誤，則可為奇數(shù)，如果只用來

21、檢查錯誤，則可以發(fā)現(xiàn)以發(fā)現(xiàn)d d1 1位錯誤；如果用來糾正錯誤，則能位錯誤；如果用來糾正錯誤，則能夠糾正夠糾正 位錯誤。位錯誤。 若碼距若碼距d d為偶數(shù)，則可以發(fā)現(xiàn)為偶數(shù)，則可以發(fā)現(xiàn) 位錯誤，并能位錯誤，并能夠糾正（夠糾正（ ）位錯誤。）位錯誤。21d21d2d693.6 3.6 校驗碼校驗碼v 7 7、常見校驗碼：、常見校驗碼： 奇偶校驗碼：奇偶校驗碼：碼距碼距d=2d=2，檢錯碼，檢錯碼，能檢驗奇數(shù)能檢驗奇數(shù)位錯誤位錯誤；通常用于磁帶或者串行通信中。；通常用于磁帶或者串行通信中。 海明校驗碼：海明校驗碼：碼距碼距d=3d=3，糾錯碼，糾錯碼，能糾正能糾正1 1位位或多位錯誤或多位錯誤；通

22、常用于磁盤冗余陣列中。；通常用于磁盤冗余陣列中。 CRCCRC校驗碼：校驗碼：碼距碼距d=3d=3，糾錯碼，糾錯碼，能糾正能糾正1 1位錯位錯誤誤；通常用于磁盤或數(shù)據(jù)塊的校驗。；通常用于磁盤或數(shù)據(jù)塊的校驗。70v在有效信息位的前面或者后面添加一位奇（偶）校驗在有效信息位的前面或者后面添加一位奇（偶）校驗位就組成了奇（偶）校驗碼。位就組成了奇（偶）校驗碼。奇（偶）校驗碼的編碼和譯碼在硬件上通常采用異奇（偶）校驗碼的編碼和譯碼在硬件上通常采用異或非門（異或門）實現(xiàn)?；蚍情T（異或門）實現(xiàn)。 1 1、編碼、編碼奇校驗位的取值應(yīng)該使整個奇校驗碼中奇校驗位的取值應(yīng)該使整個奇校驗碼中“1”1”的的個數(shù)為奇數(shù)

23、，偶校驗位的取值應(yīng)該使整個偶校個數(shù)為奇數(shù)，偶校驗位的取值應(yīng)該使整個偶校驗碼中驗碼中“1”1”的個數(shù)為偶數(shù)。的個數(shù)為偶數(shù)。假設(shè)在發(fā)送端，要發(fā)送七位假設(shè)在發(fā)送端，要發(fā)送七位ASCIIASCII碼（碼（B6 B5 B4 B6 B5 B4 B3 B2 B1 B0B3 B2 B1 B0），在），在ASCIIASCII碼前面添加一位奇校碼前面添加一位奇校驗位驗位P P奇奇或偶校驗位或偶校驗位P P偶偶變?yōu)橐粋€字節(jié)的奇偶校驗變?yōu)橐粋€字節(jié)的奇偶校驗碼，則它們的生成表達(dá)式為碼，則它們的生成表達(dá)式為01234560123456BBBBBBBPBBBBBBBP偶奇二、奇偶校驗碼二、奇偶校驗碼71 2 2、譯碼、譯碼

24、 在接收端，必須檢驗接收到的校驗碼信息的奇偶在接收端，必須檢驗接收到的校驗碼信息的奇偶性，對于奇校驗碼，校驗碼中性，對于奇校驗碼，校驗碼中“1”1”的個數(shù)應(yīng)該為的個數(shù)應(yīng)該為奇數(shù)，否則出錯；對于偶校驗碼，校驗碼中奇數(shù)，否則出錯；對于偶校驗碼，校驗碼中“1”1”的個數(shù)應(yīng)該為偶數(shù)，否則出錯。設(shè)的個數(shù)應(yīng)該為偶數(shù)，否則出錯。設(shè)E E奇奇為奇校驗碼為奇校驗碼出錯信號，出錯信號，E E偶偶為偶校驗碼出錯信號，為為偶校驗碼出錯信號，為1 1出錯，出錯，為為0 0正確，則它們的表達(dá)式為正確，則它們的表達(dá)式為0B6B5B4B2B1B0B3P奇奇P偶偶字符字符“A”A”的的ASCIIASCII碼為碼為41H41H，

25、奇校驗碼為，奇校驗碼為C1HC1H，偶校驗碼為偶校驗碼為41H41H。偶偶奇奇PBBBBBBBEPBBBBBBBE01234560123456二、奇偶校驗碼二、奇偶校驗碼72P奇奇/ /P偶偶B6B5B4B2B1B0B3E奇奇E偶偶二、奇偶校驗碼二、奇偶校驗碼73三、海明碼三、海明碼v 1 1、編碼、編碼v海明碼的編碼步驟如下：海明碼的編碼步驟如下：v（1 1）計算校驗位的位數(shù)）計算校驗位的位數(shù)假設(shè)信息位為假設(shè)信息位為k k位，增加位，增加r r位校驗位，構(gòu)成位校驗位，構(gòu)成n=k+rn=k+r位海明碼字。若要求海明碼能糾正一位位海明碼字。若要求海明碼能糾正一位錯誤，用錯誤，用r r位校驗位產(chǎn)生

26、的位校驗位產(chǎn)生的r r位指誤字來區(qū)分位指誤字來區(qū)分無錯狀態(tài)及碼字中無錯狀態(tài)及碼字中n n個不同位置的一位錯誤狀個不同位置的一位錯誤狀態(tài)，則要求態(tài)，則要求r r滿足：滿足：2 2 r r k + r + 1 k + r + 1計算出計算出k k位有效信息時，必須添加的能糾錯一位有效信息時，必須添加的能糾錯一位的海明校驗碼的校驗位的位數(shù)位的海明校驗碼的校驗位的位數(shù)r r74v（2 2）確定有效信息和校驗位的位置）確定有效信息和校驗位的位置假設(shè)假設(shè)k k位有效信息從高到低為位有效信息從高到低為 ，添加的，添加的r r位校驗位為位校驗位為 ，則它們構(gòu)成，則它們構(gòu)成n=k+rn=k+r位的海明位的海明碼

27、排列設(shè)為碼排列設(shè)為 ，H H的下標(biāo)被稱為海明位號，的下標(biāo)被稱為海明位號，則第則第i i位的校驗位位的校驗位P Pi i必須位于位號為必須位于位號為2 2i-1i-1的位置，的位置，即即 ，其中，其中，i=1i=1，2 2，r r；有效信息；有效信息則在其余的海明碼位置上順序排列。則在其余的海明碼位置上順序排列。三、海明碼三、海明碼75三、海明碼三、海明碼v（3 3）分組）分組由于海明碼是分組進(jìn)行奇偶校驗的，每一組由于海明碼是分組進(jìn)行奇偶校驗的，每一組通過一個監(jiān)督表達(dá)式來監(jiān)督有效信息的變化，通過一個監(jiān)督表達(dá)式來監(jiān)督有效信息的變化，因此，分組必須使得監(jiān)督表達(dá)式得出的指誤因此，分組必須使得監(jiān)督表達(dá)式

28、得出的指誤字能夠反映出錯位的位號。分組的原則是：字能夠反映出錯位的位號。分組的原則是：校驗位只參加一組奇偶校驗，有效信息則參校驗位只參加一組奇偶校驗，有效信息則參加至少兩組的奇偶校驗，若加至少兩組的奇偶校驗，若 D Di i = = H Hj j ，則，則D Di i參加那些位號之和等于參加那些位號之和等于j j的校驗位的分組校驗。的校驗位的分組校驗。76三、海明碼三、海明碼v（4 4）進(jìn)行奇偶校驗，合成海明碼）進(jìn)行奇偶校驗，合成海明碼首先，按照分組和奇偶校驗的規(guī)律將每個校首先，按照分組和奇偶校驗的規(guī)律將每個校驗位的生成表達(dá)式寫出，然后，再帶入有效驗位的生成表達(dá)式寫出，然后，再帶入有效信息的值

29、，依次得出校驗位的取值，最后將信息的值，依次得出校驗位的取值，最后將校驗位按各自的位置插入，與有效信息一起校驗位按各自的位置插入，與有效信息一起合成海明碼。合成海明碼。77三、海明碼三、海明碼v 2 2、譯碼、譯碼 在接收端收到每個海明碼后，也必須按上述在接收端收到每個海明碼后，也必須按上述分組檢驗每組的奇偶性有無發(fā)生變化，方法分組檢驗每組的奇偶性有無發(fā)生變化，方法是按照監(jiān)督關(guān)系式算出指誤字是按照監(jiān)督關(guān)系式算出指誤字SrSr Sr-1 Sr-1 S2 S2 S1 S1 ，若為全零，則說明各組奇偶性全部無變，若為全零，則說明各組奇偶性全部無變化，信息正確，將相應(yīng)的有效信息位析取出化，信息正確，將

30、相應(yīng)的有效信息位析取出來使用；否則，指誤字的十進(jìn)制值，就是出來使用；否則，指誤字的十進(jìn)制值，就是出錯位的海明位號。錯位的海明位號。78四、循環(huán)冗余碼四、循環(huán)冗余碼CRCCRCv循環(huán)冗余碼循環(huán)冗余碼CRCCRC（Cyclic Redundancy Cyclic Redundancy CodeCode），又稱為多項式碼。），又稱為多項式碼。 v1 1、編碼、編碼vk k位要發(fā)送的有效信息位可對應(yīng)于一個位要發(fā)送的有效信息位可對應(yīng)于一個k-1k-1次多項式次多項式M M（x x），），r r位冗余校驗位對應(yīng)于一位冗余校驗位對應(yīng)于一個個r-1r-1次多項式次多項式R R（x x）。由）。由k k位信息位

31、后面位信息位后面加上加上r r位冗余位組成的位冗余位組成的n=k+rn=k+r位位CRCCRC碼字則對碼字則對應(yīng)于一個應(yīng)于一個n-1n-1次多項式次多項式C C（x x），即：），即： C C（x x）= x= xr r M M（x x）+ R+ R（x x） 該該CRCCRC碼稱為（碼稱為（n n，k k）循環(huán)碼。）循環(huán)碼。 79四、循環(huán)冗余碼四、循環(huán)冗余碼CRCCRCv 由信息位產(chǎn)生冗余位的編碼過程，就是已知由信息位產(chǎn)生冗余位的編碼過程，就是已知M M（x x）求求R R（x x）的過程。在）的過程。在CRCCRC碼中可以通過找到一個特定碼中可以通過找到一個特定的多項式的多項式G G（x

32、x）來實現(xiàn)。用）來實現(xiàn)。用G G（x x）去除）去除x xr r M M（x x）得到的余式就是得到的余式就是R R（x x），假設(shè)商的多項式為），假設(shè)商的多項式為Q Q（x x），），編碼過程編碼過程 即即x xr r M M（x x）G G（x x） Q Q（x x）+ R+ R（x x）v 生成多項式生成多項式G G（x x）應(yīng)滿足以下條件：）應(yīng)滿足以下條件： (1)(1)必須是必須是r r次多項式，最高項次多項式，最高項x xr r 和和x x0 0的系數(shù)為的系數(shù)為1 1，即它對應(yīng)的二進(jìn)制編碼是即它對應(yīng)的二進(jìn)制編碼是r+1r+1位的。位的。 (2)CRC(2)CRC校驗碼的任何一位發(fā)生

33、錯誤，余數(shù)不為零；校驗碼的任何一位發(fā)生錯誤，余數(shù)不為零；且不同位發(fā)生錯誤，余數(shù)不同。且不同位發(fā)生錯誤，余數(shù)不同。 (3)(3)對余數(shù)繼續(xù)模對余數(shù)繼續(xù)模2 2除，應(yīng)使余數(shù)循環(huán)。除，應(yīng)使余數(shù)循環(huán)。)()()()()(xGxRxQxGxMxr80四、循環(huán)冗余碼四、循環(huán)冗余碼CRCCRCv目前已經(jīng)有多種生成多項式被列入國際標(biāo)準(zhǔn)中，目前已經(jīng)有多種生成多項式被列入國際標(biāo)準(zhǔn)中，如：如：CRC-4CRC-4、CRC-12CRC-12、CRC-16CRC-16、CCITT-16CCITT-16、CRC-CRC-3232等。等。v目前常用的目前常用的CRC-16CRC-16多項式為多項式為x x1616+x+x1

34、212+x+x5 5+1+1（記為（記為10211021），），CCITT-16CCITT-16多項式為多項式為x x1616+x+x1515+x+x2 2+1+1（記為（記為80058005）。）。圖圖3.9 CRC3.9 CRC（n,kn,k）校驗碼串行生成電路原理）校驗碼串行生成電路原理圖圖圖中圖中GiGi代表生成多項式代表生成多項式G G（x x）各項的系數(shù)）各項的系數(shù) 81四、循環(huán)冗余碼四、循環(huán)冗余碼CRCCRCv 2 2、譯碼、譯碼 v 接收端的校驗過程就是用接收端的校驗過程就是用G G（x x）來除接來除接收到的碼字多項式的過程。收到的碼字多項式的過程。若余式為零則認(rèn)為傳輸無差錯

35、；若余式為零則認(rèn)為傳輸無差錯；若余式不為零則傳輸有差錯。出錯的位置與若余式不為零則傳輸有差錯。出錯的位置與余數(shù)值是一一對應(yīng)的關(guān)系，通過查找出錯模余數(shù)值是一一對應(yīng)的關(guān)系，通過查找出錯模式表，即可以確定是那一位出錯。式表，即可以確定是那一位出錯。 823.7 3.7 現(xiàn)代計算機(jī)系統(tǒng)的數(shù)據(jù)表示現(xiàn)代計算機(jī)系統(tǒng)的數(shù)據(jù)表示v幾種類型的數(shù)據(jù)在幾種類型的數(shù)據(jù)在PentiumPentium系列系列CPUCPU中的表中的表示形式示形式 ：v1 1、字符串、字符串 由字符的由字符的ASCIIASCII碼或者文字的碼或者文字的UnicodeUnicode編碼組成，編碼組成，按順序存放在內(nèi)存或寄存器中。每個按順序存放在

36、內(nèi)存或寄存器中。每個ASCIIASCII碼碼字符占字符占1 1個字節(jié)，每個個字節(jié)，每個UnicodeUnicode編碼占用編碼占用2 2個字個字節(jié)節(jié) 833.7 3.7 現(xiàn)代計算機(jī)系統(tǒng)的數(shù)據(jù)表示現(xiàn)代計算機(jī)系統(tǒng)的數(shù)據(jù)表示vBCDBCD 在基于在基于PentiumPentium系列系列CPUCPU的的IAIA構(gòu)架中，構(gòu)架中，BCDBCD數(shù)據(jù)數(shù)據(jù)分為壓縮的（分為壓縮的（packedpacked）BCDBCD碼和非壓縮碼和非壓縮（unpackedunpacked）的）的BCDBCD碼兩種，前者以每字節(jié)碼兩種，前者以每字節(jié)2 2位位BCDBCD數(shù)字的形式存儲，后者以每字節(jié)數(shù)字的形式存儲，后者以每字節(jié)1 1位位BCDBCD數(shù)字的方法存儲數(shù)字的方法存儲 843.7 3.7