海明校验码是在n个数据位之外增设k个校验位，从而形成一个k+n位的新的码字，使新的码..

奇偶校验是一种简单而有效的校验方法。其基本思想是，通过在编码中增加一位校验位来使编码中1的个数为奇数（奇校验）或者为偶数（偶校验），从而使码距变为2。对于奇校验，它可以检测代码中奇数位出错的编码，但不能发现偶数位出错的情况，即当合法编码中奇数位发生了错误，也就是编码中的1变成0或0变成1，则该编码中1的个数的奇偶性就发生了变化，从而可以发现错误。

常用的奇偶校验码有3种，即水平奇偶校验码、垂直奇偶校验码和水平垂直校验码。

海明码

海明码的构成方法是：在数据位之间插入k个校验码，通过扩大码距来实现检错和纠错。设数据位是n位，校验位是k位，则n和k必须满足2k-1≥n+k的关系。

循环冗余校验码

循环冗余校验码（CRC）广泛应用于数据通信领域和磁介质存储系统中。它利用生成多项式为k个数据位产生r个校验位来进行编码，其编码长度为k+r。CRC的代码格式如下图所示。

CRC的代码格式

由此可知，循环冗余校验码是由两部分组成的，左边为信息码（数据），右边为校验码。若信息码占k位，则校验码就占n-k位。其中，n为CRC码的字长，所以又称为（n,k)码。校验码是由信息码产生的，校验码位数越长，该代码的校验能力就越强。在求CRC编码时，采用的是模2运算。模2运算加减运算的规则是按位运算，不发生借位和进位。

海明校验码

在数据中多加入几个校验位，把数据的每一个二进制位分配在几个奇偶校验组中，当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出哪一位出错。

首先要确定校验位的个数。假设校验位个数为r，则它能表示2^r个信息，用其中一个信息表示没有错误，其余2^r^-1个信息指出哪一位错，而错误也可能发生在校验位，因此只有k=2^r-1-r个信息能用于纠正被传送数据的位数。也就是说要满足关系

2^r≥k+r+1

注意：如要能检测与自动校正一位错，并发现两位错，那么还要加一位总校验位，则码距为4，此时应满足

2^r-1≥k+r

按上述不等式计算，可计算出数据位k与校验位r的对应关系，如下表所示。

k与r的对应关系

设海明编码为H_mH_m_-1…H₂H₁，则此海明码的编码规则是：校验位与数据位之和为m，每个校验位P_i在海明码中被分配在位号为2ⁱ^-1的位置，其余各位为数据位依次排列；海明码的每一位码H_i由多个校验位校验，其关系是被校验的每一位的位号等于校验它的各校验位之和。

可以看一个例子。现在要传送一个字节的数据，则k=8，那么r=4，所以海明码的总位数为12，可表示为

H₁₂H₁₁…H₃H₂H₁

4个校验位P₄~P₁对应的编号是H₈、H₄、H₂、H₁。其余为数据位D_i，则有以下排列：

D₈D₇D₆D₅P₄D₄D₃D₂P₃D₁P₂P₁

那么可以知道，D₈处在H₁₂的位置，12=4+8，所以由处在H₄的P₃和处在H₈的P₄检测，这样依次类推，可以得到由P₁检测的数值位有D₁、D₂、D₄、D₅和D₇，若用偶校验，其结果为

P₁=D₁⊕D₂⊕D₄⊕D₅⊕D₇

P₂=D₁⊕D₃⊕D₄⊕D₆⊕D₇

P₃=D₂⊕D₃⊕D₄⊕D₈

P₄=D₅⊕D₆⊕D₇⊕D₈

然后按下面关系对所得的关系实现偶校验，即

S₁=P₁⊕D₁⊕D₂⊕D₄⊕D₅⊕D₇

S₂=P₂⊕D₁⊕D₃⊕D₄⊕D₆⊕D₇

S₃=P₃⊕D₂⊕D₃⊕D₄⊕D₈

S₄=P₄⊕D₅⊕D₆⊕D₇⊕D₈

则校验得到的结果值S₄~S₁能反映海明码出错情况。按S₄S₃S₂S₁的顺序排列形成一个二进制数，转换为十进制数为j，表示H_j出错。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5