奇偶校验、汉明码、CRC循环冗馀校验码
必须记住三种校验码是比较重要的，在计算机网络中是有用的
奇偶校验
根据传输的二进制码集中“1”的个数是奇数还是偶数来检查。 采用奇数的叫奇检查，反之叫偶检查。 采用什么样的检查是事先决定好的。 通常，只设置一个奇偶校验位，该组中的“1”的数目是奇数或偶数。 如果使用奇数校验，当接收方收到该组代码时，它会检查“1”的数量是否为奇数，以确认传输代码的正确性。
检查方法
奇校验：是把原始数据序列中的(包括你要加的一位) 1的个数定为奇数
1000110(0)你必须加0。 这样，原来有三个的1已经是奇数了，所以追加0后1的个数仍然是奇数。
偶校验：将原始数据序列中(包括你要相加的一位) 1的个数定为偶数
1000110(1)你必须加1。 这样一来，本来就有3个1，为了使1的个数成为偶数，只能追加1
样品
串行数据在传输过程中，可能会因干扰而引起信息错误。 例如，传输字符‘e’可能如下：
0100，0101=45h
D7 D0
由于噪声，位可能会变为1。 (为什么不变成0？ )这种情况称为发生了“错误代码”。 如何发现传输中的错误称为“错误检测”。 发现错误后，如何消除错误叫做“纠错”。 最简单的检错方法是“奇偶校验”，与发送字符的各位分开发送1位奇数/偶数位。 可以采用奇检查或偶检查。
检查：“1”是所有发送的位(包括字符的各位和奇偶校验位)的奇数，如下所示：
10110，0101
0110，0101
偶数检查：“1”的数量在所有发送位(包括字符的各位和奇偶校验位)中都为偶数。 示例：
10100，0101
0100，0101
奇偶校验可以检测信息传输中的部分错误代码(可以检测奇数位错误代码，但是不能检测偶数位错误代码)，同时不能进行纠错。 如果发现错误，就只能要求重发。 但由于其实现简单，仍被广泛使用。 一些检错方法具有自动纠错能力。 例如，循环冗馀码(CRC )差错检测等
CRC检查
CRC或循环冗馀校验码(Cyclic Redundancy Check ) :数据通信领域中最常用的纠错码之一，其特征是信息字段和校验字段的长度可以任意选定。 冗馀校验(CRC )是一种数据传输错误检测功能，对数据进行多项式计算，并将结果附加在帧的后面。 接收设备也执行同样的算法以确保数据传输的准确性和完整性。
工作原理
循环冗馀校验码(CRC )的基本原理是在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 ) 2R表示)，在c ) x )的右边空出r比特的是校验码的位置C(X ) 2R除以生成多项式g ) x )的馀数为校验码。
对应关系
多项式和二进制数有直接的对应关系。 x的最高幂对应于二进制最高位，以下各位对应于多项式的各幂，如果有这个幂项则对应于1，如果没有这个幂项则对应于0。 将x的最高次设为r，变换为对应的2进制数后可知有R 1比特。
多项式包括生成多项式g[x]和信息多项式c[x]。
如果生成多项式为g(x )=X4 X3 X 1，则可以变换为二进制数字11011。
另一方面，发送信息位101至111，数据多项式可转换为c(x )=X5321。
生成多项式
接收方和发送方的约定，即二进制数，在传输过程中该数保持不变。
在发送端，用生成多项式除以模2，生成校验码。 在接收端，用生成多项式除以模2，检测并确定接收到的编码多项式。
必须满足以下条件：
a、生成多项式的最高位和最低位必须为1。
b、在发送信息(CRC码)的任一位发生错误的情况下，除以生成多项式后，使馀数不为0。
C、如果不同的位发生错误，应该使馀数不同。
d、持续清除多余物，使多余物循环。
校验码位数
CRC校验码位数=生成多项式的位数- 1。 请注意，某些生成多项式的表达式忽略了生成多项式的顶级1。
生成步骤
1、将x的最高次幂为r的生成多项式g(x )变换为对应的R 1比特的2进制。
2、将信息代码向左位移r个比特，相当于对应的信息多项式c(x ) *2R。
3、将信息代码除以生成多项式(二进制)，得到r位的馀数)注意：此处的二进制除法得到的馀数实际上是模2除法得到的馀数，它与对应于十进制除法得到的馀数不相同。 请参阅。
4、将余数移动到二维码的左边，拼写到空闲位置，得到完整的CRC码。
【例】假设使用的生成多项式为g(x )=X3 X 1。 4位原始消息在1010处请求编码消息。
解：
1、多项式g(x )=X3 X 1被生成
转换成对应的二进制除数1011。2、此题生成多项式有4位(R+1)(注意：4位的生成多项式计算所得的校验码为3位，R为校验码位数)，要把原始报文C(X)左移3(R)位变成1010 000
3、用生成多项式对应的二进制数对左移3位后的原始报文进行模2除(高位对齐)，相当于按位异或：
1010000
1011
———–】
0001000
0001011
———-】
0000011
得到的余位011，所以最终编码为：1010 011
原则
若设码字长度为N，信息字段为K位，校验字段为R位(N=K+R)，则对于CRC码集中的任一码字，存在且仅存在一个R次多项式g(x)，使得
V(x)=A(x)g(x)=xRm(x)+r(x);
其中: m(x)为K次原始的信息多项式， r(x)为R-1次校验多项式(即CRC校验和)，
g(x)称为生成多项式：
g(x)=g0+g1x1+ g2x2+…+g(R-1)x(R-1)+gRxR
发送方通过指定的g(x)产生CRC码字，接收方则通过该g(x)来验证收到的CRC码字。
生成方法
借助于模2除法则，其余数为校验字段。
例如：信息字段代码为: 1011001；对应m(x)=x6+x4+x3+1
假设生成多项式为：g(x)=x4+x3+1；则对应g(x)的代码为: 11001
x4m(x)=x10+x8+x7+x4 对应的代码记为：10110010000；
采用模2除法则: 得余数为: 1010(即校验字段为：1010)
发送方：发出的传输字段为: 1 0 1 1 0 0 1 1010
信息字段 校验字段
接收方：使用相同的生成码进行校验:接收到的字段/生成码(二进制除法)
如果能够除尽，则正确，
给出余数(1010)的计算步骤：
除法没有数学上的含义，而是采用计算机的模二除法，即除数和被除数做异或运算。进行异或运算时除数和被除数最高位对齐，按位异或。
10110010000
^11001
————————–】
01111010000
1111010000
^11001
————————-】
0011110000
11110000
^11001
————————–】
00111000
111000
^11001
——————-】
001010
则四位CRC校验码就为：1010。
利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制码序列数共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。
海明码校验
将有效信息按某种规律分成若干组，每组安排一个校验位，做奇偶测试，就能提供多位检错信息，以指出最大可能是哪位出错，从而将其纠正。实质上，海明校验是一种多重校验。
假设为k个数据位设置r个校验位，则校验位能表示2^r个状态，可用其中的一个状态指出 “没有发生错误”，用其余的2 ^r -1个状态指出有错误发生在某一位，包括k个数据位和r个校验位，因此校验位的位数应满足如下关系:
2^r ≥ k + r + 1 (2.7)
如要能检出与自动校正一位错，并能同时发现哪位错，此时校验位的位数r和数据位的位数k应满足下述关系:
2^r-1 ≥ k + r (2.8)
按上述不等式，可计算出数据位k与校验位r的对应关系，如表2.2所示。
表2.2
k值 最小r值
2～4 3
5～11 4
12～26 5
27～57 6
58～120 7
分组原则
编辑
在海明码中， 位号数(1、2、3、……、n)为2的权值的那些位，即：
1(20)、2(21)、4(22)、8(23)、…2^(r-1)位，作为奇偶校验位，并记作: P1、P2、P3 、P4、…Pr，余下各位则为有效信息位。例如： N=11(海明码位数)K=7(数据位数)r=4(校验位) ，相应海明码可表示位号为： 1， 2， 3， 4 ，5 ，6， 7， 8， 9 ，10 ，11，校验位P占第1，2，4，8位，其他位为有效信息位，海明码中的校验位分别标示为P1,P2,P3,P4… Pr ,并被信息位中的一至若干位所校验，其规律是：第i位，由校验位位号之和等于i的那些校验位所校验，如：海明码的位号为3，它被P1P2(位号分别为1,2)所校验，海明码的位号为5，它被P1P3(位号分别为1,4)所校验。归并起来: 形成了4个小组，每个小组一个校验位，校验位的取值，仍采用奇偶校验方式确定。
设计海明码编码的关键技术，是合理地把每个数据位分配到r个校验组中，以确保能发现码字中任何一位出错；若要实现纠错，还要求能指出是哪一位出错，对出错位求反则得到该位的正确值。例如，当数据位为3位(用D3 D2 D1表示)时，检验位应为4位(用P4 P3 P2 P1表示)。可通过表2.3表示的关系，完成把每个数据位划分在形成不同校验位的偶校验值的逻辑表达式中。
表2.3 校验位与数据位的对应关系
在P1、P2、P3、P4竖列相应行分别填1，
在该4列的低3横行其它位置分别填0，
在最顶横行的每个尚空位置都分别填1。
若只看低3横行，右4竖列的3个bit的组合值分别为十进制的1、2、4、0，则分配 D1 D2 D3列的组合值为3 5 6，保证低3横行各竖列的编码值各不相同。
表中D3 D2 D1为三位数据位，P4 P3 P2 P1为四位校验位。其中低三位中的每一个校验位P3 P2 P1的值，都是用三个数据位中不同的几位通过偶校验运算规则计算出来的。其对应关系是：对Pi(i的取值为1~3)，总是用处在Pi取值为1的行中的、用1标记出来的数据位计算该Pi的值。最高一个校验位P4，被称为总校验位，它的值，是通过对全部三个数据位和其它全部校验位(不含P4本身)执行偶校验计算求得的。
形成各校验位的值的过程叫做编码，按刚说明的规则，4个校验位所用的编码方程为：
P4 = D3 D2 D1 P3 P2 P1
P3 = D3 D2
P2 = D3 D1
P1 = D2 D1
由多个数据位和多个校验位组成的一个码字，将作为一个数据单位处理，例如被写入内存或被传送走。之后，在执行内存读操作或在数据接收端，则可以对得到的码字，通过偶校验来检查其合法性，通常称该操作过程为译码，所用的译码方程为：
S4 = P4 D3 D2 D1 P3 P2 P1
S3 = P3 D3 D2
S2 = P2 D3 D1
S1 = P1 D2 D1
对应关系
编辑
译码方程和编码方程的对应关系很简单。译码方程，是用一个校验码和形成这个校验码的编码方程执行异或，实际上是又一次执行偶校验运算。通过检查四个S的结果，可以实现检错纠错的的目的。实际情况是，当译码求出来的S4、S3、S2、S1的得值与表2.3中的那一列的值相同，就说明是哪一位出错；故人们又称表2.3为出错模式表。若出错的是数据位，对其求反则实现纠错；若出错的是校验位则不必理睬。举例如下：
任何一位(含数据位、校验位)均不错，则四个S都应为0值；
任何单独一位数据位出错，四个S中会有三个为1；如D3错，则S4 S3 S2 S1为1110。
若单独一位校验位出错，四个S中会有一个或两个为1；如P1错，S4 S3 S2 S1为1001，如P4错，S4 S3 S2 S1为1000。
任何两位(含数据位、校验位)同时出错，S4一定为0，而另外三个S位一定不全为0，此时只知道是两位同时出错，但不能确定是哪两位出错，故已无法纠错。如D1、 P2出错，会使S4 S3 S2 S1为0001。请注意，S4的作用在于区分是奇数位出错还是偶数位出错，S4为1是奇数位错，为0是无错或偶数位错。这不仅为发现两位错所必需，也是为确保能发现并改正一位错所必需的。若不设置S4，某种两位出错对几个S的影响与单独另一位出错可能是一样的(不必花费精力推敲)，此时若不加以区分，简单地按一位出错自动完成纠错处理反而会帮倒忙。