1、各種校驗碼校驗算法分析 二進制數據經過傳送、存取等環 節會發生誤碼 1變成 0或 0變成 1這就有如何發現及糾正誤 碼的問題。所有解決此類問題的方法就是在原始數據數碼位 基礎上增加幾位校驗冗余位。一、碼距 一個編碼系統中任意兩個合法編碼碼字之間不同 的二進數位 bit 數叫這兩個碼字的碼距而整個編碼系統中任 意兩個碼字的的最小距離就是該編碼系統的碼距。 如圖 1所示的一個編碼系統用三個 bit 來表示八個不同信息中。在 這個系統中兩個碼字之間不同的 bit 數從 1到 3不等但最小 值為 1故這個系統的碼距為 1。如果任何碼字中一位或多位 被顛倒了結果這個碼字就不能與其它有效信息區分開。例如

2、如果傳送信息 001而被誤收為 011因 011仍是表中的合法碼 字接收機仍將認為 011是正確的信息。 然而如果用四個二 進數字來編 8個碼字那么在碼字間的最小距離可以增加到 2如圖 2的表中所示。 信息序號 二進碼字 a2 a1 a0 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 圖 1 信息序號 二進碼字 a3 a2 a1 a0 0 0 0 0 0 1 1 0 0 1 2 1 0 1 0 3 0 0 1 1 4 1 1 0 0 5 0 1 0 1 6 0 1 1 0 7 1 1 1 1 圖 2 注意圖 8-

3、2的 8個碼字相互間最少有兩 bit 的差異。因此如果任何信息的一個數位被顛倒就成為一個不 用的碼字接收機能檢查出來。例如信息是 1001誤收為 1011接收機知道發生了一個差錯因為 1011不是一個碼字表中沒二、奇偶校驗 奇偶校驗碼是一種增加二進制傳輸系統最小 距離的簡單和廣泛采用的方法。例如單個的奇偶校驗將使碼 的最小距離由一增加到二。 一個二進制碼字如果它的碼元 有奇數個 1就稱為具有奇性。例如碼字“10110101”有五個 1因此這個碼字具有奇性。同樣偶性碼字具有偶數個 1。注 意奇性檢測等效于所有碼元的模二加并能夠由所有碼元的 異或運算來確定。對于一個 n 位字奇性由下式給出 奇性

4、a0 a1 a2 an 奇偶校驗可描述為給每一個碼字加一個校驗位用它來構成奇性或偶性校驗。例如在圖 8-2中就是這 樣做的。可以看出附加碼元 d2是簡單地用來使每個字成為 偶性的。因此若有一個碼元是錯的就可以分辨得出因為奇偶 校驗將成為奇性。奇偶校驗編碼通過增加一位校驗位來使編 碼中 1個個數為奇數奇校驗或者為偶數偶校驗從而使碼距變 為 2。因為其利用的是編碼中 1的個數的奇偶性作為依據所 以不能發現偶數位錯誤。 再以數字 0的七位 ASCII 碼 0110000為例如果傳送后右邊第一位出錯 0變成 1。接收端 還認為是一個合法的代碼 0110001數字 1的 ASCII 碼。若在 最左邊加一

5、位奇校驗位編碼變為 10110000如果傳送后右邊 第一位出錯則變成 101100011的個數變成偶數就不是合法的 奇校驗碼了。但若有兩位假設是第 1、 2位出錯就變成 101100111的個數為 5還是奇數。接收端還認為是一個合法 的代碼數字 3的 ASCII 碼。所以奇偶校驗不能發現。 奇偶 校驗位可由硬件電路異或門或軟件產生 偶校驗位 an a0 a1 a2 an-1 奇校驗位 an NOTa0 a1 a2 an-1。 在一個典型系統里在傳輸以前由奇偶發生器把奇偶校驗位 加到每個字中。原有信息中的數字在接收機中被檢測 如果 沒有出現正確的奇、偶性這個信息標定為錯誤的這個系統將 把錯誤的字

6、拋掉或者請求重發。 在實際工作中還經常采用 縱橫都加校驗奇偶校驗位的編碼系統 -分組奇偶校驗碼。 現在考慮一個系統 它傳輸若干個長度為 m 位的信息。如果把這些信息都編成每組 n 個信息的分組則在這些不同的信息 間也如對單個信息一樣能夠作奇偶校驗。圖 4中 n 個信息的 一個分組排列成矩形式樣并以橫向奇偶 HP 及縱向奇偶 VP 的 形式編出奇偶校驗位。 m位數字 橫向奇偶位 n 個 碼 字 a1 a2 am-1 am HP1 b1 b2 bm-1 bm HP2 c1 c2 cm-1 c m HP3 n1 n2 nm -1 nm HPn VP1 VP2 VPm-1 VPm HPn1 縱向奇偶位

