循環(huán)冗余校驗(yàn)的編碼方法比較及文化價(jià)值簡(jiǎn)析

張 銘，徐金宏

(揚(yáng)州職業(yè)大學(xué)，江蘇揚(yáng)州 225009)

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

1 編碼方法簡(jiǎn)述

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

1.1 除法編碼

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

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

式中Ci的值為0或1。

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

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

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

其編碼方法可表示為:

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

1.2 乘法編碼

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

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

1.3 CRC校驗(yàn)的原則

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

2 編碼方法的比較研究

2.1 編碼比較

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

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

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

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

2.2 對(duì)照樣本

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

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

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

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

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

從本質(zhì)上來(lái)說(shuō)，除法編碼與乘法編碼是相通的。當(dāng)然，這種相通并不是在“四則運(yùn)算”意義上的相通，而是在“?！边\(yùn)算意義上的相通。

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

2.3 比較結(jié)論

比較表1與表2，可得以下結(jié)論:

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

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

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

3 文化價(jià)值分析

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

3.1 經(jīng)濟(jì)價(jià)值

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

3.1.1 技術(shù)實(shí)現(xiàn)簡(jiǎn)易

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

3.1.2 編碼結(jié)構(gòu)巧妙

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

3.1.3 校驗(yàn)簡(jiǎn)潔高效

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

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

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

3.2 審美價(jià)值

3.2.1 奇異性審美

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

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

3.2.2 對(duì)稱(chēng)性審美

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

CRC碼之所以具有的左右循環(huán)對(duì)稱(chēng)的特點(diǎn)，這要?dú)w功于生成多項(xiàng)式G(x)。生成多項(xiàng)式G(x)可以看作是一種映射函數(shù)，通過(guò)它的映射，信息碼具備了循環(huán)整除的特點(diǎn)。這種審美價(jià)值是值得關(guān)注的。

3.3 認(rèn)知價(jià)值

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

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

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

［3］王愛(ài)英.計(jì)算機(jī)組成與結(jié)構(gòu)［M］.4版.北京:清華大學(xué)出版社，2007.

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

［5］徐紀(jì)敏.科學(xué)美學(xué)［M］.長(zhǎng)沙:湖南出版社，1991.