奇偶校验码,海明校验码 和 循环冗余校验码(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


设 k个校验码为 P1,P2...Pk, n个数据位为D0,D1...Dn
产生的海明码为 H1,H2...H(n+k)

如有8个数据位,根据pow(2,k)-1 >= n+k可以知道k最小是4
那么得到的海明码是
H12 H11 H10 H9  H8 H7 H6 H5  H4 H3 H2 H1
D7  D6  D5  D4  P4 D3 D2 D1  P3 D0 P2 P1


然后怎么知道Pi校验哪个位呢.
自己可以列个校验关系表
海明码  下标  校验位组
H1(P1)  1  P1
H2(P2)  2  P2
H3(D0)  1+2  P1,P2
H4(P3)  4  P3
H5(D1)  1+4  P1,P2
H6(D2)  2+4  P2,P3
H7(D3)  1+2+4  P1,P2,P3
H8(P4)  8  P4
H9(D4)  1+8  P1,P4
H10(D5)  2+8  P2,P4
H11(D6)  1+2+8  P1,P2,P4
H12(D7)  4+8  P3,P4

从表中可以看出
P1校验 P1,D0,D1,D3,D4,D6
P2校验 P2,D0,D2,D3,D5,D6
P3校验 P3,D1,D2,D3,D7
P4校验 P4,D4,D5,D6,D7

其实上表很有规律很容易记
要知道海明码Hi由哪些校验组校验
可以把i化成 二进制数 数中哪些位k是1,就有哪些Pk校验
如H7  7=0111 所以由P1,P2,P3
  H11 11=1011 所以由P1,P2,P4
  H3  3=0011 所以由P1,P2


那看看Pi的值怎么确定
如果使用偶校验,则
P1=D0 xor D1 xor D3 xor D4 xor D6
P2=D0 xor D2 xor D3 xor D5 xor D6
P3=D1 xor D2 xor D3 xor D7
P4=D4 xor D5 xor D6 xor D7
其中xor是异或运算
奇校验的话把偶校验的值取反即可.


那怎么校验错误呢.
其实也很简单. 先做下面运算.
G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6
G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6
G3 = P3 xor D1 xor D2 xor D3 xor D7
G4 = 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
=1

P2=D0 xor D2 xor D3 xor D5 xor D6
=1 xor 0 xor 1 xor 1 xor 1
=0

P3=D1 xor D2 xor D3 xor D7
=0 xor 0 xor 1 xor 0
=1

P4=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

传输后为011101001101
G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6
=1
G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6
=0
G3 = P3 xor D1 xor D2 xor D3 xor D7
=0
G4 = 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)

 

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 + 011/1011
所以r(x)=011

所以要求的编码为1010011

例2: 上题中,数据传输后变为1000011,试用纠错机制纠错.
1000011 / g(x) = 1011 + 110/1011

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