我们知道，数字数据在其传输线路上会受到各种干扰的影响，有时候会产生误码，因此必须引入数据校验技术来验证数据传输的正确性和有效性。

目前，最为普通的两种校验技术就是循环冗余校验和奇偶校验技术。

下面将依次说明两种校验技术的原理。

奇偶校验在发送数据时，数据位尾随的1位为奇偶校验位（1或0）。

奇校验时，数据中“1”的个数与校验位“1”的个数之和应为奇数；偶校验时，数据中“1”的个数与校验位“1”的个数之和应为偶数。

接收字符时，对“1”的个数进行校验，若发现不一致，则说明传输数据过程中出现了差错。

注意，奇校验或偶校验由通信双方提前约定。

循环冗余校验奇偶校验码作为一种检错码虽然简单,但是漏检率太高。

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

首先说明一个概念：生成多项式G(x)，目前国际上生成多项式有下面几类标准：CRC-12码: G(x)=X12+X11+X3+X2+X+1（X后数字表示X的幂次，下同）CRC-16码: G(x)=X16+X15+X2+1CRC-CCITT码: G(x)=X16+X12+X5+1CRC-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 110000011001 -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 11 1 0 0 10←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=00-0=0,0-1=1,1-0=1,1-1=0在进行基于模2运算的多项式除法时,只要部分余数首位为1,便可上商1,否则上商0。

然后按模2减法求得余数,该余数不计最高位。

当被除数逐位除完时,最后得到比除数少一位的余数。

