[转]常用校验码

http://hi.baidu.com/topasstem8/blog/item/bde149f38f24dd57342acce8.html

计算机系统运行时,各个部之间要进行数据交换. 为确保数据在传送过程正确无误,常使用检验码. 我们常使用的检验码有三种. 分别是奇偶校验码、海明校验码和循环冗余校验码(CRC) 。

奇偶校验码

奇偶校验码最简单,但只能检测出奇数位出错. 如果发生偶数位错误就无法检测. 但经研究是奇数位发生错误的概率大很多. 而且奇偶校验码无法检测出哪位出错.所以属于无法矫正错误的校验码。奇偶校验码是奇校验码和偶校验码的统称. 它们都是通过在要校验的编码上加一位校验位组成. 如果是奇校验加上校验位后,编码中1的个数为奇数个。如果是偶校验加上校验位后,编码中1的个数为偶数个。

例:
原编码 奇校验 偶校验
0000 0000 1 0000 0
0010 0010 0 0010 1
1100 1100 1 1100 0
1010 1010 1 1010 0

如果发生奇数个位传输出错,那么编码中1的个数就会发生变化. 从而校验出错误，要求从新传输数据。目前应用的奇偶校验码有3种.

水平奇偶校验码对每一个数据的编码添加校验位,使信息位与校验位处于同一行.

垂直奇偶校验码把数据分成若干组,一组数据排成一行,再加一行校验码. 针对每一行列采用奇校验 或 偶校验
例: 有32位数据10100101 00110110 11001100 10101011
垂直奇校验 垂直偶校验
数据10100101 10100101
00110110 00110110
11001100 11001100
10101011 10101011
校验00001011 11110100

水平垂直奇偶校验码就是同时用水平校验和垂直校验
例:
奇校验 奇水平 偶校验 偶水平
数据 10100101 1 10100101 0
00110110 1 00110110 0
11001100 1 11001100 0
10101011 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。

①海明校验的基本思想
将有效信息按某种规律分成若干组，每组安排一个校验位，做奇偶测试，就能提供多位检错信息，以指出最大可能是哪位出错，从而将其纠正。实质上，海明校验是一种多重校验。
②海明校验的特点
它不仅具有检测错误的能力，同时还具有给出错误所在准确位置的能力。

一．校验位的位数 校验位的位数与有效信息的长度有关

设:N--为校验码的位数 K--是有效信息位 r--校验位（分成r组作奇偶校验，能产生r位检错信息）
海明码应满足 N=K＋r≤2^r－1 若r=3 则N=K＋r≤7 所以K≤4

