大家好，欢迎来到IT知识分享网。
计算机只能识别二进制数，在信息传输过程中，都是以电信号/光信号的形式进行传输。由于传输距离远，可能会导致信号衰减产生误差，在信息使用前需要进行相应的检验，以便判别信息是否正确，这种用于检查的信息，称为校验码。
校验码是在信息中额外增加的一些数据，来帮助校验。
最常用的校验码有3种：
- 奇偶校验：能检错，不能纠错。
- CRC循环冗余校验：能检错，不能纠错。
- 海明校验：能检错，能纠错。
考试考点：
- 3者的比对；
- CRC循环冗余校验的计算过程 或 编码过程。
奇偶校验
奇偶校验码的编码方法：由若干位有效信息的头部或尾部，再加上一个二进制位（校验位）组成校验码。实际包括两种校验：
- 奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
- 偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。
如：有效信息为：1011，则：
- 奇校验位为 0，校验码为 10110；
- 偶校验位为1，校验码为 10111。
如果有奇数个位发生误码，则奇偶性发生变化，可以检查出误码，但不能纠错。
如果有偶数个位发生误码，则奇偶性不发生变化，不能检查出误码（也称漏码）。
例：给出编码 的奇校验码和偶校验码（ ）。
A）, B）,
C）, D）,
解：由于奇偶校验位一定是互斥的，因此B、C校验码相同的情况可以排除。奇校验需要确保校验码“1”总数为奇数，偶校验需要确保校验码“1”总数为偶数。因此选：A
CRC循环冗余校验
CRC循环冗余校验的预备知识：
1 异或
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
2 模2运算
- 被除数首位是几商几；
- 异或运算；
- 异或后首位一定是0舍弃掉这个0首位（去首位补末位）；
- 补末位（落数），再上商。
例：1011 0010 000 模二除 11001
解：商，余数1010。
3 CRC校验码
CRC校验码：通信领域最常用的差错校验码。有两个部分：
- 左侧信息位：待发送数据；
- 右侧差错检测码：基于待发送数据与生成多项式的差错检测码，也称冗余码。
冗余位数越多，校验能力越强。
具体过程：
- 收发双方约定好生成多项式G(x)；
- 发送方基于待发送数据和生成多项式计算出差错检测码（冗余码），将其添加到待传输数据的后面一起传输；
- 接收方通过生成多项式来计算收到的数据是否产生了误码。
【注】算法要求：生成多项式必须包含最低此项，即x的0次项。
设：
完整形式：
因此生成多项式的bit形式为：10111。
在计算时，信息进行补零后形成被除数，生成多项式串是除数，最终的校验检测码是模2运算的余数。
例1：待发信息位，生成多项式为
计算编码后的信息。
解题的步骤如下：
- 构造被除数：待发送信息后添加生成多项式最高次数个0；
- 构造除数：生成多项式各项系数构成的比特串；
- 做模二除法运算；
- 检查余数：余数的位数应与生成多项式最高次数相同，如果位数不够，则在余数前补0来凑足位数。
解：
- 由生成多项式最高次项为3次，待发信息补3个0，除数；
- 生成多项式1101；
- 进行模二除法：
- 冗余校验码为001，因此编码后的信息为：。
例2：接收到的信息为，生成多项式为：
判断传输是否有误码。
解题的步骤如下：
- 构造被除数：接收到的信息就是被除数；
- 构造函数：生成多项式各项系数沟通的比特串；
- 做模二除法运算；
- 检查余数：余数为0，传输过程无误码；余数不为0，传输过程产生误码。
解：
- 除数：；
- 构造除数：1101；
- 做模二除法：
- 由于余数不为0，所以该信息为误码。
另外，如果是例1编码后的值，模二除后，余数为0。
例3：在（ ）校验方法中，采用模二运算来构造检验位。（2019年上半年考题）
A）水平奇偶 B）垂直奇偶 C）海明码 D）循环冗余
答案：D
海明码校验
利用奇偶性来检错纠错的方法。在数据中增加冗余位来进行检错纠错的方法，以提高传输、存储的准确性。
海明码的原理
将原始数据分成若干个数据块，每一块数据中又开辟若干位校验位，用于检出错误后，利用校验位进行纠错，最终得到正确的数据。
数据之间的特定位上，加入K个校验位，通过扩大码距从而实现检错、纠错。
海明码实现方法
设数据位是n位，校验位是k位，则 n 和 k 必须满足以下关系：
【注】2^k 之所以减1，是因为数据所有可能情况中有一种情况位正确，因此要减1。
海明码的编码规则如下：
设k个校验位为：
n 个数位为：
对应的海明码为：
- 校验码Pi要放在2^(i-1)的位置；
- 海明码中的任何一位都是由若干个校验位来检验的；
- 被校验的海明位的下标等于所有参与校验该位的校验位的小标之和，而校验位由自身校验。
例：待传送信息为1010，若采用海明码校验，则奇校验规则下的海明码是（ ）。
A）0 B）0 C） D）
解：
根据：
n = 4，
可以将 k = 1, 2, 3, … 带入不等式，得到最小的 k = 3。
则H位数为：3 + 4 = 7 （位）
校验位分别为：
则校验位 Pi 与 数据 Dk的排列如下：
|
位数 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
Pi |
P1 |
P2 |
D1 |
P3 |
D2 |
D3 |
D4 |
|
Dk |
1 |
0 |
1 |
0 |
建立海明码对应表：
|
校验码的位数 |
1 |
2 |
4 |
方法 |
|
海明码 |
P1 |
P2 |
P3 |
|
|
H1(P1) |
√ |
P1自己 |
||
|
H2(P2) |
√ |
P2自己 |
||
|
H3(D1) |
√ |
√ |
第3位：1+2（P1、P2代表的位数相加等于第3位） |
|
|
H4(P3) |
√ |
P3自己 |
||
|
H5(D2) |
√ |
√ |
第5位：1+4（P1、P3代表的位数相加等于第5位） |
|
|
H6(D3) |
√ |
√ |
第6位：2+4（P2、P3代表的位数相加等于第6位） |
|
|
H7(D4) |
√ |
√ |
√ |
第7位：1+2+4（P1、P2、P3代表的位数相加等于第7位） |
将表逐列向下看：
P1校验：D1、D2、D4 → 1 0 0 → P1 = 0；
P2校验：D1、D3、D4 → 1 1 0 → P2 = 1；
P3校验：D2、D3、D4 → 0 1 0 → P3 = 0。
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
Pi |
P1 |
P2 |
D1 |
P3 |
D2 |
D3 |
D4 |
|
Dk |
1 |
0 |
1 |
0 |
|||
|
H |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
则海明码为：0，选A
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/180480.html
