当前位置: 老葡京网站娱乐 > 编程语言 > 汇编语言 > 正文

计算机体系结构(三) 循环冗余校验知识

时间:2014-10-30 csdn博客 龙轩

老葡京网站娱乐 www.sdguanhua.com 在校验码体系中,有各种校验的方法:有奇偶校验、海明码校验、循环冗余校验。今天就跟大家共同探讨一下常用的循环冗余校验吧。

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

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

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

本栏目更多精彩内容:http://www.sdguanhua.com/Programming/hb/

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

校验码的具体生成过程为:

①假设发送信息用信息多项式C(X)表示,将C(x)左移R位,则可表示成C(x)*2的R次方,这样C(x)的右边就会空出R位,这就是校验码的位置。

②移位后的信息 除以 生成多项式G(x)得到的余数多项式,可转为R位二进制。

③将余数嵌入到原信息的后面。

例如:信息位为10100110 , 生成多项式为a(x)= x5+x4+x+1

则C(x)=a(x)* x5 = (x7+x5+x2+x)* x5  = x12+ x10 +x7+x6

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

以上方法是用多项式来解的,现在我们换用二进制方式来试试。

信息位为10100110 , 生成多项式为a(x)= x5+x4+x+1。

则a(x)转换为二进制为110011,信息位左移 R位(即最高次幂+1=6位),即在信息为后补5个0 ,得10100110000000,再除以a(x)转换的110011,取R位余数,即6位。然后将余数嵌入到原信息的后面 ??赐迹?/p>

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