纠错码(error correcting code) ,是在接收端能自动地纠正数据传输中所发生差错的码。纠错码的基本思路是在所有的由发送符号组成的序列中,仅挑出其中一部分做为信息的代表向信道发送,并使得所挑出的这些序列之间有尽可能多的差异。每个被挑出的允许发送的序列被称为一个码字,而码字的总合称为码。在发送端把信息变换成码字的过程称为编码;在接收端从接收到的信号判定所发码字、从而恢复信息的过程称为解码(或译码)。在解码时,若收到的信号不是码中的一个码字,则可以肯定在传输中出现了差错,从而着手对差错进行纠正。纠错的方法是找到与接收到的信号最接近的码字,并将其判定为发送信号。一般采用“距离”来度量信号间的接近程度,一种常用的“距离”称为汉明距离,它被定义为两码字间对应位不同的个数总和。一个给定码,其全部码字两两之间距离的最小值被称为这个码的码距。码距是一个码纠错能力的重要参数,例如在汉明距离下,若接收到的信号出错的位数不多于码距的一半,则接收端总能正确地恢复所发送的码字,从而正确地恢复所发送的信息。
纠错编码又称信道编码,它与信源编码是信息传输的两个方面。它们之间存在对偶的关系。应用信道译码直接对一些自然信息进行处理,可以去掉剩余度,以达到压缩数据的目的。
为了使一种码具有检错或纠错能力,必须对原码字增加多余的码元,以扩大码字之间的差别,使一个码字在一定数目内的码元上发生错误时,不致错成另一个码字。准确地说,即把原码字按某种规则变成有一定剩余度的码字,并使每个码字的码元间有一定的关系。关系的建立称为编码。码字到达收端后,用编码时所用的规则去检验。如果没有错误,则原规则一定满足,否则就不满足。由此可以根据编码规则是否满足以判定有无错误。当不能满足时,在可纠能力之内按一定的规则确定错误所在的位置,并予以纠正。纠错并恢复原码字的过程称为译码;码元间的关系为线性时,称为线性码;否则称为非线性码。检错码与其他手段结合使用,可以纠错。检错反馈重发系统(ARQ系统)就是一例。
在构造纠错码时,将输入信息分成k位一组以进行编码。若编出的校验位仅与本组的信息位有关,则称这样的码为分组码。若不仅与本组的k个信息位有关,而且与前若干组的信息位有关,则称为格码。这种码之所以称为格码,是因为用图形分析时它象篱笆或格架。线性格码在运算时为卷积运算,所以叫卷积码。 R.W.汉明于1950年首先给出可以纠正一个独立错误的线性分组码──汉明码。差不多与此同时E.戈雷给出一种可以纠正三个错误的完备码。完备码虽然十分罕见,但有较大实用意义。1954年D.E.莫勒提出一种能纠正多个错误的码;I.S.里德则立即给出它的译码方法,用的是择多判决法,这种码常称为RM码。1957年,E.普勒齐引入了循环码的概念。1959~1960年出现了BCH码,引进有限域的概念,解决了循环码的构造和性能估计等基本问题。后来成为线性分组码中最重要的一类码。它能纠正多个错误,且在实用范围内接近信道编码定理所指出的误码率值。但当n增大时,其误码率不能呈指数下降。BCH码的译码问题是W.W.彼得森解决的;钱天闻则提供了一种系统地搜索根的方法。1967年,E.R.伯利坎普提出一种迭代算法,大大简化了译码,使纠错码趋于实用。1970年В.Д.戈帕提出一种线性分组码的构造方法,原则上它可以达到吉尔伯特限,实现了理论上预期的目标。但至今仍未解决如何具体构造这种码的问题。
卷积码最早由P.伊莱亚斯于1955年提出。它的纠错能力较强,设备复杂程度与分组码大体相当。首先获得成功的译码方法是序列译码。1967年A.J.维特比提出的译码算法,能较好地按最大似然准则译码,且在许多领域中均可应用。卷积码还可用代数方法译码。它的设备虽较简单,但性能较差。卷积码在理论上不如分组码成熟,所用的工具也比较多样,尚缺乏系统的、统一的方法处理。
分组码和卷积码不但可以用来纠正独立错误,而且可以用来恢复删除错误和纠正突发错误。如分组码中有里德-索洛蒙码,法尔码等;卷积码中有岩垂码及扩散卷积码等。
为了实现低的误码率,根据式(1),要求码长n较大。但已知的大多数码,当n变大时不是性能欠佳或者难以构造,就是译码过分复杂,不容易实现。但是,可以利用好的码进行级连,以得到性能更好的码。级连码的内码和外码,用分组码和卷积码都可以。这在深空通信中应用较多。