信息论基础：有噪信道编码定理

1948年Shannon的著名论文“通信的数学理论”中给出了下述有关信息传输的最基本的定理——有噪信道编码定理，即Shannon第二编码定理。该定理是信息论的基本定理之一。

定理6.2（有噪信道编码正定理） 设离散无记忆信道[X，P（y|x），Y]，其信道容量为C，当信息传输率R＜C时，在码长n足够大的情况下，总可以在输入符号集Xⁿ中找到M=2^nR个码字组成的一组码[n，2^nR]和相应的译码规则，使平均错误译码概率任意小（P_E→0）。

定理6.3（有噪信道编码逆定理） 设离散无记忆信道[X，P（y|x），Y]，其信道容量为C，当信息传输率R＞C时，无论码长n多长，在输入符号集Xⁿ中也找不到一种编码[n，2^nR]（码字数M=2^nR），使平均错误译码概率任意小。

定理6.2是Shannon第二编码定理的正定理。该定理表明，当R＜C时，只要码长n足够长，就一定至少存在一种编码方法，使平均错误译码概率任意小，且信息传输率R接近信道容量C。这从理论上证明，在有噪信道中可以同时进行有效地和可靠地传输信息；并隐含地说明，R越接近于C，码长n就越长，编码的复杂度也就越大，代价越高。

定理6.3是Shannon第二编码定理的逆定理。该定理表明，当R＞C时，无论采用多么复杂的编码，都不可能实现使平均错误译码概率任意小的信息传输。也就是从理论上证明，在有噪信道中不可能以高于信道容量的速率可靠地传输信息。

综合定理6.2和定理6.3可知，在任何信道中，信道容量是可靠传输的最大信息传输率。

Shannon第二编码定理对离散无记忆信道、连续信道和有记忆信道同样成立。有关定理的一般证明请参见文献[4]，以及定理在有记忆和连续信道中的推广等内容可以参考有关书籍。

对Shannon第二编码定理（有噪信道编码定理）的几点认识如下：

1）有噪信道编码定理纠正了人们认为提高可靠性必须降低有效性的传统观念，指明了高效（接近容量）和高可靠（译码差错任意小）的编码是存在的，为信道编码理论和技术的研究指明了方向。定理给出了信道编码的理想极限性能，是信道编码理论的基础。(www.xing528.com)

2）定理仅指出编码的存在性，并未给出编码的具体方法。由于证明过程采用的是随机编码，并没有给出（也不可能给出）构造具体的信道编码的方法，寻找最佳信道编码是很困难的。其原因是：

①要求编码序列足够长，加大了编译码延时和所需要的存储量，使编译码器难以实现。

②码集合的总数有2^nM种（每选择一个码字有2ⁿ种，每个码集合有M个码字，当然其中包含不少“坏”码），数量巨大，难于寻找好码。

③采用随机编码，不仅难于分析，而且难于采用有效的编、译码算法。

Shannon第二编码定理也只是一个存在定理，它说明错误概率趋于零的好码是存在的，但是没有说明如何构造这个好码。尽管如此，Shannon第二编码定理仍然具有重要的理论意义和实践指导作用，它可以指导各种通信系统的设计，有助于评价各种通信系统及编码效率。

从Shannon第一编码定理和Shannon第二编码定理可以看出，要做到有效和可靠地传输信息，可以将编码分成信源编码和信道编码两部分。首先，通过信源编码，用尽可能少的信道符号来表达信源，也就是对信源数据用最有效的方式表达，尽可能减少编码后数据的冗余度；然后，对信源编码后的数据设计信道编码，也就是适当增加一些冗余度以纠正和克服信道中干扰引起的错误。这两部分是分别独立考虑的。

这种分两部分编码的方法在实际通信系统中有着重要的意义。近代大多数通信系统都是数字通信系统，与模拟通信系统相比有着许多优点。在实际数字通信系统中，信道常常是共用的数字信道（二元信道），而无论语音、音乐、图像和数据都用同一通信信道来传输。因此，可以将语音和图像先数字化，再对数字化的语音和图像等信源进行不同的信源编码，针对各自信源的不同特点用不同的数据压缩方法。而对于共同的数字信道，输入端只是二元序列，所以信道编码只需针对信道特性进行，纠正信道中带来的错误，这样可以大大降低通信系统设计的复杂度。可以证明，这种分两步编码处理的方法与一步编码处理方法是一样有效的。

总结起来，Shannon信息论的三个基本概念——信源熵、信道容量和信息率失真函数都是临界值，是从理论上衡量通信能否满足要求的重要极限。对应这三个基本概念的是Shannon的三个基本编码定理——无失真信源编码定理、信道编码定理和限失真信源编码定理，分别又称为Shannon第一、第二和第三编码定理，或Shannon第一、第二和第三极限定理。这是三个理想编码的存在性定理，它们并不能直接得出相应的编码方法，但是对编码具有指导意义。