信道编码文献综述

信息论基础文献综述学生姓名:韩承昊学生学号: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 codes1 一文中提出的。汉明码在传输的信息流中插入验证码，以侦测并更正单一比特错 误。由于汉明码编码十分简单，使得汉明码至今还被广泛应用着。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 codes2一书中提出的。级联码 是一种乘积码，级联码的提出对于差错控制编码有着重要的意义，大名鼎鼎的 Turbo码就是一种并行级联卷积码。一个简单的级联码由两个码组成：一个(nk1)二进制码C1和一个符号取自GF(2)的(n ,k )非二进制码C。C的符号以其对应的由k个二进制符号组成的 22221字节来表示。通常，使用RS码作为C2。编码由两步组成，首先，k1k2个二进制 信息比特被划分成k2个字节，每个字节包含k1个信息比特。按照C2的规则，这k2 个字节被编码成含n个字节的码字。第二步，每个k比特的字节都被编码成C中211的码字，从而生成由n个C中的码字组成的数串，总共nn位。然后，这些数字211 2被发送，每次C码字。1译码同样需要两步。首先，每到达一个C码字就对他进行译码，去除校验位，1留下由n2个k1比特的字节组成的序列。之后，按照C2的译码方法对这些字节进 行译码，得到最终纠错信息。级联码对客服随机错误和突发错误的组合非常有效。如果级联码要纠正某个 错误模式，则通过C1码不能纠正的字节错误模式必须构成C2码的某个可纠正错 误模式。分散的随机错误C码进行纠正。突发错误可能只影响到相对较少的几1个字节，但很可能严重到C已经不能够纠正它们。此时，这较少的几个字节可1以由C2进行纠正%。3、BCH Code(1959-1960)BCH码1959年由Hocquenghem、1960年由Bose和Chandhari分别独立提出 的囹。BCH码是一种循环码，若循环码的生成多项式有如下形式：g(x) = LCMm (x),m (x),., m (x)其中LCM表示最小公倍式，t为纠错个数，m(x)为素多项式。则由此生成的循环码称为BCH码。其最小码距d d = 2t +1，它能纠正t个随机独立错误。当 0BCH码的码长为2m-1时称为本原BCH码，其他的称为非本原BCH码。BCH码的译码一直是人们讨论和研究的重点，大致分为四个步骤：1、计算接收到的向量R的2t伴随矩阵。2、计算错误定位多项式。3、解多项式，得到错误位置。4、如果不是二进制BCH码，就计算错误位置的误差值。其中比较高效的是 Peterson GorensteinZierler 算法5,6 和 Berlekamp-Massey7 算法。BCH码是对汉明码的重要推广，它可以纠正多个错误。BCH码给出了一种 新颖的方法：先定义希望它能纠错的个数，然后再构造这种码。这样可以根据信 道的实际情况来决定我们需要的纠错个位数。BCH码的诞生激励了无数码的产 生，其中就包括了著名的RS码。另外其简单的编码电路也使得BCH码成为了 一种重要的编码方式。4、RS Code(1960)RS 码是由 Reed 和 Solomon 在Polynomial codes over certain finite fields 中提出的。RS码是BCH码的一种特殊情况，当伽罗华域GF(qm)中的m = 1时的q进制 BCH码就叫做RS码。RS码在已经别广泛运用于数字通信和存储系统中，以进 行差错控制闵。RS码生成多项式为g (x) = (x-以)(x-以2).(x-以2t)，因此xq-1 -1能够被g (x) 整除。所以g(x)将生成恰好具有2个奇偶校验符号、长度为q -1的q进制循环 码。该码的最小码距为2t +1，并且该码能够纠正小于等于t个符号的错误。由于RS码也是BCH码的一种，所以同样可以用Peterson GorensteinZierler 算法5,6和 Berlekamp-Massey7算法。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 /%仅为约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 codes13中提 出了 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构造方法。不 规则码的构造主要是对分布函数(X, p)的研究。对于LDPC码的译码，Gallager 提出了基于硬判决的树型译码算法和基于软判决的迭代译码算法。另一个常用的则是 Message Passing 算法。LDPC可以说是现在信道编码界性能最接近香农限的编码了，2001年,Chung 就构造出了距离Shannon极限仅0.0045的非规则LDPC码。三、总结LDPC不是整个编码界的重点，人们不断地发现更好更先进的码。比如无线 传输中的空时编码，空时编码在不同天线所发送的信号中引入时间和空间的相关 性，从而不用牺牲带宽就可以为接收端提供不编码系统所没有的分集增益和编码 增益。就算现在来看仍然是让人感到新奇的和不可思议的。人们的眼界也不止限制在追求高信道容量上面，其中网络编码的提出就是一 个很好的例子。在传统的数据传输技术中，中继节点只负责数据的存储转发，而 基于网络编码技术的网络的中继节点在具备传统中继功能的基础上，会根据网络 编码规则将接收到的信息进行线性或非线性处理再进行传播，这种做法最直观的 优势是减少了传输次数。从香农论文发表到现在已经60多年了，差错控制编码技术飞速的发展。从 Hamming码到LDPC码，进步的不只是越来越接近的香农限，还有通信人对科 学的孜孜不倦的追求。而这，将激励我们站在前辈的努力上继续前进，最终能从 理论上找到达到香农限的编码。这对于我们来讲并不仅仅是一种学术上的追求， 而是一种对人生目标的设定和努力。四、参考文献1 Hamming R W. Error detecting and error correcting codesJ. Bell System technical journal, 1950, 29(2): 147-160.2 Forney G D, Forney G D. Concatenated codesM. Cambridge: MIT press, 1966.3 Lin S, Costello D J. Error control codingM. 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-ChaudhuricodesJ. Information Theory, IRE Transactions on, 1960, 6(4): 459-470.6 Gorenstein D, Zierler N. A Class of Cyclic Linear Error- Correcting Codes in/yJ. Journal of the Society for Industrial and Applied Mathematics, 1961, 9: 207-214.7 Berlekamp E. On Decoding Binary Bose-Chadhuri-HocquenghemCodesJ. Information Theory, IEEE Transactions on, 1965, 11(4): 577-579.8 Reed I S, Solomon G. Polynomial codes over certain finite fieldsJ. 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. 1C/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 codesJ. Information Theory, IEEE Transactions on, 1996, 42(2): 429-445.11 Benedetto S, Montorsi G. Unveiling turbo codes: Some results on parallel concatenated coding schemesJ. Information Theory, IEEE Transactions on, 1996, 42(2): 409-428.12 白宝明.Turbo码理论及其应用的研究D.西安电子科技大学博士论文，1999.13 Gallager R G. Low-density parity-check codes, 1963J.PhD, Massachusetts Institute of Technology, 1963.14MacKay D J C, Neal R M. Near Shannon limit performance of low density parity check codesJ. Electronics letters, 1996, 32(18): 1645.