1、CS&T Information CourseBeyond Technology計算機組成原理計算機組成原理大連東軟信息學院精品課程大連東軟信息學院精品課程CS&T Information Course內容回顧內容回顧 1、馮諾依曼體系結構中，計算機的設計思想是什么？ 2、計算機有哪五大部分組成？ 3、CPU中包括哪兩大部件？ 4、計算機經歷了哪四代？CS&T Information Course第第2章章 數碼系統數碼系統教學內容教學內容 2.1數制及其轉換數制及其轉換 2.2數值數據描述數值數據描述 2.3文本數據描述文本數據描述 2.4其他信息形式其他信息形式的表

2、示的表示 2.5數據校驗數據校驗教學重點教學重點 進位計數制及其進位計數制及其轉換轉換 真值和機器數真值和機器數 有符號數的表示有符號數的表示 浮點數的表示浮點數的表示 BCD碼碼 文本數據的描述文本數據的描述 校驗碼校驗碼教學難點教學難點 有符號數的表示有符號數的表示（原、反、補碼）（原、反、補碼）CS&T Information Course本章線索本章線索數制及其轉換數制及其轉換數值數據描述數值數據描述文本數據描述文本數據描述其他信息形式的其他信息形式的表示表示數據校驗數據校驗CS&T Information Course2.1數制及其轉換數制及其轉換重要概念重要概念 R

3、進制中只允許出現0、1、2、R-1共R個數碼，數碼即可以是數也可以是碼（如字母），則R就稱為R進制的基數。基數基數 R進制中，不同位置的1所表示的值不同，位號為i的1表示Ri，Ri稱為位權。位權位權 進位規則是指何種情況下向高位進位。R進制中，對位加法滿R就應向高位進位，即逢R進一。進位規則進位規則CS&T Information Course2.1數制及其轉換數制及其轉換常見進制常見進制十進制（十進制（D）二進制（二進制（B）八進制（八進制（O）十六進制（十六進制（H）0123456789101112131415000000010010001101000101011001111000

4、10011010101111001101111011110123456710111213141516170123456789ABCDEFCS&T Information Course2.1數制及其轉換數制及其轉換數制的相互轉換數制的相互轉換十進制十進制二進制二進制八進制八進制十六十六進制進制CS&T Information Course2.1數制及其轉換數制及其轉換二進制常用表達二進制常用表達（1）（1000）2 = 2N：表示1后面有N個0的二進制整數。（2）（1111）2 = 2N-1：表示共有N個1的二進制整數。（3）（0.001）2 = 2-N：表示小數點后共有N-1個

5、0的二進制純小數。（4）（0.111）2 = 1-2-N：表示 小數點后共有N個1的二進制純小數。（5）（1111）2 -（X1X2XN）2 = （X1X2XN）2：表示共有N個1的二進制整數減去一個N位的二進制整數，結果是將減數按位取反。（6）（0.1111）2 -（0.X1X2XN）2 = （0.X1X2XN）2：表示共有N個1的二進制純小數減去一個小數部分有N位的二進制純小數，結果是將減數的小數部分按位取反。（7）二進制數左移K位，相當于這個數乘以2K。（8）二進制數右移K位，相當于這個數除以2K。CS&T Information Course2.2數值數據描述數值數據描述機器數

6、機器數無符號數無符號數有符號數有符號數定點數定點數定點整數定點整數定點小數定點小數浮點數浮點數CS&T Information Course2.2數值數據描述數值數據描述無符號數和有符號數無符號數和有符號數 無符號數（unsigned） 數據與數值相等，數據本身的N+1個二進制比特位全部用來表示其數值，沒有符號位。 表示范圍： 0，2N+1-1 通常用于表示地址，作為計數器等用途CS&T Information Course2.2數值數據描述數值數據描述無符號數和有符號數無符號數和有符號數 有符號數（signed） 有符號數的數據分為符號和數值兩個部分，N+1位有符號數的二進制

