香农经典信息论以及一些现代进展总览

摘要: 香农信息论内容总览

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

香农指出，通信的基本问题是在一点精确地或近似地恢复另一点所选择的消息。从这个基本问题出发，通信系统有三项性能指标：传输的有效性、传输的可靠性、传输的安全性。

有效性指的是有效利用资源，包括时间、空间、频谱等。表现为：

• 对于离散信源，平均码长要尽量短。
• 信息传输速率要尽量快。
• 信息传输对频谱的利用率要尽量高。

可靠性是指传输的差错要尽量小，如果是数字传输，相当于误码率要尽量小。

安全性是指传输的信息不能泄露给未授权人。

通信系统的有效性、可靠性、安全性这三项考核指标，对应了通信系统的三项基本技术：数据压缩、数据纠错、数据加密。

香农在 1948 年的《通信的数学原理》解决的是前两项技术的理论问题。提高有效性可以通过信源编码实现，并给出压缩编码最低码率的极限；提高可靠性可以通过信道编码实现，并给出实现可靠传输最高信息传输速率的极限。

此外，香农在 1949 年的《保密系统的通信理论》建立了保密系统的数学理论，对密码学影响很大。

现代信息论可以分为狭义和广义，狭义信息论就是指香农的经典信息论，研究的问题是信源、信道、编码问题，核心是三个编码定理。广义信息论包括香农经典信息论、编码理论、统计通信理论、通信网理论、信号与信息处理、保密通信等。

本文我们总览一下香农经典信息论的内容，以及现代进展。

香农之前其他人的工作

奈奎斯特发现传输速率正比于单位时间内信号电平数目的对数。

哈特利提出传输速率、码间干扰，系统传输信息的容量等概念。

维纳、莱斯把随机过程作为通信研究的工具。

热力学熵对香农信息论也有很大影响，人们对热力学熵的认识有三个阶段：

• 最早是克劳修斯提出的宏观熵 $S = \frac{\Delta Q}{T}$，其中 $S$ 为熵的变化，$\Delta Q$ 为系统热量的变化，$T$ 是绝对温度。
• 之后是玻尔兹曼提出微观系统的熵和微观系统状态数的对数成正比，后由普朗克总结为 $S = k\log \Omega$，其中 $k$ 为玻尔兹曼常数，$\Omega$ 为系统的微观状态数。
• 最后是吉布斯提出在微观系统状态概率不等情况下的热力学熵计算公式 $S = -k\sum\limits_{i}p_{i}\log p_{i}$。除了玻尔兹曼常数 $k$，香农熵和吉布斯熵的表达式相同。

香农对信息论的贡献年表

1948 年发表《通信的数学原理》建立信息论的理论基础。

1956 年发表《噪声信道的零差错容量》指出当不许有传输错误时，信道编码的概率问题消失，而仅保留图论问题，开启零差错容量问题研究。

1959 年发表《在保真度准则下的离散信源编码定理》给出率失真定理的详细证明，然后推广到更一般的信源和失真测度，最后到模拟信源，推动信息率失真问题研究。

1961 年发表《双路通信信道》将信息论应用到需要双向通信，但两个方向互相干扰的情况。证明了信道容量区域是凸的。开启多用户理论(网络信息论)的研究。

香农经典信息论

香农经典信息论的内容可以概括为一个概念，三个定理。即：信息熵的概念、三个编码定理。

信息的度量

香农将信源限制为具有某一先验概率的随机过程。信息度量的对象是随机过程的输出，其中信源输出的信息度量最重要。

由于随机过程在给定时刻表现为随机变量，因此信息的度量也视为对随机变量的信息度量。

对于单一随机变量，用信息熵来描述其信息度量；对于随机变量之间，用互信息作为描述信息量多少的度量。

无失真信源编码

香农第一定理：

存在无失真编码 $\Leftrightarrow$ 信源编码码率不小于信源的熵。

香农第一定理即无失真信源编码定理，该定理解决了信源无损压缩极限的理论问题。

信道容量与信息的可靠传输

香农第二定理：

信息传输速率小于信道容量 $\Leftrightarrow$ 存在一种编码方式，使得当编码序列足够长时，传输差错任意小

香农第二定理是信道编码的理论基础，解决的是信息传输极限的理论问题。

信息率失真

香农第三定理：

对任意失真测度 $D \geq 0$，只要码字足够长，总能找到一种编码，使得当信源编码码率不小于 $R(D)$ 时，码的平均失真不大于 $D$。
其中 $R$ 为信源编码码率，$R(D)$为信息率失真函数，是满足平均失真不大于 $D$ 条件下，平均信息源符号所需最小编码比特数。

很多情况下，我们不需要信息精确地传输。而是满足一定的失真要求下，使得编码器的码率最小。这是香农第三定理解决的问题，也就是有损压缩极限的理论问题。

香农经典信息论的现代进展

信息的度量

• 以香农熵为基础，研究信息熵的估计方法。
• 将信息熵用作推断工具的最大熵原理 (Jaynes, 1957)。
• Kolmogorov 算法熵，与概率无关的信息度量。
• Renyi 熵。
• Tsallis 熵，

无损数据压缩

熵编码：

• Huffman 解决了从固定到可变长度最优编码的构造，即 Huffman 编码。
• TUNstall 解决了可变适定消息集到固定长度最优编码的构造，即 Tunstall 编码。
• Golomb 提出了一种针对二元信源的游程编码，即 Golomb 编码。

通用编码：

• LZ压缩算法，在 gif, png, rar, zip 中用到。
• Burrows-Wheeler变换，在 bzip 中用到。
• 部分匹配预测算法，在音视频编码中用到。

可靠通信

各种特殊信道与相关的编译码技术：

• 高斯信道
• 衰落信道
• 反馈信道
• 迭代译码
• 有约束信道
• 零差错信道

多用户信道：

• 多接入信道
• 广播信道
• 干扰信道
• 窃听信道

编译码理论：

• Berlecamp 系统总结了代数编码理论
• BCH 码
• RS 码
• 卷积码
• 级联码
• TCM 编码调制理论
• Turbo 码
• LDPC 码

有损数据压缩

实现有损压缩的技术：

• 标量量化
• 矢量量化
• 预测编码
• 变换编码

---