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 | |
评论