7、比特位最左一位用于表示符號，其余N位用于表示數值。 真值和機器數：真值是帶符號的數，即平時生活中數的表達方式。機器數是有符號數的符號數值化后在計算機存儲中的數，是一個0、1序列。 三個問題 符號的數值化：“+”用“0”表示，“-”用“1”表示。 數值的編碼：多種方案，如原碼，反碼，補碼，移碼等。 小數點的表示：隱藏，不表示出來，只要事先約定好即可。CS&T Information Course2.2數值數據描述數值數據描述定點數和浮點數定點數和浮點數 定點數 小數點固定在某一位置的數為定點數。 定點整數與定點小數定點小數格式 定點整數格式CS&T Information Cou

8、rse2.2數值數據描述數值數據描述定點數和浮點數定點數和浮點數 浮點數 小數點的位置可以浮動的數。 將尾數最高位為1的浮點數稱作規格化數。 左規與右規浮點數的表示形式CS&T Information Course2.2數值數據描述數值數據描述定點數的編碼方案定點數的編碼方案 原碼 求法：把數值的絕對值轉換成二進制以后在最高位加上其符號的數值表示，原數值的符號位“+”和“-”分別用“0”和“1”表示。 定義定點整數時：定點小數時：X原 = X （X0） X原 = X （X0） = 2N-X （X0） = 1-X （X0） 0的編碼 +0原=00000000 -0原=10000000 0

9、的原碼不唯一！ 表示范圍 定點整數：-（2N-1）， +（2N-1） 定點小數：-（1-2-N），+（1-2-N）CS&T Information Course2.2數值數據描述數值數據描述定點數的編碼方案定點數的編碼方案 反碼 求法：如果為正數則其編碼與原碼相同，如果為負數則除符號位外按位取反。 定義定點整數時：定點小數時：X原 = X （X0） X原 = X （X0） = 2N+1-1+X （X0） = 2-2-N+X （X0） 0的編碼+0反=00000000 -0反=11111111 0的反碼不唯一！ 表示范圍 定點整數：-（2N-1）， +（2N-1） 定點小數：-（1-2-

10、N），+（1-2-N）CS&T Information Course2.2數值數據描述數值數據描述定點數的編碼方案定點數的編碼方案 補碼 求法：如果為正數則其編碼與原碼相同；如果為負數則在反碼的基礎上+1。 定義定點整數時：定點小數時：X原 = X （X0） X原 = X （X0） = 2N+1+X （X0） = 2+X （X0） 0的編碼 +0補=00000000，-0補=00000000 0的補碼唯一！ 表示范圍 定點整數： -2N，+（2N-1） 定點小數： -1，+（1-2-N）CS&T Information Course2.2數值數據描述數值數據描述定點數的編碼方案

11、定點數的編碼方案 補碼的性質 已知X補，求X原、-X補、2X補、X/2補的方法。 X原= X補（正數），X原= X補補（負數） -X補= X補連同符號位一起按位取反，末尾加1 2X補= X補連同符號位一起左移一位，右邊補0（符號位不能變） X/2補= X補連同符號位一起右移一位，左邊補符號位（舍去） 練習：已知X補= 0.01001001，求X原、-X補、2X補、X/2補。 X原= 0.01001001 -X補= 1.10110111 2X補=0.10010010 X/2補= 0.00100100CS&T Information Course2.2數值數據描述數值數據描述定點數的編碼方

12、案定點數的編碼方案 變形補碼 求法：雙符號位補碼 用法：方便判斷運算是否溢出！ 移碼 求法：將一個數的補碼的符號位取反 定義：X移 = 2N+X 表示范圍：0，+（2N+1-1） 用法：表示浮點數的階碼CS&T Information Course2.2數值數據描述數值數據描述定點數的編碼方案定點數的編碼方案練習：4位二進制數表示的有符號的定點整數和小數的原、反、補碼的表示范圍分別是多少？4位二進制數表示的有符號整數 原碼：1111B0111B（-7+7） 反碼：1000B0111B（-7+7） 補碼：1000B0111B（-8+7）4位二進制數表示的有符號小數 原碼：1.111B0.

