network_planner:chapter_01:01_03_08_error_control [ITDatabase]

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
下面完整整理“差错控制”至“局域网”之前的内容，重点补全海明码的编码、定位纠错过程，以及 CRC 的模2除法、生成多项式和检错能力。全文只使用 DokuWiki 原生语法。

====== 差错控制 ======

===== 一、本节概述 =====

数据在通信信道中传输时，会受到噪声、干扰、衰减和信号失真的影响，导致接收数据与发送数据不一致。

为了将错误降低到系统允许的范围，需要使用：

**Error Control（差错控制）**

差错控制的基本思想是：在原始信息中增加一定数量的冗余信息，使接收方能够发现或纠正传输错误。

本节主要内容包括：

  - 差错产生的原因；
  - 随机错误与突发错误；
  - 检错与纠错；
  - 海明码；
  - 循环冗余校验码。

  差错控制
  │
  ├─ 差错产生原因
  │  ├─ 热噪声
  │  ├─ 冲击噪声
  │  ├─ 信号失真
  │  └─ 串扰
  │
  ├─ 差错类型
  │  ├─ 随机错误
  │  └─ 突发错误
  │
  ├─ 控制策略
  │  ├─ 检错后重传
  │  └─ 接收端直接纠错
  │
  └─ 典型编码
     ├─ 海明码
     └─ CRC循环冗余校验码

===== 二、差错产生的原因 =====

==== 1. 热噪声 ====

**Thermal Noise（热噪声）**是由电子随机热运动产生的噪声。

主要特点：

  * 在通信线路中持续存在；
  * 具有较宽的频谱；
  * 通常幅度较小；
  * 对数据位的影响具有随机性；
  * 往往只造成个别位错误；
  * 信噪比越高，热噪声引起的错误越少。

热噪声通常引起：

**Random Error（随机错误）**

==== 2. 冲击噪声 ====

**Impulse Noise（冲击噪声）**是短时间出现、但瞬间幅度很大的干扰。

常见来源包括：

  * 雷电；
  * 电焊机；
  * 电动机启停；
  * 电力设备瞬态变化；
  * 开关设备；
  * 外界突发电磁干扰。

冲击噪声的特点：

  * 持续时间短；
  * 瞬时幅度大；
  * 可能同时影响多个连续数据位；
  * 容易形成一串连续错误。

冲击噪声通常引起：

**Burst Error（突发错误）**

==== 3. 信号失真 ====

信号幅度、传播速度与相位、频率等参数有关。信号在传输过程中可能出现：

  * 幅度失真；
  * 相位失真；
  * 频率失真；
  * 延迟失真；
  * 波形畸变。

接收端可能因此错误判断信号状态，从而产生差错。

==== 4. 串扰 ====

**Crosstalk（串扰）**是相邻线路或相邻信道之间发生信号耦合，一个信号对另一个信号产生干扰的现象。

串扰通常具有突发性，也可能导致多个数据位连续出错。

===== 三、随机错误与突发错误 =====

^ 比较项目 ^ 随机错误 ^ 突发错误 ^
| 英文名称 | Random Error | Burst Error |
| 典型原因 | 热噪声 | 冲击噪声、串扰和瞬态干扰 |
| 错误分布 | 零散、随机出现 | 集中出现在一段数据范围内 |
| 常见影响 | 一个或少量数据位 | 多个连续范围内的数据位 |
| 常用控制方法 | 奇偶校验、海明码 | CRC、交织和重传 |

==== 1. 突发错误长度 ====

突发错误长度是指从第一个错误位开始，到最后一个错误位结束所覆盖的总位数。

例如：

  发送数据：110101101001

  接收数据：110'''01011'''1001

突发错误范围内不要求每一位都发生错误。只要第一个错误位与最后一个错误位之间覆盖5位，突发错误长度就是5。

===== 四、冗余校验原理 =====

==== 1. 信息位与冗余位 ====

假设：

  * 原始信息长度为 ''k'' 位；
  * 增加 ''r'' 位冗余信息；
  * 编码后总长度为 ''n'' 位。

则：

  ''n＝k＋r''

其中：

^ 符号 ^ 含义 ^
| ''k'' | 原始信息位数 |
| ''r'' | 冗余校验位数 |
| ''n'' | 编码后的总位数 |

发送方按照确定的算法，根据原始信息计算冗余位，再将信息位与冗余位一起发送。

