信道编码：信道容量的探索之路外文翻译资料

英语原文共 28 页，剩余内容已隐藏，支付完成后下载完整资料

信道编码：信道容量的探索之路

五十多年的努力和发明终于产生密切接近记忆性香农信道容量限制通信信道的编码方案。

摘要：从1948年香农庆祝了信道编码定理开始，我们从汉明码到能力接近码追随信道编码的演变。我们专注于在性能方面的改进与实际的复杂性的应用中已作出的显著贡献，特别是在加性高斯白噪声信道。我们讨论了代数分组码，以及他们为什么被证明是获得香农极限的方式。我们追随今天能力接近码的来历：卷积码，级联码和其他概率性的编码方案。最后，我们得到了这些代码的一些实用程序。

关键词：代数分组码;信道编码;对码图;级联码;卷积码; 低密度校验码; Turbo码

1. 介绍

信道编码领域的研究开始于香农1948年里程碑式的论文^[1]。在接下来的半个世纪中，其核心目标是要找到切实可行的的编码方案，在充分理解的的信道能中接近信道容量（以下称为香农极限），如加性高斯白噪声（AWGN）信道。这个目标被证明是具有挑战性的，但并非不可能。 在过去的十年里，随着Turbo码的出现和低密度奇偶校验（LDPC）码的再次出现，它终于被实现，至少在许多有实际意义的情况下。

正如Bob McEliece在2004年香农讲座^[2]观察到的， 为实现这一目标所需要的非凡努力可能不会被未来的历史学家完全理解。McEliece幻想在在银河百科全书沿第166版下面几行加一段简历。

香农：公元1916年出生在地球上（索尔III），普遍被视为信息时代之父，在公元1948年他规定了信道容量的概念。几十年来，数学家和工程师们已在香农极限1％以内的数据速率可靠的通信的制定切实可行的办法...

本文的目的是在故事的细节随记忆消退之前，讲诉Shannon的挑战是如何被实现的，至少像它向我们展示的那样。

我们专注于AWGN信道，因为它是许多这些工作的目标。在第二节中，我们回顾AWAN通道中香农极限的各种定义。

在第三节中，我们讨论了代数的子编码，它支配信道编码领域的前几十年。我们将讨论这两个代数编码的成就，也是它为什么没有被证明是接近的方式香农极限原因。

在第四节，我们讨论的路线发展这是更直接香农的启发随机编码方法，它有时也被称为概率解码。包含卷积码，产品代码，级联码，的块码网格译码，最终能力接近码。

在第五节，我们讨论了用于带宽限制通道的编码，亦即点阵码和网格编码。

最后，在第六部分，我们讨论能力接近代码的发展，主要是Turbo码和LDPC码。

1. AWGN信道编码

对于AWGN信道编码方法的特征可能在于由两个简单的参数：其信噪比（SNR）和它的每秒每赫兹（B / S/赫兹）比特频谱效率。信噪比是平均信号功率与平均噪声功率的比率,无量纲量。一种在AWGN信道带宽W赫兹每秒发送R比特（b/s)编码方案的频谱效率为 b/s/Hz。

AWAN的编码方法通常以每秒2比特码元的速率将比特序列以速率R位/秒映射到的实码元序列。然后在一个带宽为W的AWGN通道该实码元序列通过脉冲调制幅度调制（PAM）或正交幅度调制（QAM）传输。由奈奎斯特理论，B（有时称为香农带宽^[3]）不能超过实际带宽W。如果，则频谱效率为。因此，我们说，离散时间编码方案的标称频谱效率是2r时，离散时间码速率以每位两个码元。实际的连续时间响应的频谱效率，当时，接近2r并以2r为上限。因此，对于离散时间码，我们经常会用来表示2r，隐含条件。

香农表明，在一个已知信噪比和带宽W Hz的AWAN信道中，可靠传输的码率上限由下式确定：。此外，如果一个随机产生的长码速率满足，则存在一个将实现高度可靠的传输，具有高概率的编码器和解码器

的解码方法（即低概率解码错误）。

同样地，香农的结果表明，光谱效率上限由下式确定：。或者给定一个光谱效，则合适的可靠传输的信噪比下限确定为：。因此，我们可以说，香农限速（即信道容量)是 b/s ，或等价频谱效率的香农极限是 b/s/Hz，或者对于一个给定的频谱效率，等效的香农极限为。注意，香农极限对信噪比是下限而不是一个上限。这些限制表明，我们定义了一个标准化的SNR

参数规范如下： 。

