CRC校验

时间:2024-03-30 11:49:38

 CRC即循环冗余校验码(Cyclic Redundancy Check):是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。

基本原理:K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)。根据G(x)可以生成K位信息的校验码,而G(x)叫做这个CRC码的生成多项式。

      具体生成过程为:假设发送信息用信息多项式C(X)表示,将C(x)左移R位,则可表示成C(x)*x的R次方,这样C(x)的右边就会空出R位,这就是校验码的位置,这样C(x)的右边就会空出r位校验码的位置,做除法(模2除),得到的余数R就是校验码。发送的CRC编码是,验证接收到的报文编码是否至正确,依然是做模2除:。通过C(x)*X的R次方除以生成多项式G(x)得到的余数就是校验码。

发送方通过指定的G(x)产生r位的CRC校验码,接收方则通过该G(x)来验证收到的报文码的CRC校验码是否为0。

    任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。例如:代码1010111对应的多项式x6+x4+x2+x+1,而多项式为x5+x3+x2+x+1对应的代码101111。

计算示例:

设需要发送的信息为M = 1010001101,CRC8=X5+X4+X2+1产生多项式对应的代码为P = 110101,R=5。在M后加5个0为计算序列:101000110100000,然后对P做模2除法运算,得余数r(x)对应的代码:01110。故实际需要发送的数据是101000110101110。其中CRC校验码就为:01110。

 

五、错误检测

    当接收方收到数据后,用收到的数据对P(事先约定的)进行模2除法,若余数为0,则认为数据传输无差错;若余数不为0,则认为数据传输出现了错误,由于不知道错误发生在什么地方,因而不能进行自动纠正,一般的做法是丢弃接收的数据。

 

注释 几点说明:

    1、CRC是一种常用的检错码,并不能用于自动纠错。

    2、只要经过严格的挑选,并使用位数足够多的除数P,那么出现检测不到的差错的概率就很小很小。

    3、仅用循环冗余检验 CRC 差错检测技术只能做到无差错接受(只是非常近似的认为是无差错的),并不能保证可靠传输。

 

生成多项式:G(X)=X4+X3+1,要求出二进制序列10110011的CRC校验码。

1)G(X)=X4+X3+1,二进制比特串为11001;(有X的几次方,对应的2的几次方的位就是1)

2)因为校验码4位,所以10110011后面再加4个0,得到101100110000,用“模2除法”(其实就是亦或^)即可得出结果;

 CRC校验

                                 图5-10 CRC校验码计算示例

 (3)CRC^101100110000得到101100110100。发送到接收端;

 (4)接收端收到101100110100后除以11001(以“模2除法”方式去除),余数为0则无差错;