信息论，从名字而言似乎是研究信息的理论。
我们通常会认为，信息是一个抽象的概念，那么如何进行研究呢？事实上，信息论所说的信息并非是我们通常所说的抽象的信息，它应理解为专门指“不确定性”的信息。例如说，如果现在知道“明天必然下雨”这一事件，那么这通常来说就蕴含了有用的信息——例如它提醒我们明天应该带伞、回收户外晒太阳的东西之类，但是从信息论的角度，它没有“信息”，更具体一点，没有不确定性的信息，因为这是个必然事件。再如，扔一个色子，考虑向上的面的点数，其不确定性“信息”由6种等可能性（1~6）给出，而如果此时将色子的各面点数各自取10次方，那么从取值的角度，不确定性似乎增大了很多，然而从信息论的角度，其不确定性“信息”仍由6种等可能性给出，所以“信息”不变。简单来说，信息论研究的“信息”仅包括由事件发生概率导致的不确定性信息，而事件的内容信息等等则不在考虑范围之列。
本文主要内容是信息论的基本内核，只概览信息论最核心的部分，内容精简，不适于用来当作教程进行学习。首先，介绍了信息论的基本工具，如熵、互信息，罗列了一些它们的基本性质，例如一些等式和不等式；然后，介绍了信源编码，给出了最小期望长度与熵的联系；最后，介绍了信道编码，叙述了信道编码定理和证明。附录部分补充了放在现代数学框架下，熵等等信息论中的量的更一般定义。
事实上，本文还有很多信息论的重要内容没有覆盖到。例如，信源编码的Kraft不等式、一些重要算法如Huffman码、通用信源编码(universal source coding)，信道编码的率失真理论(rate distortion theory)，统计中的一些信息论应用。如果要扩写本文，这些内容是最先被考虑的。
基本工具
熵
信息论中，衡量上文所说的不确定性的“信息”的一个基本的量叫做熵(entropy)，也可叫Shannon熵。
这里先稍微推导一下它的形式，我们要衡量的是随机变量\mathrm x\sim p(x)的不确定性信息。而且\mathrm x考虑的仅是离散的取值于\mathcal X=\{x _ 1,\dots,x _ m\}的随机变量，以突出核心。首先按前面所说，熵H应只是p _ 1,\dots,p _ m的函数，其中p _ i=P(\mathrm x=x _ i)，于是H写为H(p _ 1,\dots,p _ m)。然后，我们希望H应具有的重要性质，应包含“可加性”，这是说，如果另有一个与\mathrm x独立的随机变量\mathrm y，从\mathrm x,\mathrm y得到的不确定性信息应等于分别从\mathrm x和\mathrm y得到的不确定性信息之和。此时由独立性有p(x _ i,y _ j)=p(x _ i)p(y _ j)，考虑极端情况：\mathrm x,\mathrm y都是常数，那么我们希望有H(p(x _ 1,y _ 1),\mathbf 0,\dots,\mathbf 0)=H(p^{\mathrm x} _ 1,0,\dots,0)+H(p^{\mathrm y} _ 1,0,\dots,0)，如果熟悉函数方程那么很自然就看出，一种能让乘积性质变成加和性质的函数就是对数函数。由p(x _ i,y _ j)=p(x _ i)p(y _ j)得到\log p(x _ 1,y _ 1)=\log p(x _ 1)+\log p(y _ 1)，这启发我们H(p _ 1,\dots,p _ m)可能能被\log p _ 1,\dots,\log p _ m简单地表示，简单的方案就是取个平均，即H(p _ 1,\dots,p _ m)=kE _ {\mathrm x\sim p}(\log p _ i)，系数k为负数，因为我们希望H作为不确定性信息的衡量应为正数。实际发现这种形式的定义恰符合很多我们对信息这一抽象概念的想象。应用最广泛的是以2为底，-1为系数，一个单位叫做一个位(bit)；以\mathrm e为底也比较常用，单位为bat。以下以2为底，熵就写成了：
H(p _ 1,\dots,p _ m)=-\sum _ {i=1}^m p _ i\log _ 2 p _ i=-E(\log _ 2 p).
实际中\log _ 2会简写为\log；另一方面底数不同时，由换底公式知得到的熵仅仅是一个系数的不同，于是不写底数也会有“保留底数和系数k自由”的额外意味。
熵更严格的推导是基于公理。有数种公理定义方式，下面给出一种。推导用到的是满足f(mn)=f(m)+f(n)的连续函数只有对数函数这一结论。
熵的一种公理化定义：存在唯一的一列函数H _ m(p _ 1,\dots,p _ m)满足如下性质，其显式表达式也可写出（为上文的形式）：
- 连续性：H _ 2(p,1-p)是p的连续函数；
- 可加性：H _ m(p _ 1,\dots,p _ m)=H _ {m-1}(p _ 1+p _ 2,p _ 3,\dots,p _ m)+(p _ 1+p _ 2)H _ 2(\frac{p _ 1}{p _ 1+p _ 2},\frac{p _ 2}{p _ 1+p _ 2})；
- 归一性：H _ 2(\frac12,\frac12)=1。
条件熵，相对熵，互信息
然后是熵的一些衍生定义。这一节仅是列举定义及其性质。
给定\mathrm x，定义\mathrm y的条件熵为
H(\mathrm y|\mathrm x)=E(-\log p(\mathrm y|\mathrm x))=\sum _ {x\in\mathcal X}p(x)H(\mathrm y\operatorname{|}\mathrm x\operatorname=x).
相对熵(relative entropy)，或称KL散度(Kullback–Leibler divergence)，给定两分布p(x),q(x)时定义为
D _ {\mathrm{KL}}(p\operatorname\|q)=-\sum _ {x}p(x)\log\frac{q(x)}{p(x)}.其中求和是对p(x),q(x)的支撑集(support)进行，就是说只考虑p(x)>0和q(x)>0的项。
随机变量\mathrm x,\mathrm y间的互信息(mutual information)定义为
I(\mathrm x;\mathrm y)=D _ {\mathrm {KL}}(p(x,y)\operatorname\|p(x)p(y)).
KL散度和互信息也有条件版。给定\mathrm z，则\mathrm x,\mathrm y间的条件互信息为
\begin{aligned}
I(\mathrm x;\mathrm y\operatorname|\mathrm z)&=E _ {\mathrm z}[D _ {\mathrm {KL}}(p(\mathrm x,\mathrm y|\mathrm z)\operatorname\|p(\mathrm x|\mathrm z)p(y|\mathrm z))]\\
&=\sum _ {z}p(z)\sum _ {x,y}-p(x,y\operatorname|z)\log\frac{p(x|z)p(y|z)}{p(x,y\operatorname|z)}\\
&=E\Big[\log\frac{p(\mathrm x|\mathrm z)p(\mathrm y|\mathrm z)}{p(\mathrm x,\mathrm y\operatorname|\mathrm z)}\Big].
\end{aligned}
对于p(x,y),q(x,y)，给定\mathrm x的分布p _ {\mathrm x}时，p,q间的条件KL散度为
D _ {\mathrm {KL}}(p _ {\mathrm y|\mathrm x}\|q _ {\mathrm y|\mathrm x}\operatorname|p _ \mathrm x)=E _ {\mathrm x}[D _ {\mathrm {KL}}(p(y|\mathrm x)\operatorname\|q(y|\mathrm x))].
这些量有如下基本的等式性质：
\begin{aligned}
H(\mathrm x,\mathrm y)&=H(\mathrm x)+H(\mathrm y|\mathrm x),\\
I(\mathrm x;\mathrm y)&=I(\mathrm y;\mathrm x)\\
&=H(\mathrm x)-H(\mathrm x|\mathrm y)=H(\mathrm y)-H(\mathrm y|\mathrm x)\\
&=H(\mathrm x)+H(\mathrm y)-H(\mathrm x,\mathrm y),\\
I(\mathrm x _ 1,\mathrm x _ 2;\, \mathrm y)&=I(\mathrm x _ 2;\mathrm y)+I(\mathrm x _ 2;\mathrm y\operatorname|\mathrm x _ 1), \\
I(\mathrm x,\mathrm x)&=H(\mathrm x).
\end{aligned}
及如下基本的不等性质：
\begin{gathered}
D _ {\mathrm {KL}}(p\operatorname \|q)\geqslant0,\\
I(\mathrm x;\mathrm y)\geqslant0,\\
H(\mathrm x|\mathrm y)\leqslant H(\mathrm x),\\
H(\mathrm x _ 1,\dots,\mathrm x _ n)\leqslant H(\mathrm x _ 1)+\dots+H(\mathrm x _ n),\\
H(\mathrm x)\leqslant\log |\mathcal X|,
\end{gathered}
设有Markov链\mathrm x\to\mathrm y\to\mathrm z，那么还有
\begin{gathered}
I(\mathrm x;\mathrm y)\geqslant I(\mathrm x;\mathrm z),\\
I(\mathrm x;\mathrm y)\geqslant I(\mathrm x;f(\mathrm y)),\\
I(\mathrm x;\mathrm y)\geqslant I(\mathrm x;\mathrm y\operatorname|\mathrm z),\\
I(\mathrm x;\mathrm z\operatorname|\mathrm y)=0.
\end{gathered}
如果此\mathrm z是\mathrm x的一个估计，考察估计错误的概率p _ e=P(\mathrm x\neq\mathrm z)，那么有Fano不等式
\begin{aligned}
&1+p _ e\log|\mathcal X|\geqslant H _ 2(p _ e)+p _ e\log|\mathcal X|\geqslant H(\mathrm x|\mathrm z)\geqslant H(\mathrm x|\mathrm y),\\
& H _ 2(P(\mathrm x\neq \mathrm y))+P(\mathrm x\neq \mathrm y)\log|\mathcal X|\geqslant H(\mathrm x|\mathrm y) \\
\implies{}&p _ e\geqslant\frac{H(\mathrm x|\mathrm y)-1}{\log|\mathcal X|}.
\end{aligned}
凸性：
- D _ {\mathrm {KL}}(p\operatorname\|q)是(p,q)的凸函数；
- -H(p)是p的凸函数；
- 设\mathrm x,\mathrm y\sim p _ {\mathrm x}(x)p _ {\mathrm y|\mathrm x}(y|x)，则当p _ {\mathrm x}(x)不变时，I(\mathrm x;\mathrm y)是p _ {\mathrm y|\mathrm x}的凸函数；当p _ {\mathrm y|\mathrm x}(y|x)不变时，-I(\mathrm x;\mathrm y)是p _ {\mathrm x}的凸函数。
熵率
最后是一个随机过程X=\{\mathrm x _ i\} _ {i\in\mathbb N}的熵，称为“熵率”(entropy rate)，定义为
H(X):=\lim _ {n\to\infty}\frac1nH(\mathrm x _ 1,\dots,\mathrm x _ n).
仅定义于极限存在时。对于平稳随机过程，极限必存在，且有如下等价定义：
H(X)=\lim _ {n\to\infty}H(\mathrm x _ n\operatorname|\mathrm x _ 1,\dots,\mathrm x _ {n-1}).
信源编码
信源编码
信源编码(source coding)是信息论的核心内容之一。
考察一个随机变量\mathrm x\sim p(x)，现在需要用一个字母表大小仅有D的编码C将其编码：x\mapsto C(x)，例如只用0和1编码所有字符。一个自然的做法是将|\mathcal X|个x按D进制从小到大的数字进行等长编码，这样每个x长度\lceil\log _ D |\mathcal X|\rceil，但事实上这是不高效的。
一个好的编码C应该是什么样？首先，不同的字符x应分配不同的码，否则解码无法区分。其次，我们希望编码应是“唯一可解的”(uniquely decodable)，就是说将任意一列x _ 1,\dots,x _ n进行编码，那么不应有一列其它的x' _ 1,\dots ,x' _ {n'}使其编码和C(x _ 1x _ 2,\dots x _ n)一样，否则解码也是无法区分。为了更高效地解码，我们会希望这编码最好是前缀码(prefix code, instantaneous code)，就是说任何C(x)都不会是另一个C(x')的前缀。这样很容易就可以判断一列编码在哪里停顿分割，不用再看后面的码是什么就能做到。前缀码还意味着我们不需要另外设计一个停顿符号，它是“自停顿的”，而当n足够大时，使用停顿符编码一列x _ 1,\dots,x _ n将需要编码n-1个额外的停顿符，效率显然是十分低下的。（唯一可解但是不是前缀码的编码是存在的，例如\mathcal X=\{1,2,3,4\}，分别编码为10,00,11,110，可以证明一列编码C(x _ 1\cdots x _ n)必可解码x _ 1：如果编码前两位是10或00则x _ 1为1或2，如果是11，则再继续看其后面接多少个连续的0，偶数个0表示x _ 1=3，奇数个表示x _ 1=4。）此外，编码后长度应该尽可能小，以求最高效地表示原信息。如果C(x)的长度为l(x)，那么这一编码过程期望上的编码长度就是E(l(\mathrm x))=\sum p(x)l(x)。显然应该对更常见的x分配更短的码，少见的分配更长的码。
那么，一个最好的编码最短能到多少？答案是熵。这就是如下定理：
定理：一个平均长度最优的唯一可解编码C的平均长度L^\ast满足
H _ D(\mathrm x)\leqslant L^\ast< H _ D(\mathrm x)+1.
如果信息源是一随机过程X=\{\mathrm x _ n\} _ {n\in\mathbb N}，要对其进行编码，若要编码长度为n的\mathrm x _ 1,\dots,\mathrm x _ n，那么H _ D(\mathrm x _ 1,\dots,\mathrm x _ n)\leqslant E[l(C(\mathrm x _ 1,\dots,\mathrm x _ n))] <H _ D(\mathrm x _ 1,\dots,\mathrm x _ n)+1（将其是做一个整体来编码，应用上述定理），于是有下面的定理：
定理：最小的每个字符的期望编码长度满足不等式
\frac{1}{n}H _ D(\mathrm x _ 1,\dots,\mathrm x _ n)\leqslant \frac1nE[l(C(\mathrm x _ 1,\dots,\mathrm x _ n))]<\frac1nH _ D(\mathrm x _ 1,\dots,\mathrm x _ n)+\frac1n.
进而，若这个随机过程是平稳的，那么最小长度趋于随机过程的熵率：
L^\ast _ n\to H(X),\quad n\to\infty.
信道编码
信道编码
信道编码(channel coding)也是信息论的核心内容之一。
考虑一个通信过程，发送端将一列x _ 1,\dots,x _ n发送到接收端，然后考虑通信干扰的存在，接收端接收到的是受干扰的讯息，于是接收端只能尽量正确识别出原来的x _ 1,\dots,x _ n。这个通信过程一般用一个信道(channel)来建模。我们考虑这个信道的“容量”问题：这个信道最多能通信多少种不同的\boldsymbol x=(x _ 1,\dots,x _ n)使得接收端能几乎不混淆地识别出它们？假设输入\boldsymbol x经过信道后变成了输出\boldsymbol y\in\mathcal Y^n，输出就通过解码器(decoder)进行恢复。如果有M个不同的\boldsymbol x能做到这点，那么就意味着：一次发送长度为n的输入时，我们能通过这个信道发送M种讯息并很好地恢复。
下面从形式上来描述，设w\in\{1,\dots,M\}，通过编码器(encoder)处理成这个信道的字符\boldsymbol x=\boldsymbol x(w)\in\mathcal X^n，然后经过信道变成输出\mathbf y\in\mathcal Y^n，解码器输出原讯息的估计\hat{w}=\hat w(\mathbf y)：
\xrightarrow[\text{Message}]{\mathrm w}\text{Encoder}\xrightarrow{\mathbf x}\text{Channel}\xrightarrow{\mathbf y}\text{Decoder}\xrightarrow[\text{Estimate}]{\widehat{\mathrm w}}
显然，一个信道的性质由概率函数p(\mathbf y|\mathbf x)来决定。如果输出的分布仅由当前的输入确定，那么这个信道就叫做无记忆的(memoryless)，此即p(\mathrm y _ k\operatorname| \mathbf x _ {1:k},\mathbf y _ {1:k-1})=p(\mathrm y _ k|\mathrm x _ k)，这里下标1:k表示1到k。此外，不特别说明时一般还会假定信道无反馈，这样p(\mathrm x _ k|\mathbf x _ {1:k-1},\mathbf y _ {1:k-1})=p(\mathrm x _ k|\mathbf x _ {1:k-1})。
我们希望解码时错误的概率越小越好。显然n越大，或者可能要编码的讯息w越少，解码时错误的概率越小，但这不是高效的做法。如果所有的编码如果只用0,1来编码，那么至少要用\log M个位来编码所有可能的讯息，现在这个信道用了n个位，可以看作有\log M个编码位和其余用来抗干扰的位，这样看的话码率 R:=\log M\operatorname/n应该越大越好，意味着编码的冗余信息越少。
由于有M种讯息，我们需要在\mathcal X^n中找到M个\boldsymbol x，每个对应于\mathcal Y^n中的一个“解码区域”（两两不交）D，如果这M个都有P(D|\boldsymbol x)充分大，那么不难发现可以利用这点来通信。将w\in\{1,\dots,M\}逐一编码为这M个\boldsymbol x，输入经过信道后如果输出\boldsymbol y在某个\boldsymbol x对应的解码区D内，那么就解码为对应的\boldsymbol x对应的w。
对于每个讯息w，我们要控制每个讯息w的错误概率P(w\neq\hat{\mathrm w})，具体地说，应该是P(\hat{\mathbf x}\neq \boldsymbol x(w))。这M个错误概率中最大者为\max _ w P(w\neq\hat {\mathrm w})。
对于一个给定的码率R，如果总存在一列编码、解码函数及讯息\{\mathbf x _ {1:n}(\cdot),\hat w _ n(\cdot),\{1,\dots,\lceil2^{nR}\rceil\}\} _ {n\in\mathbb N}，使得当n\to\infty时，这个最大错误概率\max _ w P(w\neq\hat {\mathrm w})\to0，那么这个码率叫做可行的(achievable)。如果有一列\{R _ n\}以R为极限，\{\mathbf x _ {1:n}(\cdot),\hat w _ n(\cdot),\{1,\dots,\lceil2^{nR _ n}\rceil\}\} _ {n\in\mathbb N}在n\to\infty时最大错误概率趋于0，那么也叫R是可行的。
Shannon第二定理，或称信道编码定理(Channel coding theorem)，给出了可行的码率的上限。由Shannon在其著名论文中A Mathematical Theory of Communication初次给出。据称是信息论里最重要、最著名的定理。
定理：对于一个离散无记忆信道，低于信道容量(channel capacity)C的码率都是可行的，这里信道容量C定义为
C=\max _ {p(\mathrm x)}I(\mathrm x;\mathrm y).就是说，当R<C时，总存在一列编码、解码函数及讯息\{\mathbf x _ {1:n}(\cdot),\hat w _ n(\cdot),\{1,\dots,\lceil2^{nR}\rceil\}\} _ {n\in\mathbb N}，使得当n\to\infty时，最大错误概率p _ {\max}=\max _ w P(w\neq\hat {\mathrm w})\to0。反之，若这一列满足讯息服从均匀分布时p _ {\max}\to0，那么必有R\leqslant C。
.
最后来看信源信道联合编码。
定理：设信源为S=\mathrm s _ 1,\mathrm s _ 2,\dots，是平稳无记忆随机过程，熵率为H，我们希望通过一个离散无记忆信道通信一列\mathbf s _ {1:k}，这个信道的容量为C。首先进行信源编码，编码为\mathbf x _ {1:n}，经过信道通信，输出\mathbf y _ {1:n}并解码为\hat{\mathbf s} _ {1:k}。设通过编码解码能达到的最优错误概率为\epsilon(k,n)，那么当R<C/H时，\epsilon(nR,n)\to0，反之，当\epsilon(nR,n)\to0，必有R\leqslant C/H。
证明信道编码定理
信道编码定理的一个重要证法是随机编码法，有必要给出。
信道编码定理（正向）：
下面是比较标准的证明。但叙述上改写得（个人）更为容易理解一些。这个证明的解码用的是“联合典型解码”(joint typical decoding)，这并非最优解码策略，但胜在更容易分析。
先选定一个分布p(x)，然后对\lceil 2^{nR}\rceil个讯息都进行随机编码，每个讯息w编码为\mathbf C(w)=(\mathrm C _ 1(w),\dots,\mathrm C _ n(w))，随机编码是指对任意w,i所有\mathrm C _ i(w)\stackrel{\mathrm{i.i.d}}\sim p(x)，这样编码各个bit的分布就都为p(x)，与输入的讯息w无关。发送端和接收端的操作为：发送端要发送w，按照\mathbf x=\mathbf C( w)编码，然后该码发送进信道，接收端收到的\mathbf y按照分布p(\mathbf y|\mathbf x)得到。然后，解码按照“联合典型解码”(jointly typical decoding)来进行：给定\varepsilon>0，如果有且只有一个\hat { w}使得(\mathbf x(\hat{ w}),\mathbf y)满足，|-\frac1n\log p(\mathbf x)-H(\mathrm x)|<\varepsilon，|-\frac1n\log p(\mathbf y)-H(\mathrm y)|<\varepsilon，|-\frac1n\log p(\mathbf x,\mathbf y)-H(\mathrm x,\mathrm y)|<\varepsilon，则解码为\hat {\mathrm w}。否则，接收端报错（或者可以说接收端解码为0）。
对每个w，错误概率为P(w\neq\hat {\mathrm w}(w))，考察这M个的平均错误概率\frac1M\sum _ w P(w\neq\hat {\mathrm w}(w))。我们有
\frac1M\sum _ {w=1}^M P(w\neq \hat {\mathrm w})=\frac1M\sum _ {w=1}^M E _ \mathbf C[P(w\neq \hat {\mathrm w}(w)\mid \mathbf C)].注意到E _ \mathbf C[P(w\neq\hat{\mathrm w}(w)\mid\mathbf C)]与w取值无关，因为随机编码\mathbf C\sim p^n(x)分布与w无关，故
\frac1M\sum _ {i=1}^M P(w\neq\hat{\mathrm w})=E _ \mathbf C[P(1\neq\hat {\mathrm w}(1)\mid\mathbf C)]=P(\hat {\mathrm w}(1)\neq 1).这表明错误概率在随机编码下对所有讯息是对称的，于是错误概率都可以视作发送讯息1的错误概率。
对w\in\{1,\dots,\lceil2^{nR}\rceil\}，令E _ w表示所有能被联合典型解码（即满足上面的三个\varepsilon的不等式）的(\mathbf x(w),\mathbf y _ 1)的事件，解码是错误的当且仅当E _ {1}^c发生或\bigcup _ {w\neq 1}E _ w发生。我们按如下初步思路控制错误概率：
\begin{aligned}
P(\hat {\mathrm w}(1)\neq 1)&\leqslant P(E _ {1})+\sum _ {w\neq 1}P(E _ w)\\
&\leqslant\varepsilon+\sum _ {w\neq 1}2^{-n(I(\mathrm x;\mathrm y)-3\varepsilon)}\\
&\leqslant\varepsilon+2^{nR}\cdot2^{-n(I(\mathrm x;\mathrm y)-3\varepsilon)}\\
&\leqslant2\varepsilon.
\end{aligned}
这个思路的实现需要这些不等号当n充分大时逐一成立。第一个和第三个总是成立，第四个只需要R<I(\mathrm x;\mathrm y)-3\varepsilon，第二个不等号是联合典型解码所带来的：联合典型解码要求|-\frac1n\log p(\mathbf x,\mathbf y)-H(\mathrm x,\mathrm y)|<\varepsilon，满足该不等式的(\mathbf x,\mathbf y)最多2^{n(H(\mathrm x,\mathrm y)+\varepsilon)}个（这是因为其概率p(\mathbf x,\mathbf y)\geqslant 2^{-n(H(\mathrm x,\mathrm y)+\varepsilon)}，而它们的概率和不超过1），于是由\mathbf x(w),\mathbf y(1)独立，有
\begin{aligned}P(E _ w)&=\sum _ {(\mathbf x,\mathbf y)\in E _ w} p(\mathbf x(w))p(\mathbf y)\\&\leqslant 2^{n(H(\mathrm x,\mathrm y)+\varepsilon)}2^{-n(H(\mathrm x)-\varepsilon)}2^{-n(H(\mathrm y)-\varepsilon)}\\&=2^{-n(I(\mathrm x;\mathrm y)-3\varepsilon)}.\end{aligned}由于\varepsilon的任意性，我们得知，R<I(\mathrm x;\mathrm y)，且\varepsilon充分小、n充分大时，错误概率小于2\varepsilon。
现在p(x)取为令I(\mathrm x;\mathrm y)最大的分布，此时I(\mathrm x;\mathrm y)=C，这种情况下，当R<C，且\varepsilon充分小、n充分大时，错误概率\frac1M\sum _ {i=1}^M P(w\neq\hat{\mathrm w})=E _ \mathbf C[\frac1M\sum _ {w=1}^M P(w\neq \hat {\mathrm w}(w)\mid \mathbf C)]小于2\varepsilon。这是对\mathbf C均值意义下错误概率小，于是当然存在错误概率最小的一个编码\boldsymbol C使得\frac1M\sum _ {w=1}^M P(w\neq \hat {\mathrm w}(w)\mid \boldsymbol C)\leqslant 2\varepsilon。由于\mathbf C的可能编码是有限的，这个\boldsymbol C必可以有限次搜索后找到。
现在不妨设各个讯息的错误概率在\boldsymbol C下是递增的，即P(\hat{\mathrm w}(1)\neq1\mid \boldsymbol C)最小，那么考察前面一半的\frac12\cdot2^{nR}=2^{n(R-1/n)}条讯息，它们之中的最大错误概率P(\hat{\mathrm w}(2^{nR-1})\neq 2^{nR-1}\mid\boldsymbol C)不超过4\varepsilon，否则另一半每一个至少4\varepsilon的错误概率将使得总平均错误率大于2\varepsilon，矛盾。
至此为止，当\varepsilon是给定的足够小的正数，对于讯息\{1,\dots,2^{nR-1}\}，我们找到了一个编码\boldsymbol C以及解码策略（联合典型解码），最大错误概率是4\varepsilon，码率是R-1/n。这就证明了R是可行的。
再证明反向的信道编码定理。
要证的是任一列编码、解码函数及讯息\{\mathbf x _ {1:n}(\cdot),\hat w _ n(\cdot),\{1,\dots,\lceil2^{nR}\rceil\}\} _ {n\in\mathbb N}，若最大错误概率p^{(n)} _ {\max}\to0，那么这个码率必不过C，即R\leqslant C。我们考虑随机发送均匀分布的讯息，错误概率就必有p _ e^{(n)}\to0。取定n，讯息均匀分布，则nR\leqslant\log\lceil2^{nR}\rceil=H(\mathrm w)=H(\mathrm w|\hat{\mathrm w})+I(\mathrm w;\hat{\mathrm w})，I(\mathrm w;\hat{\mathrm w})\leqslant I(\mathbf x;\hat{\mathbf x})\leqslant nI(\mathrm x;\hat{\mathrm x})\leqslant nC，而由Fano不等式，H(\mathrm w|\hat{\mathrm w})\leqslant 1+p _ e^{(n)}\log\lceil2^{nR}\rceil\leqslant1+p _ e^{(n)}(nR+1)（n充分大），代进前一式得到
R\leqslant p _ e^{(n)}R+\frac{1+p _ e^{(n)}}n+C.令n\to\infty即知R\leqslant C。
附录
信息论被认为是数学的一个分支，具体地说，概率论的分支，是不无道理的。下面介绍一下放在现代数学下引入信息论的量的一种方式。其基础部分是实分析。
一些实分析的背景。后续可能也会补充到其它地方，所以一并补充了。
设\mu,\nu是(\Omega,\mathcal A)上的两个测度，如果一个非负可测函数f满足对任意可测A都有\nu(A)=\int _ A f\, \mathrm d\mu，那么f就是v的一个密度（相对于\mu）。当然，对一个测度\mu和一个非负可测f，上式右边实际上定义了一个测度\nu。一般这些会记为f=\mathrm d\nu/\mathrm d\mu。如果g可测，那么\int g\,\mathrm d\nu=\int gf\,\mathrm d\mu，其证明也是先考虑简单函数，再考虑非负可测函数再到一般可测函数。
定理（密度的唯一性）：若\nu是\sigma有限的，f _ 1,f _ 2是\nu相对\mu的密度，那么f _ 1=f _ 2 a.e.[\mu]。
证明只需考虑证\mu(\{f _ 1>f _ 2\})=\mu(\{f _ 1<f _ 2\})=0。
绝对连续：如果总有\mu(A)=0\implies\nu(A)=0，那么称\nu相对于\mu绝对连续，记为\nu\ll\mu。
\nu对\mu是奇异的，如果存在某可测A使得\nu(A)=0且\mu(\Omega\setminus A)=0。此时显然也有\mu对\nu奇异。记为\nu\perp\mu。
定理（测度分解）：设\mu,\nu是\sigma有限的，那么\nu可唯一分解成一个绝对连续部分\nu _ {\text{ac}}和一个奇异的部分\nu _ {\text s}（相对于\mu），这里\nu _ {\text{ac}}有对于\mu的密度\mathrm d\nu _ {\text{ac}}/\mathrm d\mu，且该密度\mathcal A可测、a.e.[\mu]有限：
\nu=\nu _ {\text{ac}}+\nu _ {\text s},\quad \nu _ {\text{ac}}\ll\mu,\; \nu _ {\text s}\perp\mu.
这里不证明该定理，直接应用了。如果\nu有相对于\mu的密度，那么显然\nu\ll\mu；反之，若\nu\ll\mu，由该定理，易知\nu=\nu _ {\text{as}}，于是有下面的定理：定理(Radon–Nikodym)：仍设\mu,\nu是\sigma有限的，那么：\nu有相对于\mu的密度，当且仅当\nu\ll\mu。此时，密度\mathrm d\nu _ {\text{ac}}/\mathrm d\mu为\mathcal A可测、a.e.[\mu]有限，称之\nu的Radon–Nikodym导数（相对\mu）。
KL散度（相对熵）
首先来看KL散度，f散度的一种。
定义：\mathcal X上的两概率测度P,Q间的KL散度定义为：
D _ {\text{KL}}(P\|Q)=\mathbb E _ {Q}\Big[\frac{\mathrm dP}{\mathrm dQ}\log\frac{\mathrm dP}{\mathrm dQ}\Big]=\mathbb E _ P\Big[\log\frac{\mathrm dP}{\mathrm dQ}\Big],\quad P\ll Q.当P\not\ll Q，那么定义为+\infty。
也可以等价定义为：
D _ {\text{KL}}(P\|Q)=
\begin{cases}
-\mathbb E _ P\Big[\log\frac{\mathrm dQ}{\mathrm dP}\Big],& Q\ll P;\\
+\infty,&Q\not\ll P.
\end{cases}
为了说明定义的等价性，先考虑Q\ll P但P\not\ll Q的情形，这时候需要-\mathbb E _ P\Big[\log\frac{\mathrm dQ}{\mathrm dP}\Big]=+\infty，由假设知存在A使Q(A)=0但P(A)>0，则Q(A)=\int _ A \frac{\mathrm dQ}{\mathrm dP}\, \mathrm dP=0，这说明\mathrm dQ/\mathrm dP在A上a.e.[P]为0，易见-\mathbb E _ P\Big[\log\frac{\mathrm dQ}{\mathrm dP}\Big]=+\infty，另一个情形（Q\not\ll P但P\ll Q）也完全类似。而Q\ll P且P\ll Q时，只需注意到\frac{\mathrm dP}{\mathrm dQ}=(\frac{\mathrm dQ}{\mathrm dP})^{-1}。
当然，我们还需要考虑定义的合理性，以下不妨设\log的底为\mathrm e。设P\ll Q，那么\frac{\mathrm dP}{\mathrm dQ}\log\frac{\mathrm dP}{\mathrm dQ}=:f并不是非负可测函数，但是其负数部分被界住了，因为f\geqslant-1/\mathrm e，有\int\max\{-f,0\}\, \mathrm dQ<+\infty，这说明\int f\, \mathrm dQ=\int \ln(\mathrm dP/\mathrm dQ)\, \mathrm dP存在。
定理（信息不等式）：D _ {\text{KL}}(P\| Q)\geqslant0.
只需证Q\ll P的情形。-\log x是严格凸函数，由Jensen不等式，
D _ {\text{KL}}(P\|Q)\geqslant -\log\mathbb E _ P\Big[\frac{\mathrm dQ}{\mathrm dP}\Big]=-\log\int\mathrm dQ=0.取等即\mathrm dQ/\mathrm dP=1 a.e.[P]，亦即P=Q。
互信息、熵、微分熵
对两随机变量\mathrm x,\mathrm y，设联合分布为P _ {\mathrm x,\mathrm y}，边缘分布为P _ \mathrm x,P _ \mathrm y，边缘分布的乘积测度记为P _ {\mathrm x}P _ \mathrm y，假设给定\mathrm x存在\mathrm y正则条件分布\kappa（满足\kappa(x,\cdot)=\mathbb P(\mathrm y\in\cdot\mid \mathrm x=x)），记为P _ {\mathrm y|\mathrm x}。
定义：两随机变量\mathrm x,\mathrm y间的互信息定义为I(\mathrm x;\mathrm y)=D _ {\text{KL}}(P _ {\mathrm {x,y}}\|P _ {\mathrm x}P _ {\mathrm y})。
该定义下，有：I(\mathrm x;\mathrm x)=H(\mathrm x)，当\mathrm x为离散。因而我们导出了熵的原始定义。但是不是离散的时，该互信息量为+\infty。对于连续随机变量\mathrm x，设密度为p(x)，其微分熵(differential entropy)定义为
h(\mathrm x)=-\int p(x)\log p(x)\, \mathrm dx.对于一般的\mathrm x，记Lebesgue测度为\lambda，微分熵则定义为
h(\mathrm x)=-D _ {\text{KL}}(P _ \mathrm x\|\lambda).
观察KL散度定义并注意到p(x)=\mathrm dP _ \mathrm x/\mathrm d\lambda即知该式为合理推广。
微分熵只是形式像熵，但此熵非“真熵”，例如它可以取负值。“真熵”I(\mathrm x;\mathrm x)对非离散变量是无穷，这在不确定性的视角下是可以解释的，以bit为单位来衡量，不确定性当然是无穷多bits。注意到I(\mathrm x;\mathrm y)=h(\mathrm x)-h(\mathrm x|\mathrm y)，说明某种程度上，微分熵是减去了其中的无穷部分，使得我们仍有这些可以运算的（在离散情况下成立的）式子。
Feinstein引理
作为结尾，下面试叙述Feinstein引理。
首先需要信息密度的概念。我们假设P _ {\mathrm x,\mathrm y}\ll P _ \mathrm xP _ \mathrm y，这样就存在Radon-Nikodym导数\mathrm dP _ {\mathrm x,\mathrm y}/\mathrm d (P _ \mathrm xP _ \mathrm y)，定义信息密度如下：
定义：信息密度
i(x,y):=\log\frac{\mathrm dP _ {\mathrm x,\mathrm y}}{\mathrm d(P _ \mathrm xP _ \mathrm y)}(x,y).
当然也可以对P _ {\mathrm x,\mathrm y}\not\ll P _ \mathrm xP _ \mathrm y的情况定义，这时需要一个控制(dominating)测度\mu：P _ {\mathrm x,\mathrm y}\ll\mu，P _ \mathrm xP _ \mathrm y\ll\mu，记导数分别为f _ 1(x,y),f _ 2(x,y)，那么在f _ 1>0,f _ 2>0时i:=\log (f _ 1/f _ 2)；在f _ 1>0,f _ 2=0时定义为+\infty；在f _ 1=0,f _ 2>0时定义为-\infty；在f _ 1=f _ 2=0时i:=0。
在这定义下，就有：
I(\mathrm x;\mathrm y)=\mathbb E[i(\mathrm x;\mathrm y)].记\mathrm dP _ {\mathrm x,\mathrm y}/\mathrm d(P _ \mathrm xP _ \mathrm y)=f，那么：对几乎处处[P _ \mathrm x]的x，还有
\mathbb E _ \mathrm y[f(x,\mathrm y)]=\int P _ \mathrm y(\mathrm dy)\, f(x,y)\leqslant 1.这是因为对任意E _ x，
\int _ {E _ x}P _ \mathrm x(\mathrm dx)\int f(x,y)\, P _ \mathrm y(\mathrm dy)=\int _ {E _ x\times\mathcal Y}P _ {\mathrm x,\mathrm y}(\mathrm dx,\mathrm dy)=P _ \mathrm x(E _ x)\leqslant1.
Feinstein引理是说我们可以选M个x _ i以及对应的不相交的“解码区”D _ i使得输入为x _ i时输出在D _ i之外的概率可以充分小。
定理（Feinstein引理）：给定正整数M和一个正数a，存在x _ i\in \mathcal X (i=1,\dots,M)以及两两不交的D _ i\subseteq \mathcal Y (i=1,\dots,M)，使得
P _ {\mathrm y|\mathrm x}(D _ i^c|x _ i)\leqslant M2^{-a}+P _ {\mathrm x,\mathrm y}(i\leqslant a).
证明：令E=\{(x,y)\mid i(x,y)>a\}，对任意x，类似定义E _ x=\{(x,y)\mid i(x,y)>a\}，这样不等式右边第二项就写成P _ {\mathrm x,\mathrm y}(E^c)；设不等式右边为\varepsilon，即\varepsilon=M2^{-a}+P _ {\mathrm x,\mathrm y}(E^c)，若它大于等于1，不等式显然成立，故只需考虑小于\varepsilon<1的情况。E的概率满足P _ {\mathrm x,\mathrm y}(E)=1-P _ {\mathrm x,\mathrm y}(E^c)>1-\varepsilon>0，又P _ {\mathrm x,\mathrm y}(E)=\int P _ \mathrm x(\mathrm dx)\, P _ {\mathrm y|\mathrm x}(E _ x|x)，这表明满足P _ {\mathrm y|\mathrm x}(E _ x|x)>1-\varepsilon以及前面的\mathbb E _ \mathrm y[f(x,\mathrm y)]\leqslant 1的x必有P _ \mathrm x正测度。这其中选一个为x _ 1，对应的E _ {x _ 1}为D _ 1。
按如下策略继续从中选取x _ i,D _ i：假设已经选取好了\{x _ j,D _ j\}，j=1,\dots,i-1，然后任取x _ i使得P _ {\mathrm y|\mathrm x}(E _ {x _ i}-\bigcup _ {j<i} D _ j|x _ i)>1-\varepsilon，并令D _ i=E _ {x _ i}-\bigcup _ {j<i}D _ j。这种选取策略可见满足P _ {\mathrm y|\mathrm x}(D _ i^c|x _ i)\leqslant \varepsilon，我们证明这种选取至少可以进行M次。
假设最多选取n次，这时全部的解码区记为D=\bigcup _ {i=1}^n D _ i，重新考察E的概率：
P _ {\mathrm x,\mathrm y}(E)=P _ {\mathrm x,\mathrm y}(E\cap(\mathcal X\times D))+P _ {\mathrm x,\mathrm y}(E\cap(\mathcal X\times D^c)).对第一项，
\begin{aligned}
P _ {\mathrm x,\mathrm y}(E\cap (\mathcal X\times D))&\leqslant P _ {\mathrm x,\mathrm y}(\mathcal X\times D)=P _ \mathrm y(D)=\sum _ {i=1}^nP _ \mathrm y(D _ i)\\
&\leqslant\sum _ {i=1}^n P _ \mathrm y(E _ i)=\sum _ {i=1}^n \int _ {E _ i}P _ \mathrm y(\mathrm dy)\\&\leqslant\sum _ {i=1}^n \int _ {E _ i}P _ \mathrm y(\mathrm dy)\, \frac{f(x _ i,y)}{2^a}\\
&\leqslant2^{-a}\sum _ {i=1}^n \int P _ \mathrm y(\mathrm dy)=n2^{-a}.
\end{aligned}对第二项，
P _ {\mathrm x,\mathrm y}(E\cap(\mathcal X\times D^c))=\int P _ {\mathrm y|\mathrm x}\big(E _ x\cap D^c\mid x\big)\, P _ \mathrm x(\mathrm dx)=\int P _ {\mathrm y|\mathrm x}\Big(E _ x-\bigcup _ {i=1}^n D _ i\mathrel{\Big|} x\Big)\, P _ \mathrm x(\mathrm dx).注意到n的定义，有：对几乎处处[P _ \mathrm x]的x都有P _ {\mathrm y|\mathrm x}(E _ x-\bigcup _ {i=1}^nD _ i\mid x)\leqslant 1-\varepsilon，否则可以选取x _ {n+1}。于是上面第二项小于等于1-\varepsilon。
于是E的概率满足
P _ {\mathrm x,\mathrm y}(E)\leqslant n2^{-a}+1-\varepsilon.由\varepsilon本身的定义，\varepsilon=M2^{-a}+P _ {\mathrm x,\mathrm y}(E^c)，P _ {\mathrm x,\mathrm y}(E)=M2^{-a}+1-\varepsilon，由此立知n\geqslant M。
这就证明了Feinstein引理。
现在再次考虑信道编码。假设\mathcal X是有限alphabet、信道是无记忆无反馈的，即DMC。考虑随机过程X=\{\mathrm x _ i\} _ {i\in\mathbb N}和Y=\{\mathrm y _ i\} _ {i\in\mathbb N}。只考虑它们为平稳的、ergodic的情形。对于一个大正整数n，令M=\lceil 2^{nR}\rceil。设R<I(\mathrm x;\mathrm y)，令\delta=(I(\mathrm x;\mathrm y)-R)\mathbin/2>0，再令a=n(R+\delta)，此时对n维分布应用Feinstein引理，就得到\{\boldsymbol x _ i^n,D _ i\} _ {i=1}^M使得
\begin{aligned}
&\max _ {i} P _ {\mathbf y^n|\mathbf x^n}(D _ i^c|\boldsymbol x _ i)\leqslant M2^{-a}+P _ {\mathrm x^n,\mathrm y^n}(i _ n\leqslant a)\\
\leqslant{}&(2^{nR}+1)2^{-n(R+\delta)}+P _ {\mathbf x^n,\mathbf y^n}\Big(\frac1n\sum _ {i=1}^ni(\mathrm x _ i;\mathrm y _ i)\leqslant R+\delta\Big)\\
={}&2^{-n\delta}+2^{-n(R+\delta)}+P _ {\mathbf x^n,\mathbf y^n}\Big(\frac1n\sum _ {i=1}^ni(\mathrm x _ i;\mathrm y _ i)\leqslant I(\mathrm x;\mathrm y)-\delta\Big).
\end{aligned}其中用到了离散无记忆无反馈信道的性质
i(\mathbf x^n;\mathbf y^n)=\sum _ {i=1}^n\log\frac{\mathrm dP _ {\mathrm x,\mathrm y}}{\mathrm d(P _ \mathrm xP _ \mathrm y)}(\mathrm x _ i,\mathrm y _ i)=\sum _ {i=1}^n i(\mathrm x _ i;\mathrm y _ i).又注意到i(\mathrm x _ i;\mathrm y _ i)\stackrel p\to\mathbb E[i(\mathrm x _ i;\mathrm y _ i)]=I(\mathrm x;\mathrm y)，当n\to\infty，上面不等式最后一项趋于零，故\max _ {i} P _ {\mathbf y _ {1:n}|\mathbf x _ {1:n}}(D _ i^c|\boldsymbol x _ i)\to0。
发表回复