7、 圖 4 用綜橫奇偶校驗的分組 奇偶校驗碼 研究圖 4可知分組奇偶校驗碼不僅能檢測許多 形式的錯誤。并且在給定的行或列中產生孤立的錯誤時還可 對該錯誤進行糾正。 在初級程序員試題中早期也出現在程 序員試題中經常有綜橫奇偶校驗的題目。一般解法應該是這 樣先找一行或一列已知數據完整的確定出該行或列是奇校 驗還是偶校驗。并假設行與列都采用同一種校驗這個假設是 否正確在全部做完后可以得到驗證。然后找只有一個未知數 的行或列根據校驗性質確定該未知數這樣不斷做下去就能 求出所有未知數。 【例】 2001年初級程序員試題 由 6 個 字符的 7 位 ASCII 編碼排列再加上水平垂直奇偶校驗位 構成下列矩陣

8、最后一列為水平奇偶校驗位最后一行為垂直 奇偶校驗位 : 字符 7 位 ASCII 碼 HP 3 0 X1 X2 0 0 1 1 0 Y1 1 0 0 1 0 0 X3 1 X4 1 0 1 0 1 1 0 Y2 0 1 X5 X6 1 1 1 1 D 1 0 0 X7 1 0 X8 0 0 X9 1 1 1 X10 1 1 VP 0 0 1 1 1 X11 1 X12 則 X1 X2 X3 X4 處的比特分別為 _36_ X5 X6X7 X8 處的比特分別為 _ X9 X10 XI1 X12 處的比特分 別為 _38_ Y1 和 Y2 處的字符分別為 _39_ 和_40_ 。 解 從 ASCI

9、I 碼左起第 5列可知垂直為偶校驗。 則 從第 1列可知 X40從第 3行可知水平也是偶校驗。 從第 2行可知 X31從第 7列可知 X80從第 8列可知 X121 從第 7行可知 X111從第 6列可知 X100從第 6行可知 X91從第 2列 可知 X11 從第 1行可知 X21從第 3列可知 X51從第 4行可知 X60 從第 4列或第 5行可知 X70整理一下 36 X1X2X3X4 1110 37 X5X6X7X8 1000 38 X9X10X11X12 1011 39 由字符 Y1的 ASCII 碼 100100149H 知道 Y1即是“I”由“D”的 ASCII 碼 是 1000

10、10044H 推得 40 由字符 Y2的 ASCII 碼 011011137H 知道 Y2即是“7”由“3”的 ASCII 碼是 011001133H 推得 假 如你能記住“0”的 ASCII 碼是 011000030H“A”的 ASCII 碼 是 100000141H 則解起來就更方便了。三、海明校驗 我們在前面指出過要能糾正信息字中的單個 錯誤所需的最小距離為 3。實現這種糾正的方法之一是海明 碼。 海明碼是一種多重復式奇偶檢錯系統。它將信息用邏 輯形式編碼以便能夠檢錯和糾錯。用在海明碼中的全部傳輸 碼字是由原來的信息和附加的奇偶校驗位組成的。每一個這 種奇偶位被編在傳輸碼字的特定位置上。

11、實現得合適時這個 系統對于錯誤的數位無論是原有信息位中的還是附加校驗 位中的都能把它分離出來。 推導并使用長度為 m 位的碼字的海明碼所需步驟如下 1、確定最小的校驗位數 k 將它們記 成 D1、 D2、 、 Dk 每個校驗位符合不同的奇偶測試規定。 2、 原有信息和 k 個校驗位一起編成長為 mk 位的新碼字。 選擇 k 校驗位 0或 1以滿足必要的奇偶條件。 3、對所接收的信息 作所需的 k 個奇偶檢查。 4、如果所有的奇偶檢查結果均為 正確的則認為信息無錯誤。 如果發現有一個或多個錯了則 錯誤的位由這些檢查的結果來唯一地確定。 校驗位數的位 數 推求海明碼時的一項基本考慮是確定所需最少的

12、校驗位 數 k 。考慮長度為 m 位的信息若附加了 k 個校驗位則所發送 的總長度為 mk 。 在接收器中要進行 k 個奇偶檢查每個檢查結 果或是真或是偽。這個奇偶檢查的結果可以表示成一個 k 位 的二進字它可以確定最多 2k 種不同狀態。 這些狀態中必有 一個其所有奇偶測試試都是真的它便是判定信息正確的條 件。于是剩下的 2k-1種狀態可以用來判定誤碼的位置。于 是導出下一關系 2k-1mk 碼字格式 從理論上講校驗位可 放在任何位置但習慣上校驗位被安排在 1、 2、 4、 8、的位 置上。 圖 5列出了 m4k3時信息位和校驗位的分布情況。 碼 字位置 B1 B2 B3 B4 B5 B6

