循环冗余校验码

循环冗余校验编码( 循环冗余校验编码(CRC) ) Cyclic Redundancy checking (CRC)循环 循环 冗余校验，又称多项式码。 冗余校验，又称多项式码。 在循环冗余校验中，不是通过将各比特位 在循环冗余校验中， 相加来得到期望的校验， 相加来得到期望的校验，而是通过在数据 单元末尾加一串冗余比特，称作循环冗余 单元末尾加一串冗余比特，称作循环冗余 校验码或循环冗余校验余数， 校验码或循环冗余校验余数，使得整个数 据单元可以被另一个预定的二进制数所整 除。

1.CRC校验基本思想 校验基本思想 CRC校验的基本思想是： 根据欲发的k位信息生成一个 位信息生成一个r比特的序 (1) 根据欲发的 位信息生成一个 比特的序 列 ， 称 为 帧 校 验 序 列 FCS ( Frame checking Series)。 ) 求出实际发送的数据帧(k+r位 ( 2 ) 求出实际发送的数据帧 ( k+r 位 ) , 这 个帧所对应二进制序列恰好能够被某个预先 确定的数 生成多项式)整除。 确定的数(生成多项式)整除。 接收器用相同的数(生成多项式) (3)接收器用相同的数(生成多项式)去除 传来的帧。如果无余数，则认为无差错； 传来的帧。如果无余数，则认为无差错；如 果余数不为0 刚认为传输出错。 果余数不为0,刚认为传输出错。

2.CRC校验常用场合 校验常用场合 奇偶校验对一个字符校验一次，适合异 奇偶校验对一个字符校验一次， 步通讯； 对一个数据块( 步通讯；而CRC对一个数据块(frame) 对一个数据块 ) 校验一次，适合同步通讯。 校验一次，适合同步通讯。在串行同步 通信中，几乎都使用这种校验方法。 通信中，几乎都使用这种校验方法。如 磁盘信息的读/写等 写等。 磁盘信息的读 写等。

