循环冗余校验码---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
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
循环
循环冗余校验
冗余校验
校验码

小广播

独家专题更多

TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved