各種校驗碼校驗算法分析

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

2、011仍是表中的合法碼字接收機仍將認(rèn)為011是正確的信息。 然而如果用四個二進(jìn)數(shù)字來編8個碼字那么在碼字間的最小距離可以增加到2如圖2的表中所示。 信息序號 二進(jìn)碼字 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 信息序號 二進(jìn)碼字 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-2的8個碼字相互間最少有兩bit的差異。因此如果任何信息

3、的一個數(shù)位被顛倒就成為一個不用的碼字接收機能檢查出來。例如信息是1001誤收為1011接收機知道發(fā)生了一個差錯因為1011不是一個碼字表中沒有。然而差錯不能被糾正。假定只有一個數(shù)位是錯的正確碼字可以是100111110011或1010。接收者不能確定原來到底是這4個碼字中的那一個。也可看到 在這個系統(tǒng)中偶數(shù)個2或4差錯也無法發(fā)現(xiàn)。 為了使一個系統(tǒng)能檢查和糾正一個差錯碼間最小距離必須至少是“3”。最小距離為3時或能糾正一個錯或能檢二個錯但不能同時糾一個錯和檢二個錯。編碼信息糾錯和檢錯能力的進(jìn)一步提高需要進(jìn)一步增加碼字間的最小距離。 圖8-3的表概括了最小距離為1至7的碼的糾錯和檢錯能力。 碼距

4、碼 能 力 檢錯 糾錯 1 2 3 4 5 6 7 0 0 1 0 2 或 1 2 加 1 2 加 2 3 加 2 3 加 3 圖3 碼距越大糾錯能力越強但數(shù)據(jù)冗余也越大即編碼效率低了。所以選擇碼距要取決于特定系統(tǒng)的參數(shù)。數(shù)字系統(tǒng)的設(shè)計者必須考慮信息發(fā)生差錯的概率和該系統(tǒng)能容許的最小差錯率等因素。要有專門的研究來解決這些問題。 二、奇偶校驗 奇偶校驗碼是一種增加二進(jìn)制傳輸系統(tǒng)最小距離的簡單和廣泛采用的方法。例如單個的奇偶校驗將使碼的最小距離由一增加到二。 一個二進(jìn)制碼字如果它的碼元有奇數(shù)個1就稱為具有奇性。例如碼字“10110101”有五個1因此這個碼字具有奇性。同樣偶性碼字具有偶數(shù)個1。注意

5、奇性檢測等效于所有碼元的模二加并能夠由所有碼元的異或運算來確定。對于一個n位字奇性由下式給出 奇性a0a1a2an 奇偶校驗可描述為給每一個碼字加一個校驗位用它來構(gòu)成奇性或偶性校驗。例如在圖8-2中就是這樣做的?？梢钥闯龈郊哟a元d2是簡單地用來使每個字成為偶性的。因此若有一個碼元是錯的就可以分辨得出因為奇偶校驗將成為奇性。奇偶校驗編碼通過增加一位校驗位來使編碼中1個個數(shù)為奇數(shù)奇校驗或者為偶數(shù)偶校驗從而使碼距變?yōu)?。因為其利用的是編碼中1的個數(shù)的奇偶性作為依據(jù)所以不能發(fā)現(xiàn)偶數(shù)位錯誤。 再以數(shù)字0的七位ASCII碼0110000為例如果傳送后右邊第一位出錯0變成1。接收端還認(rèn)為是一個合法的代碼01

6、10001數(shù)字1的ASCII碼。若在最左邊加一位奇校驗位編碼變?yōu)?0110000如果傳送后右邊第一位出錯則變成101100011的個數(shù)變成偶數(shù)就不是合法的奇校驗碼了。但若有兩位假設(shè)是第1、2位出錯就變成101100111的個數(shù)為5還是奇數(shù)。接收端還認(rèn)為是一個合法的代碼數(shù)字3的ASCII碼。所以奇偶校驗不能發(fā)現(xiàn)。 奇偶校驗位可由硬件電路異或門或軟件產(chǎn)生 偶校驗位 an a0a1a2an-1 奇校驗位 an NOTa0a1a2an-1。 在一個典型系統(tǒng)里在傳輸以前由奇偶發(fā)生器把奇偶校驗位加到每個字中。原有信息中的數(shù)字在接收機中被檢測 如果沒有出現(xiàn)正確的奇、偶性這個信息標(biāo)定為錯誤的這個系統(tǒng)將把錯誤的

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

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

9、 位 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 X6 X7 X8 處的比特分別為 _ X9 X10 XI1 X12 處的比特分別為 _38_ Y1 和 Y2 處的字符分別為 _39_ 和 _40_ 。 解 從ASCII碼左起第5列可知垂直為偶校驗。則 從第1列可知X40從第3行可