接收方对收到的数据使用同一算法：

  * 若校验结果一致，则认为数据没有检测到错误；
  * 若校验结果不一致，则认为数据发生错误；
  * 若编码具有纠错能力，还可以进一步确定错误位置。

==== 2. 编码效率 ====

增加冗余位会降低有效数据比例。

编码效率为：

  ''η＝k÷(k＋r)''

例如，7位信息增加1位校验位：

  ''η＝7÷8＝87.5%''

冗余位越多：

  * 检错、纠错能力通常越强；
  * 传输开销越大；
  * 有效数据率越低；
  * 编码和译码过程越复杂。

===== 五、检错与纠错 =====

==== 1. 检错 ====

**Error Detection（检错）**是指接收方能够判断数据发生了错误，但通常不能确定正确数据是什么。

发现错误后，接收方可以请求发送方重新传输。

这种策略称为：

**ARQ（Automatic Repeat reQuest，自动重传请求）**

  发送数据
      ↓
  接收端执行校验
      ↓
  是否检测到错误？
  ├─ 否：接收数据
  └─ 是：请求发送方重传

==== 2. 纠错 ====

**Error Correction（纠错）**是指接收方不仅知道发生了错误，还能确定错误位置并恢复正确数据。

利用冗余信息在接收端直接完成纠错的技术称为：

**FEC（Forward Error Correction，前向纠错）**

==== 3. 检错与纠错比较 ====

^ 比较项目 ^ 检错 ^ 纠错 ^
| 英文名称 | Error Detection | Error Correction |
| 能否发现错误 | 是 | 是 |
| 能否确定错误位置 | 通常不能 | 在编码能力范围内可以 |
| 能否直接恢复数据 | 不能 | 可以 |
| 是否通常需要重传 | 是 | 否 |
| 冗余位数量 | 较少 | 较多 |
| 实现复杂度 | 较低 | 较高 |
| 典型机制 | 奇偶校验、CRC | 海明码、FEC编码 |

===== 六、海明码基本概念 =====

==== 1. 海明码的提出 ====

1950年，理查德·海明研究了利用冗余位检测和纠正代码错误的方法。

**Hamming Code（海明码）**是一类通过增加多个校验位，实现错误检测和错误定位的线性分组码。

海明码的基本思想是：

  * 将校验位放置在特定位置；
  * 每个校验位检查一组数据位；
  * 不同数据位参加不同的校验组合；
  * 接收端根据校验失败的组合计算错误位置；
  * 将错误位取反即可完成单比特纠错。

==== 2. 海明重量 ====

一个码字中二进制1的数量称为：

**Hamming Weight（海明重量）**

例如：

  ''10110100''

其中有4个1，因此：

  ''海明重量＝4''

==== 3. 海明距离 ====

两个等长码字在对应位置上不同的位数称为：

**Hamming Distance（海明距离）**

可通过按位异或计算：

  码字A：10110110

  码字B：10011100

  异或值：00101010

异或结果中有3个1，因此：

  ''d(A,B)＝3''

其中：

**XOR（Exclusive OR，异或）**的运算规则是：

^ A ^ B ^ A XOR B ^
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

==== 4. 最小海明距离 ====

一个编码系统中，任意两个合法码字之间海明距离的最小值称为：

**Minimum Hamming Distance（最小海明距离）**

通常记作：

  ''d_min''

最小海明距离决定了编码能够检测和纠正多少位错误。

===== 七、海明距离与差错控制能力 =====

==== 1. 检错能力 ====

如果最小海明距离为 ''d_min''，则最多能够保证检测：

  ''d_min－1''

位错误。

若要保证检测 ''s'' 位错误，需要满足：

  ''d_min≥s＋1''

例如：

^ 最小海明距离 ^ 保证检测的错误位数 ^
| 2 | 1位 |
| 3 | 2位 |
| 4 | 3位 |
| 5 | 4位 |

==== 2. 纠错能力 ====

如果要保证纠正 ''t'' 位错误，需要满足：

  ''d_min≥2t＋1''

最大保证纠错位数为：

  ''t_max＝⌊(d_min－1)÷2⌋''

其中 ''⌊x⌋'' 表示向下取整。

^ 最小海明距离 ^ 保证纠正的错误位数 ^
| 2 | 0位 |
| 3 | 1位 |
| 4 | 1位 |
| 5 | 2位 |
| 6 | 2位 |
| 7 | 3位 |

