计算机组成原理学习笔记——校验码
校验码
〇、何为校验码一、奇偶校验码1、定义2、特点3、例子4、缺点5、使用范围6、8421 码的奇偶校验码
二、海明校验码1、概念2、步骤1）确定海明码的位数2）确定校验位的分布3）分组以形成校验关系4）校验拉取值5）校验
3、校验原理
三、循环冗余校验码1、基本概念2、CRC 编码方法3、例子1）移位2）相除3）检错和纠错
3、使用范围
〇、何为校验码
校验码是指能够发现或能够自动纠正错误的数据编码，也称作检错纠错码。原理是通过增加一些冗余码，来检验或纠错编码。通常某种编码有许多码字构成，任意两个合法码字之间最少变化的二进制位数，称为数据校验码的码距，如 1100 和 1101 之间的码距为 1，因为只有最低位翻转了；而 1001 和 0010 之间的码距为 3，因为只有 1 位没有变化。对于码距不小于 2 的数据校验码，开始具有检错的能力。码距越大，检错纠错的能力越强，而且检错能力总是大于等于纠错能力。常用的校验码有奇偶校验码、海明校验码和循环冗余校验码。
一、奇偶校验码
1、定义
在被传送的 n 位代码上增加一位校验位，并使其配置后的 n+1 位代码中“1”个数为奇数，则称为奇校验；若配置后“1”的个数为偶数，则称为偶校验。
2、特点
奇偶校验码的码距为 2，可以检测出一位错误（或奇数错误），但不能确定出错的位置，也不能够检测出偶数位错误。
3、例子
简单例子如下：
4、缺点
具有局限性，奇偶校验只能发现数据代码中奇数位的出错情况，但不能纠正错误。
5、使用范围
奇偶校验通常用于 I/O 设备，如键盘输入时使用的 ASCII 码，对存储器数据的检查，对传输数据的检查。
6、8421 码的奇偶校验码
这里再补充下带符号的 BCD 码的表示
二、海明校验码
1、概念
海明码是一种多重奇偶校验码，原理是在有效信息位中加入几个校验位形成海明码，并把海明码的每个二进制位分配到几个奇偶校验组中；当某一位出错后，就会引起有关的几个校验位的值发生变化，不但可以发现错位，还能指出出错的位置，为自动纠错提供依据。 根据纠错理论得： L - 1 = D + C 且 D≥C即编码最小码距 L 越大，其检测错误的位数 D 越大，纠正错误的位数 C 也越大，且纠错能力恒小于等于检错能力。
2、步骤
在 n=4，k=3 时，求 1010 的海明码
1）确定海明码的位数
设 n 为有效信息的位数，k 为校验位的位数，则 n,k 应当满足:n+k≤2k-1（若要检测两位错，则需要再增加 1 位校验位，即 k+1 位）代入 n，k 式子成立，则 n，k 有效。设信息位为 D4D3D2D1(1010)，共四位，校验位为 P3P2P1，共 3 位，对应的海明码为：H7H6H5H4H3H2H1。
2）确定校验位的分布
规定校验位 Pi 在海明位号为 2^(i-1) 的位置上，其余各位为信息位，例如：P1 的海明位号为 2^0=1，即 H1 为 P1，所以海明码各位的分布如下：
3）分组以形成校验关系
每个数据位用多个校验位进行校验，但要满足条件：被校验数据位的海明位号等于校验该数据位的各校验位海明号之和。另外，校验位不需要再被校验。分组形成的校验关系如下：
4）校验拉取值
校验位 Pi 的值为第 I 组（由该校验位校验的数据位）所有位求异或（则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0；同为0，异为1）。由3）得： 所以，1010 对应得海明码为 1010010
5）校验
3、校验原理
三、循环冗余校验码
1、基本概念
循环冗余校验码（Cycle Redundancy Check）是基于模 2 运算而建立编码规律的校验码。 模 2 运算不考虑进位和错位，规律如下： 1）模 2 加和模 2 减的结果是相等的，即 0±1=1，0±0=0，1±0=1，1±1=0，两个相同数模 2 和恒为 0. 2）模2 乘是按模 2 和求部分之和。 3）模 2 除是按模 2 减求部分余数；每求一位商应使部分余数减少一位。上商的原则是：当部分余数的首位为 1 时，上商 1；当部分余数的首位为 0 时，上商 0；当部分余数的位数小于除数的位数时，该余数即为最后余数。
2、CRC 编码方法
3、例子
用一个例子学习循环冗余码的生成步骤。设生成多项式为 G(x)=x3+x2+1，信息码为 101001，求对应的 CRC 码。 解：R= 生成多项式的最高次幂=3，K=信息码长度=6，N=K + R = 9，生成多项式对应的二进制码为 1101（看生成多项式最高次数是多少，那么对应的二进制码就是多少位的，然后从高到低次幂有出现的，对应位就为 1，没出现的就为 0）
1）移位
先将信息码左移 R 位，也就是 3 位，低位补零得到 101001000
2）相除
对移位后的信息码，用生成多项式进行模 2 除法，产生余数，过程如下： 得到的余数为 001，则原信息码 101001 对应的 CRC 码为：101001001
3）检错和纠错
接收端收到的 CRC 码，用生成多项式G(x) 做模 2 除法，若余数为0，则码字无错； 加入接收端收到的码字为：101001011，将其与1101进行模 2 除法，得到的余数为 010，说明第 2 位（从右往左数123…）出错，只需将第 2 位取反就可以了。
3、使用范围
CRC 码在磁介质存储器和计算机之间通信方面广泛应用。
上一篇 下一篇