CRC的譯碼與糾錯
加入技術交流群
將收到的循環校驗碼用約定的生成多項式G(x)去除,如果碼字無誤則余數應為0,如有某一位出錯,則余數不為0,且不同數位出錯余數會不同。我們通過上例求出其出錯模式，如表2-4所示。更換不同的待測碼字可以證明：余數與出錯位的對應關系是不變的，只與碼制和生成多項式有關。因此表2.4給出的關系可作為系統線性(7,4)分組碼的出錯判別依據。對于其他碼制或選用其他生成多項式，出錯模式將發生變化。
表2.4 (7,4)循環碼的出錯模式 ( 生成多項式G(x)=1011 )
A1 A2 A3 A4 A5 A6 A7 | 余數 | 出錯位 | |
正確 | |||
錯誤 | 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 |
如果循環碼有一位出錯，用G(x)作模2除將得到一個不為0的余數。如果對余數補0繼續除下去,我們將發現一個有趣的結果：各次余數將按表2.4中的內容順序循環。例如第七位出錯，余數將為001，補0后再除，第二次余數為010，以后依次為100，011，…,反復循環。這是一個有價值的特點。如果我們在求出余數不為0之后,一邊對余數補0繼續做模2除，同時讓被檢測的校驗碼字循環左移。表2.4說明,當出現余數(101)時,出錯位也移到A1位置。可通過異或門將它糾正后在下一次移位時送回A7。繼續移滿一個循環(對7,4碼共移七次)，就得到一個糾正后的碼字。這樣我們就不必像海明校驗那樣用譯碼電路對每一位提供糾正條件。當數據位數增多時，循環碼校驗能有效地降低硬件代價，這是它得以廣泛應用的主要原因。
關于生成多項式，并不是任何一個r次的多項式都可以作為生成多項式。從檢錯及糾錯的要求出發,生成多項式應能滿足下列要求:
(1) 任何一位發生錯誤應當使余數不為0；
(2) 不同位發生錯誤應當使余數不同；
(3) 對余數繼續作模2除,應使余數循環。
將這些要求反映為數學關系是比較復雜的，對一個(n,k)碼來說，可將(xn -1)分解為若干質因子式(注意是模2運算)，根據編碼所要求的碼距，選取合適的r值，選其中的一個因式或若干因式的乘積作為生成多項式，為r次多項式，且最高、最低位系數均為1。
例: x7-1=( x+1)(x3+x+1)(x3+x2+1) (模2運算)
選擇 G(x)= x+1 = 11，可構成(7,6)碼，只能判一位錯。
選擇 G(x)= x3+x+1=1011,或 x3+x2+1=1101,可構成(7,4)碼,能判兩位錯或糾一位錯。
選擇 G(x)=(x+1)(x3+x+1)=11101,可構成(7,3)碼,能判兩位錯并同時糾正一位錯。
對使用者來說，可從有關資料上查到對應于不同碼制的生成多項式，表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 | |
評論