==== 3. 几何意义 ====

一个长度为 ''n'' 的二进制码字，可以看成 ''n'' 维超立方体中的一个顶点。

两个码字之间的海明距离，就是两个顶点之间需要改变的最少坐标数量。

如果两个合法码字的距离为 ''d''：

  * 小于或等于 ''d－1'' 位的错误可以被检测；
  * 小于 ''d÷2'' 位的错误可以被纠正。

纠错的本质是将接收到的错误码字判断为距离最近的合法码字。

==== 4. 奇偶校验的海明距离 ====

7位ASCII数据增加1位奇偶校验后形成8位码字。

这些合法码字之间的最小海明距离为2，因此：

  * 可以检测所有1位错误；
  * 不能纠正1位错误；
  * 不能保证发现所有2位错误。

**ASCII（American Standard Code for Information Interchange，美国信息交换标准代码）**

===== 八、海明码校验位数量 =====

==== 1. 基本条件 ====

设：

  * 原始数据有 ''m'' 位；
  * 增加 ''k'' 位校验位；
  * 编码后总长度为 ''n＝m＋k''。

对于单比特纠错，每一个有效码字需要区分：

  * ''n''个单比特错误位置；
  * 1种没有错误的情况。

因此，一个有效码字需要对应：

  ''n＋1''

种可识别状态。

由于 ''k'' 位校验位可以表示 ''2^k'' 种状态，所以必须满足：

  ''2^k≥n＋1''

代入 ''n＝m＋k''：

  ''2^k≥m＋k＋1''

也可以写成：

  ''m＋k＋1≤2^k''

这就是单比特纠错海明码校验位数量的基本条件。

==== 2. 教材推导 ====

对于 ''m'' 位数据，有：

  ''2^m''

个有效信息。

每个有效码字需要表示：

  * 1种无错误状态；
  * ''n''种单比特错误状态。

总共需要：

  ''2^m(n＋1)''

个可区分码字。

长度为 ''n'' 的二进制码字共有：

  ''2^n''

种可能，因此：

  ''2^m(n＋1)≤2^n''

因为：

  ''n＝m＋k''

所以：

  ''n＋1≤2^k''

最终得到：

  ''m＋k＋1≤2^k''

==== 3. 常见数据位与校验位对应关系 ====

^ 数据位m ^ 最少校验位k ^ 总码长n ^ 验证 ^
| 1 | 2 | 3 | ''1＋2＋1＝4≤2²'' |
| 4 | 3 | 7 | ''4＋3＋1＝8≤2³'' |
| 7 | 4 | 11 | ''7＋4＋1＝12≤2⁴'' |
| 8 | 4 | 12 | ''8＋4＋1＝13≤2⁴'' |
| 11 | 4 | 15 | ''11＋4＋1＝16≤2⁴'' |
| 12 | 5 | 17 | ''12＋5＋1＝18≤2⁵'' |
| 26 | 5 | 31 | ''26＋5＋1＝32≤2⁵'' |

==== 4. 快速判断方法 ====

给定数据位 ''m'' 后，从较小的 ''k'' 开始尝试：

  ''2^k≥m＋k＋1''

取满足条件的最小 ''k''。

例如，8位数据：

尝试 ''k＝3''：

  ''2³＝8''

  ''8＋3＋1＝12''

  ''8<12''，不满足。

尝试 ''k＝4''：

  ''2⁴＝16''

  ''8＋4＋1＝13''

  ''16≥13''，满足。

因此，8位数据至少需要4位海明校验位。

===== 九、海明码的位编号与校验关系 =====

==== 1. 校验位的位置 ====

海明码把校验位放在序号为2的整数次幂的位置：

  * 第1位：''2⁰＝1''
  * 第2位：''2¹＝2''
  * 第4位：''2²＝4''
  * 第8位：''2³＝8''
  * 第16位：''2⁴＝16''

其余位置用于存放数据位。

以11位码字为例：

^ 位置 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^
| 类型 | P1 | P2 | D1 | P4 | D2 | D3 | D4 | P8 | D5 | D6 | D7 |

其中：

  * ''P1、P2、P4、P8''是校验位；
  * ''D1～D7''是数据位。

==== 2. 校验位分组规则 ====

把每个位置编号写成二进制数：

