索阅 100例 首 页| 资 讯| 下 载| 论 坛| 博 客| Webinar| 高 校| 专 刊| 会展| EETV| 百科| 问答| 电路图| 工程师手册| Datasheet

EEPW首页 > 百科 > 循环冗余码

循环冗余码


贡献者:sdjntl    浏览:3448次    创建时间:2009-11-21

循环冗余码  奇偶校验码作为一种检错码虽然简单,但是漏检率太高。在计算机网络和数据通信中用得最广泛的检错码,是一种漏检率低得多也便于实现的循环冗余码 (Cyclic Redundancy Code, CRC),又称为多项式码。CRC的工作方法是在发送端产生一个冗余码,附加在信息位后面一起发送到接收端,接收端收到的信息按发送端形成循冗余码同样的算法进行校验,如果发现错误,则通知发送端重发。
  首先,任何一个由二进制数位串组成的代码,都可以惟一地与一个只含有0和1两个系数的多项式建立一一对应的关系。例如,代码1010111对应的多项式为X^6+X^4+X^2+X+1(这里的X^n表示x的n次方)。同样.多项式X^5+X^3+X^2+X+1对应的代码为101111。CRC码在发送端编码和接收端校验时,都可以利用事先约定的生成多项式G(X)来得到。目前广泛使用的生成多项式主要有以下四种:
  CRC12=X^12+X^11+X^3+X^2+1
  CRC16=X^16+X^15+X^2+1(IBM公司)
  CRC16=X^16+X^12+X^5+1(国际电报电话咨询委员会CCITT)
  CRC32=X^32+X^26+X^23+X^22+X^16+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1
  冗余码的计算方法是,先将信息码后面补0,补0的个数是生成多项式最高次幂减1;将补零之后的信息码除以G(X),注意除法过程中所用的减法是模2减法,即没有借位的减法,也就是异或运算。当被除数逐位除完时,得到比除数少一位的余数。此余数即为冗余位,将其添加在信息位后便构成CRC码字。
  例如,假设信息码字为11100011,生成多项式G(X)=X^5+X^4+X+1,计算CRC码字。
  G(X) = X^5+X^4+X+1,也就是110011,因为最高次是5,所以,在信息码字后补5个0,变为1110001100000。用1110001100000除以110011,余数为11010,即为所求的冗余位。
  因此发送出去的CRC码字为原始码字11100011末尾加上冗余位11010,即 1110001111010。接收端收到码字后,采用同样的方法验证,即将收到的码字G(X),发现余数是0,则认为码字在传输过程中没有出错。
  如果生成多项式选择得当,CRC是一种很有效的差错校验方法。理论上可以证明循环冗余校验码的检错能力有以下特点:
  (a)可检测出所有奇数个错误;
  (b)可检测出所有双比特的错误;
  (c)可检测出所有小于等于校验位长度的连续错误;
  (d)以相当大的概率检测出大于校验位长度的连续错误。


如果您认为本词条还有待完善,需要补充新内容或修改错误内容,请编辑词条     查看历史版本

开放分类
编码        FPGA    PLD    CPLD    

参考资料

贡献者
sdjntl    


本词条在以下词条中被提及:

关于本词条的评论共:(0条)
匿名不能发帖!请先 [ 登陆 ]