噪音信道编码定理

维基百科，自由的百科全书

在信息论里，噪音信道编码定理指出，尽管噪音会zh-cn:干扰;zh-tw:干擾通信信道，但还是有可能性在一个指定的最大信道传输率的前提下，准确无误地传送数据信息。这个令人惊讶的结果，有时候被称为信息原理基本定理，也叫做香农定理，是由克劳德·艾尔伍德·香农于1948年首次提出。

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

[编辑] 总述

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

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

$R < C \,$

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

反过来同样重要。如果

$R > C \,$

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

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

[编辑] 数学描述

定理（香农，1948年）：

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

$C = \max_{P_X} \,I(X;Y)$

有以下特点。所有ε > 0并且R < C，任意大的N，存在着长度为N速度≥ R的编码和相应解码算法，这样，最大可能传输错误率≤ ε。

2. 如果误码率p_b是可以接受的，速度提高到R(p_b)是可以实现的，

$R(p_b) = \frac{C}{1-H_2(p_b)} .$

H 2 (p b)

是一个二元熵函数。

$H_2(p_b)=- \left[ p_b \log {p_b} + (1-p_b) \log ({1-p_b}) \right]$

3对所有的p_b，速度大于R(p_b)是不可能实现的。

(MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11)

[编辑] 证明框架

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

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

[编辑] 离散无记忆信道的可实现性

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

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

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

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

$2^{-n(H(X)+\epsilon)} \le p(X_1^n) \le 2^{-n(H(X) - \epsilon)}$

$2^{-n(H(Y) + \epsilon)} \le p(Y_1^n) \le 2^{-n(H(Y)-\epsilon)}$

${2^{-n(H(X,Y) + \epsilon)}}\le p(X_1^n, Y_1^n) \le 2^{-n(H(X,Y) -\epsilon)} \}$

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

步骤

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

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

没有找到和接收到的Y序列相匹配的X序列。
接收到的Y序列解码成一个错误的X序列。

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

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

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

定义： $E_i = \{(X_1^n(i), Y_1^n) \in A_\epsilon^{(n)}\}, i = 1, 2, ..., 2^{nR}$

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

$P(error) = P(error|W=1) \le P(E_1^c) + \sum_{i=2}^{2^{nR}}P(E_i)$

$\le \epsilon + 2^{-n(I(X;Y)-R-3\epsilon)}$

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

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

[编辑] 弱逆离散无记忆信道

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

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

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

[编辑] 强逆离散无记忆信道

强逆定理证明由Wolfowitz于1957年提出。^[1], 证明如下，

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

一些有穷的正常数 $A$ 。当 $n$ 变为无穷大的时候，弱逆证明错误的可能性不可能变成0，强逆证明错误以指数方式趋向于1。因此， $C$ 是可靠连接和不可靠连接的临界点。

[编辑] 变化的无记忆信道的信道编码定理

我们假设信道是无记忆的，但是随着时间的变化，传输的可靠性是变化的。发送端和接收端一样工作正常。这样信道容量如下 $C=\lim\;\inf\;\;\max_{p^(X_1),p^(X_2),...}\frac{1}{n}\sum_{i=1}^nI(X_i;Y_i)$ 统计每一个不同的信道，得到容量的最大值，那样 $C=\lim\;\inf\;\;\frac{1}{n}\sum_{i=1}^n C_i$ 信道i的容量为 $C i$ 。

[编辑] 简略证明

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

当 $\frac{1}{n}\sum_{i=1}^n C_i$ 不逆时，极限开始起作用。

[编辑] 参考

↑ 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 - 介绍关于香农定理的一些基本知识，包括两种证明方式，也介绍了现在流行的编码方式。

来自“http://zh.wikipedia.org../../../%E5%99%AA/%E9%9F%B3/%E4%BF%A1/%E5%99%AA%E9%9F%B3%E4%BF%A1%E9%81%93%E7%BC%96%E7%A0%81%E5%AE%9A%E7%90%86.html”

页面分类: 电信 | 通信技术 | 電子學 | 通信