^ 十进制位置 ^ 8位 ^ 4位 ^ 2位 ^ 1位 ^
| 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 |
| 5 | 0 | 1 | 0 | 1 |
| 6 | 0 | 1 | 1 | 0 |
| 7 | 0 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 |
| 10 | 1 | 0 | 1 | 0 |
| 11 | 1 | 0 | 1 | 1 |

一个位置参加哪些校验，由其二进制编号中哪些位为1决定。

^ 校验位 ^ 检查条件 ^ 检查的位置 ^
| P1 | 位置编号的最低位为1 | 1、3、5、7、9、11 |
| P2 | 位置编号的2位为1 | 2、3、6、7、10、11 |
| P4 | 位置编号的4位为1 | 4、5、6、7 |
| P8 | 位置编号的8位为1 | 8、9、10、11 |

==== 3. 某数据位参加哪些校验 ====

例如，第6位：

  ''6＝0110₂''

其2位和4位为1，因此第6位参加：

  * P2校验；
  * P4校验；
  * 不参加P1和P8校验。

第9位：

  ''9＝1001₂''

其1位和8位为1，因此第9位参加：

  * P1校验；
  * P8校验。

===== 十、海明码编码示例 =====

==== 1. 放置原始数据 ====

教材示例的原始数据为：

  ''1001011''

将7个数据位依次放入：

  ''3、5、6、7、9、10、11''

号位置。

^ 位置 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^
| 类型 | P1 | P2 | D1 | P4 | D2 | D3 | D4 | P8 | D5 | D6 | D7 |
| 数据 | ？ | ？ | 1 | ？ | 0 | 0 | 1 | ？ | 0 | 1 | 1 |

==== 2. 计算P1 ====

P1检查：

  ''1、3、5、7、9、11''

不考虑P1本身，数据位为：

  ''1、0、1、0、1''

其中有3个1。

若采用偶校验，为使1的总数成为偶数：

  ''P1＝1''

==== 3. 计算P2 ====

P2检查：

  ''2、3、6、7、10、11''

不考虑P2本身，数据位为：

  ''1、0、1、1、1''

其中有4个1，已经是偶数，因此：

  ''P2＝0''

==== 4. 计算P4 ====

P4检查：

  ''4、5、6、7''

不考虑P4本身，数据位为：

  ''0、0、1''

其中有1个1，因此：

  ''P4＝1''

==== 5. 计算P8 ====

P8检查：

  ''8、9、10、11''

不考虑P8本身，数据位为：

  ''0、1、1''

其中有2个1，因此：

  ''P8＝0''

==== 6. 最终码字 ====

^ 位置 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^
| 编码结果 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |

最终海明码为：

  ''10110010011''

===== 十一、海明码纠错示例 =====

==== 1. 传输错误 ====

假设码字：

  ''10110010011''

在传输过程中第6位由0变成1，接收结果为：

  ''10110110011''

^ 位置 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^
| 接收值 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |

==== 2. 接收端重新校验 ====

接收端按照相同规则进行偶校验：

^ 校验组 ^ 校验结果 ^ 含义 ^
| P1组 | 正确 | 错误位置的1位标志为0 |
| P2组 | 错误 | 错误位置的2位标志为1 |
| P4组 | 错误 | 错误位置的4位标志为1 |
| P8组 | 正确 | 错误位置的8位标志为0 |

形成校验结果：

  ''P8 P4 P2 P1＝0110₂''

转换为十进制：

  ''0110₂＝6''

也可以直接将出错校验位编号相加：

  ''2＋4＝6''

因此可以确定：

  ''第6位发生错误''

将第6位取反：

  ''1→0''

即可恢复原码字。

==== 3. 综合校验值 ====

各校验结果组成的二进制数称为：

**Syndrome（伴随式或校验综合）**

  * Syndrome为0：未检测到错误；
  * Syndrome不为0：其数值指出单比特错误的位置。

===== 十二、海明码的能力与限制 =====

普通海明码的最小距离通常为3，因此：

  * 可以纠正1位错误；
  * 可以检测2位错误；
  * 但普通译码器如果直接按单错处理，可能把双比特错误误判成另一位置的单比特错误。

增加一个全局奇偶校验位后，可构成：

**SECDED（Single Error Correction, Double Error Detection，单错纠正、双错检测）**

其能力为：

  * 纠正所有单比特错误；
  * 检测所有双比特错误；
  * 不能纠正双比特错误。

===== 十三、循环码 =====