10、知水平也是偶校驗。 從第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碼是100010044H推得 40 由字符Y2的ASCII碼011011137H知道Y2即是“7”由“3”的ASCII碼是011001133H推得 假如你能

11、記住“0”的ASCII碼是011000030H“A”的ASCII碼是100000141H則解起來就更方便了。 三、海明校驗 我們在前面指出過要能糾正信息字中的單個錯誤所需的最小距離為3。實現(xiàn)這種糾正的方法之一是海明碼。 海明碼是一種多重復(fù)式奇偶檢錯系統(tǒng)。它將信息用邏輯形式編碼以便能夠檢錯和糾錯。用在海明碼中的全部傳輸碼字是由原來的信息和附加的奇偶校驗位組成的。每一個這種奇偶位被編在傳輸碼字的特定位置上。實現(xiàn)得合適時這個系統(tǒng)對于錯誤的數(shù)位無論是原有信息位中的還是附加校驗位中的都能把它分離出來。 推導(dǎo)并使用長度為m位的碼字的海明碼所需步驟如下 1、確定最小的校驗位數(shù)k將它們記成D1、D2、Dk每個

12、校驗位符合不同的奇偶測試規(guī)定。 2、原有信息和k個校驗位一起編成長為mk位的新碼字。選擇k校驗位0或1以滿足必要的奇偶條件。 3、對所接收的信息作所需的k個奇偶檢查。 4、如果所有的奇偶檢查結(jié)果均為正確的則認(rèn)為信息無錯誤。 如果發(fā)現(xiàn)有一個或多個錯了則錯誤的位由這些檢查的結(jié)果來唯一地確定。 校驗位數(shù)的位數(shù) 推求海明碼時的一項基本考慮是確定所需最少的校驗位數(shù)k?？紤]長度為m位的信息若附加了k個校驗位則所發(fā)送的總長度為mk。在接收器中要進(jìn)行k個奇偶檢查每個檢查結(jié)果或是真或是偽。這個奇偶檢查的結(jié)果可以表示成一個k位的二進(jìn)字它可以確定最多2k種不同狀態(tài)。 這些狀態(tài)中必有一個其所有奇偶測試試都是真的它便是

13、判定信息正確的條件。于是剩下的2k-1種狀態(tài)可以用來判定誤碼的位置。于是導(dǎo)出下一關(guān)系 2k-1mk 碼字格式 從理論上講校驗位可放在任何位置但習(xí)慣上校驗位被安排在1、2、4、8、的位置上。 圖5列出了m4k3時信息位和校驗位的分布情況。 碼字位置 B1 B2 B3 B4 B5 B6 B7 校驗位 x x x 信息位 x x x x 復(fù)合碼字 P1 P2 D1 P3 D2 D3 D4 圖5 海明碼中校驗位和信息位的定位 校驗位的確定 k個校驗位是通過對mk位復(fù)合碼字進(jìn)行奇偶校驗而確定的。 其中P1位負(fù)責(zé)校驗海明碼的第1、3、5、7、P1、D1、D2、D4、位包括P1自己 P2負(fù)責(zé)校驗海明碼的第2

14、、3、6、7、P2、D1、D3、D4、位包括P2自己 P3負(fù)責(zé)校驗海明碼的第4、5、6、7、P3、D2、D3、D4、位包括P3自己 對m4k3偶校驗的例子只要進(jìn)行式次偶性測試。這些測試以A、B、C表示在圖6所示各位的位置上進(jìn)行。 奇偶條件 碼 字 位 置 1 2 3 4 5 6 7 A B C x x x x x x x x x x x x 圖6 奇偶校驗位置 因此可得到三個校驗方程及確定校驗位的三個公式 AB1B3B5B70 得P1D1D2D4 BB2B3B6B70 得P2D1D3D4 CB4B5B6B70 得P3D2D3D4 若四位信息碼為1001利用這三個公式可求得三個校驗位P1、P2、

15、P3值。和海明碼如圖7則表示了信息碼為1001時的海明碼編碼的全部情況。而圖8中則列出了全部16種信息D1D2D3D400001111的海明碼。 碼字位置 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

16、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 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 未編碼信息的海明碼 上面是發(fā)送方的處理 在接收方也可根據(jù)這三個校驗方程對接收到的信息進(jìn)行同樣的奇偶測試 AB1B3B5B70 BB2B3B6B70 CB4B5B5B70。 若三個校驗方程都成立即方程式右邊都等于0則說明沒有錯。若不成立即方程式右邊不等于0說明有錯。從三個方程式右邊的值可以判斷那一位出錯。例如如