13、111B（-（1-2-3） 1-2-3 ） 反碼：1.000B0.111B（ -（1-2-3） 1-2-3 ） 補碼：1.000B0.111B（-1 1-2-3 ）總結 定點數表示范圍中包括0 所有編碼表示的最大數一致 原碼和反碼的表示范圍一致，且相對于0點中心對稱CS&T Information Course內容回顧內容回顧 數制及其轉換 數值數據描述（分類） 定點數的編碼方案 原碼、反碼、補碼CS&T Information Course 二進制數的位數為N+1=8位時，求+5和-5的原碼。 當N+1=8時，N=7，即數值用7位表示。所以： (5)D=(101)B=(000

14、0 101)B 前面的4個0是為了保證數據位為7位加上去的，再把“+”號變成“0”放在首位。 +5原=0 0000101 同理可得：-5原=1 0000101。CS&T Information Course二進制數的位數為二進制數的位數為N+1=8位時，求位時，求+0.625和和-0.625的原碼。的原碼。 當N+1=8時，N=7，即數值用7位表示。所以： (0.625)D=(0.101)B=(0.101 0000)BCS&T Information Course二進制數的位數為二進制數的位數為N+1=8位時，求位時，求+5和和-5的補碼。的補碼。 +5原=00000101，-

15、5原=10000101 因為+5是一個正數，其補碼與原碼相同，有+5補=00000101。 負數的補碼是在反碼的最末位加上1，由例2.7可知-5反=11111010，而11111010+1=11111011，可以得到-5補=11111011。CS&T Information Course二進制數的位數為二進制數的位數為N+1=8位時，求位時，求+0.625和和-0.625的補碼。的補碼。 +0.625原=0.1010000，-0.625原=1.1010000 因為+0.625是一個正數，其補碼與原碼相同，有+0.625補=0.1010000。 負數的補碼是在反碼的最末位加上1，由例2.

16、8可知-0.625反=1.0101111，而1.0101111+0.0000001 = 1.0110000，可以得到-0.625補=1.0110000。CS&T Information Course二進制數的位數為二進制數的位數為N+1=8位時，求位時，求+5和和-5的變形補碼的變形補碼 +5原= 0 0000101 +5反= 0 0000101 +5補= 0 0000101 +5變補=00 0000101 同理可得： -5原= 1 0000101 -5反= 1 1111010 -5補= 1 1111011 -5變補=11 1111011 另外：+0.101變補=00 .1010000

17、，-0.101變補=11 .0110000。CS&T Information Course二進制數的位數為二進制數的位數為N+1=8位時，求位時，求+5和和-5的移碼。的移碼。 +5補=0 0000101 +5移=1 0000101 同理可得： -5原=1 0000101 -5反=1 1111010 -5補=1 1111011， -5移=0 1111011。CS&T Information Course2.2數值數據描述數值數據描述浮點數的編碼方案浮點數的編碼方案 浮點數的表示： X=Mx REx，其中Mx稱為尾數，通常為帶符號的小數，Ex稱為階碼，通常為帶符號的整數。 幾個重

18、要概念 浮點數上溢：階碼比所能表示的最大正數還要大。 浮點數下溢：階碼比所能表示的最小負數還要小。 浮點數溢出處理：上溢產生中斷，停止處理；下溢強行置機器0，繼續運算。 機器0：尾數為0，階碼不管為任何值，或者階碼小于它所能表示的最小數，無論尾數為任何值。 規格化數：在R進制中，要求尾數Mx滿足1/R |Mx| 1，即R進制中尾數的第一位為有效位（非零）。 IEEE754標準CS&T Information Course浮點數浮點數IEEE754標準標準IEEE754標準標準符號位符號位階碼階碼尾數尾數偏移量偏移量是否采用隱藏位技術是否采用隱藏位技術單精度單精度32位（短實數）位（短實

