计算机组成原理学习笔记：奇偶校验码

概述

• 数据在计算机内部进行计算，存储还有传送的过程当中，由于计算机元器件有可能会发生故障
• 或者有可能会因为某些环境噪音干扰，导致我们在计算机内部存储传输的这些二进制数据会发生错误
• 所以我们就必须考虑到数据的校验这样的东西，怎么做才能知道才能发现这种错误的发生
• 另外当检测到错误发生之后，应该怎么来改正这个错误呢?
• 奇偶校验是一种可以发现数据错误的一种编码机制

校验原理

• 两台计算机之间进行数据的传输，那它们有可能会传出这样的信息：ABCD，假设对应编码如下

• 由于只有4种信息，我们只需要两个bit的信息，就可以和上述四个信息进行一个一一的映射, 假设他们想要传输的是B这个信息也就是二进制的01
• 但是现在由于某种神秘的环境因素的干扰，导致了这两个二进制位在传输的过程当中发生了跳变，也就是发生了所谓的位错误，0可能会变成1; 1可能会变为0
• 假设是第2个二进制位发生了错误，接收端的计算机最后收到的数据就变成了00，所以本来他们想传送的是B这个信息
• 但是由于环境因素的干扰，接收端计算机接收到的实际是A，由于00这个信息也是合法的，接收端计算机，并不能判断出它接受到的这个数据是不是发生了错误

• 把这个编码方案进行一个优化，我们增加一个冗余的校验位，这时候就有3位了，由于2的3次方等于8，也就是说3个二进制位，本来可以映射为8种状态
• 但是现在我们只取了其中的4个状态作为合法的状态，剩下的4个是冗余的非法状态, 采用这种编码方案来传输数据，就可以让我们发现某一些二进制位的错误
• 要发送B这个信息，B所对应的二进制编码是001，在传输的过程中，假设是最后一位发生了错误，接收端计算机就会接收到000这个信息
• 000这个信息，是一个非法的状态，所以此时接收端计算机就可以判断000，一定是发生了错误的，就可以让它重新再传输

基本概念

• 码字：由若干位代码组成的一个字叫码字
  • 第1种编码方案，2个bit位，有可能出现4种状态，而这4种状态都是合法的码字
  • 第2种，三个bit有8种状态，这8种状态当中只有其中的4个是合法的码字，剩下4个是非法的码字
• 两个码字间的距离：把两个码字进行逐位的对比，他们之间有几个位不一样，我们就称为这两个码字之间的距离为多少
  • 1 ) 比如上述第一种编码方案中的A和C
  • A: 00
  • C: 10
  • 可见，第一个二进制位是不一样的，由此它们的码字间距离是1
  • 2 ) 比如上述第二种编码方案中的A和C
  • A: 100
  • C: 010
  • 可见，前两个二进制位是不一样的，由此它们的码字间距离是2
• 码距：一种编码方案可能会有若干个合法的码字，这些合法码字之间的最小距离
  • 像第1种2bit的编码,所有的合法码字之间的最小距离是1，也就是说码距为1
  • 当码距为1就意味着当信息在传输的过程中，如果有一个比特位发生了跳变，有可能使得从一个合法的码字跳变到另一个合法的码字，由于跳变的码字也是合法的
  • 所以接收方就无法检测出数据在传输的过程当中有没有发生错误
  • 像第2种方案所有合法的码字之间，它们之间的最小距离是2, 也就是说任意两个合法码字之间至少都会有两个二进制比特位是不一样的
  • 意味着在数据传输的过程当中，如果只有一个比特位发生了跳变，一个bit的错误一定会使得我们的码字进入一个非法的状态
  • 在这种情况下我们就可以检测出数据的错误，因此可以看到一种编码方案的检测能力如何和码距是息息相关的
  • 对于码距唯一的编码方案，一定是没有检测能力的，而当马距等于2的时候，开始出现了检错的能力
  • 而如果能设计码距大于3的编码方案，在设计合理的情况下，除了检错之外，甚至还有可能会有纠错的能力，比如: 海明码

奇偶校验码

