各種校驗碼校驗算法分析

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ū)分開。例如

2、如果傳送信息 001而被誤收為 011因 011仍是表中的合法碼 字接收機(jī)仍將認(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-

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

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

5、 有奇數(shù)個 1就稱為具有奇性。例如碼字“10110101”有五個 1因此這個碼字具有奇性。同樣偶性碼字具有偶數(shù)個 1。注 意奇性檢測等效于所有碼元的模二加并能夠由所有碼元的 異或運算來確定。對于一個 n 位字奇性由下式給出 奇性 a0 a1 a2 an 奇偶校驗可描述為給每一個碼字加一個校驗位用它來構(gòu)成奇性或偶性校驗。例如在圖 8-2中就是這 樣做的?？梢钥闯龈郊哟a元 d2是簡單地用來使每個字成為 偶性的。因此若有一個碼元是錯的就可以分辨得出因為奇偶 校驗將成為奇性。奇偶校驗編碼通過增加一位校驗位來使編 碼中 1個個數(shù)為奇數(shù)奇校驗或者為偶數(shù)偶校驗從而使碼距變 為 2。因為其利用的是編碼中 1的

6、個數(shù)的奇偶性作為依據(jù)所 以不能發(fā)現(xiàn)偶數(shù)位錯誤。 再以數(shù)字 0的七位 ASCII 碼 0110000為例如果傳送后右邊第一位出錯 0變成 1。接收端 還認(rèn)為是一個合法的代碼 0110001數(shù)字 1的 ASCII 碼。若在 最左邊加一位奇校驗位編碼變?yōu)?10110000如果傳送后右邊 第一位出錯則變成 101100011的個數(shù)變成偶數(shù)就不是合法的 奇校驗碼了。但若有兩位假設(shè)是第 1、 2位出錯就變成 101100111的個數(shù)為 5還是奇數(shù)。接收端還認(rèn)為是一個合法 的代碼數(shù)字 3的 ASCII 碼。所以奇偶校驗不能發(fā)現(xiàn)。 奇偶 校驗位可由硬件電路異或門或軟件產(chǎn)生 偶校驗位 an a0 a1 a2 a

7、n-1 奇校驗位 an NOTa0 a1 a2 an-1。 在一個典型系統(tǒng)里在傳輸以前由奇偶發(fā)生器把奇偶校驗位 加到每個字中。原有信息中的數(shù)字在接收機(jī)中被檢測 如果 沒有出現(xiàn)正確的奇、偶性這個信息標(biāo)定為錯誤的這個系統(tǒng)將 把錯誤的字拋掉或者請求重發(fā)。 在實際工作中還經(jīng)常采用 縱橫都加校驗奇偶校驗位的編碼系統(tǒng) -分組奇偶校驗碼。 現(xiàn)在考慮一個系統(tǒng) 它傳輸若干個長度為 m 位的信息。如果把這些信息都編成每組 n 個信息的分組則在這些不同的信息 間也如對單個信息一樣能夠作奇偶校驗。圖 4中 n 個信息的 一個分組排列成矩形式樣并以橫向奇偶 HP 及縱向奇偶 VP 的 形式編出奇偶校驗位。 m位數(shù)字 橫

8、向奇偶位 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 縱向奇偶位 圖 4 用綜橫奇偶校驗的分組 奇偶校驗碼 研究圖 4可知分組奇偶校驗碼不僅能檢測許多 形式的錯誤。并且在給定的行或列中產(chǎn)生孤立的錯誤時還可 對該錯誤進(jìn)行糾正。 在初級程序員試題中早期也出現(xiàn)在程 序員試題中經(jīng)常有綜橫奇偶校驗的題目。一般解法應(yīng)該是這 樣先找一行或一列已知數(shù)據(jù)完整的確定出該行或列是奇校 驗還是偶校驗。并假設(shè)行與列都采用同一種校驗這個假設(shè)是 否正確在全部做

9、完后可以得到驗證。然后找只有一個未知數(shù) 的行或列根據(jù)校驗性質(zhì)確定該未知數(shù)這樣不斷做下去就能 求出所有未知數(shù)。 【例】 2001年初級程序員試題 由 6 個 字符的 7 位 ASCII 編碼排列再加上水平垂直奇偶校驗位 構(gòu)成下列矩陣最后一列為水平奇偶校驗位最后一行為垂直 奇偶校驗位 : 字符 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

10、 則 X1 X2 X3 X4 處的比特分別為 _36_ X5 X6X7 X8 處的比特分別為 _ X9 X10 XI1 X12 處的比特分 別為 _38_ Y1 和 Y2 處的字符分別為 _39_ 和_40_ 。 解 從 ASCII 碼左起第 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整理一下

11、 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 推得 假 如你能記住“0”的 ASCII 碼是 011000030H“A”的 ASCII 碼 是 100000141H 則解起來就更方便了。三、海明校驗 我們在前面指出過要能糾正信息字中的單個 錯誤所需的最小距離為 3

12、。實現(xiàn)這種糾正的方法之一是海明 碼。 海明碼是一種多重復(fù)式奇偶檢錯系統(tǒng)。它將信息用邏 輯形式編碼以便能夠檢錯和糾錯。用在海明碼中的全部傳輸 碼字是由原來的信息和附加的奇偶校驗位組成的。每一個這 種奇偶位被編在傳輸碼字的特定位置上。實現(xiàn)得合適時這個 系統(tǒng)對于錯誤的數(shù)位無論是原有信息位中的還是附加校驗 位中的都能把它分離出來。 推導(dǎo)并使用長度為 m 位的碼字的海明碼所需步驟如下 1、確定最小的校驗位數(shù) k 將它們記 成 D1、 D2、 、 Dk 每個校驗位符合不同的奇偶測試規(guī)定。 2、 原有信息和 k 個校驗位一起編成長為 mk 位的新碼字。 選擇 k 校驗位 0或 1以滿足必要的奇偶條件。 3、

