电子科技大学 信息论基础文献综述

学生姓名:韩承昊学生学号:201321260330

指导老师:许渤

综述名称:差错控制编码的发展与展望

差错控制编码的发展与展望

一、 前言

1948年Shannon首次提出：只要信息传输速率低于信道容量,通过对信息适当进行编码，可在不牺牲信息传输或存储速率的情况下，将有噪信道或存储媒质引入的差错减到任意低的程度。这就是著名的信道编码定理，信道编码定理奠定了整个纠错码的基础。

信道编码在数字通信系统中，利用纠错码或检错码进行差错控制的方式大致分为以下几类：

1、重传反馈方式（ARQ）

重传反馈方式指的是在通信之中引入反向信道，接收端收到错误信息时可以通过反向信道发送消息从而使得发送方从新发送错误消息，以减少错误概率。

ARQ方式中，编译码设备比较简单，在一定的多余度码元下，检错码的检错能力比纠错码的纠错能力要高得多，因而整个系统的纠错能力极强，能获得极低的误码率。

缺点也很明显，ARQ方式必须有一反向信道，且要求信源能够控制，系统收发两端必须互相配合、密切协作，从而导致控制电路比较复杂。再者反馈重发的次数与信道干扰情况有关，若信道干扰很频繁，则系统经常处于重发消息的状态，因此这种方式传送消息的连贯性和实时性较差。

2、前向纠错方式（FEC）

在编码过程中增加冗余位，通过增加的信息位来确保接收端可以校验或者改正传输中发生的错误，从而减小错误概率。

FEC方式最吸引人的地方就是不需要反馈信道，实时性很好，相比ARQ方式减小了一个信道的开销。同时FEC方式的控制电路也非常的简单。

FEC最令人纠结的地方就是冗余位的长度和错误概率的折中选择，冗余位的加长，虽然会使得错误概率减小，却大大减小了传输效率。但若减少冗余位，却会使得错误概率增加。

3、混合纠错方式（HEC）

顾名思义，HEC结合了前两种纠错方式。接收端收到码序列以后，首先检验错误情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果错误很多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消息。

HEC结合了两种方式的优点，使得码字的连贯性较好，纠错能力也较强，并且编码设备简单等优点，从而在应用中使用的越来越广。

二、 正文

自Shannon之后，人们不断向逼近信道容量努力，并取得重大发展，如分组码，代数码，卷积码，网格码和Turbo码。所能达到的性能也越来越接近Shannon限间的距离。

1、Hamming Code(1950)

汉明码是Hamming在1950年《Error detecting and error correcting codes[1]》一文中提出的。汉明码在传输的信息流中插入验证码，以侦测并更正单一比特错误。由于汉明码编码十分简单，使得汉明码至今还被广泛应用着。

Hamming在文中提出了一种新颖的编码方式。设数据位数为n，校验位数为k，则总编码位数为n，则n?m?k。有Hamming不等式：

2k?1?n，2k?m?k?1

对于这个不等式可以理解为：由于n位码长中有一位出错，所以可能产生n个不正确的代码。其中错误位也可能发生在校验位，所以加上k位校验后，就需要定位n?m?k个状态。用k个状态中的一个状态指出“有无错”，其余2k?1个状态便可用于错误的定位。若要能充分地进行错误定位，则须满足Hamming不等式的关系。

汉明码在不增加码距的情况下很难纠正多位错误，所以对于突发的连续性干扰很难纠正，这也是汉明码的缺点之一。但这扔不妨碍汉明码是一个创新性的思想，它给了信道编码界一个新的活力，促进了诸如BCH码的诞生，从而使得信道编码的研究更进一步。

2、 Concatenated Codes(1966)

级联码是Forney于1966年《Concatenated codes[2]》一书中提出的。级联码是一种乘积码，级联码的提出对于差错控制编码有着重要的意义，大名鼎鼎的Turbo码就是一种并行级联卷积码。

一个简单的级联码由两个码组成：一个(n1,k1)二进制码C1和一个符号取自

C2的符号以其对应的由k1个二进制符号组成的GF(2k1)的(n2,k2)非二进制码C2。

字节来表示。通常，使用RS码作为C2。编码由两步组成，首先，k1k2个二进制

信息比特被划分成k2个字节，每个字节包含k1个信息比特。按照C2的规则，这k2个字节被编码成含n2个字节的码字。第二步，每个k1比特的字节都被编码成C1中的码字，从而生成由n2个C1中的码字组成的数串，总共n1n2位。然后，这些数字被发送，每次C1码字。

译码同样需要两步。首先，每到达一个C1码字就对他进行译码，去除校验位，留下由n2个k1比特的字节组成的序列。之后，按照C2的译码方法对这些字节进行译码，得到最终纠错信息。

级联码对客服随机错误和突发错误的组合非常有效。如果级联码要纠正某个错误模式，则通过C1码不能纠正的字节错误模式必须构成C2码的某个可纠正错误模式。分散的随机错误C1码进行纠正。突发错误可能只影响到相对较少的几个字节，但很可能严重到C1已经不能够纠正它们。此时，这较少的几个字节可以由C2进行纠正[3]。

