原创 数据校验技术（CRC，奇偶法）

我们知道，数字数据在其传输线路上会受到各种干扰的影响，有时候会产生误码，因此必须引入数据校验技术来验证数据传输的正确性和有效性。目前，最为普通的两种校验技术就是循环冗余校验和奇偶校验技术。下面将依次说明两种校验技术的原理。

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

奇偶校验

在发送数据时，数据位尾随的1位为奇偶校验位（1或0）。奇校验时，数据中“1”的个数与校验位“1”的个数之和应为奇数；偶校验时，数据中“1”的个数与校验位“1”的个数之和应为偶数。接收字符时，对“1”的个数进行校验，若发现不一致，则说明传输数据过程中出现了差错。注意，奇校验或偶校验由通信双方提前约定。

循环冗余校验

奇偶校验码作为一种检错码虽然简单,但是漏检率太高。在计算机网络和数据通信中用的最广泛的检错码,是一种漏检率低得多也便于实现的循环冗余码CRC (Cyclic Redundancy Code),CRC码又称为多项式码。

首先说明一个概念：生成多项式G(x)，目前国际上生成多项式有下面几类标准：
CRC<?xml:namespace prefix = st1 ns = "urn:schemas-microsoft-com:office:smarttags" />-12码:   G(x)=X12+X11+X3+X2+X+1（X后数字表示X的幂次，下同）
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+X1+X+1

针对不同的数据传输类型（数据位不同，同步or异步传输）可选择不同的传输标准。此外，不同国家也采用不同生成多项式标准。

下面先给两个个例子（纯数学运算），大家先体会一下运算过程：

例1．已知：信息码:110011　信息多项式:K(X)=X5+X4+X+1
　　　      生成码:11001   生成多项式:G(X)=X4+X3+1(r=4，表示冗余码位数)
　　　求：循环冗余码和码字。
　　解：1)(X5+X4+X+1)*X4的积是 X9+X8+X5+X4 对应的码是1100110000。
　　　　2)积／G(X)(按模二算法)。
　　　　 
　　　　　　　　　　　　 　1 00001←Q(X) （商）
　　    G(x)→1 1 0 0 1 )1 1 0 0 1 1 0 0 0 0←K(X)*Xr　 （“）”表示模二除号）
　　　　　　　　　　 1 1 0 0 1
　　　　　　　　　　　　　  100000
　　　　　　　　　　　　　　 11001  -
　　　　　　　　　　　　　　　1 0 0 1←R(X)(冗余码)

由计算结果知冗余码是1001，码字就是1100111001（K(X)*Xr＋R(x)对应码为待发送码字）。

例2.已知：接收码字:1100111001　多项式:T(X)=X9+X8+X5+X4+X3+1
　　　　　生成码: 11001    生成多项式:G(X)=X4+X3+1(r=4)
　　求：码字的正确性。若正确，则指出冗余码和信息码。
　　解：1)用码字除以生成码，余数为0，所以码字正确。 

　　　　　　　　　　　 　　1 0 0 0 0 1←Q(X)
　G(x)→1 1 0 0 1 )1 1 0 0 1 1 1 0 0 1←K(X)*Xr＋R(x)　 （“）”表示模二除号）
　　　　　　　　　 1 1 0 0 1　　　　　，
　　　　　　　　　　　　　　 1 1 0 0 1
　　　　　　　　　　　　　　 1 1 0 0 1
　　　　　　　　　　　　　　　 　　　0←S(X)(余数)
 　2)因r=4，所以冗余码是：1001，信息码是:110011

总结CRC机理为（结合上述例子来理解）：

约定：二进制序列与多项式转换格式（X后数字为X的幂，如X0=1）

例：X5+X3+X2+X1+ X0（X5+X3+X2+X1+ 1）对应的代码为101111）

前提：给定待传输序列，给出冗余位数r, 并选定给定选择的生成多项式（其最高项Xr的系数恒为1），

原理：CRC码在发送端编码和接收端校验时,都利用事先约定的生成多项式G(X)进行计算来得到。 k位要发送的信息位可对应于一个(k-1)次多项式K(X),r位冗余位则对应于一个(r-1)次多项式R(X),由k位信息位后面加上r位冗余位组成的 n="k"+r位码字则对应于一个(n-1)次多项式T(X)=Xr·K(X)+R(X)。例如

信息位:1011001→K(X)=X6+X4+X3+1

    冗余位:1010→R(X)=X3+X

    码字:10110011010→T(X)=X4·K(X)+R(X)=X10+X8+X7+X4+X3+X

过程：
1. 由信息位产生冗余位的编码（已知K(X)求R(X)）

Xr·K (X)%G(X)=R(X)   （均为模2运算）

2. T(X)=Xr·K(X)+R(X) （发送码）

3.接受端若T(X)% G(X)=0  则传输正确

4．通过其他算术运算实现：

(1)可检测出所有奇数位错。

    (2)可检测出所有双比特的错。

    (3)可检测出所有小于、等于校验位长度的突发错。

附录：

模二运算规则：

0+0=0,0+1=1,1+0=1,1+1=0

0-0=0,0-1=1,1-0=1,1-1=0

在进行基于模2运算的多项式除法时,只要部分余数首位为1,便可上商1,否则上商0。然后按模2减法求得余数,该余数不计最高位。当被除数逐位除完时,最后得到比除数少一位的余数。