13、B7 校驗位 x x x 信息位 x x x x 復合碼字 P1 P2 D1 P3 D2 D3 D4 圖 5 海明碼中校驗位和 信息位的定位 校驗位的確定 k個校驗位是通過對 mk 位復合 碼字進行奇偶校驗而確定的。 其中 P1位負責校驗海明碼的 第 1、 3、 5、 7、P1、 D1、 D2、 D4、位包括 P1自己 P2負責校驗海明碼的第 2、 3、 6、 7、P2、 D1、 D3、 D4、位 包括 P2自己 P3負責校驗海明碼的第 4、 5、 6、 7、P3、 D2、 D3、 D4、位包括 P3自己 對 m4k3偶校驗的例子只要 進行式次偶性測試。這些測試以 A 、 B 、 C 表示在圖

14、 6所示各 位的位置上進行。 奇偶條件 碼 字 位 置 1 2 3 4 5 6 7 A B C x x x x x x x x x x x x 圖 6 奇偶校驗位置 因此可 得到三個校驗方程及確定校驗位的三個公式 AB1 B3 B5 B70 得 P1D1 D2 D4 BB2 B3 B6 B70 得 P2D1 D3 D4 CB4 B5 B6 B70 得 P3D2 D3 D4 若四位信息碼 為 1001利用這三個公式可求得三個校驗位 P1、 P2、 P3值。 和海明碼如圖 7則表示了信息碼為 1001時的海明碼編碼的 全部情況。而圖 8中則列出了全部 16種信息 D1D2D3D400001111的

15、海明碼。 碼字位置 B1 B2 B3 B4 B5 B6 B7 碼位類型 P1 P2 D1 P3 D2 D3 D4 信息碼 - - 1 - 0 0 1 校驗位 0 0 - 1 - - - 編碼后的海明碼 0 0 1 1 0 0 1 圖 7 四位信息碼的海明編碼 P1 P2 D1 P3 D2 D3 D4 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0

16、 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 圖 8 未編碼信息的海明碼 上面是發送方的處理 在接收方也 可根據這三個校驗方程對接收到的信息進行同樣的奇偶測試 AB1 B3 B5 B70 BB2 B3 B6 B70 CB4 B5 B5 B70。 若三個校驗方程都成立即方程式右邊都等于 0則說 明沒有錯。若不成立即方程式右邊不等于 0說明有錯。從三 個方程式右邊的值可以判斷那一位出錯。例如如果第 3位數 字反了則 C0此方程沒有 B3AB1這兩個方程有 B3。可構成二 進數 CBA 以 A 為

17、最低有效位則錯誤位置就可簡單地用二進數 CBA011指出。 同樣若三個方程式右邊的值為 001說明第 1位出錯。 若三個方程式右邊的值為 100說明第 4位出錯。 海 明碼的碼距應該是 3所以能糾正 1位出錯。而奇偶校驗碼的 碼距才是 2只能發現 1位出錯但不能糾正不知道那一位錯。 無校驗的碼距是 1它出任何一位出錯后還是合法代碼所以也 就無法發現出錯。 這是關于海明碼的經典說法即碼距為 3可以發現 2位或者糾正 1位錯。應滿足 2k-1mk。 但在清 華的王愛英主編的計算機組成與結構該書已成為國內的 權威中還提出了一種碼距為 4的海明碼可以發現 2位并且糾 正 1位錯。應滿足 2k-1mk。

18、 由于王愛英書上對這兩種概 念沒有很仔細解釋特別對碼距為 3的海明碼過渡很突然。有 些書簡單抄襲時沒有仔細消化所以出現一些概念錯。對于一 般碼距為 3的海明碼應該是“可以發現 2位或者糾正 1位 錯”而不是“可以發現 2位并且糾正 1位錯”。在試題中出 現過類似的錯誤。 四、循環冗余校驗碼 在串行傳送磁盤、 通訊中廣泛采用循環冗余校驗碼 CRC 。 CRC 也是給信息碼加上幾位校驗碼以增加整個編碼系統的碼距和查錯糾錯能力。 CRC 的理論很復雜一般書上只介紹已有生成多項式后計算校 驗碼的方法。檢錯能力與生成多項式有關只能根據書上的結 論死記。 循環冗余校驗碼 CRC 的基本原理是在 K 位信息