3、BCH Code(1959-1960)

BCH码1959年由Hocquenghem、1960年由Bose和Chandhari分别独立提出的[4]。

BCH码是一种循环码，若循环码的生成多项式有如下形式：

g(x)?LCM[m1(x),m3(x),...,m2t?1(x)]

其中LCM表示最小公倍式，t为纠错个数，mi(x)为素多项式。则由此生成的循环码称为BCH码。其最小码距d?d0?2t?1，它能纠正t个随机独立错误。当BCH码的码长为2m?1时称为本原BCH码，其他的称为非本原BCH码。

BCH码的译码一直是人们讨论和研究的重点，大致分为四个步骤： 1、计算接收到的向量R的2t伴随矩阵。 2、计算错误定位多项式。 3、解多项式，得到错误位置。

4、如果不是二进制 BCH 码，就计算错误位置的误差值。

其中比较高效的是Peterson GorensteinZierler算法[5],[6]和Berlekamp-Massey[7]算法。

BCH码是对汉明码的重要推广，它可以纠正多个错误。BCH码给出了一种

新颖的方法：先定义希望它能纠错的个数，然后再构造这种码。这样可以根据信道的实际情况来决定我们需要的纠错个位数。BCH码的诞生激励了无数码的产生，其中就包括了著名的RS码。另外其简单的编码电路也使得BCH码成为了一种重要的编码方式。

4、RS Code(1960)

RS码是由Reed和Solomon在《Polynomial codes over certain finite fields[8]》中提出的。

RS码是BCH码的一种特殊情况，当伽罗华域GF(qm)中的m?1时的q进制BCH码就叫做RS码。RS码在已经别广泛运用于数字通信和存储系统中，以进行差错控制[3]。

RS码生成多项式为g(x)?(x??)(x??2)...(x??2t)，因此xq?1?1能够被g(x)整除。所以g(x)将生成恰好具有2t个奇偶校验符号、长度为q?1的q进制循环码。该码的最小码距为2t?1，并且该码能够纠正小于等于t个符号的错误。

由于RS码也是BCH码的一种，所以同样可以用Peterson GorensteinZierler算法[5],[6]和Berlekamp-Massey[7]算法。

5、Turbo Code(1993)

1993年，Berrou、Glavieux、Thitimajshima在ICC会议上发表了《Near Shannon limit error-correcting coding and decoding: Turbo codes[9]》。单是这个论文名字就足够有诱惑力了，“逼近香农限的纠错码”，这是以前的Hamming、BCH、RS等码所不具有的。论文中，在高斯信道下的情况下，码率为1/2的Turbo码在达到误比特率BER?10?5时，Eb/N0仅为约0.7dB。这个结果震惊了整个信道编码界。

从1993年Turbo码提出以来，尽管有关Turbo码的研究成果层出不穷，但Turbo码的整体构架还是很不完善，对Turbo码的数学理论仍缺乏全面透彻的认识。其中有一定成果的是1996年在IEEE发表的两篇论文《Iterative decoding of binary block and convolutional codes[10]》和《Some results on parallel concatenated coding schemes[11]》。在第一篇中，Hagenauer等首次清晰的运用数学理论阐明了迭代译码的原理，系统地给出了二进制分组码与卷积码的软输出译码算法，包括MAP与Apriori-SOVA算法。提出了基于相对熵的迭代停止判决条件，并基于计算机模拟结果指出：在低码率时由卷积码构成的Turbo码的性能较好，而在高码率时，由分组码构成的Turbo码的性能较好[12]。

Benedetto等首次提出了均匀交织器的概念，并基于此，从码的重量枚举函数

出发，利用联合界技术给出了Turbo码的一个在所有交织器上平均的性能上界，启发式地说明了随着迭代次数的增加，迭代译码收敛于最大似然译码，这是首次系统地对Turbo码进行性能分析[12]。

一个码所包含的结构特点越多，其译码也就越简单，对于编码而言，高度结构化的编码性能往往会远远低于香农所提供给我们的极限理论。尽管如此，随机码研究没有进展的主要原因是由于随机码缺少结构特征，难以译码。但Turbo码有类随机码的特征，也有足够的信息，这使得我们能够更简单的实现Turbo码的译码[3]。

Turbo码的发明可以说是开启了编码界一个新的纪元，当这并不代表着Turbo码没有缺点.Turbo码编码复杂，使得编码延时很长。再者由于最小距离性能较差，在极低误比特率条件下，性能会下降。

6、LDPC Code(1963)

