2024年2月21日发(作者：云厚)
我们知道，数字数据在其传输线路上会受到各种干扰的影响，有时候会产生误码，因此必须引入数据校验技术来验证数据传输的正确性和有效性。目前，最为普通的两种校验技术就是循环冗余校验和奇偶校验技术。下面将依次说明两种校验技术的原理。
奇偶校验
在发送数据时，数据位尾随的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+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
码字:1→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减法求得余数,该余数不计最高位。当被除数逐位除完时,最后得到比除数少一位的余数。
奇偶,海明,CRC校验码
计算机系统运行时,各个部之间要进行数据交换.
为确保数据在传送过程正确无误,常使用检验码.
我们常使用的检验码有三种.
分别是 奇偶校验码,海明校验码 和 循环冗余校验码(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个校验码为 Pk, n个数据位为Dn
产生的海明码为 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 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个校验位求其偶校验方式的海明码.
传输后数据为,是否有错?
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
传输后为
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出错了,对它求反
和我们算的一样.
由此可见 海明码 不但有检错还有纠错能力
下面说下最后一种 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
对应二进制编码是 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
1
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位出错.对其求反即可.
2024年2月21日发(作者：云厚)
我们知道，数字数据在其传输线路上会受到各种干扰的影响，有时候会产生误码，因此必须引入数据校验技术来验证数据传输的正确性和有效性。目前，最为普通的两种校验技术就是循环冗余校验和奇偶校验技术。下面将依次说明两种校验技术的原理。
奇偶校验
在发送数据时，数据位尾随的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+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
码字:1→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减法求得余数,该余数不计最高位。当被除数逐位除完时,最后得到比除数少一位的余数。
奇偶,海明,CRC校验码
计算机系统运行时,各个部之间要进行数据交换.
为确保数据在传送过程正确无误,常使用检验码.
我们常使用的检验码有三种.
分别是 奇偶校验码,海明校验码 和 循环冗余校验码(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个校验码为 Pk, n个数据位为Dn
产生的海明码为 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 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个校验位求其偶校验方式的海明码.
传输后数据为,是否有错?
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
传输后为
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出错了,对它求反
和我们算的一样.
由此可见 海明码 不但有检错还有纠错能力
下面说下最后一种 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
对应二进制编码是 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
1
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位出错.对其求反即可.