理解循環冗余碼CRC

奇偶校驗碼作為一種檢錯碼雖然簡單,但是漏檢率太高。在計算機網絡和數據通信中用E得最廣泛的檢錯碼,是一種漏檢率低得多也便于實現的循環冗余碼CRC (Cyclic Redundancy .Code),CRC碼又稱為多項式碼。
任何一個由二進制數位串組成的代碼,都可以惟一地與一個只含有0和1兩個系數的多項式建立一一對應的關系。例如,代碼1010111對應的多項式為X₆+X₄+X₂+X+1,同樣.多項式X₅+X₃+X₂+X+1對應的代碼為101111。
CRC碼在發送端編碼和接收端校驗時,都可以利用事先約定的生成多項式G(X)來得到。 k位要發送的信息位可對應于一個(k-1)次多項式K(X),r位冗余位則對應于一個(r-1)次多項式R(X),由k位信息位后面加上r位冗余位組成的n=k+r位碼字則對應于一個(n-1)次多項式T(X)=X^r·K(X)+R(X)。例如

由信息位產生冗余位的編碼過程,就是已知K(X)求R(X)的過程。在CRC碼中可以通過找到一個特定的r次多項式G (X)(其最高項Xr的系數恒為1),然后用Xr·K(X)去除以G(X),得到的余式就是R(X)。特別要強調的是,這些多項式中的"+"都是模2加(也即異或運算);此外,這里的除法用的也是模2除法,即除法過程中用到的減法是模2減法,它和模2加法的運算規則一樣,都是異或運算,這是一種不考慮加法進位和減法借位的運算,即

0+O=0,0+1=1,1+0=1,1+1=0
0-0=0,0-1=1,1-0=1,1-1=0

在進行基于模2運算的多項式除法時,只要部分余數首位為1,便可上商1,否則上商0。然后按模2減法求得余數,該余數不計最高位。當被除數逐位除完時,最后得到比除數少一位的余數。此余數即為冗余位,將其添加在信息位后便構成CRC碼字。
仍以上例中K(X)=X⁶+X⁴+X³+1為例(即信息位為1011001),若G(X)=X⁴+X³+1
(對應代碼11001),取r=4,則X⁴·K(X)=X¹⁰+X⁸+X⁷+X⁴(對應代碼為0110010000),其由模2除法求余式R(X)的過程所示如下:

得到的最后余數為1010,這就是冗余位,對應R(X)=X3+X。
由于R(X)是X^r·K(X)除以G(X)的余式,那么下列關系式必然滿足
X^r·K(X)=G(X)Q(X)+R(X)
其中Q(X)為商式。根據模二運算規則R(X)+R(X)=0的特點,可將上式改記為

[X^r-K(X)+R(X)]/G(X)=Q(X)

即 T(X)/G(X)=Q(X)

由此可見,信道上發送的碼字多項式T(X)=Xr-K(X)+R(X)。若傳輸過程無錯，則接收方收到的碼字也對應于此多項式,也即接收到的碼字多項式能被G(X)整除。因而接收端的校驗過程就是將接收到的碼字多項式除以G(X)的過程。若余式為零則認為傳輸元差錯;若余式不為零則傳輸有差錯。

例如,前述例子中若碼字10110011010經傳輸后由于受噪聲的干擾,在接收端變成為10110011100,則求余式的除法如下:
求得的余式不為零,相當于在碼字上面半加上了差錯模式00000000110。差錯模式對應的多項式記為E(X),上例中E(X)=X2+X。有差錯時,接收端收到的不再是T(X),而是T(X)與E(X)之模二加,即
[T(X)+E(X)]/G(X)=T(X)/G(X)+E(X)/G(X)
若E(X)/G(X)=0,則這種差錯就能檢測出來;若E(X)/G(X)=0,那么由于接收到的碼字多項式仍然可被G(X)整除,錯誤就檢測不出來,也即發生了漏檢。

理論上可以證明循環冗余校驗碼的檢錯能力有以下特點:
(1)可檢測出所有奇數位錯。
(2)可檢測出所有雙比特的錯。
(3)可檢測出所有小于、等于校驗位長度的突發錯。

CRC碼是由r-K(X)除以某個選定的多項式后產生的,所以該多現式稱生成多項式。一般來說,生成多項式位數越多校驗能力越強。但并不是任何一個r+1位的二進制數都可以做生成多項式。目前廣泛使用的生成多項式主要有以下四種:

posted on 2008-08-04 16:57 王光平 閱讀(2191) 評論(0)  編輯 收藏 引用 所屬分類: 編程技術