[中级]软考_软件设计_计算机组成与体系结构_02_校验码

校验码

• 前言
• 考点一 奇偶校验码
• • 概念：
  • • 概念解析
    • 往年真题
  • 结论
• 考点二 CRC循环冗余校验码
• • 概念：
  • • 往年真题
  • 结论
• 考点三 海明校验码
• • 概念：
  • 校验位的求取公式
  • • 往年真题
  • 结论
• 章节总结

前言

校验码基础知识：

• 码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。

  0,1：从0变成了1，只发生了一个数字的变化，所以码距是1

例如：用4位二进制表示16种状态，则有16个不同的码字(0000 ~ 1111)，此时码距为1。因为变化最少的尾数是：0000与0001。

考点一 奇偶校验码

概念：

奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加
上一个二进制位（校验位）组成校验码。

• 奇校验：整个校验码(有效信息位和校验位)中“1”的个数为奇数。

• 偶校验：整个校验码(有效信息位和校验位中“1”的个数为偶数。

概念解析

往年真题

以下关于采用一位奇校验方法的叙述中，正确的是 ( C )。
A、若所有奇数位出错，则可以检测出该错误但无法纠正错误
B、若所有偶数位出错，则可以检测出该错误并加以纠正
C、若有奇数个数据位出错，则可以检测出该错误但无法纠正错误
D、若有偶数个数据位出错，则可以检测出该错误并加以纠正

备注：所有奇数位：0101，所有奇数位为1，3为奇数位出错，2，4为偶数位出错

结论

奇偶校验可检查1位(奇数位)的错误，不可纠错

考点二 CRC循环冗余校验码

概念：

CRC的编码方法是：在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错。

• r位校验码生成：根据生成多项式决定

把接收到的CRC码用约定的生成多项式G(X)去除（模二除法），如果正确，则余数为0；如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有惟一的对应关系。

• 中级目前没有涉及,在高级中有考到，但是曾考到过模二除法，了解即可，无需过多关注

往年真题

在( D )校验方法中，采用模2运算来构造校验位。
A、水平奇偶
B、垂直奇偶
C、海明码
D、循环冗余

结论

CRC校验，可检错，不可纠错。

考点三 海明校验码

概念：

  海明校验码的原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据

校验位的求取公式

2 r ≥ m + r + 1 2^r ≥ m+r+1 2r≥m+r+1

也可写作
2 r − 1 ≥ m + r 2^r-1 ≥m+r 2r−1≥m+r

• r 要求的是最小值
• m 是信息位的个数
  假设是16位信息，m就是16，也就是说：2^r≥16+r+1,所以r≥5才满足。

往年真题

以下关于海明码的叙述中，正确的是( A )
A、海明码利用奇偶性进行检错和纠错
B、海明码的码距为1
C、海明码可以检错但不能纠错
D、海明码中数据位的长度与校验位的长度必须相同

海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于某些被校位的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。对于32位的数据，至少需要增加( D )个校验位才能构成海明码。
以10位数据为例，其海明码表示 D 9 D_9 D9​ D 8 D_8 D8​ D 7 D_7 D7​ D 6 D_6 D6​ D 5 D_5 D5​ D 4 D_4 D4​ P 4 P_4 P4​ D 3 D_3 D3​ D 3 D_3 D3​ D 2 D_2 D2​ D 1 D_1 D1​ P 3 P_3 P3​ D 0 D_0 D0​ P 2 P_2 P2​ P 1 P_1 P1​中，其中 D i D_i Di​(0≤i≤9)表示数据位， P j P_j Pj​(1≤j≤4)表示校验位，数据位 D 9 D_9 D9​由 P 4 P_4 P4​、 P 3 P_3 P3​和 P 2 P_2 P2​进行校验（从右至左 D 9 D_9 D9​的位序为14，即等于8+4+2，因此用第8位的 P 4 P_4 P4​第4位的 P 3 P_3 P3​,和第2位的 P 2 P_2 P2​校验)，数据位 D 5 D_5 D5​由( B )进行校验。

A、3      B、4
C、5      D、6

A. P 4 P_4 P4​ P 1 P_1 P1​       B、 P 4 P 2 P_4P_2 P4​P2​
C. P 4 P 3 P 1 P_4P_3P_1 P4​P3​P1​       D、 P 3 P 2 P 1 P_3P_2P_1 P3​P2​P1​

备注：32位，m = 32;这道题，可以通过找规律的方式求解

结论

海明校验，可检错，也可纠错。

章节总结