CRC的譯碼與糾錯(cuò)

表2.4 (7,4)循環(huán)碼的出錯(cuò)模式 ( 生成多項(xiàng)式G(x)=1011 )

　　如果循環(huán)碼有一位出錯(cuò)，用G(x)作模2除將得到一個(gè)不為0的余數(shù)。如果對(duì)余數(shù)補(bǔ)0繼續(xù)除下去,我們將發(fā)現(xiàn)一個(gè)有趣的結(jié)果：各次余數(shù)將按表2.4中的內(nèi)容順序循環(huán)。例如第七位出錯(cuò)，余數(shù)將為001，補(bǔ)0后再除，第二次余數(shù)為010，以后依次為100，011，…,反復(fù)循環(huán)。這是一個(gè)有價(jià)值的特點(diǎn)。如果我們?cè)谇蟪鲇鄶?shù)不為0之后,一邊對(duì)余數(shù)補(bǔ)0繼續(xù)做模2除，同時(shí)讓被檢測(cè)的校驗(yàn)碼字循環(huán)左移。表2.4說(shuō)明,當(dāng)出現(xiàn)余數(shù)(101)時(shí),出錯(cuò)位也移到A1位置。可通過(guò)異或門將它糾正后在下一次移位時(shí)送回A7。繼續(xù)移滿一個(gè)循環(huán)(對(duì)7,4碼共移七次)，就得到一個(gè)糾正后的碼字。這樣我們就不必像海明校驗(yàn)?zāi)菢佑米g碼電路對(duì)每一位提供糾正條件。當(dāng)數(shù)據(jù)位數(shù)增多時(shí)，循環(huán)碼校驗(yàn)?zāi)苡行У亟档陀布鷥r(jià)，這是它得以廣泛應(yīng)用的主要原因。

　　關(guān)于生成多項(xiàng)式，并不是任何一個(gè)r次的多項(xiàng)式都可以作為生成多項(xiàng)式。從檢錯(cuò)及糾錯(cuò)的要求出發(fā),生成多項(xiàng)式應(yīng)能滿足下列要求:
　　(1) 任何一位發(fā)生錯(cuò)誤應(yīng)當(dāng)使余數(shù)不為0；
　　(2) 不同位發(fā)生錯(cuò)誤應(yīng)當(dāng)使余數(shù)不同；
　　(3) 對(duì)余數(shù)繼續(xù)作模2除,應(yīng)使余數(shù)循環(huán)。

　　將這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的，對(duì)一個(gè)(n,k)碼來(lái)說(shuō)，可將(xn -1)分解為若干質(zhì)因子式(注意是模2運(yùn)算)，根據(jù)編碼所要求的碼距，選取合適的r值，選其中的一個(gè)因式或若干因式的乘積作為生成多項(xiàng)式，為r次多項(xiàng)式，且最高、最低位系數(shù)均為1。

　　例: x⁷-1=( x+1)(x³+x+1)(x³+x²+1) (模2運(yùn)算)
　　選擇 G(x)= x+1 = 11，可構(gòu)成(7,6)碼，只能判一位錯(cuò)。
　　選擇 G(x)= x³+x+1=1011,或 x³+x²+1=1101,可構(gòu)成(7,4)碼,能判兩位錯(cuò)或糾一位錯(cuò)。
　　選擇 G(x)=(x+1)(x³+x+1)=11101,可構(gòu)成(7,3)碼,能判兩位錯(cuò)并同時(shí)糾正一位錯(cuò)。

　　對(duì)使用者來(lái)說(shuō)，可從有關(guān)資料上查到對(duì)應(yīng)于不同碼制的生成多項(xiàng)式，表2.5僅給出了一部分。

表2.5 生成多項(xiàng)式