冗余校验(CRC)原理与编码方法

关键词：通讯 冗余校验 编码 摘要：通信的目的是要把信息及时可靠地传送给对方，因此要求一个通信系统传输消息必须可靠与快速，在数字通信系统中可靠与快速往往是一对矛盾。为了解决可靠性，通信系统都采用了差错控制。本文着重介绍了循环冗余校验CRC（Cyclic Redundancy Check）的差错控制原理及其编码方法。

1、 概述

在数字通信系统中实现检错功能的差错控制方法很多，传统的有：奇偶校验、重复码校验、恒比码校验、行列冗余码校验等，这些方法都是增加数据的冗余量，将校验码和数据一起发送到接受端。接受端对接受到的数据进行相同校验，再将得到的校验码和接受到的校验码比较，如果二者一致则认为传输正确。但这些方法都有各自的缺点，误判的概率比较高。

循环冗余校验 CRC（Cyclic Redundancy Check）是由分组线性码的分支而来，其主要应用是二元码组。编码简单且误判概率很低，在通信系统中得到了广泛的应用。下面重点介绍了CRC校验的原理及其算法。

2、 冗余校验标准分类

循环冗余码校验英文名称为Cyclical Redundancy Check，简称CRC。它是利用多项式除法及余数的原理来作错误侦测（Error Detecting）的。它将要发送的数据比特序列当作一个多项式f(x)的系数，发送时用双方预先约定的生成多项式G(x)去除，求得一个余数多项式，将余数多项式加到数据多项式之后发送到接收端，接收端同样用G(x)去除接收到的数据，进行计算，然后把计算结果和实际接收到的余数多项式数据进行比较，相同的话表示传输正确。CRC校验检错能力强，容易实现，是目前应用最广的检错码编码方式之一。

在国际标准中，根据生成多项式G(x)的不同，CRC又可分为以下几种标准： ①CRC-4码： G(X)=X4+X+1

②CRC-12码： G(X)=X12+X11+X3+X2+X+1 ③CRC-16码： G(X)=X16+X15+X2+1 ④CRC-CCITT码：G(X)=X16+X12+X5+1 ⑤CRC-32码：

G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1

CRC-12码通常用来传送6-bit字符串。CRC-16及CRC-CCITT码则用是来传送8-bit字符，其中CRC-16为美国采用，而CRC-CCITT为欧洲国家所采用。CRC-32码大都被采用在一种称为Point-to-Point的同步传输中。

3、 冗余校验原理

CRC校验采用多项式编码方法，如一个8位二进制数(B7B6B5B4B3B2B1B0)可以用7阶二进制码多项式 B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1+B0X0表示。

例如11000001可表示为1X7+1X6+0X5+0X4+0X3+0X2+0X1+0X0。

一般说，n位二进制数可用(n-1)阶多项式表示。它把要发送的数据位串看成是系数只能 为“1”或“0”的多项式。一个n位的数据块可以看成是从Xn-1到X0的n项多项式的系数序列，位于数据块左边的最高位是Xn-1项的系数，次高位是Xn-2项的系数，依此类推，位于数据块右边的最低位是X0项的系数，这个多项式的阶数为n-1。

多项式乘除法运算过程与普通代数多项式的乘除法相同。加减时不进、错位，如同逻辑

异或运算。

采用CRC校验时，发送方和接收方事先约定一个生成多项式G(X)，并且G(X)的最高项和最低项的系数必须为1。设m位数据块的多项式为M(X)，生成多项式G(X)的阶数必需比M(X)的阶数低。

CRC校验码的检错原理是：发送方先为数据块生成 CRC 校验码，使这个CRC校验码的多项式能被G(X)除尽，实际发送此CRC校验码；接收方用收到的CRC校验码除以G(X)，如果能除尽，表明传输正确，否则，表示有传输错误，请求重发。

生成数据块的CRC校验码的步骤如下：

（1）设G(X)为r阶，在数据块末尾添加r个0，使数据块为m+r位，则相应的多项式为 XrM(X)；

（2）以2为模，用对应于G(X)的位串去除对应于XrM(X)的位串，求得余数位串； （3）以2为模，从对应于XrM(X)的位串中减去余数位串，结果就是为数据块生成的带足够校验信息的CRC校验码位串。

4、 冗余校验码编码举例

由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致，只有位数和生成多项式不一样。为了叙述简单，用一个CRC-4编码的例子来说明CRC的编码过程。

例如，设要发送的数据为1101011011，G(X)=X4+X+1，则首先在发送数据块的末尾加4个0，得到11010110110000，然后用G(X)的位串10011去除，再用11010110110000减去余数位串1110，得到的即为CRC位串11010110111110，将对应多项式称为T(X)，显然，T(X)能被G(X)除尽。这样，一旦接收到的CRC位串不能被同样的G(X)的位串除尽，那么一定有传输错误。

编码过程如下图所示。