==== 1. 基本概念 ====

**Cyclic Code（循环码）**是一类具有循环性质的线性分组码。

如果一个码字是合法码字，那么将其循环左移或循环右移任意位后，得到的码字仍然是合法码字。

例如，若：

  ''a_(n-1) a_(n-2) … a₁ a₀''

是合法码字，则其循环移位结果也是合法码字：

  ''a_(n-2) a_(n-3) … a₀ a_(n-1)''

循环码便于使用移位寄存器和异或门实现。

===== 十四、CRC循环冗余校验 =====

==== 1. 基本概念 ====

**CRC（Cyclic Redundancy Check，循环冗余校验）**是一种基于循环码和模2多项式除法的检错方法。

CRC的主要特点：

  * 检错能力强；
  * 特别适合检测突发错误；
  * 数学基础严谨；
  * 容易使用硬件实现；
  * 广泛应用于局域网和数据链路协议；
  * 通常只负责检错，不直接纠错。

==== 2. CRC基本过程 ====

发送端：

  - 选择生成多项式；
  - 在原始数据后补0；
  - 执行模2除法；
  - 取得余数作为CRC校验码；
  - 将原始数据与CRC余数组成发送码字。

接收端：

  - 用相同生成多项式除接收到的完整码字；
  - 如果余数为0，则未检测到错误；
  - 如果余数不为0，则判定传输出现错误。

  原始数据D
      ↓
  末尾补r个0
      ↓
  除以生成多项式G
      ↓
  得到r位余数R
      ↓
  原始数据＋余数
      ↓
  发送

===== 十五、模2运算 =====

CRC使用：

**Modulo-2 Arithmetic（模2运算）**

其特点：

  * 加法等同于异或；
  * 减法也等同于异或；
  * 不产生进位；
  * 不发生借位。

==== 1. 模2加减法 ====

^ A ^ B ^ A＋B或A－B ^
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

因此：

  ''1＋1＝0''

  ''1－1＝0''

  ''0－1＝1''

在CRC运算中，加法和减法均可使用XOR实现。

==== 2. 移位与乘法 ====

多项式乘以 ''x''，相当于二进制码左移一位。

多项式乘以 ''x^r''，相当于二进制码末尾补 ''r'' 个0。

===== 十六、二进制码与多项式 =====

一个二进制码字可以表示为一个系数属于0或1的多项式。

例如：

  ''00101011''

从最高非零位开始对应：

  ''x⁵＋x³＋x＋1''

因为：

^ 二进制位 ^ 对应多项式项 ^
| 第5次项为1 | ''x⁵'' |
| 第4次项为0 | 无 |
| 第3次项为1 | ''x³'' |
| 第2次项为0 | 无 |
| 第1次项为1 | ''x'' |
| 常数项为1 | ''1'' |

因此：

  ''00101011 ↔ x⁵＋x³＋x＋1''

==== 1. 生成多项式 ====

CRC使用的除数称为：

**Generator Polynomial（生成多项式）**

通常记作：

  ''G(x)''

如果生成多项式最高次数为 ''r''，则：

  * CRC校验码长度为 ''r'' 位；
  * 生成多项式的二进制表示长度为 ''r＋1'' 位。

===== 十七、CRC数学模型 =====

设：

  * 数据多项式为 ''D(x)''；
  * 生成多项式为 ''G(x)''；
  * 生成多项式次数为 ''r''；
  * 商多项式为 ''Q(x)''；
  * 余数多项式为 ''R(x)''。

对数据多项式补 ''r'' 个0，相当于：

  ''x^rD(x)''

执行模2除法：

  ''x^rD(x)＝Q(x)G(x)＋R(x)''

其中：

  ''deg R(x)<r''

实际发送的码字为：

  ''F(x)＝x^rD(x)＋R(x)''

由于模2运算中的加法和减法相同，所以：

  ''F(x)''

能够被：

  ''G(x)''

整除。

接收端计算：

  ''F(x)÷G(x)''

正确情况下余数应为0。

===== 十八、CRC计算步骤 =====

假设：

  * 原始数据为 ''M''；
  * 生成多项式的二进制码为 ''P''；
  * ''P''的最高次数为 ''r''。

