循環冗余校驗的編碼方法比較及文化價值簡析

張 銘，徐金宏

(揚州職業大學，江蘇揚州 225009)

在計算機的信息傳輸過程中，為了保證信息的正確可靠，人們采用了特定的編碼和校驗方法。當信息串行傳輸時，循環冗余校驗(以下簡稱CRC校驗)不啻是一種行之有效的方法。本文研究了采用CRC校驗時的除法編碼和乘法編碼方法，在比較了它們之間的相同和不同之后，特別地揭示了它們之間的內在聯系。然后從人文科學的角度簡述了CRC校驗的廣義文化價值。

1 編碼方法簡述

CRC校驗的基本理念:按照一定的規則在k位數據碼后綴入r位冗余碼，從而構成k+r位的CRC校驗碼，借以校驗通信過程中是否發生差錯。這里的r位冗余碼之碼值取決于生成多項式G(x)。CRC校驗的具體編碼過程又有除法編碼與乘法編碼之別。

1.1 除法編碼

在CRC校驗中，發送端的編碼大多采用除法編碼。其編碼方法如下:

(1)將待編碼的k位數據信息位表達為多項式M(x)形式:

式中Ci的值為0或1。

(2)將信息位組左移r位，即表示為多項式M(x)×xr，這時右邊將空出r位，以便放置r位冗余校驗位。

(3)選擇一個(r+1)次的生成多項式G(x)，對M(x)×xr作模2的除法運算，所得的余數R(x)就是冗余校驗位的值。

(4)將M(x)×xr與余數R(x)作模2的加法運算，即可構成(k+r)位的CRC碼。從總體效果上看，它相當于在原來的信息多項式M(x)后面拼接了r位冗余校驗位。

其編碼方法可表示為:

式中P(x)是商式，R(x)是余數。最后:

1.2 乘法編碼

信息的校驗編碼過程，實際上是將數據信息根據一定的規則進行某種運算的過程。根據CRC編碼和校驗原則——余數原則，還可以采用乘法編碼。其編碼方法是:將信息多項式M(x)和生成多項式G(x)做模2的乘法運算，所得結果就是CRC校驗碼。其編碼方法可以表示為:

顯然，這種方法更加直觀、簡潔、明快。在接收端的校驗過程與除法編碼校驗一樣，即用生成多項式G(x)做模2的除法運算。如果在傳輸過程中沒有發生錯誤的話，顯然是能夠整除的。

1.3 CRC校驗的原則

CRC校驗的目標是查錯與糾錯。在查錯方面:當在數據傳輸無誤時，接收端接收到的CRC校驗碼能夠被生成多項式整除(模2除)。我們還發現一個有趣的現象:CRC校驗碼取反碼以后，也是能夠被生成多項式整除。這個發現很重要，它是進行除法編碼與乘法編碼比較研究的重要依據之一。當數據位有任意一位出錯時，則CRC校驗碼不能被生成多項式模2整除，且當數據位循環移位時，其余數也隨之發生循環變化，這時可以用余數的變化去“跟蹤”出錯的數據位。這是查錯的基本思想。至于糾錯方面，則比較簡單，只要將錯誤位取反碼即可。

2 編碼方法的比較研究

2.1 編碼比較

為了比較除法編碼與乘法編碼結果的異同，同時為了避免復雜的運算掩蓋本文的核心內容，試取4位數據信息的全部16個碼字，生成多項式G(x)也只取最簡單的形式(1011)，由此得到的CRC(7，4)碼見表 1。

表1 CRC(7，4)碼的除法編碼與乘法編碼結果(G(x)=1011)

顯然，兩種方法的編碼結果總體來說是不同的，這種不同只是表面的。綜合CRC編碼的特征，可知它們之間有著本質的關聯和一致。只要通過適當的變化，充分利用其“循環”的特點，就可以揭示它們的內在的一致性。

表1中的第4列所謂“取反”是指將乘法編碼的結果取反。乘法和除法編碼的一致性大體有兩種情形:一是直接一致或循環移位一致;二是取反碼并循環移位一致。循環移位的比較依據是CRC碼的本質特征之一(這一操作的意義見下文)，取反碼的比較依據是基于模運算。

2.2 對照樣本

需要特別注意的是，表1中的第6列(以???標出)，有兩組數據，即1101和1111，用上述比較方法無法取得一致。是比較方法有問題還是編碼過程中固有的現象呢?為了更好地說明問題，不妨再用其它的生成多項式(比如G(x)=1101)編碼，并借以比較之。結果見表2。

在表2中第6列中，同樣出現了表1中類似的現象(以???標出)。

表2 CRC(7，4)碼的除法編碼與乘法編碼結果(G(x)=1101)

綜合表1和表2的結果表明，對于某一生成多項式而言，各有一對編碼無法取得一致。原因為在表1中，生成多項式(1011)與數據多項式(1101)的乘積是(1111111)。這是對應數據多項式與生成多項式一致時出現的“共軛”奇異映射。在表2中，生成多項式(1101)與數據多項式(1011)也出現了類似的情況。

同樣的情況也出現在CRC(7，3)碼中，生成多項式(11101)和(10111)也是一對“共軛”的多項式。它們對于特定數據組的編碼也會出現奇異映射(11000011)。由于生成多項式自身具有一定的特殊性，對于上述現象到目前為止只發現兩對。

從本質上來說，除法編碼與乘法編碼是相通的。當然，這種相通并不是在“四則運算”意義上的相通，而是在“?！边\算意義上的相通。