奇偶,海明,CRC校验码计算机系统运行时,各个部之间要进行数据交换.为确保数据在传送过程正确无误,常使用检验码.我们常使用的检验码有三种.分别是奇偶校验码,海明校验码和循环冗余校验码(CRC)奇偶校验码最简单,但只能检测出奇数位出错.如果发生偶数位错误就无法检测.但经研究是奇数位发生错误的概率大很多.而且奇偶校验码无法检测出哪位出错.所以属于无法矫正错误的校验码而其他两种可以.下面按顺序介绍这几种校验码.奇偶校验码是奇校验码和偶校验码的统称.它们都是通过在要校验的编码上加一位校验位组成.如果是奇校验加上校验位后,编码中1的个数为奇数个如果是偶校验加上校验位后,编码中1的个数为偶数个例:原编码奇校验偶校验0000 0000 1 0000 00010 0010 0 0010 11100 1100 1 1100 01010 1010 1 1010 0如果发生奇数个位传输出错,那么编码中1的个数就会发生变化.从而校验出错误. 要求从新传输数据.目前应用的奇偶校验码有3种.水平奇偶校验码对每一个数据的编码添加校验位,使信息位与校验位处于同一行.垂直奇偶校验码把数据分成若干组,一组数据排成一行,再加一行校验码.针对每一行列采用奇校验或偶校验例: 有32位数据10100101 00110110 11001100 10101011垂直奇校验垂直偶校验数据10100101 1010010100110110 0011011011001100 1100110010101011 10101011校验为00001011 11110100水平垂直奇偶校验码就是同时用水平校验和垂直校验例:奇校验奇水平偶校验偶水平数据10100101 1 10100101 000110110 1 00110110 011001100 1 11001100 010101011 0 10101011 1校验00001011 0 11110100 1然后是海明校验码海明码也是利用奇偶性来校验数据的.它是一种多重奇偶校验检错系统,它通过在数据位之间插入k个校验位,来扩大码距,从而实现检错和纠错.设原来数据有n位,要加入k位校验码.怎么确定k的大小呢?k个校验位可以有pow(2,k) (代表2的k次方) 个编码,其中有一个代表是否出错.剩下pow(2,k)-1个编码则用来表示到底是哪一位出错.因为n个数据位和k个校验位都可能出错所以k满足pow(2,k)-1 >= n+k设k个校验码为P1,P2...Pk, n个数据位为D0,D1...Dn产生的海明码为H1,H2...H(n+k)Pi放在海明码的pow(2,i-1)个位置上.如有8个数据位,根据pow(2,k)-1 >= n+k可以知道k最小是4 那么得到的海明码是H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1然后怎么知道Pi校验哪个位呢.自己可以列个校验关系表海明码下标校验位组H1(P1) 1 P1H2(P2) 2 P2H3(D0) 1+2 P1,P2H4(P3) 4 P3H5(D1) 1+4 P1,P2H6(D2) 2+4 P2,P3H7(D3) 1+2+4 P1,P2,P3H8(P4) 8 P4H9(D4) 1+8 P1,P4H10(D5) 2+8 P2,P4H11(D6) 1+2+8 P1,P2,P4H12(D7) 4+8 P3,P4从表中可以看出P1校验P1,D0,D1,D3,D4,D6P2校验P2,D0,D2,D3,D5,D6P3校验P3,D1,D2,D3,D7P4校验P4,D4,D5,D6,D7其实上表很有规律很容易记要知道海明码Hi由哪些校验组校验可以把i化成二进制数数中哪些位k是1,就有哪些Pk校验如H7 7=0111 所以由P1,P2,P3H11 11=1011 所以由P1,P2,P4H3 3=0011 所以由P1,P2那看看Pi的值怎么确定如果使用偶校验,则P1=D0 xor D1 xor D3 xor D4 xor D6P2=D0 xor D2 xor D3 xor D5 xor D6P3=D1 xor D2 xor D3 xor D7P4=D4 xor D5 xor D6 xor D7其中xor是异或运算奇校验的话把偶校验的值取反即可.那怎么校验错误呢.其实也很简单. 先做下面运算.G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6G3 = P3 xor D1 xor D2 xor D3 xor D7G4 = P4 xor D4 xor D5 xor D6 xor D7如果用偶校验那么G4G3G2G1 全为0是表示无错误(奇校验全为1) 当不全为0表示有错G4G3G2G1 的十进制值代表出错的位.如G4G3G2G1 =1010 表示H10(D5)出错了.把它求反就可以纠正错误了.下面举一个比较完全的例子:设数据为01101001,试用4个校验位求其偶校验方式的海明码.传输后数据为011101001101,是否有错?P1=D0 xor D1 xor D3 xor D4 xor D6=1 xor 0 xor 1 xor 0 xor 1=1P2=D0 xor D2 xor D3 xor D5 xor D6=1 xor 0 xor 1 xor 1 xor 1=0P3=D1 xor D2 xor D3 xor D7=0 xor 0 xor 1 xor 0=1P4=D4 xor D5 xor D6 xor D7=0 xor 1 xor 1 xor 0=0所以得到的海明码为0 1 1 0 0 1 0 0 1 1 0 1传输后为011101001101G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6=1G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6=0G3 = P3 xor D1 xor D2 xor D3 xor D7=0G4 = P4 xor D4 xor D5 xor D6 xor D7=1所以1001代表9即H9出错了,对它求反011001001101 和我们算的一样.由此可见海明码不但有检错还有纠错能力下面说下最后一种CRC即循环冗余校验码CRC码利用生成多项式为k个数据位产生r个校验位进行编码,其编码长度为n=k+r所以又称(n,k)码.CRC码广泛应用于数据通信领域和磁介质存储系统中.CRC理论非常复杂,一般书就给个例题,讲讲方法.现在简单介绍下它的原理:在k位信息码后接r位校验码,对于一个给定的(n,k)码可以证明(数学高手自己琢磨证明过程)存在一个最高次幂为n-k=r 的多项式g(x)根据g(x)可以生成k位信息的校验码,g(x)被称为生成多项式用C(x)=C(k-1)C(k-2)...C0表示k个信息位把C(x)左移r位,就是相当于C(x)*pow(2,r)给校验位空出r个位来了.给定一个生成多项式g(x),可以求出一个校验位表达式r(x)C(x)*pow(2,r) / g(x) = q(x) + r(x)/g(x)用C(x)*pow(2,r)去除生成多项式g(x)商为q(x)余数是r(x)所以有C(x)*pow(2,r) = q(x)*g(x) + r(x)在CRC运算过程中,四则运算采用mod 2运算(后面介绍),即不考虑进位和借位.所以上式等价于C(x)*pow(2,r) + r(x) = q(x)*g(x)C(x)*pow(2,r) + r(x)就是所求的n位CRC码,由上式可以看出它是生成多项式g(x)的倍式.所以如果用得到的n位CRC码去除g(x)如果余数是0,就证明数据正确.否则可以根据余数知道出错位.继续前先说下基本概念吧.1.多项式和二进制编码x的最高次幂位对应二进制数的最高位.以下各位对应多项式的各幂次.有此幂次项为1,无为0. x的最高幂次为r时, 对应的二进制数有r+1位例如g(x)=pow(x,4) + pow(x,3) + x + 1对应二进制编码是110112.生成多项式是发送方和接受方的一个约定,也是一个二进制数,在整个传输过程中,这个数不会变. 在发送方,利用生成多项式对信息多项式做模2运算生成校验码.在接受方利用生成多项式对收到的编码多项式做模2运算校验和纠错.生成多项式应满足:a.生成多项式的最高位和最低位必须为1b.当信息任何一位发生错误时,被生成多项式模2运算后应该使余数不为0c.不同位发生错误时,应该使余数不同.d.对余数继续做模2除,应使余数循环.生成多项式很复杂不过不用我们生成下面给出一些常用的生成多项式表n k 二进制码(自己根据多项式和二进制编码的介绍转)7 4 1011 或11017 3 11011 或1011115 11 101131 26 1001013.模2运算a.加减法法则0 +/- 0 = 00 +/- 1 = 11 +/- 0 = 11 +/- 1 = 0注意:没有进位和借位b.乘法法则利用模2加求部分积之和,没有进位c.除法法则利用模2减求部分余数没有借位每商1位则部分余数减1位余数最高位是1就商1,不是就商0当部分余数的位数小于余数时,该余数就是最后余数.例11101011)1100000101111101011101010110010(每商1位则部分余数减1位,所以前两个0写出)0000010(当部分余数的位数小于余数时,该余数就是最后余数)最后商是1110余数是010好了说了那么多没用的理论.下面讲下CRC的实际应用例: 给定的生成多项式g(x)=1011, 用(7,4)CRC码对C(x)=1010进行编码. 由题目可以知道下列的信息:C(x)=1010,n=7,k=4,r=3,g(x)=1011C(x)*pow(2,3)=1010000C(x)*pow(2,3) / g(x) = 1001 + 011/1011所以r(x)=011所以要求的编码为1010011例2: 上题中,数据传输后变为1000011,试用纠错机制纠错.1000011 / g(x) = 1011 + 110/1011不能整除,所以出错了. 因为余数是110查1011出错位表可以知道是第5位出错.对其求反即可.。