1963年，Galleger在他的博士论文《Low-density parity-check codes[13]》中提出了LDPC码，LDPC码具有很好的汉明距离特性，是满足Shannon限的渐进好码，经过迭代后验概率译码可以获得依码字长度指数降低的误比特率，虽然LDPC码迭代译码时每个码元的复杂度独立于码长，但是由于计算复杂度超出当时的计算能力，LDPC码被人们所遗忘。此后的几十年时间里，除了Tanner等人对其进行了一些研究以外，LDPC码几乎被人们遗忘了。时间逝水而过，直到1996年，MacKay重新发现LDPC码[14]，并指出LDPC的优秀性能可以逼近Shannon极限。LDPC码才重新进入大家的视野，并受到广泛重视。

LDPC码是一种校验矩阵H中只有很少的元素为“1”，大部分元素都是“0”的一种线性分组码。Gallager最早给出了规则LDPC码的定义，采用三个参数n，

p，q来定义规则LDPC码(n,p,q)，其中p是校验矩阵H中每列所包含的“1”

的个数，q是H中每行所包含的“1”的个数。之所以叫规则码，就是因为H中每行所包含的“1”的个数以及每列所包含的“1”的个数分别相同，这里的q，

p也称为矩阵H的行重和列重。由于q和p都很小，校验矩阵H具有很低的“密

度”，因此由校验矩阵H所确定的码称为低密码校验码。

LDPC码的构造有两个要点，第一个是构造尽可能大的码距，再者是Tanner图中没有短环。规则码的构造主要由Gallager构造方法和MacKay构造方法。不规则码的构造主要是对分布函数(?,?)的研究。对于LDPC码的译码，Gallager提出了基于硬判决的树型译码算法和基于软判决的迭代译码算法。另一个常用的

则是Message Passing算法。

LDPC可以说是现在信道编码界性能最接近香农限的编码了，2001年，Chung就构造出了距离Shannon极限仅0.0045的非规则LDPC码。

三、总结

LDPC不是整个编码界的重点，人们不断地发现更好更先进的码。比如无线传输中的空时编码，空时编码在不同天线所发送的信号中引入时间和空间的相关性，从而不用牺牲带宽就可以为接收端提供不编码系统所没有的分集增益和编码增益。就算现在来看仍然是让人感到新奇的和不可思议的。

人们的眼界也不止限制在追求高信道容量上面，其中网络编码的提出就是一个很好的例子。在传统的数据传输技术中，中继节点只负责数据的存储转发，而基于网络编码技术的网络的中继节点在具备传统中继功能的基础上，会根据网络编码规则将接收到的信息进行线性或非线性处理再进行传播，这种做法最直观的优势是减少了传输次数。

从香农论文发表到现在已经60多年了，差错控制编码技术飞速的发展。从Hamming码到LDPC码，进步的不只是越来越接近的香农限，还有通信人对科学的孜孜不倦的追求。而这，将激励我们站在前辈的努力上继续前进，最终能从理论上找到达到香农限的编码。这对于我们来讲并不仅仅是一种学术上的追求，而是一种对人生目标的设定和努力。

四、参考文献

[1]Hamming R W. Error detecting and error correcting codes[J]. Bell System technical journal, 1950, 29(2): 147-160.

[2]Forney G D, Forney G D. Concatenated codes[M]. Cambridge: MIT press, 1966. [3]Lin S, Costello D J. Error control coding[M]. Englewood Cliffs: Prentice-hall, 2004.

[4]Wilson S G. Digital modulaion and coding.Beijing:Pub-lishing House ofElectronic Industy,1998.

[5]Peterson W. Encoding and error-correction procedures for the Bose-Chaudhuricodes[J]. Information Theory, IRE Transactions on, 1960, 6(4): 459-470.

[6]Gorenstein D, Zierler N. A Class of Cyclic Linear Error-Correcting Codes in/У[J]. Journal of the Society for Industrial and Applied Mathematics, 1961, 9: 207-214. [7]Berlekamp E. On Decoding Binary Bose-Chadhuri-HocquenghemCodes[J]. Information Theory, IEEE Transactions on, 1965, 11(4): 577-579.

[8]Reed I S, Solomon G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial & Applied Mathematics, 1960, 8(2): 300-304.

[9]Berrou C, Glavieux A, Thitimajshima P. Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1[C]//Communications, 1993.ICC 93. Geneva. Technical Program, Conference Record, IEEE International Conference on. IEEE, 1993, 2: 1064-1070.

[10]Hagenauer J, Offer E, Papke L. Iterative decoding of binary block and convolutional codes[J]. Information Theory, IEEE Transactions on, 1996, 42(2): 429-445.

[11]Benedetto S, Montorsi G. Unveiling turbo codes: Some results on parallel concatenated coding schemes[J]. Information Theory, IEEE Transactions on, 1996, 42(2): 409-428.

[12]白宝明.Turbo码理论及其应用的研究[D].西安电子科技大学博士论文, 1999. [13]Gallager R G. Low-density parity-check codes, 1963[J].PhD, Massachusetts Institute of Technology, 1963.

[14]MacKay D J C, Neal R M. Near Shannon limit performance of low density parity check codes[J]. Electronics letters, 1996, 32(18): 1645.