然后，对于任何可靠的编码方法，，香农极限（下限）在标准是1（0 dB为单位），独立于。此外，衡量误码能力，即是实际所用的信噪比和已知时由香农极限确定的信噪比在分贝（dB)上的差异，亦即。如果所需的光谱效率比1 b/s/Hz (所谓的功率限制体系），那么可以表明二进制代码可以在以香农极限不到0.2 dB的信噪比的情况下使用AWAN信道。另一方面，由于二进制编码方法离

散时间码速的上界由每个信号的确定，二进制编码方案的频谱效率被限制为b/s/Hz。所以如果所需的光谱功率比2 b/s/Hz（所谓的有限带宽体系）大，就必须采用多级编码。在实践中，编码方法对于功率受限和带宽受限体系的差别很大。有一个已经在功率受限体系传统使用的密切相关的归一化SNR参数为，定义为。对于给定的光谱效率，的下限由下式确定：。因此我们说香农极限（下限）在对的函数是。这个函数随单调减少，且当时接近ln2，因此我们说对任意，最终的香农极限（下限）是ln2(-1.59dB)。

可见，当时，，因此在严格的功率受限体系中和变为等价的参量。在功率受限体制中，我们会用传统的参量。然而，在带宽限制系统中，我们用，在这个体系中更加信息化。

3.代数编码

在以代数编码模式为主的信道编码领域的几十年来。事实上，在此期间大部分的编码教科书（包括彼得森[4]，的Berlekamp[5]，莱恩[6]，Peterson和威尔顿[7]，MacWilliams恒和斯隆[8]，以及Blahut[9]）涉及的只有代数编码理论。

代数编码理论主要运用二进制数域F2的（n,k,d)线性分组码。一个（n,k,d)线性分组码包含个二进制元组，称为码字，它具有组属性，即任何两个码字作模2加法运算得到另外一个码字。参数d表示汉明码任意两个不同码字之间的最小码距，即任意两个不同码字之间坐标差异的最小值。该理论概括了非二进制领域F2的（n,k,d)线性分组码。

代数编码理论的主要目标是使得对于给定的（n,k)的最小距离d最大化。这样做的目的是最大化纠错能力。通过二进制对称信道（BSC：一个具有统计独立的二进制错误的二进制输入二进制输出信道），最优解码规则是解码在所接收到的n元组最接近汉明距离的时候解码。有了这个规则，最小距离为d的码字可以纠正所有内或更少的信道错误（假设d是奇数）的图，但不能纠正包含一些更大数量错误的图。

代数编码理论的领域有过许多成功，我们将在下面简要调查。 然而，即使二进制代数分组码可用于对在AWGN信道，它们还没有被证明是在此通道上接近信道容量的方法，甚至在功率受限制度。事实上，甚至在在BSC，他们也不是接近信道容量的方法，。 接下来，我们将讨论一些导致这些失败的根本原因。

B.最早的代码：汉明，格雷和里德-缪勒

在文献中第一个出现的不平凡的代码是在香农最初的论文^[1]中提及的（7，4，3）汉明码。理查德·汉明，香农在贝尔实验室的一个同事，开发了一个无限的类单纠错（）二元线性码，对有参数（,,)。因此，当时，且，而（4.77dB)。然而，即使用最佳软判决解码，汉明码在AWAN信道上的实际编码增益从未超过3dB。

汉明码是完美的，从某种意义上说，海明半径关于每个2K的球码字包含2米二进制n元组，从而形成一二元n维空间完美（全部）分区。香农的论文在瑞士公布不久后，数学家马塞尔格雷发表了一篇半页纸的论文^[11]，用一种完美的（23,12,7）二进制线性码

D.BCH码和RS码

在20世纪60年代，研究信道编码是通过代数分组码开发为主，尤其是循环码。在代数编码范例使用有限场代数的结构设计为线性块有效的编码和纠错程序码操作上一个硬判决信道。重点在于构建一种保证最小距离d的代码，然后用代码的代数结构去设计一种有限距离纠错算法，这种算法的复杂度仅随d的低次幂增长。具体而言，目的是开发比RS 码性能更好，易于实现且灵活的代码。

循环代码是在n元组码字循环不变（弯绕）变化的代码。 这种代码最先在1957年^[16]。由尤金普兰奇调查，在韦斯利彼得森于1961年开创性的文献^[4]出版后成为研究的重点。循环码有良好的代数理论和基于循环移位寄存器相当简单的编译码程序。汉明码，格雷码和短化的RM码可以被放入环状形式。

在这一领域的“大爆炸”是在 1959年和1960年三篇独立文章里的BCH码和RS码。人们很快认识到，RS码是一类非二进制BCH码，或者该BCH码是RS码子码。

二进制BCH码是包含长度为的一大类循环纠错码，奇数最小码间距，维度。与给定长度的短化RM码相比，可供选择的代码更多，对于，给定最小间距，BCH码可有稍大一点的维度。然而，BCH码仍然不是足够好，虽然他们是最大类的二进制代数分组码，它们还没有被广泛应用于实践，只有循环冗余校验（CRC）码进行错误检测用于自动重复请求（ARQ）系统。