19、數）1823127采用雙精度雙精度64位（長實數）位（長實數）111521023采用臨時實數臨時實數80位位1156416383不采用CS&T Information Course已知一單精度浮點數的機器碼為：已知一單精度浮點數的機器碼為：42C88000H，求其真值，求其真值 解：解：42C88000H = （0100,0010,1100,1000,1000,0000,0000,0000）2 = （0,10000101,10010001000000000000000）2 尾符為0，尾數為0.10010001000000000000000，階碼為10000101 真值=（-1）0（1+

20、0.10010001000000000000000）2（100001011111111）=1.1001000126=（100.25）10。CS&T Information Course2.2數值數據描述數值數據描述十進制數的編碼十進制數的編碼 BCD碼：十進制數的二進制編碼。 BCD碼的編碼方案 有權碼：8421碼、5421碼、2421碼等 無權碼：余三碼、格雷碼等 8421碼CS&T Information Course8421碼的編碼方式碼的編碼方式 BCD碼實質都是利用四位二進制來表示一位十進制數碼，方案有多種，按其編碼是否根據特定的權值構成，分為有權碼和無權碼。有權碼有

21、8421碼、2421碼和5421碼等編碼方式，通常用得最多的是8421碼，所以一般BCD碼如不特殊說明就指8421碼。 如十進制的128，用8421碼的1表示為0001，2表示為0010，8表示為1000，得(128)D=(0001 0010 1000)BCD。CS&T Information Course其他有權碼其他有權碼 2421碼和5421碼等編碼方式 自己設計一種有權碼 如：84-2-1？ 用84-2-1碼表示1，如何表示？CS&T Information Course練習練習 一種BCD碼，其中09的編碼為0000，0001，0010，0011，0100，0101，

22、0110，0111，1110，1111，則各位的權值為_。 A. 8421 B. 5421 C. 4421 D. 2421CS&T Information Course無權碼無權碼 余3碼的編碼方式就是在8421碼的編碼上加上3，做數值計算得到的編碼。 格雷碼的主要特點為任何兩組相鄰碼字中只有一位二進制不同，它有多種編碼方案。一種方案為8421碼加一個前導0，然后相鄰兩位異或得到。 求：數字9的格雷碼CS&T Information Course2.3文本數據描述文本數據描述ACSII碼碼 鍵盤有多少個按鍵？ 101個 AscII碼用幾位可以表示這些按鍵？CS&T In

23、formation Course2.3文本數據描述文本數據描述ACSII碼碼 基本的ASCII字符集：使用7位二進制數對字符進行編碼，包括128個字符，其中有96個可打印字符，包括常用的字母、數字、標點符號等，另外還有32個控制字符。 常用幾個編碼 0：30H（48） A：41H（65） a：61H（97） 一個字節的最高位為0，可用于奇偶校驗。CS&T Information Course練習練習 已知0和9的ASCII碼分別為0110000和0111001，請分別寫出3、5、7的ASCII碼、8421碼及余三碼。CS&T Information Course內容回顧內容回顧

24、 1、浮點數的編碼方案 2、浮點數真值計算公式 浮點數真值 =（-1）尾符（1+尾數）2（階碼偏移量） 3、十進制數的編碼 4、ASCII碼CS&T Information Course本次課內容要點本次課內容要點 1、漢字的編碼 2、數據校驗CS&T Information Course2.3文本數據描述文本數據描述漢字的編碼漢字的編碼 輸入碼：用來將漢字輸入到計算機中的一組鍵盤符號。 交換碼：計算機內部處理的信息，都是用二進制代碼表示的。 國標碼：GB2312-80 區位碼： 94（區）94（位） 機內碼：每一個漢字確定的二進制代碼，既把國標碼的每一個字節的首位置1（為了解