13、對所接收的信息 作所需的 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)中必有 一個其所有奇偶測試試都是真的它便是判定信息正確的條 件。于是剩下的 2k-1種狀態(tài)可以用來判定誤碼的位置。于 是

14、導(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、 3、 6、 7、P

15、2、 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 奇偶校驗位置 因此可 得到三個校驗方程及確定校驗位的三個公式 AB1 B3 B5 B70 得 P1D1 D2 D4 BB2 B3 B6 B70 得 P2D1 D3 D4 CB4 B5 B6 B70 得 P3D2 D3

16、D4 若四位信息碼 為 1001利用這三個公式可求得三個校驗位 P1、 P2、 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

17、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 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)行同樣的奇偶測試 AB1 B3 B5 B70 BB2 B3 B6 B70 CB4 B5 B5 B70。 若三個校驗方程都成立

18、即方程式右邊都等于 0則說 明沒有錯。若不成立即方程式右邊不等于 0說明有錯。從三 個方程式右邊的值可以判斷那一位出錯。例如如果第 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)于海明

19、碼的經(jīng)典說法即碼距為 3可以發(fā)現(xiàn) 2位或者糾正 1位錯。應(yīng)滿足 2k-1mk。 但在清 華的王愛英主編的計算機(jī)組成與結(jié)構(gòu)該書已成為國內(nèi)的 權(quán)威中還提出了一種碼距為 4的海明碼可以發(fā)現(xiàn) 2位并且糾 正 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 也是給信息

20、碼加上幾位校驗碼以增加整個編碼系統(tǒng)的碼距和查錯糾錯能力。 CRC 的理論很復(fù)雜一般書上只介紹已有生成多項式后計算校 驗碼的方法。檢錯能力與生成多項式有關(guān)只能根據(jù)書上的結(jié) 論死記。 循環(huán)冗余校驗碼 CRC 的基本原理是在 K 位信息碼 后再拼接 R 位的校驗碼整個編碼長度為 N 位因此這種編碼又 叫 NK 碼。對于一個給定的 NK 碼可以證明存在一個最高次冪 為 N-KR 的多項式 Gx 。 根據(jù) Gx 可以生成 K 位信息的校驗碼而 Gx 叫做這個 CRC 碼的生成多項式。 校驗碼的具體生成過程 為假設(shè)發(fā)送信息用信息多項式 CX 表示將 Cx 左移 R 位則可表 示成 Cx2R 這樣 Cx 的

21、右邊就會空出 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位。 多項式包括生成多項式 Gx 和信息多項式 Cx 。 如生成多項式 為 Gxx4x3x1 可轉(zhuǎn)換為二進(jìn)制數(shù)碼 11011。 而發(fā)送信息位 1111可轉(zhuǎn)換為數(shù)據(jù)多項式為 Cxx3x2x1。 2、生成多項式 是 接受方和發(fā)送方的一個約定也就是一個二進(jìn)制數(shù)在整個

22、傳 輸過程中這個數(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)。 將 這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的。但可以從有關(guān)資料 查到常用的對應(yīng)于不同碼制的生成多項式如圖 9所示 N K 碼距 d Gx多項式 Gx 7 4 3 x3x1 1011 7 4 3 x3x21

23、 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 1041 1024 x16x15x21 11000000000000101 圖 9 常用的生成多項式 3、 模 2除按位 除 模 2除做法與算術(shù)除法類似但每一位除減的結(jié)果不影響 其它位即不向上

24、一位借位。所以實際上就是異或。然后再移 位移位做下一位的模 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碼的生成步驟 1、將 x 的最高冪次為R 的生成多項式 Gx 轉(zhuǎn)換成對應(yīng)的 R1 位二進(jìn)制數(shù)。 2、將信 息碼左移 R 位相當(dāng)與對應(yīng)的信息多項式 Cx2

25、R 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 1011 - 011-余 數(shù)校驗位 5、編碼后的報文 CRC

26、碼 1010000 011 - 1010011 CRC 的和糾錯 在接收端收到 了 CRC 碼后用生成多項式為 Gx 去做模 2 除若得到余數(shù)為 0 則碼字無誤。若如果有一位出錯則余數(shù)不為 0 而且不同位出 錯其余數(shù)也不同。可以證明余數(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 0 1

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

28、到第二次余數(shù)為 010。以后繼續(xù)補(bǔ) 0 作模 2 除依次得到 余數(shù)為 1000ll反復(fù)循環(huán)這就是“循環(huán)碼”名稱的由來。 這 是一個有價值的特點。如果我們在求出余數(shù)不為 0 后一邊對 余數(shù)補(bǔ) 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 用

29、Gx1011 做模 2 除得到一 個不為 0 的余數(shù) 100 說明傳輸有錯。將此余數(shù)繼續(xù)補(bǔ) 0 用 Gx1011 作模 2 除同時讓碼字循環(huán)左移 1010111。做了 4 次后 得到余數(shù)為 101 這時碼字也循環(huán)左移 4 位變成 1111010。說 明出錯位已移到最高位 A7 將最高位 1 取反后變成 0111010。 再將它循環(huán)左移 3 位補(bǔ)足 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 的突