17、果第3位數(shù)字反了則C0此方程沒有B3AB1這兩個方程有B3?？蓸?gòu)成二進(jìn)數(shù)CBA以A為最低有效位則錯誤位置就可簡單地用二進(jìn)數(shù)CBA011指出。 同樣若三個方程式右邊的值為001說明第1位出錯。若三個方程式右邊的值為100說明第4位出錯。 海明碼的碼距應(yīng)該是3所以能糾正1位出錯。而奇偶校驗碼的碼距才是2只能發(fā)現(xiàn)1位出錯但不能糾正不知道那一位錯。無校驗的碼距是1它出任何一位出錯后還是合法代碼所以也就無法發(fā)現(xiàn)出錯。 這是關(guān)于海明碼的經(jīng)典說法即碼距為3可以發(fā)現(xiàn)2位或者糾正1位錯。應(yīng)滿足2k-1mk。 但在清華的王愛英主編的計算機組成與結(jié)構(gòu)該書已成為國內(nèi)的權(quán)威中還提出了一種碼距為4的海明碼可以發(fā)現(xiàn)2位并且

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

19、的校驗碼整個編碼長度為N位因此這種編碼又叫NK碼。對于一個給定的NK碼可以證明存在一個最高次冪為N-KR的多項式Gx。根據(jù)Gx可以生成K位信息的校驗碼而Gx叫做這個CRC碼的生成多項式。 校驗碼的具體生成過程為假設(shè)發(fā)送信息用信息多項式CX表示將Cx左移R位則可表示成Cx2R這樣Cx的右邊就會空出R位這就是校驗碼的位置。通過Cx2R除以生成多項式Gx得到的余數(shù)就是校驗碼。 幾個基本概念 1、多項式與二進(jìn)制數(shù)碼 多項式和二進(jìn)制數(shù)有直接對應(yīng)關(guān)系x的最高冪次對應(yīng)二進(jìn)制數(shù)的最高位以下各位對應(yīng)多項式的各冪次有此冪次項對應(yīng)1無此冪次項對應(yīng)0。可以看出x的最高冪次為R轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)有R1位。 多項式包括

20、生成多項式Gx和信息多項式Cx。 如生成多項式為Gxx4x3x1 可轉(zhuǎn)換為二進(jìn)制數(shù)碼11011。 而發(fā)送信息位 1111可轉(zhuǎn)換為數(shù)據(jù)多項式為Cxx3x2x1。 2、生成多項式 是接受方和發(fā)送方的一個約定也就是一個二進(jìn)制數(shù)在整個傳輸過程中這個數(shù)始終保持不變。 在發(fā)送方利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。 應(yīng)滿足以下條件 a、生成多項式的最高位和最低位必須為1。 b、當(dāng)被傳送信息CRC碼任何一位發(fā)生錯誤時被生成多項式做模2除后應(yīng)該使余數(shù)不為0。 c、不同位發(fā)生錯誤時應(yīng)該使余數(shù)不同。 d、對余數(shù)繼續(xù)做模2除應(yīng)使余數(shù)循環(huán)。

21、將這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的。但可以從有關(guān)資料查到常用的對應(yīng)于不同碼制的生成多項式如圖9所示 N K 碼距d Gx多項式 Gx 7 4 3 x3x1 1011 7 4 3 x3x21 1101 7 3 4 x4x3x21 11101 7 3 4 x4x2x1 10111 15 11 3 x4x1 10011 15 7 5 x8x7x6x41 111010001 31 26 3 x5x21 100101 31 21 5 x10x9x8x6x5x31 11101101001 63 57 3 x6x1 1000011 63 51 5 x12x10x5x4x21 1010000110101 1

22、041 1024 x16x15x21 11000000000000101 圖9 常用的生成多項式 3、模2除按位除 模2除做法與算術(shù)除法類似但每一位除減的結(jié)果不影響其它位即不向上一位借位。所以實際上就是異或。然后再移位移位做下一位的模2減。步驟如下 a、用除數(shù)對被除數(shù)最高幾位做模2減沒有借位。 b、除數(shù)右移一位若余數(shù)最高位為1商為1并對余數(shù)做模2減。若余數(shù)最高位為0商為0除數(shù)繼續(xù)右移一位。 c、一直做到余數(shù)的位數(shù)小于除數(shù)時該余數(shù)就是最終余數(shù)。 【例】1111000除以1101 1011商 1111000-被除數(shù) 1101 除數(shù) 010000 1101 01010 1101 111余數(shù) CRC碼

