错误检测与纠正（链路层）

错误检测与纠正通过向传输数据添加经过精心计算的冗余位，使接收方能够检测并有时纠正由噪声通信链路引入的位错误。

Definition

错误检测与纠正是一种编码技术，它附加从数据计算出的冗余校验位，以便接收方能够确定传输过程中位是否损坏（检测），并且使用更强的编码，能够重建原始数据（纠正）。

Scope

本主题涵盖了链路层用于处理位错误的编码技术：用于检测的简单奇偶校验、二维奇偶校验、互联网校验和以及循环冗余校验（CRC），以及用于纠正的前向纠错码，如汉明码。它讨论了冗余开销与检测或纠正强度之间的权衡，以及每种技术的应用场景。它不包括在更高层构建的基于重传的可靠性，后者是编码的补充而非替代。

Core questions

• 冗余校验位如何让接收方检测到传输已损坏？
• 奇偶校验、校验和与循环冗余校验在强度和成本上有何不同？
• 前向纠错码（如汉明码）如何在不重传的情况下纠正错误？
• 编码开销与错误处理能力之间有何权衡？
• 何时错误纠正优于检测加重传？

Key concepts

• 奇偶校验
• 二维奇偶校验
• 互联网校验和
• 循环冗余校验（CRC）
• 生成多项式
• 前向纠错
• 汉明码
• 突发错误
• 编码开销

Key theories

用于错误检测的冗余

通过传输从数据计算出的额外位——一个奇偶校验位、一个校验和或一个CRC余数——接收方可以重新计算并比较以检测损坏；基于多项式算术的CRC可以捕获所有突发错误，其长度可达生成多项式的度数。

前向纠错

汉明码等纠错码添加了足够的结构化冗余，使得接收方不仅可以检测到，还可以定位并修复有限数量的位错误，从而避免了重传，但代价是增加了开销。

信道容量与可靠通信

信息论确立了每个噪声信道都有一个容量，低于该容量，通过适当的编码可以实现任意可靠的通信，这构成了实际错误控制码所接近的基本限制。

Clinical relevance

错误控制无形但无处不在：CRC保护以太网和Wi-Fi帧，校验和保护IP和传输头，而前向纠错在重传成本高昂或不可能的情况下至关重要，例如在深空链路、存储介质和通过有损无线进行流媒体传输时。检测与纠正之间的适当平衡塑造了通信和存储系统的可靠性和效率。

History

克劳德·香农（Claude Shannon）1948年的信息论确立了在信道容量范围内可靠编码的存在，理查德·汉明（Richard Hamming）1950年的编码方案首次提供了实用的单错误纠正方案。随后出现了循环冗余校验和更强的编码，成为链路层帧中的标准，此后该领域产生了强大的编码（如涡轮码和LDPC码），这些编码接近香农极限。

Key figures

• Claude Shannon
• Richard Hamming

Seminal works

• shannon1948
• hamming1950
• kurose2021

Frequently asked questions

错误检测和错误纠正有什么区别？

错误检测只告诉接收方数据已损坏，之后接收方可以丢弃数据或请求重传。错误纠正增加了足够的冗余，使得接收方无需再次请求即可重建原始数据，这在重传缓慢或不可能时非常有价值。

为什么网络使用CRC而不是简单的奇偶校验？

单个奇偶校验位会遗漏任何偶数个位错误，而基于多项式除法的循环冗余校验可以检测所有单比特错误、所有双比特错误以及所有短于校验码的突发错误，这使其对于链路实际产生的错误类型来说要强大得多。