大多数人可能会认为信息熵抽象而不明确，这的确很难避免；另一些人会认为信息熵仅是玻尔兹曼熵的推广、或者信息熵度量了信息量，这很大程度上是不对的。严格的说，信息熵的定义一方面依赖于概率论，其度量了随机变量的不确定度；另一方面则依赖于信息的编码理论。下面我们要从两个方面导出信息熵。并且如若不特别说明，我们只考虑离散的情况。

随机变量的不确定度

对于离散随机变量，假设其不确定度的度量为，我们期待满足以下几条公理：
1. 对于的分布连续。即，假设的样本空间大小为 ¹ ，我们将的概率质量函数视作定义在维概率单纯形上的向量，那么我们要求是连续的。
2. 若，则应关于单增。
3. 若可以被以概率分解为后续的两个随机变量，则应有：
而由以上的三条公理就足以导出的表达式。首先由公理 1 ，我们只关注概率质量函数均为有理数的随机变量。再由公理 3 ，我们可以使用均匀分布的熵的组合表示出所有的有理分布的熵，所以我们只用关注均匀分布。记，容易验证。对于任意的，任取充分大的，并寻一使得：由公理 2 ：令，由夹逼准则：固定，就得到了。可以验证，对于任意概率质量函数为的随机变量，其熵满足：一般取使得对数的底为。这样，我们就证明了熵的唯一形式必然满足上式。²

信息的编码

假设我们要用字符集为包含个文字的语言做编码。具体的，令随机变量服从该语言中每个文字的分布，为的样本空间（即所有文字）。定义编码为映射，将映射为一个字符集构成的字符串集中的元素，称为码字。定义扩展编码为映射，其将个文字构成的句子映射为一字符串。在编解码过程中，我们不允许歧义，即要求为一双射。一个常见的实现方式是强制任意码字不能为另一码字的前缀，称作即时码或前缀码。假定第个文字的码字长度为，容易看出存在满足该长度要求的即时码的一个充分条件是：³ 上式被称作 Kraft Inequality ，实际上可以证明其是存在满足要求的码字的充要条件。⁴假设文字的出现服从概率质量函数，现在我们希望求出最优编码，即最小化编码长度的期望。我们写出其优化形式：要解这个优化问题，直接用 Lagrangian 算即可，这里无意赘述。最后可以得到在实数域上的最优解是：若定义随机变量表示文字的编码长度，服从文字出现概率的分布，则其期望就为文字的期望长度，恰好服从刚刚的熵的形式：这说明熵描述了最优编码的期望长度。当然，显示中编码的长度不能是实数，所以一种可能的编码，称作香农码，是：其期望与熵的差不超过。然而香农码并非实际上的最优编码，可以证明，后者应是霍夫曼编码。⁵

Kraft 不等式

假设我们要用大小为的字符串为随机变量编码。对于，令其码字长度为。则对于给定的码字长度，对应的无歧义码存在的充要条件是： Kraft 不等式指出了一个深刻的道理：无歧义码基本和即时码等价，而这个结论其实很让我震惊。下面我们将给出其证明。令码字长度具有上界，考虑：令中码字长度之和为的元素个数为，则：令，即得：

霍夫曼编码

任何学过算法的人应该都会这个。

Shannon-Fano-Elias 编码

以下我们将简要介绍 Shannon-Fano-Elias coding 的构造。⁶对于随机变量，令，其对应的概率质量函数为，定义其前缀和为 ⁷ ，再定义：显然是上的实数。对于任意，我们截取的前小数位作为的码字，将其对应的小数记作。我们先说明该编码的无歧义性。考虑：从而：那么与差的至少为，这说明的小数位必然是即时码。⁸容易看出，如上编码的期望长度的上界是。

香农码的最优性

实际上香农码在理论上具备一些特别的深刻之处，例如我们可以证明，给定某一随机变量与任意编码，该编码大多数时候不会显著优于香农码。形式化的叙述如下：
- 对于随机变量，令表示按照香农码编码的码字长度，令表示另一无歧义码的码字长度。则：
这里就不给出证明了。

可数的情况也是类似的。但以下我们假设离散随机变量的样本空间大小总是有限的。↩︎
容易看出，熵是概率单纯形上的凹函数，其具备唯一的最大值点，即均匀分布，此时。↩︎
方便起见，将简记为。↩︎
我们先承认这一点，下面会给出证明。↩︎
这是一个简单的算法，待会我们再谈。↩︎
实际上我没有看出其相比 Shannon coding 和 Huffman coding 有什么显著的好处。我猜测这种编码方式可能在实践中有些好处，例如其编码时间是的。或者可能是因为要将 Shannon-Fano-Elias coding 作为 Arithmetic coding 的引入，但本文并不会涉及 Arithmetic coding 。↩︎
有些地方直接把这个叫累计分布函数，但是我认为这样并不严谨。实际上概率论中的累积分布函数是对值域谈的，而非样本空间。↩︎
把这一点拿到 Trie 上看其实会更直观一点，即只需要保证差的下界就可以保证不存在前缀关系。↩︎