有噪信道编码定理

在信息论里，有噪信道编码定理指出，尽管噪声会干扰通信信道，但还是有可能在信息传输速率小于信道容量的前提下，以任意低的错误概率传送数据信息。这个令人惊讶的结果，有时候被称为信息原理基本定理，也叫做香农-哈特利定理或香农定理，是由克劳德·艾尔伍德·香农于1948年首次提出。

通信信道的信道容量或香农限制是指在指定的噪音标准下，信道理论上的最大传输率。

总述

根据香农1948年的陈述，本定理描述了在不同级别的噪音干扰和数据损坏情况下，错误监测和纠正可能达到的最高效率。定理没有指出如何构造错误监测的模型，只是告诉大家有可能达到的最佳效果。香农定理可以广泛应用在通信和数据存储领域。本定理是现代信息论的基础理论。香农只是提出了证明的大概提纲。1954年，艾米尔·范斯坦第一个提出了严密的论证。

香农定理假设一个有噪音的信道，信道容量为C，信息以速度R传送，如果

${\displaystyle R<C\,}$

那么就存在一种编码技术使接收端收到的错误达到任意小的数值。这意味着理论上，有可能无错误地传送信息直到达到速度限制C。

反过来同样重要。如果

${\displaystyle R>C\,}$

那么想达到任意小的错误率是不可能实现的。因此，在传送速度超过信道容量的时候，可靠传输信息是不能被保证的。定理并没有指出在什么特殊情况下速度和容量相等。

简单的流程如“重复发送数据3遍，用一个投票系统在数据不一样的时候选择3个里面相同的那两个的值”是低效的错误纠正的方式，不能保证数据块能完全没有错误地传送。先进一些的技术如里德-所罗门码编码技术和更现代一些的Turbo码、低密度奇偶检查码等编码技术更逼近香农限制，但是计算复杂度很高。

数学描述

定理（香农，1948年）：

1.一个离散无记忆信道的信道容量

${\displaystyle C=\max _{P_{X}}\,I(X;Y)}$

具有以下特点：任给ε > 0, R < C，存在着长度为N，信息传输速率小于等于R的编码和相应解码算法，使得最大可能传输错误率≤ ε。

2.如果允许误码率p_b，那么存在一种编码方式，使得信息传输速率速度可以提高到R(p_b)，其中

${\displaystyle R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.}$

而${\displaystyle H_{2}(p_{b})}$是一个二元熵函数，定义为

${\displaystyle H_{2}(p_{b})=-\left[p_{b}\log {p_{b}}+(1-p_{b})\log({1-p_{b}})\right]}$

3.给定${\displaystyle p_{b}}$，不存在速度大于R(p_b)的编码方式，使得最大可能传输错误率小于${\displaystyle p_{b}}$。（MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11）

证明框架

和信息论的其它主要结果一样，噪音信道编码定理包括一个可以实现的结果和相应的相反的结果。这两个组成部分中间有一个界线。在本案例中，可以通过有噪音的信道的可能速度的集合和相应边界显示出这是一个紧密边界。

下面的证明框架只是已有的许多种不同证明方法中的一种而已。

离散无记忆信道的可实现性

下面这个可实现性的证明是使用渐近等同分割特性（Asymptotic equipartition property（英语：Asymptotic equipartition property） - AEP）方法。另一种信息论常用证明方法是错误列举法（Error Exponent（英语：Error Exponent））。

两种证明方法都使用随机编码参数来构造信道。这样的目的是减少计算的复杂度，同时仍旧可以证明在速度低于信道容量的时候，存在误码率在可接受范围甚至是接近于理想的无失真的编码方式。

采用AEP相关的参数，一个指定的信道，长度为n的源字符串${\displaystyle X_{1}^{n}}$，和长度为n的信道输出的字符串${\displaystyle Y_{1}^{n}}$，我们可以定义一个以下匹配序列集合：

${\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}$

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}}$

${\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}}$

${\displaystyle {2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}}$

我们可以说两个序列${\displaystyle {X_{1}^{n}}}$和${\displaystyle Y_{1}^{n}}$是匹配序列，如果它们是基于上述定义的匹配序列集合。

步骤

1. 在随机编码参数的方法上，我们可能的范围Q里面随机产生${\displaystyle 2^{nR}}$长度为n的编码串。
2. 这个编码和发送端与接收端有关。同样假设双方知道传输信道使用的传输矩阵${\displaystyle p(y|x)}$。
3. 在同样的范围里选择消息W，因此，${\displaystyle \operatorname {Pr} (W=w)=2^{-nR},w=1,2,...,2^{nR}}$。
4. 消息W通过信道传送。
5. 接收端收到了一个基于${\displaystyle P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))}$的序列。
6. 将这些编码串通过信道发送，我们收到了${\displaystyle Y_{1}^{n}}$，如果在编码表里存在和Y匹配的一个序列，该序列并被解码成为源编码序列，如果没有找到，就报告一个错误。如果解码出的序列和原来的序列不一样，同样报告一个错误。

这个流程产生的错误可以分成两个部分：