计算步骤：

  - 在原始数据后补 ''r'' 个0；
  - 使用生成多项式对应的二进制数进行模2长除；
  - 模2减法使用异或，不借位；
  - 得到长度不超过 ''r'' 位的余数；
  - 不足 ''r'' 位时在左侧补0；
  - 用余数替换原来补入的 ''r'' 个0；
  - 得到最终发送码字。

表达式为：

  ''发送码字＝原始数据＋CRC余数''

===== 十九、CRC校验示例 =====

教材示例使用：

  ''D＝00101011''

对应数据多项式：

  ''D(x)＝x⁵＋x³＋x＋1''

生成多项式采用CRC-CCITT：

  ''G(x)＝x¹⁶＋x¹²＋x⁵＋1''

生成多项式二进制形式为：

  ''1 0001 0000 0010 0001''

十六进制形式通常简写为：

  ''1021H''

因为生成多项式次数为16，所以在原始数据后补16个0：

  ''00101011 0000000000000000''

进行模2长除后，教材得到余数：

  ''9509H''

因此，16位CRC校验和为：

  ''9509H''

其中：

  * ''H''表示Hexadecimal，即十六进制；
  * ''9509H''的二进制形式为 ''1001010100001001''。

最终发送的数据形式为：

  ''00101011 1001010100001001''

===== 二十、CRC硬件实现 =====

CRC可以使用以下电路实现：

  * 移位寄存器；
  * 异或门；
  * 反馈回路。

使用：

**LFSR（Linear Feedback Shift Register，线性反馈移位寄存器）**

实现CRC时：

  - 先将寄存器清零；
  - 数据逐位输入移位寄存器；
  - 移出的位通过反馈线路参与异或；
  - 数据全部输入后，再输入与校验位数量相同个数的0；
  - 最终寄存器内容就是CRC余数。

生成多项式中系数为1的项，决定反馈异或连接的位置。

CRC-CCITT的生成多项式为：

  ''G(x)＝x¹⁶＋x¹²＋x⁵＋1''

因此其硬件反馈路径与：

  * 第16次项；
  * 第12次项；
  * 第5次项；
  * 常数项；

相对应。

===== 二十一、CRC接收端校验 =====

设正确发送码字为：

  ''F(x)''

传输过程中产生的错误多项式为：

  ''E(x)''

接收到的码字为：

  ''H(x)＝F(x)＋E(x)''

因为正确码字 ''F(x)'' 能被 ''G(x)'' 整除：

  * 如果 ''H(x)''不能被''G(x)''整除，说明检测到错误；
  * 如果 ''H(x)''能被''G(x)''整除，则校验余数为0。

需要注意：

如果错误多项式 ''E(x)'' 恰好也能被 ''G(x)'' 整除，则：

  ''H(x)''

仍能被 ''G(x)'' 整除，此时错误无法被CRC检测。

因此，CRC不能检测所有理论上可能的错误，但合适的生成多项式可以使漏检概率非常低。

===== 二十二、CRC的检错能力 =====

CRC检错能力取决于生成多项式 ''G(x)''。

==== 1. 单比特错误 ====

如果 ''G(x)''至少包含两个非零项，即不是单项式，则可以检测所有单比特错误。

教材表述为：

> 如果生成多项式的项数大于1，可以检测所有单比特错误。

==== 2. 奇数位错误 ====

如果 ''G(x)''含有因子：

  ''x＋1''

则能够检测所有奇数个位发生的错误。

==== 3. 突发错误 ====

如果CRC校验位长度为 ''r''，则可以检测所有长度：

  ''≤r''

的突发错误。

对于长度为 ''r＋1'' 的突发错误，绝大多数也能够被检测。

更长的突发错误也具有较高的检出概率。

==== 4. CRC核心结论 ====

^ 错误类型 ^ 检测条件或能力 ^
| 单比特错误 | 生成多项式至少包含两个非零项时可全部检测 |
| 奇数位错误 | ''G(x)''含有因子''x＋1''时可全部检测 |
| 长度不超过r的突发错误 | 可全部检测 |
| 更长突发错误 | 可检测绝大多数，但不能保证全部检测 |

===== 二十三、常用CRC生成多项式 =====

==== 1. CRC-CCITT ====

**CRC-CCITT（Consultative Committee for International Telegraph and Telephone CRC，国际电报电话咨询委员会循环冗余校验）**

  ''G(x)＝x¹⁶＋x¹²＋x⁵＋1''

常见十六进制表示：

  ''1021H''