3.CRC码的生成 码的生成 CRC码生成和校验基本分为三步： 码生成和校验基本分为三步： 码生成和校验基本分为三步 –第一步： 在数据单元 (k 位 ) 的末尾加 第一步： (k位 第一步 在数据单元(k 上r个0。r是一个比预定除数的比特位 (r+1 的数。 数(r+1)少1的数。 –第二步： 采用二进制除法将新的加长 第二步： 第二步 的数据单元( k+r位 除以除数 除数。 的数据单元 ( k+r 位 ) 除以 除数 。 由此 除法产生的余数 就是循环冗余码校验 除法产生的 余数就是循环冗余码校验 余数 码。

CRC码的生成 码的生成第三步： CRC循环冗余校验码 第三步：求CRC循环冗余校验码 (K+r)被除数 余数 被除数+r(余数 被除数 余数)如果余数位数小于r,最左的缺省位数为0。 如果余数位数小于 ，最左的缺省位数为 。 如果余数为0,则 如果余数为 则r=0。 。

4.CRC码的校验 码的校验 CRC码校验：

码校验： 码校验

–到达接收方的数据单去除以用来产生 到达接收方的数据单去除以用来产生 循环冗余校验余数的G 循环冗余校验余数的G(X)。 –如果余数 0 , 将通过检验。 如果余数 如果余数0 将通过检验 。 如果余数 非零，将通不过检验。 非零，将通不过检验。

5.多项式 多项式 任何一个二进制数序列可以和一个只含有

0和1两个系数的代数多项式建立起一一对 和 两个系数的代数多项式建立起一一对 应的关系。因此，用来求CRC码的那个除 应的关系。因此，用来求 码的那个除 数通常用多项式来表示。原因如下： 数通常用多项式来表示。原因如下：– 代数多项式很短 – 可以通过多项式来进行概念的数学证明。 可以通过多项式来进行概念的数学证明。

多项式 任何一个 位的二进制数都可以用一个n-1 次的 任何一个n位的二进制数都可以用一个 位的二进制数都可以用一个 多项式来表示,这种多项式叫 这种多项式叫码多项式(又叫信息 多项式来表示 这种多项式叫 ( 多项式) 多项式) 。 码多项式与二进制序列之间的一一对应关系： 码多项式与二进制序列之间的一一对应关系：– (an-1 an-2……a1a0)N – A (x)= an-1Xn-1+an-2Xn-2 +……+a1X+a0X0

码多项式

多项式

二进制序列实例

以n=3位二进制数为例 位二进制数为例 二进制数 对应多项式 000 0 1 001 x 010 x+1 011 x2 100 x2+1 101 111 x2+ x+1

1011011 x6+x4+x3+x+1 x5+x4+x2+x 110110

码多项式 码多项式运算法则 码多项式运算法则:– 二进制码多项式的加减运算为⊕模2加运算， 二进制码多项式的加减运算为⊕ 加运算， 加运算 即两个码多项式相加时， 即两个码多项式相加时，对应项系数进行 加减。 模2加减。 加减 – 乘除运算与普通多项式类似； 乘除运算与普通多项式类似；

模2加减：即各位做不带进位、借位的按 加减： 加减 即各位做不带进位、 位加减。 位加减。这种加减运算实际上就是逻辑 上的异或运算。即加法和减法等价。 上的异或运算。即加法和减法等价。

码多项式 生成多项式 生成多项式G(x):– 求CRC码时所用的“除数”所对应的多项 码时所用的“ 码时所用的 除数” 式叫生成多项式。 式叫 。

在串行通信中通常使用下列三种生成多 项式G( )来产生CRC码。 项式 (X)来产生 码–CRC-16:G(x)=X16+X15+X2+1,美国二进制同 CRC-16: +1, CRC 步系统中采用。 步系统中采用。 –CRC-CCITT:G(x)=X16+X12+X5+1,CCITT推荐。 CRC+1,CCITT推荐 推荐。 CRC CCITT: –CRC-32:G(x)=X32+X26+X23+X22+ X16+X12+ CRCCRC 32: X11+X10+X8+1X7+ X5+X4+X2+X+ 1

6.CRC码生成器和校验器 码生成器和校验器 循环冗余码生成器采用

模2除法。下图显 循环冗余码生成器采用模2除法。 示了这一过程。 示了这一过程。 CRC校验器的功能完全像发生器一样，当 CRC校验器的功能完全像发生器一样 校验器的功能完全像发生器一样， 收到附加了CRC码的数据后， CRC码的数据后 收到附加了CRC码的数据后，做同样的模 除法。如果余数是全0 则将CRC CRC码丢 2 除法。如果余数是全0,则将CRC码丢 接受数据。否则，丢弃收到的数据。 弃，接受数据。否则，丢弃收到的数据。

CRC校验码的生成器和校验器 校验码的生成器和校验器数据 r个比特0数据 数据

g(x)

r+1 余数 先发数据位 后发校验位

g(x)

r+1

CRC校验码

r

余数0接收，非0拒绝 接收， 接收 拒绝

r

发送方

接收方

G(X) ⊕

0

111010100011010 CRC校验码 校验码 信息码 CRC冗余校验码 冗余校验码

7.CRC码性能 码性能 CRC码是很有效的差错校验方法。除了正好 CRC码是很有效的差错校验方法。 码是很有效的差错校验方法 数据块的比特值是按除数值变化的错误外， 数据块的比特值是按除数值变化的错误外， 循环冗余校验(CRC)将检测出其他所有错误。 将检测出其他所有错误。 循环冗余校验 将检测出其他所有错误 而且，常用的CRC除数通常有 ，或是 除数通常有17,或是33 而且，常用的 除数通常有 个比特， 个比特，使得不可检测的错误可能降低到几 乎近于零。 乎近于零。 CRC接收电路再配上适当的硬件电路不仅可 接收电路再配上适当的硬件电路不仅可 以检错，而且可以纠错，纠错能力很强特别 以检错，而且可以纠错， 适合检测突发性错误， 适合检测突发性错误，在数据通信中得到较 广泛的应用。 广泛的应用。