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 ，
2 k 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 和一个符号取自
电子科技大学 信息论基础 文献综述
学生姓名:
韩承昊
学生学号: 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 不等式：
GF (2k1 ) 的 (n2 , k2 ) 非二进制码 C2 。 C2 的符号以其对应的由 k1 个二进制符号组成的
字节来表示。通常，使用 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 分别独立提出 的 。 BCH 码是一种循环码，若循环码的生成多项式有如下形式：
[4]
g ( x) LCM [m1 ( x), m3 ( x),..., m2t 1 ( x)]
其中 LCM 表示最小公倍式，t 为纠错个数， mi ( x) 为素多项式。则由此生成的循 环码称为 BCH 码。其最小码距 d d 0 2t 1 ，它能纠正 t 个随机独立错误。当 BCH 码的码长为 2m 1 时称为本原 BCH 码，其他的称为非本原 BCH 码。 BCH 码的译码一直是人们讨论和研究的重点，大致分为四个步骤： 1、计算接收到的向量 R 的 2t 伴随矩阵。 2、计算错误定位多项式。 3、解多项式，得到错误位置。 4、如果不是二进制 BCH 码，就计算错误位置的误差值。 其中比较高效的是 Peterson Gorenstein Zierler 算法 [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 (q m ) 中的 m 1 时的 q 进制 BCH 码就叫做 RS 码。RS 码在已经别广泛运用于数字通信和存储系统中，以进 行差错控制[3]。 RS 码生成多项式为 g ( x) ( x )( x 2 )...( x 2t ) ，因此 x q 1 1 能够被 g ( x ) 整除。所以 g ( x ) 将生成恰好具有 2t 个奇偶校验符号、长度为 q 1 的 q 进制循环 码。该码的最小码距为 2t 1 ，并且该码能够纠正小于等于 t 个符号的错误。 由于 RS 码也是 BCH 码的一种，所以同样可以用 Peterson Gorenstein Zierler 算法[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 / N 0 仅为约 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]。