==== 2. CRC-16 ====

  ''G(x)＝x¹⁶＋x¹⁵＋x²＋1''

==== 3. CRC-12 ====

  ''G(x)＝x¹²＋x¹¹＋x³＋x²＋x＋1''

==== 4. CRC-32 ====

  ''G(x)＝x³²＋x²⁶＋x²³＋x²²＋x¹⁶＋x¹²＋x¹¹＋x¹⁰＋x⁸＋x⁷＋x⁵＋x⁴＋x²＋x＋1''

CRC-32广泛应用于局域网及其他计算机网络。

^ CRC类型 ^ 校验位长度 ^ 教材给出的生成多项式 ^
| CRC-12 | 12位 | ''x¹²＋x¹¹＋x³＋x²＋x＋1'' |
| CRC-16 | 16位 | ''x¹⁶＋x¹⁵＋x²＋1'' |
| CRC-CCITT | 16位 | ''x¹⁶＋x¹²＋x⁵＋1'' |
| CRC-32 | 32位 | ''x³²＋x²⁶＋x²³＋x²²＋x¹⁶＋x¹²＋x¹¹＋x¹⁰＋x⁸＋x⁷＋x⁵＋x⁴＋x²＋x＋1'' |

===== 二十四、海明码与CRC比较 =====

^ 比较项目 ^ 海明码 ^ CRC ^
| 英文名称 | Hamming Code | Cyclic Redundancy Check |
| 主要目的 | 检错并纠正单比特错误 | 检测传输错误 |
| 数学基础 | 海明距离与校验位分组 | 循环码与模2多项式除法 |
| 错误定位 | 可以定位能力范围内的错误 | 通常不能定位具体错误位 |
| 直接纠错 | 可以 | 通常不可以 |
| 突发错误检测 | 一般 | 很强 |
| 冗余位计算 | ''2^k≥m＋k＋1'' | 由生成多项式次数决定 |
| 硬件实现 | 校验网络 | 移位寄存器和异或门 |
| 典型应用 | 存储器纠错、数字通信 | 局域网、数据链路和存储系统 |

===== 二十五、考试重点 =====

**必须掌握：**

  * 热噪声通常产生随机错误。
  * 冲击噪声通常产生突发错误。
  * 检错只能发现错误，纠错可以确定并恢复错误。
  * 海明距离是两个等长码字对应位置不同的位数。
  * 海明重量是码字中二进制1的数量。
  * 检测 ''s'' 位错误要求 ''d_min≥s＋1''。
  * 纠正 ''t'' 位错误要求 ''d_min≥2t＋1''。
  * 单比特纠错海明码满足 ''2^k≥m＋k＋1''。
  * 海明码校验位放在1、2、4、8等位置。
  * 一个数据位参加哪些校验，由其位置编号的二进制形式决定。
  * 校验综合的二进制数直接指出单比特错误位置。
  * CRC是Cyclic Redundancy Check的缩写。
  * CRC使用模2除法，加法和减法均为异或。
  * 生成多项式为 ''r'' 次时，CRC余数为 ''r'' 位。
  * 发送端用余数替换数据后补的 ''r'' 个0。
  * 接收端使用相同生成多项式进行除法校验。
  * 接收余数为0表示未检测到错误，而不是绝对保证没有错误。
  * ''r''位CRC可以检测所有长度不超过''r''的突发错误。
  * CRC-32广泛应用于局域网。

===== 二十六、常见易错点 =====

  * 能检测1位错误不等于能纠正1位错误。
  * 最小海明距离为2时只能保证检出1位错误，不能纠正。
  * 纠正1位错误至少要求最小海明距离为3。
  * 海明距离不是码字中1的数量；后者是海明重量。
  * 海明码公式中的校验状态要包含“无错误”状态。
  * 校验位数量应取满足公式的最小整数。
  * 海明码校验位编号是1、2、4、8，不是第1、2、3、4位连续放置。
  * CRC生成多项式的次数等于校验位数量。
  * ''r''次生成多项式的二进制形式有''r＋1''位。
  * CRC模2减法不借位，本质上是异或。
  * CRC余数不足规定长度时，应在左侧补0。
  * CRC校验余数为0只表示没有检测到错误。
  * CRC通常用于检错，不能直接指出错误位的位置。
  * 生成多项式必须由通信双方事先约定。
  * 多项式二进制表示中的最高位和最低位不能随意省略。

===== 二十七、快速解题方法 =====