与此相反，该非二进制RS码已被证明是在实践中非常有用的（虽然在环状形式不一定）。一个（延长或缩短的）RS码，在有限域，，可以有内的任意块长度和以内的任意最小码间距（其中汉明距离根据元码定义），大小，符合一个所谓约束辛格尔顿的基本上限^[20]。在这个意义上说，RS码是最佳的。

RS与BCH码的一个重要特性是它们可以采用有限域算术算法通过代数解码被有效地解码。在一览对内容信息论的IEEE交易数据的表明发展这样的算法是20世纪60年代最活跃的研究领域之一。

早在1960年，彼得森就发现了一种复杂度数量级在上的纠错算法^[21]。在1968年，埃尔温·伯利坎普修正了一种复杂度数量级在上的纠错算法，这是由吉姆·梅西^[22]解释为一种寻找最短线性反馈移位寄存器的算法，它可以产生一定的序列。这钟Berlekamp - 梅西算法成为未来十年的标准。最后，事实表明这些算法可以直接延伸到纠正擦除和错误，甚至纠正软判决^[24]，[25]（次优，但在某些情况下，接近最优）。

事实上RS码固有的非二进制（最长二进制RS码具有长度3）可能使得它们在二进制信道的使用了造成了困难。如果元RS码简单地被表示为二进制元组发送在二进制信道，则一个单一的二进制错误可以引起整个2M-进制符号错误；这使得作为二进制纠错编码RS码稍逊BCH码。然而，在这种模式下的RS码是固有地良好突发纠错码，由于被集中在一个单一的m位突发的效果RS码符号是只有一个单一的符号错误。事实上，可以证明，RS码是有效的最佳二进制突发纠错码。

RS码的能力来纠正随机和突发错误使得它们特别适用于应用，如磁带和磁盘存储，其中在存储介质的缺陷，有时会引起突发性的错误。它们也可以用作在级联外部码编码方案，这将会在第四节-D来讨论。 由于这些原因，RS码可能是应用最广泛的代码。

B.20世纪60年代和70年代的卷积码

Elias的论文发表后不久，Wozencraft发现该卷积码的树结构允许通过顺序搜索算法解码^[51]。顺序解码成为麻省理工学院深入研究的课题，最终形成了快速的发展，存储免费法诺顺序解码算法^[52]和一个分析证明顺序解码系统的速率受计算截止速率R0^[53]的限制。

后来，吉姆·梅西提出了一种对卷积码非常简单的叫做阈解码^[54]的解码方法。梅西和开发加拉格尔证明突发纠错的变体门限解码非常适合于实际的纠错^[26]。法典公司成立于1962年各地梅西和代码界洛格（包括从未用在实际中实现的LDPC码）。20世纪60年代期间法典内置数百突发纠错的门限解码器，但业务未曾增长非常大，法典在1970年放弃了它。

1967年，安迪·维特为了证明指数误差范围^[55]，推出了有名的作为一个对于卷积码渐近最优解码算法，Viterbi算法（VA）。很快证明VA实际上是一个最佳译码算法。更重要的是，杰里海勒在喷气推进实验室（JPL）^[58][59]认识到相对短的卷积码由VA解码可能相当实用，例如64状态代码可以得到可观的实际编码增益，量级6分贝。

LINKABIT公司是由艾文·雅各布创立的，1968年莱恩·克兰罗克，和安迪·维特比为公司顾问。1969年，杰里海勒被聘为的Linkabit第一个全职员工。此后不久，的Linkabit

建立了一个原型64状态Viterbi算法解码器（“一个大怪物填充架^[60]”），可以以2 Mb/s运行。

20世纪70年代，经过的Linkabit的领导和喷气推进实验室，VA 成为了美国航空航天局深空通信标准的一部分。大约在1975年，Linkabit发现了一种相对便宜，灵活，快捷的VA芯片。VA很快开始被纳入许多其他通信应用。

同时，虽然卷积码与顺序解码是在太空中的第一个代码（用于1968年先锋9任务^[56]），一些连续原型解码系统已建成，连续解码从来没有在实践中起步。由时电子技术可以支持顺序解码，VA已成为一个更有吸引力的替代方案。然而，似乎在顺序的兴趣的电流回潮专业应用解码。

VII.结论

仅仅花了50年，但现在香农极限在AWGN信道通常接近为1 dB以内，同时受功率限制和带宽限制。类似的增益在其他重要应用正在实现，如无线信道以及因特网（分组消失）。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[148607]，资料为PDF文档或Word文档，PDF文档可免费转换为Word