Methods of error detection

介绍：确保传输中的数据安全

欢迎来到计算机科学中至关重要的一课：确保数据从一地传送到另一地时准确无误！数据传输永远无法做到绝对可靠；信号会减弱，干扰会发生，比特位也可能发生翻转。
如果你下载了一个大型软件更新，你必须确保收到的文件与服务器发送的文件完全一致。

本章重点讲解错误检测（Error Detection）——即计算机识别损坏数据所使用的技术，以及发现错误后的处理方式。这一过程对于维护数据完整性（Data Integrity）至关重要。

1. 为什么需要进行错误检测？

数据传输过程中出现错误，主要原因是传输介质（如电缆、无线信号）中存在的干扰（例如电气噪声或信号失真）。

可能出现的错误类型：

当发送数据（以 0 和 1 表示）时，信号损坏可能导致：

• 数据更改（损坏）： 一个 0 位可能意外变成了 1，或者一个 1 位变成了 0。这是最常见且需要检测的错误。
• 数据丢失： 一块数据或整个数据包可能完全丢失。
• 数据增加： 不需要的或重复的数据可能意外被添加到数据流中。

2. 传输错误检测方法

数据一旦传输完成，接收设备会立即进行检查。我们需要快速且可靠的方法。

2.1 奇偶校验（Parity Check - 奇偶校验位和校验块）

奇偶校验是最简单的方法之一。它检查一组比特位中 1 的总数是偶数还是奇数。

奇偶校验的工作原理：

首先必须商定一个规则：采用偶校验（Even Parity）还是奇校验（Odd Parity）。在数据块（通常为 7 或 8 位）中会添加一个额外的位，即校验位（Parity Bit），以强制执行此规则。

操作步骤：

1. 发送端操作： 计算原始数据中 1 的个数。
2. 发送端操作： 设置校验位（0 或 1），使整个组（数据 + 校验位）中 1 的总数符合商定的规则。
3. 接收端操作： 计算接收到的组中 1 的总数。
4. 接收端操作： 如果总数符合规则，则假定数据正确。如果不符合，则检测到错误。

示例：使用偶校验

我们约定 1 的总数必须为偶数。

• 发送的数据： 1 0 0 1 1 0 1 0 （有四个 1 —— 已经是偶数）。
• 校验位： 设置为 0。
• 发送的总数： 1 0 0 1 1 0 1 0 0 （仍为四个 1。总数为偶数。）

现在，假设传输过程中发生了一个错误：第三位从 0 变成了 1。

• 接收到的数据： 1 0 1 1 1 0 1 0 0 （五个 1）。
• 接收端检查： 五个 1 是奇数。系统期望的是偶数。检测到错误！

简单奇偶校验的局限性

最大的缺陷是，如果两个位发生翻转（或任何偶数个位翻转），奇偶校验仍然可以通过！系统会错误地认为损坏的数据是正确的。

校验块（提高可靠性）

为了克服逐字节校验的局限性，可以将数据作为块（字节网格）发送。在数据块末尾添加一个额外的字节，即校验字节（Parity Byte），其中包含每一列的校验位。这就是所谓的校验块（Parity Block Check）。

• 系统检查每一行的奇偶性（标准奇偶校验）。
• 系统还检查每一列的奇偶性（使用校验字节）。

如果检测到错误，同时检查行校验和列校验，系统就能精确定位发生翻转的特定比特位，从而更容易发现甚至纠正单个错误。

---

2.2 校验和（Checksum）

校验和是一种更健壮的数学方法，通常用于检查大数据块，例如整个文件或传输数据包。

校验和的工作原理：

1. 发送端计算： 数据被分成固定大小的段。这些段通过数学方法相加（通常使用专门的求和方法）。
2. 生成校验和： 该计算结果存储为校验和（Checksum）。
3. 传输： 数据块和校验和一起发送。
4. 接收端计算： 接收端对接收到的数据段执行完全相同的数学加法。
5. 验证： 接收端将新计算出的校验和与从发送端收到的校验和进行比较。
6. 结果： 如果两个校验和匹配，则接受数据。如果不匹配，说明传输过程中发生了错误。

