1 概述

1.1 检错和纠错

• 无论通信系统如何可靠，都不能做到完美无缺。因此，必须考虑怎样发现和纠正信号传输中的差错。
  • 检错：接收方知道有差错发生，但不知道是怎样的差错，向发送方请求重传（发现错误）
  • 纠错：接收方知道有差错发生，而且知道是怎样的差错，自行纠正（发现并改正错误）

1.2 差错控制原理

• 原理：传输 K 位，加入 r 位冗余（某种算法定义），接收方收到并进行计算比较
• 思考：检错和纠错哪种好？（假设有 100 件商品，成本都是 1 元，要求：发出 100 件合格的产品）

• 序号1：类似检错。合格的产品数量为 90，不符合要求。
• 序号2：类似纠错，其中 “增加合格率的成本” 相当于 纠错策略。合格的产品数量为 100，符合要求，但总成本过高。
• 序号3：类似加入 差错控制。将 “数量” 改为 120 件（冗余），合格的产品数量为 108，符合要求，同时总成本较低。

2 差错控制的方法

2.1 奇偶校验

• 检错：最常用的 ~ 方法，能检出 一位错位。
• 原理：在 7 位 ASCII 码 后 增加一位，使 码中 1 的个数 变成 奇数（奇校验） 或 偶数（偶校验）
  • 奇校验：1011 010（1）=> 5 个 1
  • 偶校验：1011 010（0） => 4 个 1

2.2 海明码

• 纠错：通过冗余数据位来检测和纠正差错的编码方式。（只能纠正 1 位错误）
• 原理：在数据 中间 加入几个校验码，码距均匀拉大，当某一位出错，会引起几个校验位的值发生变化。
• 海明距离：一个码字要变成另一个码字时必须改变的最小位数（不同位的个数）。
  • 0101 => 0100 => 不同位的个数为 1 位，故海明距离 = 1
  • 0101 => 0000 => 不同位的个数为 2 位，故海明距离 = 2
• 海明不等式： 2 k − 1 ≥ m + k 2^k - 1 \\geq m + k 2k−1≥m+k
  • k：校验位的个数
  • m：数据位的个数
• 海明码编码方式：
  • 规则：第 2 i 2^i 2i(i = 0, 1, 2, 3…) 位是 校验位，其余是 数据位
  • 数据位和校验位的关系：数据位 = 校验位之和（ 2 i 2^i 2i）
    • 3 = 2 + 1 = 2 1 + 2 0 3 = 2 + 1 = 2^1 + 2^0 3=2+1=21+20 表示：位置 3 上的数据位经过位置 2 和 位置 1 的校验
    • 10 = 8 + 2 = 2 3 + 2 1 10 = 8 + 2 = 2^3 + 2^1 10=8+2=23+21 表示：位置 10 上的数据位经过位置 8 和 位置 2 的校验
  • 举例：假设传送信息 1001011，按 偶校验 计算
    • 参加位置 1 校验的有：3、5、7、9、11 =》对应数据：10101 =》偶校验计算结果为 1
    • 参加位置 2 校验的有：3、6、7、10、11 =》对应数据：10111 =》偶校验计算结果为 0
    • 参加位置 4 校验的有：5、6、7 =》对应数据：001 =》偶校验计算结果为 1
    • 参加位置 8 校验的有：9、10、11 =》对应数据：011 =》偶校验计算结果为 0
  • 最终 海明码 为 校验码校验结果 + 原数据

2.3 CRC循环冗余校验码

• 检错。末尾 加入CRC循环冗余校验码 能检错不能纠错，广泛用于网络通信和磁盘存储
• 四个步骤。原理很复杂，计算时，记住下列四个步骤即可。
  

3 扩展

3.1 网工软考真题

// 2016年 上半年
[例1]海明码是一种纠错码，一对有效码字之间的海明距离是（14），如果信息位为6位，
要求纠正 1 个错位，按照海明编码规则，需要增加的校验位至少（15）位。
14 A.两个码字的比特数之和B.两个码字的比特数之差C.两个码字之间相同的比特数D.两个码字之间不同的比特数15 A.3   B.4   B.5   B.6

【参考答案：14-D，15-B】

• 海明不等式： 2 k − 1 ≥ m + k 2^k - 1 \\geq m + k 2k−1≥m+k（m：数据位，k：校验位）
  • 根据题干：m = 6，带入选项得 k = 4 时，符合题意