简述crc的纠错原理

Python09

简述crc的纠错原理,第1张

在接收端收到了CRC码后用生成多项式为G(x)去做模2除,若得到余数为0,则码字无误。若如果有一位出错,则余数不为0,而且不同位出错,其余数也不同。可以证明,余数与出错位的对应关系只与码制及生成多项式有关,而与待测码字(信息位)无关。图10给出了G(x)=1011,C(x)=1010的出错模式,改变C(x)(码字),只会改变表中码字内容,不改变余数与出错位的对应关系。

‍‍‍‍

图10 (7,4)CRC码的出错模式(G(x)=1011)

如果循环码有一位出错,用G(x)作模2除将得到一个不为0的余数。如果对余数补0继续除下去,我们将发现一个有趣的结果;各次余数将按图10顺序循环。例如第一位出错,余数将为001,补0后再除(补0后若最高位为1,则用除数做模2减取余;若最高位为0,则其最低3位就是余数),得到第二次余数为010。以后继续补0作模2除,依次得到余数为100,0ll…,反复循环,这就是“循环码”名称的由来。这是一个有价值的特点。如果我们在求出余数不为0后,一边对余数补0继续做模2除,同时让被检测的校验码字循环左移。图10说明,当出现余数(101)时,出错位也移到A7位置。可通过异或门将它纠正后在下一次移位时送回A1。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件。当位数增多时,循环码校验能有效地降低硬件代价,这是它得以广泛应用的主要原因。

【例】对图10的CRC码(G(x)=1011,C(x)=1010),若接收端收到的码字为1010111,用G(x)=1011做模2除得到一个不为0的余数100,说明传输有错。将此余数继续补0用G(x)=1011作模2除,同时让码字循环左移1010111。做了4次后,得到余数为101,这时码字也循环左移4位,变成1111010。说明出错位已移到最高位A7,将最高位1取反后变成0111010。再将它循环左移3位,补足7次,出错位回到A3位,就成为一个正确的码字1010011。

光盘或安装文件坏了,无法读取,就出现crc错误,很常见的。

-

crc数据校验的一种算法.

循环冗余校验(Cyclic

Redundancy

Check)

这是利用除法及余数的原理来进行错误检测的.将接收到的码组进行除法运算,如果除尽,则说明传输无误;如果未除尽,则表明传输出现差错。crc校验具还有自动纠错能力。