25、決和ASCII碼的沖突）。 字形碼：漢字的輸出碼，輸出漢字時都采用圖形方式，無論漢字的筆畫多少，每個漢字都可以寫在同樣大小的方塊中。CS&T Information Course2.3文本數據描述文本數據描述漢字的編碼漢字的編碼 區位碼、國標碼和漢字的內碼的關系 （國標碼） H =（區位碼）H +（2020）H （內碼）H = （國標碼）H+ （8080）H （內碼）H = （區位碼）H+ （A0A0）H 例：“啊”字的國標碼為3021H 區位碼=3021H 2020H = 1001H，即它在第16區，第01位。 內碼=3021H + 8080H = B0A1H。十進制十進制CS&am

26、p;T Information Course區位碼區位碼-94個區可分為個區可分為5組組 01-15區：是各種圖形符號、制表符和一些主要國家的語言字母，其中01-09區為標準符號區，共有682個常用符號。 10-15區：為自定義符號區，可留作用戶自己定義。 16-55區：是一級漢字區，共有3755個常用漢字，以拼音為序排列。 56-87區：是二級漢字區，共有3008個次常用漢字，以部首為序排列。 88-94區：自定義漢字區，可留作用戶自己定義。CS&T Information Course2.4其他信息形式的表示其他信息形式的表示圖像的格式簡介圖像的格式簡介 BMP：位圖格式 GIF：

27、圖形交換格式 JPEG：有損壓縮格式CS&T Information Course2.4其他信息形式的表示其他信息形式的表示有關音頻編碼有關音頻編碼 采樣率和采樣大小 采樣的過程就是抽取某點的頻率值。 采樣率：采樣的頻率 采樣大小：采樣頻率的能量值并量化 有損與無損 相對自然界的信號，任何數字音頻編碼方案都是有損的 PCM約定俗成了無損編碼 PCM編碼：音質好，體積大CS&T Information Course2.4其他信息形式的表示其他信息形式的表示視頻格式視頻格式 FLC：無聲時代 AVI：載歌載舞 MPEG編碼 流媒體：MPEG-4，邊下載邊播放CS&T Inf

28、ormation Course2.5數據校驗數據校驗 即檢查代碼是否出錯，但不能確定何處出錯，不能修改。檢錯碼 即不僅能檢查出錯誤，還能定位錯誤并糾正。糾錯碼CS&T Information Course2.5數據校驗數據校驗校驗碼的工作原理校驗碼的工作原理碼距：任意兩個合法編碼之間不相同的位數的最小值。合法的數據非法的編碼數據傳輸合法的編碼非法的編碼傳輸數據正確傳輸數據錯誤校驗碼CS&T Information Course差錯編碼差錯編碼q 附加監督位：在數據塊中加入一些冗余信息，使數據塊中的各個比特建立起某種形式的關聯，接收端通過驗證這種關聯關系是否存在，來判斷數據在傳輸

29、過程中有沒有出錯。q 差錯編碼：在數據塊中加入冗余信息的過程。CS&T Information Course 術術 語語 碼字只有檢錯的功能，接收方只能判斷數據塊有錯，但不能確切知道錯誤的位置，從而也不能糾正錯誤。 碼字具有一定的糾錯功能，接收方不僅能檢出錯，還知道錯在什么地方，這時只需將數據位取反即能獲得正確的數據。CS&T Information Course2.5數據校驗數據校驗奇偶校驗碼奇偶校驗碼 由n-1位信息元和1位校驗元組成 奇校驗碼：在附加上一個校驗元以后，碼長為n的碼字中“1”的個數為奇數個 偶校驗碼：附加上一個校驗元以后，碼長為n的碼字中“1”的個數為偶數個

