什么是纠错码?

[拼音]：jiucuoma

[外文]：error correcting code

在传输过程中发生错误后能在收端自行发现或纠正的码。仅用来发现错误的码一般常称为检错码。纠错编码又称信道编码，它与信源编码是信息传输的两个方面。它们之间存在对偶的关系。应用信道译码直接对一些自然信息进行处理，可以去掉剩余度，以达到压缩数据的目的。

为了使一种码具有检错或纠错能力，必须对原码字增加多余的码元，以扩大码字之间的差别，使一个码字在一定数目内的码元上发生错误时，不致错成另一个码字。准确地说，即把原码字按某种规则变成有一定剩余度的码字，并使每个码字的码元间有一定的关系。关系的建立称为编码。码字到达收端后，用编码时所用的规则去检验。如果没有错误，则原规则一定满足，否则就不满足。由此可以根据编码规则是否满足以判定有无错误。当不能满足时，在可纠能力之内按一定的规则确定错误所在的位置，并予以纠正。纠错并恢复原码字的过程称为译码；码元间的关系为线性时，称为线性码；否则称为非线性码。检错码与其他手段结合使用，可以纠错。检错反馈重发系统（ARQ系统）就是一例。

在构造纠错码时，将输入信息分成 k位一组以进行编码。若编出的校验位仅与本组的信息位有关，则称这样的码为分组码。若不仅与本组的 k个信息位有关，而且与前若干组的信息位有关，则称为格码。这种码之所以称为格码，是因为用图形分析时它象篱笆或格架。线性格码在运算时为卷积运算，所以叫卷积码。

C.E.仙农在1948年发表在《通信的数学理论》一文中的信道编码定理指出：只要采用适当的纠错码，就可在多类信道上传输消息，其误码率pe可以任意小

(1)

式中n为码长；Er(R)为信息率R的函数，与信道有关。当R小于信道容量C时，Er(R)为正值。可惜的是这一定理仅仅指出理论上可以达到的目标，而未能给出构造性的实现方法。自仙农的论文发表以来，人们经过持续不懈的努力已找到多种好码，可以满足许多实用要求。但在理论上，仍存在一些问题未能解决。

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变大时不是性能欠佳或者难以构造，就是译码过分复杂，不容易实现。但是，可以利用好的码进行级连，以得到性能更好的码。级连码的内码和外码，用分组码和卷积码都可以。这在深空通信中应用较多。

纠错码能够检错或纠错，主要是靠码字之间有较大的差别。这可用码字之间的汉明距离 d(x，y)来衡量。它的定义为码字x与y之间的对应位取不同值的码元个数。一种纠错码的最小距离 d定义为该种码中任两个码字之间的距离的最小值。一种码要能发现e个错误，它的最小距离d应不小于e+1。若要能纠正t个错误，则d应不小于2t+1。一个码字中非零码元的个数，称为此码字的汉明重量。一种码中非零码字的重量的最小值，称为该码的最小重量。对线性码来说，一种码的最小重量与其最小距离在数值上是相等的。

在构造线性码时，数字上是从n维空间中选一k维子空间，且使此子空间内各非零码字的重量尽可能大。当构造循环码时，可进一步将每一码字看成一多项式，将整个码看成是多项式环中的理想，这一理想是主理想，故可由生成多项式决定；而多项式完全可由它的根规定。这样，就容易对码进行构造和分析。这是BCH码等循环码构造的出发点。一般地说，构造一种码时，均设法将它与某种代数结构相联系，以便对它进行描述，进而推导它的性质，估计它的性能和给出它的译码方法。若一种码的码长为n，码字数为M，或信息位为h，以及最小距离为d，则可把此码记作[n，M，d]码。若此码为线性码，常简记作(n，k)或(n，k，d)码。人们还常用R=log2M/n表示码的信息率或简称码率，单位为比特/码元。R越大，则每个码元所携带的信息量越大，编码效率越高。

纠错码实现中最复杂的部分是译码。它是纠错码能否应用的关键。根据式(1)，采用的码长n越大，则误码率越小。但n越大，编译码设备也越复杂，且延迟也越大。人们希望找到的译码方法是:误码率随码长n的增加按指数规律下降;译码的复杂程度随码长n的增加接近线性地增加；译码的计算量则与码长 n基本无关。可惜，已经找到的码能满足这样要求的很少。不过由于大规模集成电路的发展，既使应用比较复杂的但性能良好的码，成本也并不太高。因此，纠错码的应用越来越广泛。

纠错码传输的都是数字信号。这既可用硬件实现，也可用软件实现。前者主要用各种数字电路，主要是采用大规模集成电路。软件实现特别适合计算机通信网等场合。因为这时可以直接利用网中的计算机进行编码和译码，不需要另加专用设备。硬件实现的速度较高，比软件可快几个数量级。

在传信率一定的情况下，如果采用纠错码提高可靠性，要求信道的传输率增加，带宽加大。因此，纠错码主要用于功率受限制而带宽较大的信道，如卫星、散射等系统中。纠错码还用在一些可靠性要求较高，但设备或器件的可靠性较差，而余量较大的场合，如磁带、磁盘和半导体存储器等。

在分组码的研究中，谱分析的方法受到人们的重视。纠同步错误码、算术码、不对称码、不等错误纠正码等，也得到较多的研究。

参考书目

万哲先：《代数与编码》，科学出版社，北京，1976。W.W.Peterson， Error-Correcting Codes，MIT Press，Cambridge，Mass.，1961.E.R.Berlekamp， Algebraic Coding Theory，McGraw-Hill，New York，1968.