第03章 37 数据校验码

★校验码

●将有效代码和增加的校验位一起，按约定的

校验规律进行编码而获得。

3.7数据校验码●是一种常用的带有发现错误或带有自动改错

能力的数据编码方法。●实现原理：

加进一些冗余码，使合法编码出现某些错误时，就

成为非法编码。这样，就可通过检测编码的合法性

来达到发现错误的目的。11/27★码距：指任意两个合法码之间至少有几个

二进制位不相同。

●若码距为1，则发生错误时仍是合法码，无查错能力。

●一般来说，合理增大码距，就能提高发现错误的能力，

但码使用的二进制位数变多，增加了数据存储的容量

或数据传送的数量。

●在确定与使用数据校验码时，通常要考虑在不过多增

加硬件开销的情况下，尽可能发现或改正更多的错误。22/27★例：有一个4位编码的全部码字为：a．0000b．0011c．1100，问此编码的码距是多少？说明理由。

解：因为：d(a,b)=2d(a,c)=2d(b,c)=4

编码的码距为代码码距的最小值，所以：此编码的码距为2。33/27★开销最小，能发现数据中一位出错的情况。一、奇偶校验码★实现原理：使码距由1增加到2。

若编码中有一个二进制位出错（由1变成0，或由0变成1），这个码都将成为非法编码。

★实现方法

为一个字节补充一个二进制位（校验位），设置该校验位的值为0或1，使字节的8位和该校验位中含有“1”值的总个数为奇数（奇校验）或偶数（偶校验）。44/27★例如

设某数据为：10110001

奇校验码为：

偶校验码为：★缺点

●只能发现奇数位错，但不能确定是哪一位。

●因一位出错的几率大，故有实用价值。11011000101011000155/27★逻辑实现：多采用并行奇偶统计方法。编码译码66/27★实质：是一种多重奇偶校验。二、海明校验码（广泛采用）★实现原理：

●将代码按一定的规律组织为若干组，分组

进行奇偶校验。●各组的检错信息构成一个指误字，不但可以

发现出错，还能指出是哪一位出错，为自动

纠错提供依据。77/27(1)分成几组？增加多少校验位？

设待编信息k位，分为r组，每组增加一个

校验位，则r位校验位构成一个r位的指误字。★

r位校验位能表示2r种状态：●用全0表示“没有错误”；

●用其余2r-1种状态指出错误发生在哪一位。★具体实现88/27★

因为错误也可能发生在校验位，所以只有k=2r-1-r个信息能用于纠正被传送数据的位数。即需要满足：

2r≥k+r+1若设k=4，则r≥3，组成7位的（7,4）海明码。99/27(2)分组方法？

设4位待编信息A4A3A2A1，增加3位校验位

P3P2P1，构成一个3位的指误字G3G2G1。7654321A4A3A2P3A1P2P1★

Pi在海明码中位号为2i-1的位置上。？1010/277654321指误字A4A3A2P3A1P2P1第3组G3第2组G2第1组G1①“√”表示某位海明码参加某组。②有效信息位Ai分别参加2组以上。③每个校验位Pi只参加1组。√√√√√√√√√√√√1111/27(3)编码（以偶校验为例）？第1组：P1=A1A2A4第2组：P2=A1A3A4第3组：P3=A2A3A41212/27第1组：G1=P1A1A2A4第2组：G2=P2A1A3A4第3组：G3=P3A2A3A4(4)查错与纠错若G3G2G1＝000，若G3G2G1≠000，则无错；则G3G2G1的值即指明出错位，将该位取反即可纠正。1313/277654321指误字G3G2G1A4A3A2P3A1P2P1正确码0101101000出错码0111101101G1=P1A1A2A4=1110=1G2=P2A1A3A4=0110=0G3=P3A2A3A4=1110=11414/277654321指误字G3G2G1A4A3A2P3A1P2P1正确码0101101000出错码0110101001G1=P1A1A2A4=1110=1G2=P2A1A3A4=0110=0G3=P3A2A3A4=0110=01515/27(5)逻辑实现(译码电路)1616/27★在k＝4，r＝3的海明码中，其码距d＝

。两个合法码之间至少有1个有效信息位不同。因一个有效信息位至少参加2组校验，相应的两个校验位也会不同。(6)分析★d＝3的码能够检测2位错，或用来检测并纠正

1位错，但两者只能择一。31717/27●若G4＝0，G3G2G1=000，为无错。★如要能检测并纠正1位错，同时能发现2位错，此时应增加一个校验位，即应满足：

2r-1≥k+r P4=A1A2A3

A4P1P2

P3●若G4＝1，是1位错，再根据G3G2G1修正。总校验位●若G4＝0，G3G2G1≠000，即为2位错。G4=P4

A1A2A3

A4P1P2

P3码距d＝41818/27★校验规则：让校验码能被某一约定代码除尽。

●若能除尽，表明代码无错；

●若除不尽，余数将指明出错位置。

三、循环冗余校验码（CRC码）★实现原理：在k位信息位之后拼接r位校验位。

●问题1：如何从k位信息位简便地得到r位校验位？

●问题2：如何从k+r位信息码判断是否有错？1919/27★模2运算：以按位模2相加为基础，

运算时不考虑进位和借位。

●模2加减（异或）

0±0＝00±1＝11±0＝11±1＝0

●模2乘（用模2加求和）

例如：1010

×101

1010

0000

＋1010

1000102020/27●模2除（用模2减求余数）

～每求1位商使部分余数减少1位。

上商原则：部分余数的首位为1，商取1；

部分余数的首位为0，商取0。

当部分余数位数小于除数位数时，该余数为最后余数。

例如：101

10110000

101

0100

000

100

101

012121/27设：被除数M(x)：k位待编信息除数G(x)：r+1位？

余数R(x)：r位校验位商Q(x)

(1)CRC码的编码方法★具体实现a.将待编码的k位有效信息位组写成表达式：

M(x)=Ck-1Xk-1+Ck-2Xk-2+……+C1X+C0(Ci=0或1)b.将信息位组左移r位，变成多项式M(x)·

Xr；c.用M(x)·

Xr除以G(x)，所得余数作为校验位。d.有效的CRC码为：

M(x)·

Xr+R(x)=[Q(x)·

G(x)+R(x)]+R(x)=Q(x)·

G(x)。所以：CRC码能够被G(x)除尽。2222/27例如：对M(x)=1100，用G(x)=1011，求CRC码。a.将待编码的k=4位有效信息位组写成表达式：

M(x)=Ck-1Xk-1+Ck-2Xk-2+……+C1X+C0=X3+X2=1100b.将信息位组左移r=3位,M(x)·

Xr=M(X)·

X3=1100000c.用M(x)·

Xr除以G(x)，所得余数作为校验位。d.有效的CRC码[此处为(7,4)码]为：

M(x)·

Xr+R(x)=1100000+010=1100010。2323/27(2)CRC码的译码与纠错★译码：用收到的CRC码除以G(x)。

●若码字无误，则余数为0；

●若有某1位错，则余数不为0且不同位出错时的余数不同。注意：余数与出错位的对应关系不变，

它只与码制和生成多项式G(x)有关，

而与待测码字无关。2424/27

(7，4)循环码的出错模式(生成多项式G(x)=1011)

A1A2A3A4A5A6A7余数出错位正确1100010000无错误110001100171100000010611001101005110101001141110010110310000101112010001010112525/27★纠错：

对于用G(x)作模2除得到的余数R(x)，若补0

继续除下去，发现各次的余数按上表的顺序循环。

所以，可以采用一种节省硬件的纠错办法：●如只设置余数101的译码输出，对应于第1位A1出错。●