30、 例：被校驗的代碼為1000001，則奇偶校驗碼分別為 奇校驗碼：11000001 （最左位為校驗位） 偶校驗碼：01000001 （最左位為校驗位） 是一種檢錯碼CS&T Information Course2. 2.奇偶校驗的校驗方程奇偶校驗的校驗方程 設設7 7位信息碼組為位信息碼組為C C7 7C C6 6C C5 5C C4 4C C3 3C C2 2C C1 1, , 校驗碼為校驗碼為C C0 0 , ,則對偶則對偶校驗校驗, , 當滿足當滿足 C C7 7CC6 6CC5 5CC4 4CC3 3CC2 2CC1 1CC0 00 0 （1 1） 時時, , 為合法碼為合法碼

31、; ; 對奇校驗對奇校驗, , 當滿足當滿足 C C7 7CC6 6CC5 5CC4 4CC3 3CC2 2CC1 1CC0 0 1 1 （2 2） 時時, , 為合法碼。為合法碼。 對于偶校驗對于偶校驗, , 合法碼字應滿足合法碼字應滿足n n C Ci iCC0 00 0 （3 3）i-1i-1 對于奇校驗對于奇校驗, , 合法碼字應滿足合法碼字應滿足n n C Ci iCC0 01 1 （4 4）i-1i-1注意注意: :公式公式(1)(2)(1)(2)為奇偶校驗位為奇偶校驗位的生成方程的生成方程; ;公式公式(3)(4)(3)(4)為校驗方程。為校驗方程。CS&T Inform

32、ation Course發明糾錯碼的大數學家發明糾錯碼的大數學家里查德里查德. .海明海明 Richard HammingRichard Hamming于于19151915年生于美國芝加哥。年生于美國芝加哥。 19371937年在芝加哥大學獲得數學碩士學位年在芝加哥大學獲得數學碩士學位, 1939, 1939年在年在內布拉斯加大學獲得碩士學位內布拉斯加大學獲得碩士學位, , 又于又于19421942年在伊利諾大年在伊利諾大學獲得博士學位。他長期在貝爾實驗室工作，擔任計學獲得博士學位。他長期在貝爾實驗室工作，擔任計算機科學部的主任。他成功地解決了通信時發送方發算機科學部的主任。他成功地解決了通信

33、時發送方發出的信息在傳輸過程中的誤碼問題，并于出的信息在傳輸過程中的誤碼問題，并于19471947年發明年發明了一種能糾錯的編碼，稱為糾錯碼或海明碼。這種方了一種能糾錯的編碼，稱為糾錯碼或海明碼。這種方法在計算機各部件間進行信息傳輸時以及在計算機網法在計算機各部件間進行信息傳輸時以及在計算機網絡的信息傳輸中同樣有用。為此，他于絡的信息傳輸中同樣有用。為此，他于19681968年榮獲圖年榮獲圖靈獎。靈獎。HammingHamming作為數學家在數值方法、編碼與信息作為數學家在數值方法、編碼與信息論、統計學和數字濾波器等領域也有重大的貢獻。論、統計學和數字濾波器等領域也有重大的貢獻。Hamming

34、Hamming是美國工程院院士，曾任是美國工程院院士，曾任ACMACM第七屆主席，第七屆主席，還獲得了除圖靈獎之外的多個重大獎項。還獲得了除圖靈獎之外的多個重大獎項。CS&T Information Course2.5數據校驗數據校驗海明碼海明碼 設信息位為k位，增加r位冗余位，構成一個n=k+r位的碼字。可以用r個監督關系式產生的r個校正因子來區分無錯和在碼字中的n個不同位置的一位錯。 滿足關系式2r=n+1或2r=k+r+1。 在接收端收到每個碼字后，按監督關系式算出S2、S1和S0，若它們全為“0”，則認為無錯；若不全為“0”，在一位錯的情況下，可查表判定是哪一位錯，從而糾正之。