二．分组原则`

在海明码中， 位号数（1、2、3、……、n）为2的权值的那些位，即：
1(2⁰)、2(2¹)、4(2²)、8(2³)、…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占位 P1 P2 × P3 × × × P4 × × ×
其中×均为有效信息，海明码中的每一位分别被P1P2P3P4… Pr 中的一至若干位所校验，其规律是：
第i位由校验位位号之和等于i的那些校验位所校验
如：海明码的位号为3，它被P1P2（位号分别为1,2）所校验
海明码的位号为5，它被P1P3（位号分别为1,4）所校验
归并起来: 形成了4个小组，每个小组一个校验位，校验位的取值，仍采用奇偶校验方式确定。
如表 2·6 、表2·7所示：

三．编码、查错、纠错原理
以4位有效信息(b1、b2、b3、b4)和3位校验位(P1、P2、P3)为例: K=4 r=3
海明序号 1 2 3 4 5 6 7
海明码 P1 P2 b1 P3 b2 b3 b4
根据表2-8可以看到
（1）每个小组只有一位校验位，第一组是P1、第二组是P2、第三组是P3。
（2）每个校验位校验着它本身和它后面的一些确定位。



1.编码原理（采用偶校验）

1)若有效信息b1b2b3b4=1011 先将它们分别填入第3、5、6、7位
2)再分组进行奇偶统计，分别填入校验位P1、P2、P3的值
如：第一组有：P1b1b2b4 因b1b2b4含偶数个1，故P1应取值为0
第二组有：P2b1b3b4 因b1b3b4含奇数个1，故P2应取值为1
第三组有：P3b2b3b4 因b2b3b4含偶数个1，故P3应取值为0
海明编码为:P1P2b1P3b2b3b4=0110011

2.查错与纠错

因为分三组校验，每组产生一位检错信息、3组共3位检错信息，便构成一个指误字，上例指误字由G1G2G3组成。
其中：
G3=P3⊕b2⊕b3⊕b4 P3b2b3b4=0011
G2=P2⊕b1⊕b3⊕b4 P2b1b3b4=1111
G1=P1⊕b1⊕b2⊕b4 P1b1b2b4=0101
采用偶校验，在没有出错情况下G1G2G3=000。由于在分组时，就确定了每一位参加校验的组别,所以指误字能准确地指出错误所在位。
如：若第3位b1出错，由于b1参加了第一组和第二组的校验，必然破坏了第一组和第二组的偶性，从而使G1和G2为1。 因为b1未参加第三组校验，故G3=0，所以构成的指误字G3G2G1=011它指出第3位出错。
反之：若G3G2G1=111 则说明海明码第7位b4出错。因为只有第7位b4参加了3个小组的校验，破坏了三个小组的偶性。
假定：
源部件发送海明码为：0110011 接收端接收海明码为：0110011
则: 三个小组都满足偶校验要求，这时G3G2G1=000，表明收到信息正确，可以从中提出有效信息1011参与运算处理。
纠错：若接收端收到的海明码为0110111，分组检测后指误字G3G2G1=101，它指出第5位出错，则只须将第5位变反，就可还原成正确的数码0110011。

循环冗余校验码

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)

C(x)*pow(2,r) + r(x)就是所求的n位CRC码,由上式可以看出它是生成多项式g(x)的倍式.所以如果用得到的n位CRC码去除g(x)如果余数是0,就证明数据正确. 否则可以根据余数知道出错位.
在CRC运算过程中,四则运算采用 mod 2运算(后面介绍),即不考虑进位和借位. 所以上式等价于C(x)*pow(2,r) + r(x) = q(x)*g(x)

继续前先说下基本概念吧.
1.多项式和二进制编码
x的最高次幂位对应二进制数的最高位.以下各位对应多项式的各幂次. 有此幂次项为1,无为0. x的最高幂次为r时, 对应的二进制数有r+1位 例如g(x)=pow(x,4) + pow(x,3) + x + 1 对应二进制编码是 11011

2.生成多项式 是发送方和接受方的一个约定,也是一个二进制数,在整个传输过程中,这个数不会变.
在发送方利用 生成多项式 对信息多项式做 模2运算 生成校验码.
在接受方利用 生成多项式 对收到的 编码多项式 做 模2运算 校验和纠错.

生成多项式应满足:
a.生成多项式的最高位和最低位必须为1
b.当信息任何一位发生错误时,被生成多项式模2运算后应该使余数不为0
c.不同位发生错误时,应该使余数不同.
d.对余数继续做模2除,应使余数循环.

生成多项式很复杂，不过不用我们生成。

下面给出一些常用的生成多项式表
n k 二进制码(自己根据 多项式和二进制编码 的介绍转)
7 4 1011 或 1101
7 3 11011 或 10111
15 11 1011
31 26 100101

3.模2运算
a.加减法法则
0 +/- 0 = 0
0 +/- 1 = 1
1 +/- 0 = 1
1 +/- 1 = 0
注意:没有进位和借位

b.乘法法则
利用模2加求部分积之和,没有进位

c.除法法则
利用模2减求部分余数，没有借位，每商1位则部分余数减1位，余数最高位是1就商1,不是就商0， 当部分余数的位数小于余数时,该余数就是最后余数.

例 1110
1011)1100000
1011
1110
1011
1010
1011
0010(每商1位则部分余数减1位,所以前两个0写出)
0000
010(当部分余数的位数小于余数时,该余数就是最后余数)
最后商是1110余数是010

好了说了那么多没用的理论.下面讲下CRC的实际应用.例: 给定的生成多项式g(x)=1011, 用(7,4)CRC码对C(x)=1010进行编码.
由题目可以知道下列的信息:
C(x)=1010,n=7,k=4,r=3,g(x)=1011 C(x)*pow(2,3)=1010000 C(x)*pow(2,3) / g(x) = 1001 + 11/1011 所以r(x)=011.所以要求的编码为1010011
例2: 上题中,数据传输后变为1000011,试用纠错机制纠错. 1000011 / g(x) = 1011 + 110/1011

不能整除,所以出错了. 因为余数是110.查1011出错位表可以知道是第5位出错.对其求反即可.