在實際通信過程中，人們普遍采用了除法編碼。這是因為除法編碼的CRC碼數據位和冗余校驗位相對集中，并出現在不同的字段上，它易于區分和提取，它的解碼時間比較短。但是，從編碼過程來看，對于同樣的數據位而言，除法編碼所需要的操作明顯多于乘法編碼，這就是說，除法編碼是以犧牲發送端的信道編碼時間來換取接收端的信息解碼時間的。

2.3 比較結論

比較表1與表2，可得以下結論:

(1)對于相同的生成多項式，相應的CRC校驗信息是成對出現的。在表1和表2中第2列除法編碼的碼點全部出現的第3列乘法編碼之中了，它們之間是1→1映射的。這就是說，CRC碼集具有自封閉性。

(2)在CRC(7，4)中，有3位冗余位。這3位冗余位出現的幾率是相等的。冗余碼點是23=8，在4位信息的編碼中，共有信息碼點24=16，CRC校驗是一種線性分組校驗。理論上說，冗余碼字的分組是均勻的，也就是說，它的出現幾率是相等的。從表1和表2中可知它們出現的幾率是16/8=2，即每一個冗余碼點都出現了2次。顯然，編碼方法不同，冗余位的出現幾率是相同的。

(3)在除法編碼與乘法編碼中，各自總有且只有一對數據信息，不管是移位還是取反移位，它們都無法取得一致。這是編碼方法自身的特點所產生的現象。

3 文化價值分析

“文化”是一個很大的，內涵十分豐富的概念。它具有物質的層面和精神的層面。信息傳輸的校驗(或者更廣義地包括計算機文化)，其物質層面的意義不必贅述，而它的精神層面，即人文科學層面的意義，通常人們似乎關注得不多。這里的文化價值分析，主要是從社會人文科學的三個不同層面來審視不同的CRC編碼與校驗的作用和意義。

3.1 經濟價值

CRC碼的編碼與校驗方法是近世代數的多項式理論對現代信息傳輸理論的一大貢獻。既經濟又巧妙。

3.1.1 技術實現簡易

雖然CRC編碼在數學原理上來說是復雜的，但是兩種編碼方法在技術上都是易于實現的。它既可以用軟件方式來實現，也可以用硬件方式來實現。為了追求高速度，人們更加青睞硬件方式。它與并行傳輸校驗的海明碼校驗方法相比較，顯得更具有經濟價值。

3.1.2 編碼結構巧妙

CRC碼的碼字結構是巧妙的，特別是除法編碼方法，它的冗余校驗位是在串行傳輸過程中經校驗電路自然而然形成的，并且數據位和冗余校驗位出在不同的字段上，它特別易于解碼，從而免去了煩瑣的信息判斷和識別過程。

3.1.3 校驗簡潔高效

就CRC(7，4)碼而言，它用3位冗余位去跟蹤7位信息的傳輸校驗，這顯然是簡潔高效的。

有比較，才有鑒別。CRC校驗的經濟高效與海明碼校方法不便于比較，因為一個是用于串行傳輸，另一個是用于并行傳輸。CRC的經濟高效可以和奇偶校驗相比較。

一維奇偶校驗，加入1位冗余位校驗后只能查出1位或奇數個錯誤，它沒有糾錯能力;二維奇偶校驗(縱橫奇偶校驗，n位并行，傳輸m位)，需加入n+m位冗余位，它的經濟代價太大。而CRC校驗，加入n位冗余位后，可以監視2n－1位，而且能夠糾正一位出錯的情況。

3.2 審美價值

3.2.1 奇異性審美

在自然科學美學中，審美價值有五大方面:簡潔、統一、對稱、奇異、思辨。CRC碼具有獨特的對稱審美價值，這個問題往往沒有得到足夠的關注。在表1中，任取CRC(7，4)碼的一個碼字，比如1001110，經6次循環左移位后，分別得到其余6 個碼字:0011101，0111010，1110100，1101001，1010011，0100111。我們發現，這6個碼字都是能夠被生成多項式G(x)=1011整除(模2除)的。這是一個有趣的現象。

經6次循環右移位后得到的新碼字，也具有這樣的特性，CRC(7，4)碼的任意一個碼字都具有這樣的特性，這不能不說CRC碼是獨具奇異美感的。

3.2.2 對稱性審美

CRC碼的對稱性審美價值，一方面表現在CRC碼除法編碼和乘法編碼的碼點分布的對稱性，詳見前文1.3之結論。另一方面，CRC碼左循環移位和右循環移位的對稱性。這一奇特的現象或許從另一個側面再度表明:在宏觀自然中宇稱是守恒的!

CRC碼之所以具有的左右循環對稱的特點，這要歸功于生成多項式G(x)。生成多項式G(x)可以看作是一種映射函數，通過它的映射，信息碼具備了循環整除的特點。這種審美價值是值得關注的。

3.3 認知價值

科學史，抑或廣義地說人類文化發展史表明，認識世界的途徑不是唯一的，解決問題的方法常常是多種多樣的。凡是科學的認知方法和解決問題的方法，它們常常是殊途而同歸、百慮而一致的。CRC碼的不同編碼方法(乘法編碼和除法編碼)，從一個側面反映了文化的多樣性和價值觀的多元性。

［1］姜楠.信息論與編碼理論［M］.北京:清華大學出版社，2010.

［2］宋鵬.信息論與編碼原理［M］.北京:電子工業出版社，2011.

［3］王愛英.計算機組成與結構［M］.4版.北京:清華大學出版社，2007.

［4］徐輔新.自然科學美學［M］.合肥:安徽教育出版社，1992.

［5］徐紀敏.科學美學［M］.長沙:湖南出版社，1991.