南寧最高端網(wǎng)站建設(shè)如何搭建網(wǎng)站平臺
前言?
1、小提示：本篇博文是參考王道，在復(fù)習(xí) ASCII 碼的基礎(chǔ)上，總結(jié)校驗碼的相關(guān)學(xué)習(xí)知識點，并在最后搭配習(xí)題（含408真題）進(jìn)行鞏固練習(xí)。（對重點內(nèi)容進(jìn)行劃線、標(biāo)色）
2、適用人群：408考研、備考高中信息技術(shù)教師資格證、學(xué)習(xí)《計算機(jī)組成原理》的人員
3、可搭配學(xué)習(xí)的鏈接：
【考研】計組：中斷_計組中斷過程
【考研】計組習(xí)題：存儲器
一、字符編碼 ASCII 碼與校驗碼
1、ASCII 碼的概念
7 位的二進(jìn)制編碼（字符系統(tǒng)），每個字節(jié)的最高位保持為0，可用于傳輸時的奇偶校驗位，可表示 10 個十進(jìn)制數(shù)碼、52 個英文大寫和小寫字母（A - Z, a - z），及一定數(shù)量的專用符號（如 %、+、=、$ 等），共 128 個字符。
2、編碼值與其對應(yīng)的ASCII 碼表示
| 編碼值 | 0-31 | 32 | 32-126 | 127 |
| ASCII 碼 | 控制字符 | 空格SP | 可印刷字符（95個字符） | DEL碼 |
| 注意：0 - 9 的 ASCII 碼值為 48 （011 0000） - 57（011 1001），即去掉高 3 位，只保留低 4 位，正好是二進(jìn)制形式的 0 - 9。 | ||||
3、校驗碼（又稱檢錯糾錯編碼）
1、定義
指能夠發(fā)現(xiàn)或能夠自動糾正錯誤的數(shù)據(jù)編碼。
2、原理
通過增加一些冗余碼，來檢驗和糾錯編碼。
3、碼距
任意兩個合法碼字之間最少變化的二進(jìn)制位數(shù)，稱為數(shù)據(jù)檢驗碼的碼距。
對于碼距不小于 2 的數(shù)據(jù)檢驗碼，開始具有檢錯能力。
碼距越大，檢錯糾錯能力就越強(qiáng)，而且檢錯能力總是大于等于糾錯能力。
如：
（1）1100 和 1101 之間的碼距為1（因為只有最低位翻轉(zhuǎn)了）?
（2）1100 和 1011 之間的碼距為3（因為低 3 位翻轉(zhuǎn)了）
二、奇偶校驗碼
1、定義與實現(xiàn)方法
（1）定義
在原編碼上加一個校驗位，它的碼距等于 2，可檢測出一位錯誤（或奇數(shù)位錯誤），但不能確定出錯的位置，也不能檢測出偶數(shù)位錯誤，增加的冗余位稱為奇偶校驗位。
| 奇偶校驗碼的格式 | |
| 奇偶校驗位 | 有效信息位 |
| 1位 | ?n 位 |
?（2）實現(xiàn)方法
由若干位有效信息（如 1 B）再加上一個二進(jìn)制位（校驗位）組成校驗碼，如上圖。校驗位的取值（ 0 或 1 ）將使整個校驗碼中的 “ 1 ” 的個數(shù)為奇數(shù)或偶數(shù)。
2、奇偶校驗碼的校驗規(guī)律
| 整個校驗碼（有效信息位和校驗位）中 “ 1 ”的個數(shù) | |
| 奇校驗碼 | 奇數(shù) |
| 偶校驗碼 | 偶數(shù) |
3、缺點
?具有局限性，奇偶校驗只能發(fā)現(xiàn)數(shù)據(jù)代碼中奇數(shù)位的出錯情況，但不能糾正錯誤，常用于對存儲器數(shù)據(jù)的檢查或傳輸數(shù)據(jù)的檢查。
4、用習(xí)題理解概念
例1 ： 給出兩個編碼 100 1101 和 101 0111 的奇校驗碼和偶校驗碼。
解：設(shè)最高位為校驗位，余 7 位是信息位，則對應(yīng)的奇偶校驗碼為：
三、海明校驗碼
1、實現(xiàn)原理
在有效信息位中加入幾個校驗位形成海明碼（又稱漢明碼），并把海明碼的每個二進(jìn)制位分配到幾個奇偶校驗組中。當(dāng)某一位出錯后，就會引起有關(guān)的幾個校驗位的值發(fā)生變化。（即可發(fā)現(xiàn)錯位，也可指出錯位的位置，為自動糾錯提供依據(jù)）
2、糾錯理論【?L - 1 = D + C，且 D >= C】
編碼最小碼距 L 越大，其檢測的錯誤的位數(shù) D 越大，糾正錯誤的位數(shù) C 也越大，且糾錯能力小于等于檢錯能力。
3、求解海明碼的步驟
假設(shè)：海明碼為?
信息位（n）為?
校驗位（k）為?
| 步驟（共五步） | 說明 |
| （1）確定海明碼的位數(shù) | 設(shè) n 為有效信息的位數(shù)，k 為檢驗位的位數(shù)，則需滿足? （若要檢測 2 位錯，則需再增加 1 位校驗位，即 k+1 位） |
| （2）確定校驗位的分布 | 規(guī)定校驗位? |
| （3）分組以形成校驗關(guān)系 | 每個數(shù)據(jù)位用多個校驗位進(jìn)行校驗，要滿足：被校驗數(shù)據(jù)位的海明位號等于校驗該數(shù)據(jù)位的各校驗位海明位號之和。（校驗位不需要再被校驗） |
| （4）校驗位取值 | 校驗位 0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同為0，異為1） |
| （5）海明碼的校驗原理 | 每個校驗組分別利用校驗位和參與形成該校驗位的信息位進(jìn)行奇偶校驗檢查，構(gòu)成 k 個校驗方程。 |
4、用習(xí)題理解概念
例2 ： 在 n = 4、k = 3 時，求 1010 的海明碼。
解：如下圖
四、CRC（循環(huán)冗余校驗碼）
1、基本思想
在 K 位信息碼后再拼接 R 位的校驗碼，整個編碼長度為 N 位，因此，CRC 又稱 （N , K）碼。
2、用習(xí)題理解概念
例3：設(shè)生成多項式為??
?，信息碼為10 1001，求對應(yīng)的 CRC 碼。
解：如下圖
五、習(xí)題（含真題）
1、用海明碼對長度為 8 位的數(shù)據(jù)進(jìn)行檢錯、糾錯時，若能糾正一位錯則校驗位數(shù)至少為 （? ? ?C? ?）?
A. 2? ? ? ? ? ? ? ? ? ? ? ? ? ? ? B. 3? ? ? ? ? ? ? ? ? ? ? ? ? C. 4? ? ? ? ? ? ? ? ? ? ? ? ? ?D. 5
解：設(shè)校驗位的位數(shù)為 k ，數(shù)據(jù)位的位數(shù)為 n ，海明碼能糾正一位錯應(yīng)滿足關(guān)系?
。當(dāng) n = 8 時，當(dāng) k = 4 時滿足關(guān)系式，有?
，即 校驗位至少是 4 位。
?2、設(shè)在網(wǎng)絡(luò)中傳送采用偶校驗的 ASCII 碼，當(dāng)收到的數(shù)據(jù)位為 10101001 時，可以斷定（? ? ?C? ?）
A. 未出錯? ? ? ? ? ? B. 出現(xiàn)偶數(shù)位錯? ? ? ? ? C. 未出錯或出現(xiàn)偶數(shù)位錯? ? ? ? ? D. 出現(xiàn)奇數(shù)位錯
解：一位奇偶校驗碼只能發(fā)現(xiàn)奇數(shù)位錯誤。
本題中，收到的數(shù)據(jù)中有偶數(shù)個 1（即4個“1”），這樣可能沒有出錯，也可能出現(xiàn)了偶數(shù)位錯誤。（奇偶校驗碼無法發(fā)現(xiàn)偶數(shù)位錯）
3、能發(fā)現(xiàn)兩位錯誤，并能糾正 1 位錯的編碼的是（? ?B? ?）
A. CRC 碼? ? ? ? ? ? ? ? B. 海明碼? ? ? ? ? ? ? C. 奇校驗? ? ? ? ? ? ? ? ?D. 偶校驗碼
解： （1）奇偶校驗碼都不能糾錯。
（2）CRC 碼可以發(fā)現(xiàn)并糾正信息串行讀 / 寫、存儲或傳送中出現(xiàn)的一位或多位錯（與多項式的選取有關(guān)）
（3）海明碼能發(fā)現(xiàn)兩位錯誤，并糾正 1 位錯。