• 原理：如果有n个有效的信息位，那么我们会在这些信息位的首部或者尾部加入一位的奇偶校验位
• 如果采用奇校验的策略，我们需要保证我们添加的这个校验位，还有所有的信息位里面，1的个数必须是奇数个，那偶校验的策略也是类似的
• 奇校验码：整个校验码(有效信息位和校验位)中的"1"的个数为奇数
• 偶校验码：整个校验码(有效信息位和校验位)中的"1"的个数为偶数
• 备注：奇偶校验码只具有检错能力

• 例题：给出两个编码：1001101 和 1010111的奇校验码和偶校验码, 设最高位为校验位，余7位是信息位，求对应的奇偶校验码为
  • 1001101的奇校验码：
    • 目前已经有4个1了，因此我们需要在高位再补上一个1让其变成奇数个1，即：11001101
  • 1010111偶校验码：
    • 目前已经有5个1了，因此我们需要在高位再补上一个1让其变成偶数个1，即：11010111
  • 检测错误: 以偶校验码为例
    • 如果11010111在发送过程中发生了一个bit的信息跳变，比如最后的1变成了0，当接收的时候，并不符合偶校验码的规定，确定出了问题并要求重新传送
    • 如果11010111在发送过程中发生了两个bit的信息跳变，比如最后的两个1变成了0，当接收的时候，发现有4个1，这时符合偶校验码的规定，接收方会以为自己收到合法的数据, 这时候是检测不出来错误的
    • 由上可知，这是奇偶校验码检测错误的局限性

奇偶校验的硬件实现

• 以偶校验的硬件实现为例, 确定一串信息位的校验位是多少位, 可以通过硬件的异或(模2加)运算来确定
• 关于异或运算的规则是相同为0，相异为1, 如下例：
  • $0\oplus 0=0$
  • $0\oplus 1=1$
  • $1\oplus 0=1$
  • $1\oplus 1=0$

1 ) 获取偶校验码示例

• 对于编码1001101求其偶校验位, 我们可以基于异或来实现, 将其所有的比特位进行异或运算
  • $1\oplus 0\oplus 0\oplus 1\oplus 1\oplus 0\oplus 1=0$
  • 所有比特位进行异或运算得到的结果是0
  • 这个0就是最高位补全的偶校验位上的数字
  • 把完整的数字拼接，得到偶校验码：01001101
• 对于编码1010111求其偶校验位, 我们可以基于异或来实现, 将其所有的比特位进行异或运算
  • $1\oplus 0\oplus 1\oplus 0\oplus 1\oplus 1\oplus 1=1$
  • 所有比特位进行异或运算得到的结果是1
  • 这个1就是最高位补全的偶校验位上的数字
  • 把完整的数字拼接，得到偶校验码：11010111

2 ) 进行校验

• 同样需要进行异或运算，对所有的二进制位，包括校验位进行异或, 若结果为1，则说明出错
• 对于偶校验码: 01001101
  • $0\oplus 1\oplus 0\oplus 0\oplus 1\oplus 1\oplus 0\oplus 1=0$
• 对于偶校验码: 11010111
  • $1\oplus 1\oplus 0\oplus 1\oplus 0\oplus 1\oplus 1\oplus 1=0$
• 基于如上可知：
  • 目前都是通过校验的
  • 如果某一位跳变会得到结果为1，则发生错误
  • 如果其中两位发生了跳变，则校验结果为0，此时无法正确检测出来错误
  • 对于偶校验码来说，如果有偶数个比特发生了错误，那么我们是无法检测出错误的

总结

• 奇偶校验
  • 校验原理
    • 码字间的距离：两个码字之间有几个位不同
    • 码距：一个编码方案中，合法码字间的最小距离
    • 若码距=2，有检错能力；若码距 >= 3, 可能还会有纠错能力
  • 奇偶校验
    • 在信息位的首部或尾部添加一个奇偶校验位
    • 奇校验：整个校验码(信息位和校验位)中"1"的个数为奇数
    • 偶校验：整个校验码(信息位和校验位)中"1"的个数为偶数
    • 奇偶校验码的码距d=2, 仅能检测出奇数位错误，无纠错能力
  • 异或运算(模二加)
    • 两个比特进行异或运算，仅当二者不同时计算结果为1