35、 是一種糾錯碼，但只能糾一位錯。CS&T Information Course海明碼海明碼 設信息位為k位，增加r位冗余位，構成一個n=k+r位的碼字。若希望用r個監督關系式產生的r個校正因子來區分無錯和在碼字中的n個不同位置的一位錯，則要求滿足關系式2r=n+1或2r=k+r+1 以k=4為例來說明，要滿足上述不等式，必須r=3。假設取r=3，則n=k+r=7，即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0，構成7位碼字a6a5a4a3a2a1a0信息位冗余位CS&T Information Course 在校驗時，a2、a1和a0就分別和這些位半加構成三個不同

36、的監督關系式。在無錯時，這三個關系式的值S2、S1和S0全為“0”。若a2錯，則S2=1，而S1=S0=0；若a1錯，則S1=1，而S2=S0=0；若a0錯，則S0=1S2 S1 S0000001010100011101110111錯碼錯碼位置位置無錯a0a1a2a3a4a5a6S2、S1和S0這三個校正因子的其它4種編碼值可用來區分a3、a4、a5、a6中的一位錯CS&T Information Course監督關系式監督關系式S2 S1 S0000001010100011101110111錯碼位置錯碼位置無錯無錯a0a1a2a3a4a5a6a2、a4、a5或a6的一位錯都應使S2=

37、1，由此可以得到監督關系式S2=a2a4a5a6， 同理可得S1=a1a3a5a6， S0=a0a3a4a6。S2、S1和S0是偶校驗碼的校驗元監督關系式CS&T Information Course冗余碼的確定冗余碼的確定 在發送端編碼時，信息位a6、a5、a4和a3的值取決于輸入信號，它們在具體的應用中有確定的值。冗余位a2、a1和a0的值應根據信息位的取值按監督關系式來確定 使監督關系式中的S2、S1和S0取值為零，即 a2 a4 a5 a6=0 a1 a3 a5 a6=0 a0 a3 a4 a6=0 由此可求得：a2=a4 a5 a6 a1=a3 a5 a6 a0=a3 a4

38、a6a2,a1,a0a2,a1,a0即為冗余碼即為冗余碼CS&T Information Course已知信息位，即可確定冗余位已知信息位，即可確定冗余位信息位信息位a3冗余位冗余位a0信息位信息位a3冗余位冗余位a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111CS&T Information Course接收端糾錯接收端糾錯 在接收端收到每個碼字后，按監督關系式算出S2、S1和S0，若它們全為“0”

39、，則認為無錯；若不全為“0”，在一位錯的情況下，可查表2.6來判定是哪一位錯，從而糾正之。CS&T Information Course海明碼海明碼例例發送發送發送端想發送一個數字9，直接發送沒法校驗和糾錯，怎么辦？給它加上校驗碼，數字9的BCD碼是1001，加幾位校驗碼合適？根據海明碼的構造方法，加3位冗余位，可校驗一位錯查P45頁表2.7，1001加冗余位100把加了冗余位的碼字一起發送過去CS&T Information Course海明碼海明碼例例發送發送 組合成的碼字按照a6,a5,a4,a3,a2,a1,a0的順序排列，即為：1001100 最后，把這串碼字發送出去

40、CS&T Information Course海明碼海明碼例例接收接收 剛才我們發送了碼字1001100，如果在通訊過程中收到干擾，到接收端變成了：1101100 接收端則通過監督關系式判斷是否有錯，如何糾正 根據監督關系式， S2=a2 a4 a5 a6，則S2=1 S1=a1 a3 a5 a6，則S1=1 S0=a0 a3 a4 a6。則S0=0CS&T Information CourseS2,S1,S0的取值為的取值為110S2 S1 S0000001010100011101110111錯碼位置錯碼位置無無錯錯a0a1a2a3a4a5a6A5位錯了！修正，把收到的碼字1