类比： 把大数据块想象成一个大的快递箱。发送者在外面贴上一个总重量标签（即校验和）。如果接收者称重里面的物品，发现总重量与标签不符，他们就知道运输过程中东西被添加或拿走了。

核心要点： 校验和在检测数据块内的多处错误方面比简单的奇偶校验更有效。

---

2.3 回声校验（Echo Check）

回声校验是一种非常直观的方法，即接收设备直接将收到的数据发回给发送者进行确认。

操作步骤：

1. 发送端传输数据。
2. 接收端立即将数据发回（即“回声”）。
3. 发送端将回传的数据与发送的原始数据进行比较。
4. 如果两者完全相同，则假定传输正确。

缺点： 主要风险是错误可能发生在回传过程中。发送端会将损坏的接收数据与完美的原始数据进行比较并正确发现差异，但它无法准确判断传输是在哪一步失败的（是去程还是回程）。

---

3. 校验位（检测数据录入错误）

虽然奇偶校验和校验和处理的是传输错误，但校验位（Check Digit）是一种专门用于检测人为在输入或扫描长参考编号时产生错误的技巧（即数据录入错误）。

什么是校验位？

校验位是附加到代码编号末尾的额外数字。该数字是使用代码中的其他数字通过数学计算得出的。它起到了安全验证的作用。

校验位的使用场景：

• 国际标准书号（ISBN）： 最后一个数字是校验位。
• 条形码（UPC/EAN）： 条形码线条下方可见的最后一个数字即为校验位。

验证过程：

当数字被输入（或扫描）时：

1. 计算机获取代码的主要数字。
2. 应用特定的计算算法（通常涉及将每个数字乘以不同的权重）。
3. 计算出校验位应该是多少。
4. 将计算得出的校验位与实际输入的校验位（代码的最后一位）进行比较。

如果输入的数字有错误，例如转置错误（Transposition error）（交换相邻数字，例如输入 1234 而不是 1243）或单个数字错误，计算通常会失败，数字会被拒绝。

鼓励一下： 不用担心去学习具体的 ISBN 计算方法，只需理解其目的（检测数据录入/转置错误）以及使用场景（用于代码，而非通用数据文件）即可。

4. 自动重复请求（ARQ）

一旦使用奇偶校验或校验和等方法检测到错误，系统就需要修复它。由于错误检测方法通常无法纠正损坏的数据，最简单的解决方案是要求发送端重新发送数据包。这就是自动重复请求（Automatic Repeat Query, ARQ）协议的任务。

ARQ 使用两个主要机制来确保可靠交付：

4.1 确认应答（ACK 和 NACK）

接收端向发送端发回一个信号，以确认接收到的数据包的状态：

• 肯定应答（ACK）： 如果数据包接收正确（例如校验和匹配），接收端发送 ACK。发送端随后可以继续发送下一个数据包。
• 否定应答（NACK）： 如果收到了数据包，但检测到错误（例如校验和失败），接收端发送 NACK。该信号告诉发送端：“我收到了第 5 个包，但它损坏了，请重发。”

4.2 超时（Timeout）

如果数据包完全丢失，接收端没有发回任何东西怎么办？

超时机制处理此情况：

1. 当发送端传输一个数据包时，它会启动一个计时器。
2. 计时器设置为一个合理的时间段，称为超时（Timeout）。
3. 如果在计时器耗尽之前，发送端没有收到 ACK 或 NACK，它就会假定原始数据包（或确认信号）丢失了。
4. 然后发送端会自动重新发送数据包。

核心要点： ARQ 结合了确认应答和超时机制，即使发生错误，也能保证数据传输的可靠性。