错误检测与纠正
在计算机科学和通信的信息论和编码理论应用中，错误检测和纠正（英語：error detection and correction）或错误控制（error control）是在不可靠的通信信道上可靠地传送数字数据的技术。许多通信信道会经受信道噪声，因此可能在源至接收器的传输期间引入错误。错误检测技术能够检测这样的错误，而错误纠正能在不少情况下重建原始数据。
定义
[编辑]该术语的一般定义如下：
- 错误检测是检测发射机到接收机的传输期间由噪声或其他原因所致的错误。
- 错误纠正是检测错误并重建无错误的原样数据。
历史
[编辑]错误纠正编码的现代发展在1947年由理查德·衛斯里·漢明带来。[1]汉明码的描述出现于克劳德·香农的《通信的数学理论》一书中[2]，并由Marcel J. E. Golay迅速推广。[3]
引入
[编辑]实现错误检测和纠正的一般思路是添加一些信息冗余（例如一些额外数据）到消息，从而使接收器可以用它来检查消息的一致性，并恢复被确定为损坏的数据。错误检测和纠正的方案可以是系统性或非系统性：在系统性方案中，发射机发送原始数据，并且附加其通过一些确定性算法从数据位元导出的固定数量的校验位（或奇偶校验数据）。如果仅需要错误检测，则接收器可以简单对接收到的数据位应用相同的算法，并将其输出与接收到的校验位进行比较。如果值不匹配，则传输期间的某个点位发生错误。在非系统性的编码系统中，原始消息被变换与原始消息相等或更长位元的被编码消息。
良好的错误控制性能需要基于通信信道的特性来选择方案。常见的信道模型包括无记忆模型，其中错误以一定概率随机发生，以及错误主要突发出现的动态模型。因此，错误检测与纠正编码通常可分为：随机错误检测/纠正与突发错误检测/纠正。一些编码是同时适用随机错误与突发错误的混合体。
如果信道容量不能被确定，或者高度可变，错误检测方案可以与重传出错数据的系统组合。这也称之为自动重传请求（ARQ），它在互联网中极为常用。用于替代错误控制的一种方案是混合式自動重送請求（HARQ），它是ARQ与错误纠正编码的组合。
实现
[编辑]错误纠正通常可以用两种方式实现：
- 自动重传请求（ARQ），有时也称后向纠错：这是一种错误控制技术，其中将错误检测方案与重传错误数据的请求组合。其中使用错误检测代码检查接收的每个数据块，如果检查失败则请求重传数据——这可以被重复进行，直至数据可通过验证。
- 前向錯誤更正（FEC）：发送者在传输前使用纠错码（ECC）对数据进行编码。额外信息（信息冗余）由代码添加以供接收者用来恢复原始数据。一般来说，重建的数据被认为是“最有可能”的原始数据。
ARQ与FEC可以组合，使得不需重传就纠正微小错误，并经由重传请求校正大的错误，这被称为混合式自動重送請求（HARQ）。
错误检测方案
[编辑]错误检测通常使用适合的散列函數（或校验和 算法）实现。散列算法添加定长的标签到消息，从而使接收者能通过计算标签并与所提供的标签比较来验证传递的消息。
散列函数存在多种多样的设计。其中一部分因其简单性或适合检测某些类型的错误（例如循環冗餘校驗的性能优势 为检测突发错误而使用）而被广泛使用。
一个随机前向錯誤更正 基于最小距离编码的可以对可检测误差的数量提供严格保证，但它可能不能防御原像攻击。下面章节中描述的重复编码就是纠错码的一种特殊案例。虽然相当低效，但由于其简单性，重复编码适合部分纠错与检测的应用。
重复编码
[编辑]重复编码是在信道上重复比特信息以实现无差错通信的编码方案。首先将要发送的数据流划分为比特块，然后将每个传输预定的次数。例如，要发送位元“1011”，四位元块((what))则再重复三次而产生“1011 1011 1011”。但是，如果此例中收到12位元信息为“1010 1011 1011”，其中第一个块不同于其他两个，则可以确定已经发生错误。
重复编码非常低效，并且如果错误在每个组的完全相同的地方发生，则很容易出现问题（例如上例中正巧错误为“1010 1010 1010”，将被检测为传输无误）。重复编码的优点是它非常简单，并实际上用于某些数字电台的传输。[4][5]
奇偶校验位
[编辑]奇偶校验位（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需要一个反向信道可用，这使重传可能增加延迟，并且需要维护用于重传的缓冲器和计时器，这在拥塞控制的情况下可对服务器和整体网络容量造成压力。[6]
举例来说，ARQ在短波无线电数据链路中的应用为ARQ-E，结合复用为ARQ-M。
纠错码（ECC）
[编辑]前向錯誤更正（ECC）或前向纠错（FEC）码是一种添加信息冗余数据或奇偶校验数据到消息的过程，使得即使在传输或存储中发生多个错误，接收方也可以用它恢复（不能超过编码本身的能力限制）。因为接收方不必要求发送方重传数据，在前向纠错中不需要反向信道，并因此适合诸如广播等单边通信。纠错码经常用于底层通信，以及用于诸如CD、DVD、硬盘和RAM等介质中的可靠存储。
- 卷积码是逐位元处理。它特别适合于硬件，并且Viterbi解码器允许译码方法。
- 分组码是以逐块为基础。分组码的早期例子有重复码、汉明码和多维奇偶校验码。在它们之后是一些更有效的代码，里德-所罗门码因为其最显着所以目前被广泛使用。Turbo码和低密度奇偶檢查碼（LDPC）相对较新的方法，可以提供几乎最佳的效率。
香农定理是前向纠错的一个重要定理，并且描述了在具有特定错误概率或信噪比（SNR）的信道上可进行可靠通信的最大信息速率。这个严格的上限以信道容量表示。
所允许的实际最大码率取决于所使用的纠错码，并可能更低。这是因为香农的证明只是存在性的，并没有显示如何构建代码是为最优并具有高效的编码和解码算法。
混合方案
[编辑]混合式自動重送請求是ARQ与前向纠错的组合。有两种基本方法：[6]
- 消息始终与FEC奇偶校验数据（和错误检测冗余）一起发送。接收机使用奇偶校验信息解码消息，并仅在奇偶校验数据不足以成功解码（通过失败的完整性校验来识别）时才使用ARQ请求重传。
- 消息在没有奇偶校验数据的情况下传输（仅具有错误检测信息）。如果接收方检测到错误，则其使用ARQ向发送方请求FEC信息，然后用它来重建原始消息。
后一种方法在擦除信道上使用喷泉码时尤为有吸引力。
应用程序
[编辑]需要低延迟的应用程序（如电话通话）不能使用ARQ；它们必须使用前向錯誤更正（FEC）。在此类应用中，当ARQ系统发现错误及重新请求和完成发送，重新发送的数据到达之时对于此类应用已然太迟以至没有任何作用。
发送方在发送后立即忘记信息的应用（例如大多数摄像头）不能使用ARQ；它们必须使用FEC，因为当发现错误时，原始数据已不再可用。（这也是为什么FEC被用于RAID、分散式檔案系統等数据存储系统）。
使用ARQ的应用程序必须有一个返回信道；没有返回信道的应用程序不能使用ARQ。需要极低错误率的应用程序（如数字货币转移）必须使用ARQ。可靠性和检验工程也利用了纠错码的理论。[7]
互联网
[编辑]在典型的TCP/IP栈中，错误控制在多个层级施行：
- 每个以太网帧携带一个CRC-32校验和。接收到校验和不正确的帧将由接收器硬件丢弃。
- IPv4报头包含保护头内容的校验和。不正确校验和的網路封包将在网络或接收处丢弃。
- IPv6报头中省略了校验和，以最小化网络路由的处理成本，并也假设当前的链路层技术足以提供足够的错误检测（另见RFC 3819）。
- UDP具有覆盖有效载荷和来自UDP和IP报头寻址信息的可选校验和。有不正确校验和的数据包将被操作系统协议栈丢弃。校验和仅在IPv4下可选，因为数据链路层的校验和可能已提供了所期望的错误保护。
- TCP提供用于保护有效载荷和来自TCP和IP报头寻址信息的校验和。有不正确校验和的数据包将在网络堆栈中被丢弃，并最终使用ARQ进行重传，可能显式（例如通过三重ack）或因超时而隐含。
深空通信
[编辑]由于信号功率在星际距离上的极度稀释，以及空间探测器上有限的可用功率，纠错码的开发与深空任务的历史紧密相关。在早期任务中，发送数据未被编码，而从1968年开始，则以（子最优解码）卷积码和里德-穆勒码的形式实现数字纠错。[8]里德-穆勒码非常适合于航天器所受噪声（大致匹配钟形曲线），并在1969年至1977年期间在水手航天器上执行任务。
在自1977年开始的旅行者1号和旅行者2号任务中，设计包括在木星和土星的科学信息中提供彩色成像。[9]这使得编码的要求增加，因此航天器得到了可以级联外部Golay (24,12,8)码的卷积码（最优Viterbi解码器）的支持。
旅行者2号探测器也添加了一种里德-所罗门码的支持：串联的里德-所罗门-维特比（RSV）码允许非常强效的错误纠正，并使航天器的旅程延长到天王星和海王星。两个探测器在1989年ECC系统升级后使用V2 RSV编码。
CCSDS目前建议至少使用性能类似于Voyager 2 RSV代码的纠错码。串联码日已失去了空间任务的青睐，并正被更强大的编码所取代，例如Turbo码或低密度奇偶檢查碼。
不同种类的深空和轨道任务表明，试图找到一个“万能”的纠错系统将是一段时间以来一个持续的问题。对于接近地球的任务，信道雜訊的性质与星际任务中的宇宙飞船经历并不相同。此外，随着航天器与地球距离的增加，校正噪声的问题也日益严重。
卫星广播（DVB）
[编辑]受到提供电视节目（包括提供新频道和高清晰度电视）和IP数据需求的推动，卫星转发器带宽需求持续增长。转发器的可用性和带宽限制限制了这种增长，因为转发器的容量是由所选择的調變模式和前向錯誤更正（FEC）速率决定。
概述
- QPSK加上传统的里德·所罗门和维特比码已经为提供数字卫星电视使用了近20年。
- 高阶调制方案如8PSK、16QAM和32QAM已使卫星工业将转发器效率提高了几个数量级。
- 这种应答器中信息速率的增加以牺牲载波功率的代码以满足现有天线的阈值要求。[需要解释]
- 使用最新芯片组进行的测试表明，使用Turbo码实现的性能可能甚至低于早期设计中假定的0.8 dB。
数据存储
[编辑]错误检测和纠正码经常被用于提供数据存储介质的可靠性。[來源請求]第一例是1951年在磁带数据存储上的“奇数轨道”。用于分组代码记录磁带的“最佳矩形代码”不仅能检测，还能校正单位元错误。部分檔案格式，尤其是归档格式，包含一个校验和（通常以CRC32提供）以检测损坏与截断，并可以采用冗余和/或奇偶效验文件来恢复损坏部分的数据。里德-所罗门码就被用于光盘中，以纠正由划痕引起的错误。
现代的硬盘驱动器使用CRC代码来检测和里德-所罗门码校正扇区读取中的较小错误，以及从“损坏”的扇区恢复数据并将该数据存储在备用扇区中。[10]RAID系统使用各种纠错技术来纠正硬盘驱动器出现完全故障时导致的错误。诸如ZFS或Btrfs等文件系统以及部分RAID实现支持数据擦洗和弹性，这允许在使用之前检测并希望恢复坏块。恢复的数据可能被重写到完全相同的物理位置，以备在同一硬件上的另一处坏块，或者替换硬件。
错误纠正内存
[编辑]动态随机存取存储器（DRAM）内存可以采用纠错码提供对軟性錯誤的增强保护。诸如纠错内存（也称ECC或'EDAC保护内存）就是一种面向高容错应用提供的内存，它适合服务器以及要经受宇宙線增加考验的深空应用。
错误纠正存储器的控制器通常使用汉明码，也有些使用三重冗余模块。
交织允许通过将相邻位与不同的字相关联来分散单个宇宙射线对多个物理相邻位的潜在破坏。只要一次单粒子翻转在特定期间内不超过错误阈值（例如：单比特错误），它就可以被纠正（例如通过单比特纠错码），并使存储系统维持在无错误的状态。[11]
除了通过ECC内存硬件提供此项特性外，操作系统通常也包含相关的报告措施，用以在软错误被透明恢复时提供通知。软错误的增加率可能预示着DIMM模块需要被更换，但在没有相关手段的情况下，此类报告信息不容易取得。例如，Linux内核的EDAC子系统（以前称为bluesmoke）会在启用错误检查的计算机系统内部收集数据；除了收集和报告与ECC内存相关的事件外，它还支持其他校验和错误，包括在PCI总线上检测到的错误。[12][13][14]
有几个系统也支持内存刷洗。
参见
[编辑]- 伯格码
- 突发错误纠正码
- 前向錯誤更正
- 自適應調變和編碼
- 错误检测与纠正算法列表
- 前向錯誤更正
- 散列函数列表
- 可靠性 (计算机网络)
参考资料
[编辑]- ^ Thompson, Thomas M., From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America: vii, 1983, ISBN 0-88385-023-0
- ^ Shannon, C.E., A Mathematical Theory of Communication, Bell System Tech. Journal (p. 418), 1948, 27
- ^ Golay, Marcel J. E., Notes on Digital Coding, Proc.I.R.E. (I.E.E.E.) (p. 657), 1949, 37
- ^ Frank van Gerwen. Numbers (and other mysterious) stations. [12 March 2012]. （原始内容存档于2017-07-12）.
- ^ Gary Cutlack. Mysterious Russian ‘Numbers Station’ Changes Broadcast After 20 Years. Gizmodo. 2010-08-25 [12 March 2012]. （原始内容存档于2017-07-05）.
- ^ 6.0 6.1 A. J. McAuley, Reliable Broadband Communication Using a Burst Erasure Correcting Code, ACM SIGCOMM, 1990.
- ^ Ben-Gal I.; Herer Y.; Raz T. Self-correcting inspection procedure under inspection errors (PDF). IIE Transactions on Quality and Reliability, 34(6), pp. 529-540. 2003 [2017-03-16]. （原始内容 (PDF)存档于2013-10-13）.
- ^ K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007.
- ^ Huffman, William Cary; Pless, Vera S. Fundamentals of Error-Correcting Codes. Cambridge University Press. 2003. ISBN 978-0-521-78280-7.
- ^ My Hard Drive Died.
- ^ Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite. 北京清华大学清华空间中心. [2009-02-16]. （原始内容存档于2011-10-02）.
- ^ Jeff Layton. Error Detection and Correction. Linux Magazine. [2014-08-12]. （原始内容存档于2020-11-11）.
- ^ EDAC Project. [2014-08-12]. （原始内容存档于2014-09-25）.
- ^ Documentation/edac.txt. Linux kernel documentation. kernel.org. 2014-06-16 [2014-08-12]. （原始内容存档于2009-09-05）.
拓展阅读
[编辑]- Shu Lin; Daniel J. Costello, Jr. Error Control Coding: Fundamentals and Applications. Prentice Hall. 1983. ISBN 0-13-283796-X.
外部链接
[编辑]- The on-line textbook: Information Theory, Inference, and Learning Algorithms （页面存档备份，存于互联网档案馆），作者戴维·J·C·麦凯。章节包括有关基本纠错码，关于误差校正的理论极限，以及最新、最前沿的错误纠正码，例如低密度奇偶檢查碼、turbo codes和喷泉码。
- Compute parameters of linear codes （页面存档备份，存于互联网档案馆） – 用于生成和计算参数的在线接口（例如线性误差校正码的最小距离、覆盖半径）。
- ECC Page（页面存档备份，存于互联网档案馆）
- SoftECC: A System for Software Memory Integrity Checking （页面存档备份，存于互联网档案馆）
- A Tunable, Software-based DRAM Error Detection and Correction Library for HPC （页面存档备份，存于互联网档案馆）
- Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing （页面存档备份，存于互联网档案馆）
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
