串行编程/错误纠正方法
串行编程: 介绍和 OSI 网络模型 -- RS-232 布线和连接 -- 典型的 RS232 硬件配置 -- 8250 UART -- DOS -- MAX232 驱动器/接收器系列 -- Windows 中的 TAPI 通信 -- Linux 和 Unix -- Java -- Hayes 兼容调制解调器和 AT 命令 -- 通用串行总线 (USB) -- 形成数据包 -- 错误纠正方法 -- 双向通信 -- 数据包恢复方法 -- 串行数据网络 -- 实际应用开发 -- 串行连接上的 IP
主要有三种处理错误的方式
- 确认或重试 (ACK-NAK)。
- "前向纠错" (FEC)
- 假装从未发生
每个数据包都会由接收器检查，以确保它是“有效的”。
如果它*是*有效的，接收器（最终）会告诉发送器它已成功接收 - 它会确认（ACK）数据包。
所有版本的 ACK-NAK 绝对需要 双向通信。
发送器会计算整个数据包的校验和或 CRC（除了页脚），然后将其附加到数据包的末尾（在页脚/尾部）。
典型的 CRC 是 32 位，通常是 Fletcher-32 校验和。
旁注：请注意，校验和或 CRC 是哈希的形式，即不可逆地缩减数据。校验和和 CRC 比“加密强度高”的消息认证代码算法（如 MD5 或 SHA 变体）弱。加密强度高的算法可以比校验和或 CRC 更好地检测错误，但它们计算起来需要更多时间。
每当接收器收到数据包时，接收器都会计算完全相同的校验和或 CRC，然后将其与页脚/尾部中的校验和或 CRC 进行比较。如果匹配，整个数据包（几乎可以肯定）是有效的，因此接收器会发送 ACK。
当对数据包有任何错误（可能是*实际数据*或*标头*或*校验和位*中的错误 - 接收器无法判断）存在哪怕一丝疑问时，接收器会完全丢弃它，并且（在大多数情况下）假装从未看到它。
如果它不是有效的，发送器 会再次发送它。
它没有收到 ACK。（因此数据包要么被破坏，要么 ACK 被破坏 - 发送器无法判断）。
ACK-NAK 的最简单版本是“停等 ARQ”。
发送器发送一个数据包，然后等待一会儿以接收 ACK。一旦它收到 ACK，它就会立即发送下一个数据包。如果发送器没有及时收到 ACK，它会从头开始，再次发送相同的数据包，直到收到 ACK。
接收器会等待数据包。如果数据包完全通过了所有错误检测测试，接收器会向发送器传输 ACK（确认）。
细微之处：如果接收器完美地接收了数据包，但 ACK 消息延迟太长，则发送器会发送消息的另一个副本（“通信回声”）。想象一下，数据包包含消息“从弗雷德的账户中扣除 11,000 美元”。当接收器收到此消息的第二个副本时，它应该怎么做？当然，它应该发送 ACK（否则发送器将不断尝试发送此消息）。以下问题中的一个或两个都可能发生
- 延迟的第一个 ACK 可能会在发送器传输消息的第二个副本后到达发送器，因此它会传输下一个数据包。然后，第二个 ACK 命中发送器，欺骗发送器认为“下一个数据包”已成功接收，而实际上并没有。
- 当接收器收到两个相同且连续的数据包，上面写着“从弗雷德的账户中扣除 11,000 美元”时，这是否是两个合法的独立交易，因此它应该从弗雷德的账户中扣除 22,000 美元？还是它实际上只是一笔交易，只是有一点回声，因此应该只从弗雷德的账户中扣除 11,000 美元？
这两个问题都可以通过添加“序列号”来解决。发送方跟踪发送给接收方的独立数据包数量，并将该序列号放到每个数据包的头部。但当重传数据包时，会重传相同的数据包，并使用相同的序列号。同样，接收方在发送通用“ACK”消息时，会通过在ACK消息中添加序列号来指定它正在回复哪个特定数据包。当出现通信回声时，接收方会看到相同的序列号，因此会再次对该序列号进行ACK确认，但随后会丢弃和忽略它已经接收到的多余冗余数据包副本。当发送方发送一个恰好包含相同数据的新数据包时，接收方会看到一个不同的序列号，因此会对该新序列号进行ACK确认，并从弗雷德的账户中再提取 11,000 美元。可怜的弗雷德。
对于停止-等待系统，一个比特的序列号（对于每个新数据包交替使用 1 - 0 - 1 - 0，并以 ACK1 ACK0 ACK1 ACK0 的方式进行响应）就足够了。但正如我们将在后面看到的，其他 ARQ 协议需要更大的序列号。
微妙之处：一些早期的协议要求接收方在接收到错误数据包时向发送方发送一个 NAK（负确认），而发送方会无限期地等待，直到收到 ACK 或 NAK。这是一个糟糕的主意。想象一下，当 (a) 一点噪声导致了一个错误数据包，因此接收方向发送方发送了 NAK，但随后 (b) 一点噪声又让该 NAK 变得无法识别时，会发生什么。或者，想象一下一个共享介质网络，其中有一个发送方和两个接收方。当一点噪声破坏了数据包的“目标”字段时，会发生什么？
使用“停止-等待 ARQ”，发送方和接收方只需要在一次处理一个数据包。
流式 ARQ
[edit | edit source]发送方发送一个数据包，然后发送下一个数据包，再发送下一个数据包，无需等待。
发送每个数据包时，它会将该数据包的副本放入一个“窗口”。
每个数据包都进行连续编号。（序列号必须至少足够大，以唯一地标识窗口中的每个数据包）。
… 周转时间 … 从地球同步卫星上反弹 …
接收方偶尔会发送一个确认消息（“我已经收到所有序号小于 8980 的数据包”，“我已经收到所有序号小于 8990 的数据包”）。
如果接收方正在等待序号为 9007 的数据包，但它收到一个序号 *更早* 的数据包（它已经成功接收过该数据包），它会发送（或者可能重新发送）一个“我已经收到所有序号小于 9006 的数据包”消息。
当发送方收到“窗口”中任何数据包的确认消息时，它会删除该副本。
当发送方的窗口已满时，它会等待一小段时间，然后尝试重新发送窗口中的数据包，从最旧的数据包开始。
因此，当发送方怀疑某些数据包有错误时，它会从错误数据包开始重新发送 *所有* 数据包。这保证接收方最终将按照顺序收到所有数据包。
可选地，如果接收方正在等待序号为 9007 的数据包，但它收到序号为 9008 的数据包，它可以发送一个 9007 的负确认 (NAK)，并在收到 9007 的数据包之前忽略任何更高序号的数据包。
当发送方收到“窗口”中任何数据包的 NAK 时，它会从该数据包开始重新传输（并将其保留在窗口中）。
使用“流式 ARQ”，发送方需要在一次处理整个窗口的数据包。但接收方仍然只需要一次处理一个数据包，并按照顺序处理它们。
（有些人认为“流式”就像一个使用“停止-等待”协议的大数据包，其大小与窗口相同，被分成更小的“子数据包”）。
选择重传 ARQ
[edit | edit source]
选择重传 ARQ 系统是一种流式 ARQ。
但接收方不是只处理一次一个数据包，并丢弃所有序号高于或低于它正在查找的数据包的数据包，而是尝试在自己的窗口中保留所有接收到的数据包的副本，并与发送方协商，只尝试重新发送有误的数据包。
FEC
[edit | edit source]如果只有单向通信，则必须使用前向纠错，有时称为 EDAC（错误检测和纠正）。
发送数据，然后（而不是 CRC）发送“校验位”，这些校验位是根据数据计算出来的。
… NASA 太空探测器 … 光盘 …
最简单的类型是“重复消息”。
如果发送同一个数据包两次，并且噪声只破坏了其中一个，*并且* 接收方可以识别出哪个数据包被破坏，那么就不会丢失任何数据。如果发送同一个数据包三次，并且噪声破坏了其中任何一个，那么接收方就可以执行“最佳 2/3”。“校验位”是数据位的两个副本。事实上，噪声可能会破坏所有三个数据包的一小部分，你仍然可以提取所有数据——将三个数据包并排放置，并对每一位执行“最佳 2/3”。只要每个数据包中只有少量噪声，并且噪声在每个数据包中的位置不同，就可以恢复所有数据。
… （在此处添加图片）…
有一些非常巧妙的 FEC 类型（汉明码、里德-所罗门码）可以比“最佳 2/3”更好地纠正各种常见错误，并且只需要与数据位一样多的“校验位”。
假装从未发生
[edit | edit source]发送方通常会实时流式传输音频和视频。
当数据包被破坏时，接收方应该怎么做？
如果它向发送方发送一条消息，要求它重新发送该数据包，那么当回复返回时，可能已经是几个视频帧之后了。使用这些信息已经太晚了。
与其暂停整个电影，直到请求完成往返，不如让接收方在悄无声息地接受一些信号退化的情况下，将注意力从它身上转移开，这样观众的观感不会那么突兀。接收方会丢弃破坏的数据包，尽力猜测数据包中本来应该有的数据，然后继续进行，就好像什么也没发生一样。例如，它可能会用附近像素的颜色填充空白区域。采用这种策略的接收方应该记录它不得不填充空白的次数，以便用户可以排除无法持续准确复制的连接故障。
组合
[edit | edit source]即使有双向通信，有时人们也会使用 FEC。这样就可以在接收方纠正少量噪声。如果数据包被严重破坏，FEC 无法修复，协议会回退到 ACK-NAK 重传（或“假装从未发生”）。
进一步阅读
[edit | edit source]一个 ACK-NAK 协议的详细描述：“XModem / YModem 协议参考”，作者：查克·福斯伯格，1988 年 10 月 14 日 https://web.archive.org/web/20070717073025/http://www.commonsoftinc.com:80/Babylon_Cpp/Documentation/Res/KYModemProtocol.htm 来自原始网站的存档 http://www.commonsoftinc.com/Babylon_Cpp/Documentation/Res/yModem.htm
一个流式协议的详细描述：“ZMODEM 应用程序间文件传输协议”，作者：查克·福斯伯格，1988 年 10 月 14 日 https://web.archive.org/web/20061017125259/http://www.commonsoftinc.com/Babylon_Cpp/Documentation/Res/KZModem.htm 来自原始网站的存档 http://www.commonsoftinc.com/Babylon_Cpp/Documentation/Res/zModem.htm
“数据链路错误检测/纠正方法” http://techref.massmind.org/techref/method/errors.htm 对几种错误纠正方法的简要描述：汉明码、火码、里德-所罗门码、维特比解码等。