1. 没有找到和接收到的Y序列相匹配（或在允许的误码率条件下）的X序列。
2. 接收到的Y序列解码成一个错误的X序列。

• 考虑到构造码时的随机性，我们可以假设平均的错误的产生率和码发送的序列没有关系。因此，我们假设W = 1。

• 从匹配AEP方法考虑，我们知道随着n的逐渐增加，没有对应的X的可能性慢慢降为0。我们可以用${\displaystyle \epsilon }$来标记这个错误的可能性。

• 同样从匹配AEP方法考虑，我们知道一个指定的${\displaystyle X_{1}^{n(i)}}$和${\displaystyle Y_{1}^{n}}$，作为W = 1的结果是匹配序列的可能性为${\displaystyle \leq 2^{-n(I(X;Y)-3\epsilon )}}$。

定义：${\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\epsilon }^{(n)}\},i=1,2,...,2^{nR}}$

作为消息1发送出去，消息i作为匹配的消息接收到的结果。

${\displaystyle {\begin{aligned}P({\text{error}})&{}=P({\text{error}}|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})\\&{}\leq P(E_{1}^{c})+(2^{nR}-1)2^{-n(I(X;Y)-3\varepsilon )}\\&{}\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}.\end{aligned}}}$

我们可以发现如果信道${\displaystyle R<I(X;Y)}$，n变为无穷大，错误的可能性将降为0。

最后，假设平均的编码方式是“好”的话，我们知道存在一个编码方式的效率比平均的值要好，因此可以满足我们在有噪音的信道低误码率的要求。

弱逆离散无记忆信道

假设一种编码有${\displaystyle 2^{nR}}$个编码词语。W假设为在这个集合上的一个索引。设${\displaystyle X^{n}}$和${\displaystyle Y^{n}}$分别为编码词和接收到的词。

1. ${\displaystyle nR=H(W)=H(W|Y^{n})+I(W;Y^{n})\;}$使用同样的熵和同样的信息
2. ${\displaystyle \leq H(W|Y^{n})+I(X^{n}(W);Y^{n})}$X是W的一个函数
3. ${\displaystyle \leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})}$使用Fano不等式
4. ${\displaystyle \leq 1+P_{e}^{(n)}nR+nC}$信道容量设为最大化

这些步骤的结果是${\displaystyle P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}}$。当块的长度变为无穷大，如果R比C大，我们得到${\displaystyle P_{e}^{(n)}}$不可能降到0。只有在R比C小的情况下，我们可以得到任意低的误码率。

强逆离散无记忆信道

强逆定理证明由Wolfowitz于1957年提出。^[1]，证明归结于证明如下不等式，

${\displaystyle P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-n(R-C)}}$

其中${\displaystyle A}$为有限的正常数。当${\displaystyle n}$变为无穷大的时候，弱逆定理证明错误的可能性不可能变成0，而强逆定理证明了错误以指数方式趋向于1。因此，${\displaystyle C}$是可靠连接和不可靠连接的临界点。

时变无记忆信道的信道编码定理

我们假设信道是无记忆的，但是随着时间的变化，传输的可靠性是变化的。发送端和接收端一样工作正常。这样信道容量如下

${\displaystyle C=\liminf \max _{p^{X_{1}},p^{X_{2}},...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i})}$。

针对每个不同的信道，计算出取得该信道容量似的分布，以求得上式中的最大值，这样 ${\displaystyle C=\liminf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$ ，信道i的容量为${\displaystyle C_{i}}$。

简略证明

证明方法和上面信道编码定理几乎一样。在指定的信道里面，每一个符号的选择是随机的，编码方式也是随机的，采用渐近等同分割特性（AEP）方法来定义变化的无记忆信道的参数集。

当${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$不收敛时，下极限开始起作用。

参考文献

引用

1. Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley and Sons, 1968. ISBN 0-471-29048-3

来源

• 克劳德·艾尔伍德·香农：《通信的数学理论 （页面存档备份，存于互联网档案馆）》Urbana, IL:University of Illinois Press, 1949（reprinted 1998）。
• 艾米尔·范斯坦：《信息论的一个新的基础定理》IEEE Transactions on Information Theory, 4(4):2-22, 1954.
• 罗卜特·梵高：《信息传输，通信的一个统计理论》Cambridge, Mass., M.I.T. Press, 1961. ISBN 0-262-06001-9
• 雅各布·Wolfowitz：《面对误码的信息编码》Illinois J. Math., vol. 1, pp. 591-606, 1957.
• David J. C. MacKay.《信息论推理，算法演绎》Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Thomas Cover, Joy Thomas，《信息论要素》。New York, NY:John Wiley & Sons, Inc., 1991. ISBN 0-471-06259-6

外部链接

• 香农定律 （页面存档备份，存于互联网档案馆）
• 在线书：信息论推理，算法演绎 （页面存档备份，存于互联网档案馆），by David MacKay（英语：David MacKay） - 介绍关于香农定理的一些基本知识，包括两种证明方式，也介绍了现在流行的编码方式。

参见

• 电信主题
• 数学主题

• 通信、信道、信道容量、香农极限
• 信息论、克劳德·香农