循环冗余校验码---CRC码

2011-07-03 16:51:16来源: 互联网 关键字:循环  循环冗余校验  冗余校验  校验码
二进制信息位串沿一条信号线逐位在部件之间或计算机之间传送称为串行传送。CRC(Cyclic Redundancy check)码可以发现并纠正信息串行读写、存储或传送过程中出现的一位、多位错误,因此在磁介质存储器读写和计算机之间通信方面得到广泛应用。

  CRC码一般是指k位信息码之后拼接r位校验码。应用CRC码的关键,是如何从k位信息位简便地得到r位校验位(编码)的值,以及如何判断k+r位的码字是否正确。下面仅就CRC码应用中的问题做简单介绍(有关的理论问题请参阅有关书籍)。

① CRC码的编码方法

  先介绍CRC码编码用到的模2除运算。

  模2运算是指以按位模2相加为基础的四则运算,运算时不考虑位间进位和借位。

  模2加减:即按位加,可用异或逻辑实现。模2加与模2减的结果相同,即
    0±0=0 0±1=1 1±0=1 1±1=0。两个相同的数据的模2和为0。

  模2乘:按模2加求部分积之和。
  例:    1010
        101
     
       1010
       0000
      1010
     
       100010

  模2除:按模2减(加)求部分余数。每求一位商应使部分余数减少一位。
  上商的原则是:当部分余数的最高位为1时,该位商取1;为0时,该位商取0。当部分的余数的位数小于除数的位数时,该余数即为最后余数。
  例如,


    

  下面介绍CRC码的编码方法。
  首先,可将待编码的k位有效信息位表达为多项式M(x)形式:
    M(x)= Ck-1xk-1 + Ck-2x k-2+…+Cixi+…+C1x1+C0
  式中Ci为0或1,x为伪变量,并用xi指明各位间的排列位置。

  若将信息位组左移r位,则可表示为多项式M(x) * xr ,这样就可以空出初值为0的r个校验位,即
      

  CRC码的码字,是用k个数据位拼接上r个校验位得到的。校验位的值,就是通过对多项式M(x) * xr除以生成多项式G(x)(特定的一个多项式)所得到的余式。为了得到r位余数(校验位),G(x)必须是r+1位的,即为r次的多项式。
设所得余数表达式为R(x),商为 Q(x),就有:
     M(x).xr / G(x) = Q(x) + R(x) / G(x)

  将r次余式直接拼接在源数据多项式的右侧,可写成M(x).xr + R(x),并可推导出:
     M(x).xr + R(x) = [ Q(x)* G(x) + R(x) ] + R(x)
             = [ Q(x)* G(x) ] + [ R(x)+R(x) ]
             = Q(X)* G(x)

  这证明所得到的CRC码字是一个可被G(x)(多项式)数码除尽的数码(多项式)。
  例:对四位源信息 1100,来求三个校验位的值,可选择生成多项式为 1011,则有:
     M(x) = x3 + x2 = 1100    (k = 4)
     M(x)*x3 = x6 + x5 = 1100000 (左移, r = 3位)
     G(x) = x3+ x + 1 =1011    (r+1 = 4位)

  

  所得到的码字(系统线性(7,4)分组码)为:
     M(x).x3 + R(x) = 1100000 + 010 = 1100010

关键字:循环  循环冗余校验  冗余校验  校验码

编辑:神话 引用地址:http://www.eeworld.com.cn/mndz/2011/0703/article_10440.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:CRC的译码与纠错
下一篇:海明校验码

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利
推荐阅读
全部
循环
循环冗余校验
冗余校验
校验码

小广播

独家专题更多

东芝在线展会——芯科技智社会创未来
东芝在线展会——芯科技智社会创未来
2017东芝PCIM在线展会
2017东芝PCIM在线展会
TI车载信息娱乐系统的音视频解决方案
TI车载信息娱乐系统的音视频解决方案
汇总了TI汽车信息娱乐系统方案、优质音频解决方案、汽车娱乐系统和仪表盘参考设计相关的文档、视频等资源
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2017 EEWORLD.com.cn, Inc. All rights reserved