在串行傳送（磁盤、通訊）中，廣泛采用循環冗余校驗碼（CRC）。CRC也是給信息碼加上幾位校驗碼，以增加整個編碼系統的碼距和查錯糾錯能力。
CRC的理論很復雜，一般書上只介紹已有生成多項式后計算校驗碼的方法。檢錯能力與生成多項式有關，只能根據書上的結論死記。 循 環冗余校驗碼（CRC）的基本原理是：在K位信息碼后再拼接R位的校驗碼，整個編碼長度為N位，因此，這種編碼又叫（N，K）碼。對于一個給定的 （N，K）碼，可以證明存在一個最高次冪為N-K=R的多項式G(x)。根據G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRC碼的生成多項 式。 校驗碼的具體生成過程為：假設發送信息用信息多項式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R，這樣C(x)的右邊就會空出R位，這就是校驗碼的位置。通過C(x)*2R除以生成多項式G(x)得到的余數就是校驗碼。 幾個基本概念 1、多項式與二進制數碼 多項式和二進制數有直接對應關系：x的最高冪次對應二進制數的最高位，以下各位對應多項式的各冪次，有此冪次項對應1，無此冪次項對應0。可以看出：x的最高冪次為R，轉換成對應的二進制數有R+1位。 多項式包括生成多項式G(x)和信息多項式C(x)。 如生成多項式為G(x)=x4+x3+x+1， 可轉換為二進制數碼11011。 而發送信息位 1111，可轉換為數據多項式為C(x)=x3+x2+x+1。 2、生成多項式 是接受方和發送方的一個約定，也就是一個二進制數，在整個傳輸過程中，這個數始終保持不變。 在發送方,利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。 應滿足以下條件： a、生成多項式的最高位和最低位必須為1。 b、當被傳送信息（CRC碼）任何一位發生錯誤時，被生成多項式做模2除后應該使余數不為0。 c、不同位發生錯誤時，應該使余數不同。 d、對余數繼續做模2除，應使余數循環。 將這些要求反映為數學關系是比較復雜的。但可以從有關資料查到常用的對應于不同碼制的生成多項式如圖9所示：
N | K | 碼距d | G(x)多項式 | G(x) | 7 | 4 | 3 | | 1011 | 7 | 4 | 3 | | 1101 | 7 | 3 | 4 | | 11101 | 7 | 3 | 4 | | 10111 | 15 | 11 | 3 | | 10011 | 15 | 7 | 5 | | 111010001 | 31 | 26 | 3 | | 100101 | 31 | 21 | 5 | | | 63 | 57 | 3 | | | 63 | 51 | 5 | | | 1041 | 1024 | | | |
圖9 常用的生成多項式
3、模2除（按位除） 模2除做法與算術除法類似，但每一位除（減）的結果不影響其它位，即不向上一位借位。所以實際上就是異或。然后再移位移位做下一位的模2減。步驟如下： a、用除數對被除數最高幾位做模2減，沒有借位。 b、除數右移一位，若余數最高位為1，商為1，并對余數做模2減。若余數最高位為0，商為0，除數繼續右移一位。 c、一直做到余數的位數小于除數時，該余數就是最終余數。 【例】1111000除以1101： 1011———商 ———— 1111000-----被除數 1101———— 除數 ———— 010000 1101 ———— 01010 1101 ———— 111————余數 CRC碼的生成步驟 1、將x的最高冪次為R的生成多項式G(x)轉換成對應的R+1位二進制數。 2、將信息碼左移R位，相當與對應的信息多項式C(x)*2R 3、用生成多項式（二進制數）對信息碼做模2除，得到R位的余數。 4、將余數拼到信息碼左移后空出的位置，得到完整的CRC碼。 【例】假設使用的生成多項式是G(x)=x3+x+1。4位的原始報文為1010，求編碼后的報文。 解： 1、將生成多項式G(x)=x3+x+1轉換成對應的二進制除數1011。 2、此題生成多項式有4位（R+1），要把原始報文C(x)左移3（R）位變成1010000 3、用生成多項式對應的二進制數對左移4位后的原始報文進行模2除： 1001-------商 ------------------------ 1010000 1011----------除數 ------------ 1000 1011 ------------ 011-------余數（校驗位） 5、編碼后的報文（CRC碼）： 1010000 + 011 ------------------ 1010011 CRC的和糾錯 在 接收端收到了CRC碼后用生成多項式為G(x)去做模2除，若得到余數為0,則碼字無誤。若如果有一位出錯，則余數不為0，而且不同位出錯，其余數也不 同。可以證明，余數與出錯位的對應關系只與碼制及生成多項式有關，而與待測碼字（信息位）無關。圖10給出了G(x)＝1011，C(x)＝1010的出 錯模式，改變C(x)（碼字），只會改變表中碼字內容，不改變余數與出錯位的對應關系。
| | 余數 | 出錯位 | 碼位 | | 正確 | | 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 |
| | |
圖10 （7，4）CRC碼的出錯模式（G(x)＝1011） 如 果循環碼有一位出錯，用G(x)作模2除將得到一個不為0的余數。如果對余數補0繼續除下去，我們將發現一個有趣的結果；各次余數將按圖10順序循環。例 如第一位出錯，余數將為001，補0后再除（補0后若最高位為1，則用除數做模2減取余；若最高位為0，則其最低3位就是余數），得到第二次余數為 010。以后繼續補0作模2除，依次得到余數為100，0ll…，反復循環，這就是“循環碼”名稱的由來。這是一個有價值的特點。如果我們在求出余數不為 0后，一邊對余數補0繼續做模2除，同時讓被檢測的校驗碼字循環左移。圖10說明，當出現余數(101)時，出錯位也移到A7位置。可通過異或門將它糾正后在下一次移位時送回A1。這樣我們就不必像海明校驗那樣用譯碼電路對每一位提供糾正條件。當位數增多時，循環碼校驗能有效地降低硬件代價，這是它得以廣泛應用的主要原因。 【例】 對圖10的CRC碼（G(x)＝1011，C(x)＝1010），若接收端收到的碼字為1010111，用G(x)＝1011做模2除得到一個不為0的余 數100，說明傳輸有錯。將此余數繼續補0用G(x)＝1011作模2除，同時讓碼字循環左移1010111。做了4次后，得到余數為101，這時碼字也 循環左移4位，變成1111010。說明出錯位已移到最高位A7，將最高位1取反后變成0111010。再將它循環左移3位，補足7次，出錯位回到A3位，就成為一個正確的碼字1010011。
| 
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