41、101100的a5位取反正確的碼字是：1001100，再去掉冗余位，則發送的正確信息是1001，即數字9CS&T Information Course校驗碼工作過程總結校驗碼工作過程總結差錯編碼差錯編碼q 附加監督位：在數據塊中加入一些冗余信息，使數據塊中的各個比特建立起某種形式的關聯，接收端通過驗證這種關聯關系是否存在，來判斷數據在傳輸過程中有沒有出錯。q 差錯編碼：在數據塊中加入冗余信息的過程。CS&T Information Course練習練習1發送數字5，要求接收端可以校驗1位錯。設計海明碼校驗碼字發送。接收端接收正確的情形如何判斷？如果接收端的信息錯了1位，如何判斷

42、哪位錯并糾正？CS&T Information Course練習練習2 接收方接收到了一串用海明碼進行校驗的編碼： 0101110 判斷：接收到的編碼是否有錯？ 如果有錯，錯在哪一位？ 糾正該編碼？CS&T Information Course2.5數據校驗數據校驗循環冗余碼循環冗余碼 在發送端根據要傳送的k位二進制碼序列，以一定的規則產生一個校驗用的監督碼（既CRC碼）r位，并附在信息后邊，構成一個新的二進制碼序列數共（k+r）位，最后發送出去。在接收端，則根據信息碼和CRC碼之間所遵循的規則進行檢驗，以確定傳送中是否出錯。 是一種常用的糾錯碼。CS&T Inform

43、ation Course計算機網絡第4章 數據鏈路層68 循環冗余檢驗的原理 碼字多項式： 讓數據碼字的每一位對應于多項式中每一位的系數。如：數據碼字： 1010101則：碼字多項式：x6 + x4 + x2 + 1（n+k,k）碼：即：數據碼為：n位，冗余碼為k位， 則：其合法編碼有2k個。 例如：(7,3)碼的合法編碼有八個： 000 0000 100 1110 001 1101 011 1010 111 0100 110 1001 101 0011 010 0111CS&T Information Course計算機網絡第4章 數據鏈路層69 循環冗余檢驗的原理 CRC編碼方法設

44、：要發送的信息碼字多項式為：F(x) 雙方協議規定的生成多項式為：G(x)編碼步驟： (1)用生成多項式的最高位乘以M(x)：xkF(x) (2)用(1)的結果除以G(x) (3)所得余數R(x)即為CRC的冗余碼。CS&T Information Course計算機網絡第4章 數據鏈路層70即有： xkF(x) G(x)xkF(x)= Q(x)G(x)+R(x)有：xkF(x)+R(x) = Q(x)G(x)CS&T Information Course計算機網絡第4章 數據鏈路層71CRC譯碼方法設：收到的信息碼字多項式為：F(x) 雙方協議規定的生成多項式為：G(x)則：

45、能除盡，傳輸正確否 則，傳輸錯誤若傳輸正確，則F(x) = Q(x)G(x)Q(x)G(x) G(x)顯然是可以除盡的，反之，除不盡CS&T Information Course計算機網絡第4章 數據鏈路層72校驗位的生成 用一個例子來說明校驗位的生成過程。 假設要傳送的數據信息為：100011，即報文多項式為：F(x)= x5 + x + 1。 若約定的生成多項式為：G(x)= x3+ 1，則數據信息位數n=6，生成多項式位數為4位，所以校驗位位數k=3。 生成校驗位時，用x3.F(x)去除以G(x)，相除時采用“模運算”的多項式除法。 CS&T Information Course計算機網絡第4章 數據鏈路層7373 100011000100111100100110000011100001110100111101001111010011111001X3.F(x)G(x)(x8+ x4 + x3)(x3 + 1) 校驗位為111，CRC碼為100011 111。如果要校驗CRC碼，則可將CRC碼用同一個多項式相除，若余數為，則說明無錯；否則說明有錯。例如，若在接收方的CRC碼也為100011 111時，用同一個多項式相