计算机组成原理-03-校验码

计算机组成原理-03-校验码

1. 校验码概述

• 校验码：指能够发现或能够自动纠正错误的数据编码，也称检错纠错编码。

• 实现原理：通过加一冗余码，来检验或纠错编码

• 码距：简单来说就是两个二进制数比较，在同一数位的地方，数位值不同的个数有多少个，即码距，也称海明距离；

• 两种方法计算码距。比如0100和1111
  直接观察法：可以看出，有3个数位值不同，所以码距为3.
  异或计算法：0100⊕1111=1011 ，结果为1011，里面有几个1就代表有多少个数位值不同，即码距是多少，这里码距是3。

2. 奇偶校验码

• 实现原理： 在原编码中加一个校验位，则原编码就变成了校验码，它的码距为2，可以检查出奇数位错误，但不能检查出偶数位错误，增加的冗余位为奇偶校验位，一般校验位设置在原编码的最左边或最右边。
• 奇校验码：整个校验码（信息位+校验位）中1的个数位奇数
• 偶校验码：整个校验码（信息位+校验位）中1的个数位偶数

2.1 奇校验

如何检测出错误？

• 首先在计算机中，我们就要约定好，数据是采用奇校验还是偶校验，下面分奇校验和偶校验来说明一下奇偶校验如何检查在计算机传输数据的过程中数据是否正确。
• 假设我们的原始编码是10110111，因为我们规定计算机采用奇校验，所以我们在原编码最左边多加了一个校验位，并置为1，那么原编码就变成了奇校验码，有奇数（7）个1。
  • 传输过程中奇数个数据改变：在传输过程中有奇数个数位值发生了改变，那么我们通过奇校验运算，可以发现现在变成了6个1，和奇校验码相比有3个数位值发生了改变，奇校验码不再有奇数个1，而是变成了偶数个1，可以判断我们的数据发生了改变，可以检查出错误。
  • 传输过程中有偶数个数据改变：在传输过程中有偶数个数位值发生了改变，那么我们通过奇校验运算，都是奇数，这时我们便无法通过奇校验运算判断数据是否发生了改变，即无法检查出偶数个错误。

2.2 偶校验

• 假设我们的原始编码是10110111，因为我们规定计算机采用偶校验，所以我们在原编码最左边多加了一个校验位，并置为0，那么原编码就变成了偶校验码，有偶数（6）个1。
  • 传输过程中奇数个数据改变：在传输过程中有奇数个数位值发生了改变，那么我们通过偶校验运算，可以发现现在变成了5个1，和偶校验码相比有3个数位值发生了改变，偶校验码不再有偶数个1，而是变成了奇数个1，可以判断我们的数据发生了改变，可以检查出错误。
  • 传输过程中有偶数个数据改变：在传输过程中有偶数个数位值发生了改变，那么我们通过偶校验运算，可以发现现在变成了6个1，和原偶校验码6个1一样，都是偶数，这时我们便无法通过偶校验运算判断数据是否发生了改变，即无法检查出偶数个错误。

2.3 小结

• 通过上述奇偶校验两种方式校验数据，可以比较得出奇偶校验可以检测出奇数个错误而无法检查出偶数个错误，也无法纠正错误，无法定位错误位置。

3. 汉明校验码

• 一种多重奇偶校验码。
• 实现原理：在有效信息位中加入几个校验位形成海明码，并把海明码的每一个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化。
• 特点：可以发现错误，定位错误位置，自动纠正错误。 可以检测双比特错误，但只能纠正单比特错误。

纠错理论：L-1=D+C且D≥C
编码最小码距L越大，其检测错误的位数D越大，纠正错误的位数C也越大，且纠错能力恒小于检错能力

3.1 例题讲解

• 信息为 n=4 , 校验位 k=3,求1010的海明码

1. 确定海明码的位数

• 根据公式：2k ≥ n+k+1（若要检测两位错，则需再增加1位校验位，即k+1位）
• 海明码位数n+k=7，公式 2^3 ≥ n+k+1=8成立，n,k有效。设置变量来表示信息位、校验位、海明码。

2. 确定校验位的分布

• 规定校验位 pi 在海明位号位 2^(i-1) 的位置上，所以：

3. 分组形成校验关系

• 每个数据位用多个校验位来检验。
• 必须满足条件：被校验数据位的海明码位号 = 校验该数据位的各校验位海明位号之和，比如校验D3，它的海明位号H6为6，那么校验它的校验位为P3和P2，因为他们的海明位号H4和H2加起来等于6。（化为二进制的位数）
• 校验位不需要再被校验
• 分组关系如图：

4. 校验位的取值

• Pi的值 = 第 i 组所有数据位求异或⨁
• P1=D1⨁D2⨁D4=0
• P2=D1⨁D3⨁D4=1
• P3=D2⨁D3⨁D4=0

5. 海明码的校验原理

• 每个校验组分别利用校验位和参与形成该校验位的信息位进行奇偶校验检查，即异或运算⨁，构成k个校验方程。

  • S1=P1⨁D1⨁D2⨁D4
  • S2=P2⨁D1⨁D3⨁D4
  • S3=P3⨁D2⨁D3⨁D4

• 若S1S2S3=000,则说明无错，否则说明出错。

• 这个数的值就是出错的位置，如S1S2S3=001,表示第1位出错，即H1出错，直接将该位取反就可以达到纠错的目的。

4. 循环冗余CRC码

• 基本思想：校验码中的一种。在K位信息位后拼接R位检验位，组成CRC码，这种编码也称(N,R)码
• 特点：可以发现错误，定位错误位置，自动纠正错误。可检测出所有奇数位错，所有双比特的错和所有小于、等于校验位长度的突发错

1. 生成多项式

• 首先，发送端和接受端会有一个生成多项式G(x)约定,生成多项式G(x)的最高次幂为R。任意一个二进制数码都可用一个系数为0或1的多项式与之对应。比如：二进制数码 1101 对应的G(x)=1X^3+1X^2+0X^1+1X^0= X^3+X^2+1
• 在发送端，将要传送的K位二进制信息码左移R位，将它与生成多项式G(x)所对应的的二进制数码进行模2除法，产生余数，生成一个R位检验码，并附在信息码后，构成一个新的二进制码（CRC）码，共K+R位。

4.1 例题讲解

• 例题： 设生成多项式G(x)=X^3+X^2+1 ,信息码为 101001 ，求对应的CRC码 。

分析

• 分析：校验位长度：R=3 , 信息码长度：K=6 , CRC码长度：N=R+K= 9
• 生成多项式对应二进制码：1101

1. 信息码左移R位

• 发送端将原信息码左移R位，低位补0：101001 000

2. 模2除得到余数

• 方法：发送端用移位后的信息码 101001000 除以G(x)所对应的二进制数码 1101 求余数，余数除得够就写1，不够就写0，直到余数小于 1101 ，余数即为校验位的数值。
• 图中即为具体计算步骤，得到最后的结果CRC码为：101001 001，然后发送端将CRC码101001 001发送给接收端。

3. 如何检错和纠错？

• 接收端收到CRC码后，用生成的CRC码除以生成多项式G(x)所对应的的二进制数码，若余数为0，则信息码在传输过程中没有产生错误，数据正确。

• 若接受到的CRC码为C9C8C7C6C5C4C3C2C1= 101001011,除以G(x)所对应的二进制码1101得到余数为010，不为0，说明数据在传输过程中产生错误。010=2（10）说明C2出错，将C2取反即可纠正错误。

打赏