19、碼 后再拼接 R 位的校驗碼整個編碼長度為 N 位因此這種編碼又 叫 NK 碼。對于一個給定的 NK 碼可以證明存在一個最高次冪 為 N-KR 的多項式 Gx 。 根據 Gx 可以生成 K 位信息的校驗碼而 Gx 叫做這個 CRC 碼的生成多項式。 校驗碼的具體生成過程 為假設發送信息用信息多項式 CX 表示將 Cx 左移 R 位則可表 示成 Cx2R 這樣 Cx 的右邊就會空出 R 位這就是校驗碼的位置。 通過 Cx2R 除以生成多項式 Gx 得到的余數就是校驗碼。 幾 個基本概念 1、多項式與二進制數碼 多項式和二進制數有 直接對應關系 x 的最高冪次對應二進制數的最高位以下各位 對應多項

20、式的各冪次有此冪次項對應 1無此冪次項對應 0。 可以看出 x 的最高冪次為 R 轉換成對應的二進制數有 R1位。 多項式包括生成多項式 Gx 和信息多項式 Cx 。 如生成多項式 為 Gxx4x3x1 可轉換為二進制數碼 11011。 而發送信息位 1111可轉換為數據多項式為 Cxx3x2x1。 2、生成多項式 是 接受方和發送方的一個約定也就是一個二進制數在整個傳 輸過程中這個數始終保持不變。 在發送方利用生成多項式 對信息多項式做模 2除生成校驗碼。在接受方利用生成多項 式對收到的編碼多項式做模 2除檢測和確定錯誤位置。 應R 的生成多項式 Gx 轉換成對應的 R1 位二進制數。 2、

21、將信 息碼左移 R 位相當與對應的信息多項式 Cx2R 3、用生成多項 式二進制數對信息碼做模 2 除得到 R 位的余數。 4、將余數 拼到信息碼左移后空出的位置得到完整的 CRC 碼。 【例】 假設使用的生成多項式是 Gxx3x1。4 位的原始報文為 1010 求編碼后的報文。 解 1、將生成多項式 Gxx3x1 轉換成對應 的二進制除數 1011。 2、此題生成多項式有 4 位 R1 要把原 始報文 Cx 左移 3R 位變成 1010000 3、用生成多項式對應的 二進制數對左移 4 位后的原始報文進行模 2 除 1001-商 - 1010000 1011-除 數 - 1000 1011

22、- 011-余 數校驗位 5、編碼后的報文 CRC 碼 1010000 011 - 1010011 CRC 的和糾錯 在接收端收到 了 CRC 碼后用生成多項式為 Gx 去做模 2 除若得到余數為 0 則碼字無誤。若如果有一位出錯則余數不為 0 而且不同位出 錯其余數也不同。可以證明余數與出錯位的對應關系只與碼 制及生成多項式有關而與待測碼字信息位無關。圖 10 給出 了 Gx1011Cx1010 的出錯模式改變 Cx 碼字只會改變表中碼字 內容不改變余數與出錯位的對應關系。 收到的 CRC 碼字 余 數 出錯位 碼位 A7 A6 A5 A4 A3 A2 A1 正確 1 0 1 0 0 1 1

23、 000 無 錯 誤 1 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 001 010 100 011 110 111 101 1 2 3 4 5 6 7 圖 10 74CRC 碼的出錯模式 Gx1011 如果循環碼有一位出錯用 Gx 作 模 2 除將得到一個不為 0 的余數。如果對余數補 0 繼續除下 去我們將發現一個有趣的結果各次余數將按圖 10 順序循環。 例如第一位出錯余數將為 001 補 0 后再除補 0 后若最高位為 1 則用除數做模 2

24、 減取余若最高位為 0 則其最低 3 位就是余 數得到第二次余數為 010。以后繼續補 0 作模 2 除依次得到 余數為 1000ll反復循環這就是“循環碼”名稱的由來。 這 是一個有價值的特點。如果我們在求出余數不為 0 后一邊對 余數補 0 繼續做模 2 除同時讓被檢測的校驗碼字循環左移。 圖 10 說明當出現余數 101 時出錯位也移到 A7 位置。可通過 異或門將它糾正后在下一次移位時送回 A1。 這樣我們就不必 像海明校驗那樣用譯碼電路對每一位提供糾正條件。當位數 增多時循環碼校驗能有效地降低硬件代價這是它得以廣泛 應用的主要原因。 【例】對圖 10 的 CRC 碼 Gx1011Cx1010 若接收端收到的碼字為 1010111 用 Gx1011 做模 2 除得到一 個不為 0 的余數 100 說明傳輸有錯。將此余數繼續補 0 用 Gx1011 作模 2 除同時讓碼字循環左移 1010111。做了 4 次后 得到余數為 101 這時碼字也循環左移 4 位變成 1111010。說 明出錯位已移到最高位 A7 將最高位 1 取反后變成 0111010。