错误检测与纠正

历史

错误纠正编码的现代发展在1947年由理查德·卫斯里·汉明带来。汉明码的描述出现于克劳德·香农的《通信的数学理论》一书中，并由Marcel J. E. Golay迅速推广。

引入

实现错误检测和纠正的一般思路是添加一些信息冗余（例如一些额外数据）到消息，从而使接收器可以用它来检查消息的一致性，并恢复被确定为损坏的数据。错误检测和纠正的方案可以是系统性或非系统性：在系统性方案中，发射机发送原始数据，并且附加其通过一些确定性算法从数据比特导出的固定数量的校验位（或奇偶校验数据）。如果仅需要错误检测，则接收器可以简单对接收到的数据位应用相同的算法，并将其输出与接收到的校验位进行比较。如果值不匹配，则传输期间的某个点位发生错误。在非系统性的编码系统中，原始消息被变换与原始消息相等或更长比特的被编码消息。
良好的错误控制性能需要基于通信信道的特性来选择方案。常见的信道模型包括无记忆模型，其中错误以一定概率随机发生，以及错误主要突发出现的动态模型。因此，错误检测与纠正编码通常可分为：随机错误检测/纠正与突发错误检测/纠正。一些编码是同时适用随机错误与突发错误的混合体。
如果信道容量不能被确定，或者高度可变，错误检测方案可以与重传出错数据的系统组合。这也称之为自动重传请求（ARQ），它在互联网中极为常用。用于替代错误控制的一种方案是混合式自动重送请求（HARQ），它是ARQ与错误纠正编码的组合。

错误检测方案

错误检测通常使用适合的散列函数（或校验和 算法）实现。散列算法添加定长的标签到消息，从而使接收者能通过计算标签并与所提供的标签比较来验证传递的消息。
散列函数存在多种多样的设计。其中一部分因其简单性或适合检测某些类型的错误（例如循环冗余校验的性能优势  为检测突发错误而使用）而被广泛使用。
一个随机前向纠错  基于最小距离编码的可以对可检测误差的数量提供严格保证，但它可能不能防御原像攻击。下面章节中描述的重复编码就是纠错码的一种特殊案例。虽然相当低效，但由于其简单性，重复编码适合部分纠错与检测的应用。

重复编码

重复编码是在信道上重复比特信息以实现无差错通信的编码方案。首先将要发送的数据流划分为比特块，然后将每个传输预定的次数。例如，要发送比特“1011”，四比特块{{what}}则再重复三次而产生“1011 1011 1011”。但是，如果此例中收到12位信息为“1010 1011 1011”，其中第一个块不同于其他两个，则可以确定已经发生错误。
重复编码非常低效，并且如果错误在每个组的完全相同的地方发生，则很容易出现问题（例如上例中正巧错误为“1010 1010 1010”，将被检测为传输无误）。重复编码的优点是它非常简单，并实际上用于某些数字电台的传输。

奇偶校验位

奇偶校验位（parity bit）是一种非常简单的方案，可以用于检测任何奇数个错误的发生。但如果发生的错误数量为偶数，则奇偶效验位看上去是正确的。
对奇偶效验位的扩展和改变有纵向冗余校验、垂直冗余检查，以及双或对角奇偶（在RAID-DP中使用）。

校验和

消息的校验和是固定字长（例如字节值）的字节码的模算数和。和可能在传输前用一补数以检测全零消息出现的错误。
校验和方案包括奇偶校验位、校验码和纵向冗余校验。部分校验和方案如Damm算法、Luhn算法和Verhoeff算法在设计上是专门用于检测人类书写或记录数字时常出现的错误。

循环冗余校验（CRC）

循环冗余校验（CRC）是一个非安全的散列函数，旨在检测计算机网络中数字数据的意外变化。因此，它不适合检测恶意引入的错误。
循环码有着非常适合检测突发错误的有利特性。CRC尤其容易在硬件中实现，并且因此常用在数字网络和诸如硬盘等存储设备中。
奇偶校验是循环冗余校验的特殊案例，其中单比特CRC由除数x + 1生成。

加密散列函数

加密散列函数的输出也称消息摘要，它可以提供强力的数据完整性保证，无论数据改变是偶然（例如由于传输错误）还是被恶意引入。对数据的任何修改都可用检测散列值是否匹配判断。此外，指出某些散列值并找到产生相同散列值的另一组输入数据（原输入数据除外）一般是不可行的。如果攻击者不仅能改变消息，还可以改变散列值，那么含密钥散列或或消息认证码（MAC）可用于提供额外的安全性（即密钥散列消息认证码）。在不了解密钥的情况下，攻击者不可能计算出结果正确的含密钥散列值。

错误纠正码

任何错误纠正码都可用于错误检测。最小汉明距离为d的编码在码字中最多可以检测出d − 1个错误。如果对要检测的最小错误数量有严格限制，使用基于最小距离的纠错码进行错误检测则很合适。
最小汉明距离d = 2的编码是纠错码的退化情况，并可用于检测单个错误。奇偶校验位是单错误检测的一个例子。

自动重传请求（ARQ）

