计算机体系结构(三)——循环冗余校验
计算机体系结构(三)——循环冗余校验
白志华 发表于2年前
计算机体系结构(三)——循环冗余校验
  • 发表于 2年前
  • 阅读 6
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

    在校验码体系中,有各种校验的方法:有奇偶校验、海明码校验、循环冗余校验。今天就跟大家共同探讨一下常用的循环冗余校验吧。

    循环冗余校验(CRC,Cyclic Redundancy Check),是最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。已经被广泛应用于网络通信即磁盘存储。

    多项式:一个二进制数可以用一个多项式来表示,如1011 表示为 x 3+x 1+x 。最高次幂n,可以转为长度为n+1的二进制数。

    CRC编码组成:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码又叫(N,K)码。

    生成多项式:编码方程除以信息码的多项式,得到余数多项式即为校验码,解码方程将接收到的信息除以生成多项式,若余数=0,则说明正确,反则,则传输出错,余数的大小即为错误位置。

    校验码的具体生成过程为:
        ①假设发送信息用信息多项式C(X)表示,将C(x)左移R位,则可表示成C(x)*2的R次方,这样C(x)的右边就会空出R位,这就是校验码的位置。
        ②移位后的信息 除以 生成多项式G(x)得到的余数多项式,可转为R位二进制。
        ③将余数嵌入到原信息的后面。
例如:信息位为10100110 , 生成多项式为a(x)= x 5+x 4+x+1
    则C(x)=a(x)* x 5 = (x 7+x 5+x 2+x)* x  =  x 12+  x 10 +x 7+x 6

 

    余数为x 4+x ,转为二进制为11000,所以CRC码为10100110110000 。

以上方法是用多项式来解的,现在我们换用二进制方式来试试。
    信息位为10100110 , 生成多项式为a(x)= x 5+x 4+x+1。
    则a(x)转换为二进制为110011,信息位左移 R位(即最高次幂+1=6位),即在信息为后补5个0 ,得10100110000000,再除以a(x)转换的110011,取R位余数,即6位。然后将余数嵌入到原信息的后面 。看图:

 
余数为110000,6位,正好,补充到信息位的后面为:10100110110000,跟上面的方法结果一致。
   

版权声明:本文为博主原创文章,未经博主允许不得转载。

共有 人打赏支持
粉丝 29
博文 260
码字总数 57524
×
白志华
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: