張 銘，徐金宏

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

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

1 編碼方法簡述

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

1.1 除法編碼

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

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

式中Ci的值為0或1。

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

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

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

其編碼方法可表示為:

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

1.2 乘法編碼

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

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

1.3 CRC校驗的原則

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

2 編碼方法的比較研究

2.1 編碼比較

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

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

顯然，兩種方法的編碼結果總體來說是不同的，這種不同只是表面的。綜合CRC編碼的特征，可知它們之間有著本質的關聯(lián)和一致。只要通過適當?shù)淖兓浞掷闷洹把h(huán)”的特點，就可以揭示它們的內在的一致性。

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

2.2 對照樣本

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

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

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

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

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

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

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

2.3 比較結論

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

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

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

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

3 文化價值分析

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

3.1 經(jīng)濟價值

CRC碼的編碼與校驗方法是近世代數(shù)的多項式理論對現(xiàn)代信息傳輸理論的一大貢獻。既經(jīng)濟又巧妙。

3.1.1 技術實現(xiàn)簡易

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

3.1.2 編碼結構巧妙

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

3.1.3 校驗簡潔高效

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

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

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

3.2 審美價值

3.2.1 奇異性審美

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

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

3.2.2 對稱性審美

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

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

3.3 認知價值

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

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

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

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

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

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