自动重传请求（ARQ）是通过错误检测码、确认或否决消息，以及可靠消息数据传输的消息超时来完成数据传输的一种错误控制方法。确认消息是由接收方发送，以表明其已正确接收数据帧。
通常来说，当发送方没有在超时发生前（即发送数据帧之后的合理时间内）接收到确认，则它将重传该帧，直到该帧被正确接收，或者该错误反复存在而超过预定的重传次数。
ARQ协议的三种类型是停止并等待ARQ、后退N帧ARQ和选择重传ARQ。
如果通信信道具有变化或未知的容量，例如在互联网，则ARQ适宜使用。但是，ARQ需要一个反向信道可用，这使重传可能增加延迟，并且需要维护用于重传的缓冲器和计时器，这在拥塞控制的情况下可对服务器和整体网络容量造成压力。
举例来说，ARQ在短波无线电数据链路中的应用为ARQ-E，结合复用为ARQ-M。

应用程序

需要低延迟的应用程序（如电话通话）不能使用ARQ；它们必须使用前向纠错（FEC）。在此类应用中，当ARQ系统发现错误及重新请求和完成发送，重新发送的数据到达之时对于此类应用已然太迟以至没有任何作用。
发送方在发送后立即忘记信息的应用（例如大多数摄像头）不能使用ARQ；它们必须使用FEC，因为当发现错误时，原始数据已不再可用。（这也是为什么FEC被用于RAID、分布式文件系统等数据存储系统）。
使用ARQ的应用程序必须有一个返回信道；没有返回信道的应用程序不能使用ARQ。需要极低错误率的应用程序（如数字货币转移）必须使用ARQ。可靠性和检验工程也利用了纠错码的理论。

深空通信

由于信号功率在星际距离上的极度稀释，以及空间探测器上有限的可用功率，纠错码的开发与深空任务的历史紧密相关。在早期任务中，发送数据未被编码，而从1968年开始，则以（子最优解码）卷积码和里德-穆勒码的形式实现数字纠错。里德-穆勒码非常适合于航天器所受噪声（大致匹配钟形曲线），并在1969年至1977年期间在水手航天器上执行任务。
在自1977年开始的旅行者1号和旅行者2号任务中，设计包括在木星和土星的科学信息中提供彩色成像。这使得编码的要求增加，因此航天器得到了可以级联外部Golay (24,12,8)码的卷积码（最优Viterbi解码器）的支持。
旅行者2号探测器也添加了一种里德-所罗门码的支持：串联的里德-所罗门-维特比（RSV）码允许非常强效的错误纠正，并使航天器的旅程延长到天王星和海王星。两个探测器在1989年ECC系统升级后使用V2 RSV编码。
CCSDS当前建议至少使用性能类似于Voyager 2 RSV代码的纠错码。串联码日已失去了空间任务的青睐，并正被更强大的编码所取代，例如Turbo码或低密度奇偶检查码。
不同种类的深空和轨道任务表明，试图找到一个“万能”的纠错系统将是一段时间以来一个持续的问题。对于接近地球的任务，信道噪声的性质与星际任务中的宇宙飞船经历并不相同。此外，随着航天器与地球距离的增加，校正噪声的问题也日益严重。

数据存储

错误检测和纠正码经常被用于提供数据存储介质的可靠性。第一例是1951年在磁带数据存储上的“奇数轨道”。用于分组代码记录磁带的“最佳矩形代码”不仅能检测，还能校正单比特错误。部分文件格式，尤其是归档格式，包含一个校验和（通常以CRC32提供）以检测损坏与截断，并可以采用冗余和/或奇偶效验文件来恢复损坏部分的数据。里德-所罗门码就被用于光盘中，以纠正由划痕引起的错误。
现代的硬盘驱动器使用CRC代码来检测和里德-所罗门码校正扇区读取中的较小错误，以及从“损坏”的扇区恢复数据并将该数据存储在备用扇区中。RAID系统使用各种纠错技术来纠正硬盘驱动器出现完全故障时导致的错误。诸如ZFS或Btrfs等文件系统以及部分RAID实现支持数据擦洗和弹性，这允许在使用之前检测并希望恢复坏块。恢复的数据可能被重写到完全相同的物理位置，以备在同一硬件上的另一处坏块，或者替换硬件。

错误纠正内存

动态随机存取存储器（DRAM）内存可以采用纠错码提供对软性错误的增强保护。诸如纠错内存（也称ECC或'EDAC保护内存）就是一种面向高容错应用提供的内存，它适合服务器以及要经受宇宙线增加考验的深空应用。
错误纠正存储器的控制器通常使用汉明码，也有些使用三重冗余模块。
交织允许通过将相邻位与不同的字相关联来分散单个宇宙射线对多个物理相邻位的潜在破坏。只要一次单粒子翻转在特定期间内不超过错误阈值（例如：单比特错误），它就可以被纠正（例如通过单比特纠错码），并使存储系统维持在无错误的状态。
除了通过ECC内存硬件提供此项特性外，操作系统通常也包含相关的报告措施，用以在软错误被透明恢复时提供通知。软错误的增加率可能预示着DIMM模块需要被更换，但在没有相关手段的情况下，此类报告信息不容易获取。例如，Linux内核的EDAC子系统（以前称为bluesmoke）会在启用错误检查的计算机系统内部收集数据；除了收集和报告与ECC内存相关的事件外，它还支持其他校验和错误，包括在PCI总线上检测到的错误。
有几个系统也支持内存刷洗。