23、的生成步驟 1、將x的最高冪次為R的生成多項式Gx轉(zhuǎn)換成對應(yīng)的R1位二進(jìn)制數(shù)。 2、將信息碼左移R位相當(dāng)與對應(yīng)的信息多項式Cx2R 3、用生成多項式二進(jìn)制數(shù)對信息碼做模2除得到R位的余數(shù)。 4、將余數(shù)拼到信息碼左移后空出的位置得到完整的CRC碼。 【例】假設(shè)使用的生成多項式是Gxx3x1。4位的原始報文為1010求編碼后的報文。 解 1、將生成多項式Gxx3x1轉(zhuǎn)換成對應(yīng)的二進(jìn)制除數(shù)1011。 2、此題生成多項式有4位R1要把原始報文Cx左移3R位變成1010000 3、用生成多項式對應(yīng)的二進(jìn)制數(shù)對左移4位后的原始報文進(jìn)行模2除 1001-商 - 1010000 1011-除數(shù) - 1000

24、1011 - 011-余數(shù)校驗位 5、編碼后的報文CRC碼 1010000 011 - 1010011 CRC的和糾錯 在接收端收到了CRC碼后用生成多項式為Gx去做模2除若得到余數(shù)為0則碼字無誤。若如果有一位出錯則余數(shù)不為0而且不同位出錯其余數(shù)也不同?？梢宰C明余數(shù)與出錯位的對應(yīng)關(guān)系只與碼制及生成多項式有關(guān)而與待測碼字信息位無關(guān)。圖10給出了Gx1011Cx1010的出錯模式改變Cx碼字只會改變表中碼字內(nèi)容不改變余數(shù)與出錯位的對應(yīng)關(guān)系。 收到的CRC碼字 余數(shù) 出錯位 碼位 A7 A6 A5 A4 A3 A2 A1 正確 1 0 1 0 0 1 1 000 無 錯 誤 1 0 1 0 0 1

25、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 如果循環(huán)碼有一位出錯用Gx作模2除將得到一個不為0的余數(shù)。如果對余數(shù)補0繼續(xù)除下去我們將發(fā)現(xiàn)一個有趣的結(jié)果各次余數(shù)將按圖10順序循環(huán)。例如第一位出錯余數(shù)將為001補0后再除補0后若最高位為1則用除數(shù)做模2減取余若最高位為0則其最低3位就是余數(shù)得到第二次余數(shù)為010。以后繼續(xù)補0作模2除依次得到余數(shù)為

26、1000ll反復(fù)循環(huán)這就是“循環(huán)碼”名稱的由來。這是一個有價值的特點。如果我們在求出余數(shù)不為0后一邊對余數(shù)補0繼續(xù)做模2除同時讓被檢測的校驗碼字循環(huán)左移。圖10說明當(dāng)出現(xiàn)余數(shù)101時出錯位也移到A7位置?？赏ㄟ^異或門將它糾正后在下一次移位時送回A1。這樣我們就不必像海明校驗?zāi)菢佑米g碼電路對每一位提供糾正條件。當(dāng)位數(shù)增多時循環(huán)碼校驗?zāi)苡行У亟档陀布鷥r這是它得以廣泛應(yīng)用的主要原因。 【例】對圖10的CRC碼Gx1011Cx1010若接收端收到的碼字為1010111用Gx1011做模2除得到一個不為0的余數(shù)100說明傳輸有錯。將此余數(shù)繼續(xù)補0用Gx1011作模2除同時讓碼字循環(huán)左移1010111。

27、做了4次后得到余數(shù)為101這時碼字也循環(huán)左移4位變成1111010。說明出錯位已移到最高位A7將最高位1取反后變成0111010。再將它循環(huán)左移3位補足7次出錯位回到A3位就成為一個正確的碼字1010011。 通信與網(wǎng)絡(luò)中常用的CRC 在數(shù)據(jù)通信與網(wǎng)絡(luò)中通常k相當(dāng)大由一千甚至數(shù)千數(shù)據(jù)位構(gòu)成一幀而后采用CRC碼產(chǎn)生r位的校驗位。它只能檢測出錯誤而不能糾正錯誤。一般取r16標(biāo)準(zhǔn)的16位生成多項式有CRC-16x16x15x21 和 CRC-CCITTx16x15x21。 一般情況下r位生成多項式產(chǎn)生的CRC碼可檢測出所有的雙錯、奇數(shù)位錯和突發(fā)長度小于等于r的突發(fā)錯以及1-2-r-1的突發(fā)長度為r1的突發(fā)錯和1-2-r的突發(fā)長度大于r1的突發(fā)錯。例如對上述r16的情況就能檢測出所有突發(fā)長度小于等于16的突發(fā)錯以及99997的突發(fā)長度為17