CRC的譯碼與糾錯
加入技術(shù)交流群
將收到的循環(huán)校驗碼用約定的生成多項式G(x)去除,如果碼字無誤則余數(shù)應(yīng)為0,如有某一位出錯,則余數(shù)不為0,且不同數(shù)位出錯余數(shù)會不同。我們通過上例求出其出錯模式，如表2-4所示。更換不同的待測碼字可以證明：余數(shù)與出錯位的對應(yīng)關(guān)系是不變的，只與碼制和生成多項式有關(guān)。因此表2.4給出的關(guān)系可作為系統(tǒng)線性(7,4)分組碼的出錯判別依據(jù)。對于其他碼制或選用其他生成多項式，出錯模式將發(fā)生變化。
表2.4 (7,4)循環(huán)碼的出錯模式 ( 生成多項式G(x)=1011 )
A1 A2 A3 A4 A5 A6 A7 | 余數(shù) | 出錯位 | |
正確 | |||
錯誤 | 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 | 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 | 6 5 4 3 2 1 |
如果循環(huán)碼有一位出錯，用G(x)作模2除將得到一個不為0的余數(shù)。如果對余數(shù)補0繼續(xù)除下去,我們將發(fā)現(xiàn)一個有趣的結(jié)果：各次余數(shù)將按表2.4中的內(nèi)容順序循環(huán)。例如第七位出錯，余數(shù)將為001，補0后再除，第二次余數(shù)為010，以后依次為100，011，…,反復(fù)循環(huán)。這是一個有價值的特點。如果我們在求出余數(shù)不為0之后,一邊對余數(shù)補0繼續(xù)做模2除，同時讓被檢測的校驗碼字循環(huán)左移。表2.4說明,當出現(xiàn)余數(shù)(101)時,出錯位也移到A1位置。可通過異或門將它糾正后在下一次移位時送回A7。繼續(xù)移滿一個循環(huán)(對7,4碼共移七次)，就得到一個糾正后的碼字。這樣我們就不必像海明校驗?zāi)菢佑米g碼電路對每一位提供糾正條件。當數(shù)據(jù)位數(shù)增多時，循環(huán)碼校驗?zāi)苡行У亟档陀布鷥r，這是它得以廣泛應(yīng)用的主要原因。
關(guān)于生成多項式，并不是任何一個r次的多項式都可以作為生成多項式。從檢錯及糾錯的要求出發(fā),生成多項式應(yīng)能滿足下列要求:
(1) 任何一位發(fā)生錯誤應(yīng)當使余數(shù)不為0；
(2) 不同位發(fā)生錯誤應(yīng)當使余數(shù)不同；
(3) 對余數(shù)繼續(xù)作模2除,應(yīng)使余數(shù)循環(huán)。
將這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的，對一個(n,k)碼來說，可將(xn -1)分解為若干質(zhì)因子式(注意是模2運算)，根據(jù)編碼所要求的碼距，選取合適的r值，選其中的一個因式或若干因式的乘積作為生成多項式，為r次多項式，且最高、最低位系數(shù)均為1。
例: x7-1=( x+1)(x3+x+1)(x3+x2+1) (模2運算)
選擇 G(x)= x+1 = 11，可構(gòu)成(7,6)碼，只能判一位錯。
選擇 G(x)= x3+x+1=1011,或 x3+x2+1=1101,可構(gòu)成(7,4)碼,能判兩位錯或糾一位錯。
選擇 G(x)=(x+1)(x3+x+1)=11101,可構(gòu)成(7,3)碼,能判兩位錯并同時糾正一位錯。
對使用者來說，可從有關(guān)資料上查到對應(yīng)于不同碼制的生成多項式，表2.5僅給出了一部分。
表2.5 生成多項式
N | K | 碼距d | G(x)多項式 | G(x)二進制碼 |
3+x+1)或 (x3+x2+1)G(x)=G1(x)(x+1)=(x3+x+1)(x+1)或 (x3+x2+1)(x+1) | 1101 | |||
4+x+1)(x4+x+1)(x4+x3+x2+x+1) | 10111 | |||
7 | 5 | 5+x2+1)(x5+x2+1)(x5+x4+x3+x2+1) | 111010001 | |
| 26 21 | 5 | 4+x+1)(x4+x+1)(x6+x4+x+1) | 11101101001 | |
51 | 5 | 16+x15+x2+1) | 1010000110101 | |
評論