在计算机,电信,信息理论和编码理论中,纠错码(ECC,error correction/correcting code)是信息传输中错误检测与纠正的工具。它通常用在不可靠或嘈杂的信道中。数据发送方利用纠错码中的冗余信息,使得接收方能够检测消息传输中发生的错误,而且通常可以纠正这些错误而无需重新传输。美国数学家理查德·汉明(Richard Hamming)在1940年代开创了这一领域,并在1950年发明了第一个纠错码:汉明(7,4)代码。
相比错误检测,纠错码不仅能够检测到错误,而且可以将其更正。它的优点是在出现错误时不需要反向信道来请求重发数据,缺点是消息中增加了固定开销,因此需要更高的前向信道带宽。因此,纠错码用于重传成本高昂或无法实现的情况,例如单向通信链路,时延较长的链接,以及以多播方式发送给多个接收者的链接。比如,绕天王星运行的卫星,由于传输错误而造成的重发会造成5个小时的延迟。纠错码信息通常添加到大容量存储设备中,以恢复损坏的数据,并广泛用于调制解调器,以及主存储器为 ECC 内存的系统中。
接收机中的纠错码处理可以应用于数字比特流,也可以应用于数字调制载波的解调。对于后者,纠错码是接收器中模拟数字转换器的组成部分。维特比(Viterbi)解码器采用软判决算法,以从被噪声破坏的模拟信号中解调数字数据。许多纠错码编码器/解码器还可以生成比特误码率(BER)信号,该信号可用作反馈以微调模拟接收电子设备。
纠错码能够纠正的错误位/丢失位的最大数量取决于它的的设计,因此,不同的纠错码适用于不同的环境。一般来说,能够纠正大量错误的代码中有着更多的冗余信息,所以会需要更多带宽进行传输,从而降低了有效比特率,且同时提高了接收到的有效信噪比。克劳德·香农(Claude Shannon)的有噪信道编码定理回答了以下问题:若使用最有效的代码将解码错误概率变为零,数据通信还剩下多少带宽?对于具有基本噪声水平的信道,该定理给出了理论上的最大信息传输速率。但是,该证明不具建设性,也就是说它并不能用来构建实现最大速率的代码。经过多年的研究,如今一些先进的纠错码系统,其速率已非常接近理论最大值。
纠错码的编码方法如下:发信方利用算法,向要传输的信息添加冗余位。这些冗余位通常是将原始输入位由复杂的函数转换而成。原始信息不一定原样出现在输出的编码中;包含原始信息的代码称为系统代码,反之称为非系统代码。
下面是一个简单纠错码的例子:将每个数据位发送3次。这种编码称为(3,1)重复码。 通过嘈杂的频道,接收器可能会收到8个不同版本的输出,参见下表:
若收到的信息非3个重复的数位,则以重复次数较多的数位为准。该纠错码最多纠正一位错误位,或两位丢失位。虽然这种纠错码实施方便且应用广泛,但这种三重模块冗余的形式是效率较低的。更好的纠错码通常会检查先前接收到的几十位,或几百位,由此判断如何解码当前的几位(通常以2到8位为一组)。
纠错码的使用对信息噪声产生的破坏有“平均化”的作用。由于每一个原始数据位生成了多于一个的传输符,尽管某些传输符可能遭到噪声的破坏,接收方通常能够依赖其它未损坏的,由相同原始位生成的接收符来获取原本数据。由于这种效应,使用纠错码的数字通信系统往往能够在信噪比远高于最小信噪比的情况下运转。在运转过程中,系统的信噪比永远不会低于最小信噪比。当使用更强的,接近香农极限的代码时,这种悬崖效应将变得更加明显。有时,信道错误通常是突发型的。在这种情况下,可以使用交错的纠错码来将数据编码,这样能够降低所传输纠错码的悬崖效应。但是,这种方法也有局限性,它比较适用于窄带数据。
大多数电信系统使用固定的信道代码,这样的信道代码通常可以容忍预期的最坏误码率;如果误码率高于该值,则系统根本无法运转。但是,有些系统能够适应特定的信道错误条件:在一些混合式自动重送请求的实例中,错误率较低时系统使用固定的纠错码,而在错误率过高时切换到自动重传请求。 自适应调变和编码能够应对多种错误率:当通道中的错误率较高时,在每个数据包中添加更多的纠错位,而在不需要它们时将其删除。
纠错码分为两大类:分组码和卷积码。
分组码适用于一连串固定长度的数据包,而每一种分组码只能用于特定长度的数据包。实际用途中的分组码一般使用硬解码方式,所需时间为每一个数据包长度的多项式时间。分组码有许多不同的类型,值得关注的有里德-所罗门码,它被广泛的应用于光盘,DVD和硬盘驱动器中。经典分组码的其他例子有格雷码,BCH码,多维奇偶校验码(英语:Multidimensional parity-check code)和汉明码。
卷积码适用于任意长度的比特流/符号流。接收方通常使用维特比算法将其软解码,但有时也会用其他算法。随着卷积码约束条件的长度增加,维特比解码的解码效率渐近最优;但作为代价,计算时间将以对数式增长。长度有限的卷积码也可以看作一种“分组码”,因为输入数据是成组的;但是卷积码的每一“组”长度不一,而分组码的长度是固定的,且由其特定的代数性质而定。 卷积码有几种不同的终止方式,如“咬尾巴(tail-biting)”和“比特刷新(bit-flushing)”。
汉明纠错码一般用来纠正NAND闪存错误。它可以矫正一位错误或检测两位错误。汉明码仅适用于相对可靠的单层单元NAND,较稠密的多层单元NAND需要能够校正更多位的纠错码,例如BCH或里德-所罗门码 。NOR闪存通常不需要任何错误校正。
分组码通常使用硬决策算法解码,在这种决策方式下,每个输入和输出信号都非1即0。而卷积码则相反,使用如维特比,MAP或BCJR(英语:BCJR)算法之类的软决策算法进行解码,该算法用于离散化的模拟信号,并且比硬判决解码具有更高的纠错性能。
几乎所有的经典分组码都利用了有限域的代数性质。因此,经典分组码也称为代数码。
经典分组码的检错或纠错能力通常是事先预定的,而许多现代的分组码(例如低密度奇偶检查码)并没有这方面的保证;它们的能力是由误码率来评估的。
大多数前向纠错码仅纠正翻转位,而不能纠正插入位或丢失位。在这种情况下,计算误码率时应使用汉明距离。一些前向纠错码可以纠正插入位和丢失位,例如标记码和水印码。若使用此类代码,测量比特误码率时使用莱文斯坦距离更加合适。