==== 1. 求海明码校验位数量 ====

已知数据位 ''m''：

  - 从 ''k＝1''开始尝试；
  - 计算 ''2^k''；
  - 计算 ''m＋k＋1''；
  - 找到第一个满足 ''2^k≥m＋k＋1'' 的 ''k''。

==== 2. 求海明码错误位置 ====

  - 按原校验规则重新计算各校验组；
  - 正确记为0，错误记为1；
  - 按照 ''P8、P4、P2、P1'' 的顺序组合；
  - 将所得二进制数转换为十进制；
  - 十进制数就是错误位置；
  - 将该位置取反完成单比特纠错。

==== 3. 求CRC校验码 ====

  - 确定生成多项式的最高次数 ''r''；
  - 在数据后补 ''r'' 个0；
  - 使用生成多项式执行模2长除；
  - 每次减法使用异或；
  - 得到 ''r'' 位余数；
  - 将余数附加到原数据后形成发送码字。

==== 4. 验证CRC码字 ====

  - 用相同生成多项式除完整接收码字；
  - 余数非0：检测到错误；
  - 余数为0：未检测到错误。

===== 二十八、英文缩写与术语速查表 =====

^ 缩写或术语 ^ 英文全称 ^ 中文含义 ^
| Error Control | Error Control | 差错控制 |
| Random Error | Random Error | 随机错误 |
| Burst Error | Burst Error | 突发错误 |
| Thermal Noise | Thermal Noise | 热噪声 |
| Impulse Noise | Impulse Noise | 冲击噪声 |
| Crosstalk | Crosstalk | 串扰 |
| Error Detection | Error Detection | 检错 |
| Error Correction | Error Correction | 纠错 |
| ARQ | Automatic Repeat reQuest | 自动重传请求 |
| FEC | Forward Error Correction | 前向纠错 |
| Hamming Code | Hamming Code | 海明码 |
| Hamming Weight | Hamming Weight | 海明重量 |
| Hamming Distance | Hamming Distance | 海明距离 |
| d_min | Minimum Hamming Distance | 最小海明距离 |
| Syndrome | Syndrome | 伴随式或校验综合 |
| SECDED | Single Error Correction, Double Error Detection | 单错纠正、双错检测 |
| XOR | Exclusive OR | 异或 |
| CRC | Cyclic Redundancy Check | 循环冗余校验 |
| CRC-CCITT | Consultative Committee for International Telegraph and Telephone CRC | 国际电报电话咨询委员会CRC |
| LFSR | Linear Feedback Shift Register | 线性反馈移位寄存器 |
| Generator Polynomial | Generator Polynomial | 生成多项式 |
| Modulo-2 Arithmetic | Modulo-2 Arithmetic | 模2运算 |
| ASCII | American Standard Code for Information Interchange | 美国信息交换标准代码 |
| H | Hexadecimal | 十六进制表示标记 |

===== 二十九、本节知识脉络 =====

  差错控制
  │
  ├─ 差错原因
  │  ├─ 热噪声 → 随机错误
  │  ├─ 冲击噪声 → 突发错误
  │  ├─ 信号失真
  │  └─ 串扰
  │
  ├─ 控制策略
  │  ├─ 检错
  │  │  └─ ARQ请求重传
  │  └─ 纠错
  │     └─ FEC直接恢复
  │
  ├─ 海明码
  │  ├─ 海明距离
  │  ├─ d_min决定检错纠错能力
  │  ├─ 2^k≥m＋k＋1
  │  ├─ 校验位位于1、2、4、8
  │  └─ Syndrome指出错误位置
  │
  └─ CRC
     ├─ 循环码
     ├─ 模2多项式除法
     ├─ 生成多项式G(x)
     ├─ 余数作为校验码
     ├─ 接收端重新计算余数
     └─ 擅长检测突发错误

===== 三十、相关条目 =====

  * [[network_planner:chapter_01:01_03_06_multiplexing|多路复用技术]]
  * [[network_planner:chapter_01:01_03_07_spread_spectrum|扩频技术]]
  * [[network_planner:chapter_01:01_04_lan|局域网]]
  * [[network_planner:chapter_01:start|返回第1章首页]]

{{tag>软考 网络规划设计师 计算机网络 数据通信 差错控制 海明码 海明距离 CRC 循环冗余校验 模2运算 检错 纠错 ARQ FEC}}