Shannon熵 – 佚名

编码

字母表、字
- 字母表 $A$ 是一个有限集，它生成的自由半群为
  $S(A) = \bigcup_{n \geq 1} A^n.$
- $S(A)$ 中的元素称为字。字的长度为
  $l: S(A) \to \mathbb{Z}_+,\; l(w) = n, \text{ where } w \in A^n.$
基本码字、码字
- 设 $A$ 、 $B$ 为字母表。如果 $f: A \to S(B)$ 是单射，那么 $f$ 称为编码， $f(A) \subset S(B)$ 中的元素称为基本码字
- 进一步，如果 $f$ 的自由扩张 $\widetilde{f}: S(A) \to S(B)$ 也是单射，那么 $f$ 称为唯一译码的编码， $\widetilde{f}(S(A)) \subset S(B)$ 中的元素称为码字

唯一译码的编码

如果为唯一译码的编码，那么
$\sum_{w \in A} b^{-l(f(w))} \leq 1.$
- 设长度为 $i$ 的基本码字的个数为
  $a_i = card\{ w \in A : l(f(w)) = i \},\; i \geq 1,$
  长度为 $j$ 的码字的个数为
  $b_j = card\{ w \in S(A) : l(\widetilde{f}(w)) = j \},\; j \geq 1.$
- 一个长度为 $j - r$ 的码字乘以一个长度为 $r$ 的基本码字（ $1 \leq r \leq j - 1$ ），或者一个长度为 $j$ 的基本码字是一个长度为 $j$ 的码字。也就是说，
  $b_{j - 1}a_1 + \cdots + b_1a_{j - 1} + a_j \leq b_j.$
  进一步，因为 $f$ 为唯一译码的编码，所以相反方向的不等式、以及等式也成立。定义 $A(z) = \sum_{i \geq 1} a_iz^i$ ， $B(z) = \sum_{j \geq 1} b_jz^j$ 。那么，
  $B(z) = B(z)A(z) + A(z).$
- 由于 $b_j \leq b^j$ ，故 $B(z)$ 在 $\{ z \in \mathbb{C} : |z| < b^{-1} \}$ 上为解析函数。另一方面，
  $B(z) = \frac{A(z)}{1 - A(z)},$
  所以 $1 - A(z)$ 在 $\{ z \in \mathbb{C} : |z| < b^{-1} \}$ 上没有零点。由 $1 - A(0) = 1 > 0$ ，可得
  $1 - A(t) > 0,\; 0 \leq t < b^{-1}.$
  从而， $A(b^{-1}) \leq 1$ ，并且
  $\sum_{w \in A} b^{-l(f(w))} = \sum_{i \geq 1} a_ib^{-i} = A(b^{-1}) \leq 1.$
反过来，如果满足
$\sum_{w \in A} b^{-m(w)} \leq 1,$
那么存在唯一译码的编码，使得
- 定义
  $A_i = \{ w \in A : m(w) = i \},\; a_i = card(A_i),\; i \geq 1.$
  我们只需构造一个唯一译码的编码 $f: A \to S(B)$ ，使得 $f(A_i) \subset B^i$ , $i \geq 1$
- 由 $a_1b^{-1} \leq \sum_{i \geq 1} a_ib^{-i} \leq 1$ ，可得
  $a_1 \leq b.$
  因此，我们可以取 $B_1 \subset B^1$ ，使得 $card(B_1) = a_1$ 。让 $f$ 将 $A_1$ 一一映射到 $B_1$
- 由 $\sum_{i = 1}^j a_ib^{-i} \leq \sum_{i \geq 1} a_ib^{-i} \leq 1$ ，可得
  $a_j \leq b^j - \sum_{i = 1}^{j - 1} a_ib^{j - i}.$
  如果 $B_i \subset B^i$ ， $1 \leq i \leq j - 1$ 已经取定，并且满足 $card(B_i) = a_i$ ，那么，由于
  $card[B^j - \cup_{i = 1}^{j - 1} (B_i \times B^{j - i})] \geq b^j - \sum_{i = 1}^{j - 1} a_ib^{j - i} \geq a_j,$
  故我们可以取 $B_j \subset B^j$ ，使得 $card(B_j) = a_j$ ，并且
  $B_j \subset B^j - \cup_{i = 1}^{j - 1} (B_i \times B^{j - i}).$
  让 $f$ 将 $A_j$ 一一映射到 $B_j$
- 由数学归纳法，我们可以得到编码 $f: A \to S(B)$ ，满足 $f(A_i) = B_i \subset B^i$ ， $i \geq 1$ ，并且
  $B_j \subset B^j - \cup_{i = 1}^{j - 1} (B_i \times B^{j - i}).$
  进一步， $f$ 是唯一译码的编码，原因是如果一个码字有两种不同的译码方法，那么我们可以将其从左到右分解为基本码字，直到得到矛盾
  $B_j \cap (B_i \times B^{j - i}) \neq \emptyset \text{ for some } i < j.$

最小平均长度

设 $A$ 为字母表（带有离散 $\sigma$ -代数）。如果 $(A, \mu)$ 是一个概率空间，那么 $(A, \mu)$ 称为基本信源（Elementary Information Source，EIS）
如果 $(A, \mu)$ 是一个EIS，那么唯一译码的编码 $f: A \to S(B)$ 的平均长度为
$\overline{l}(\mu, f) = \sum_{w \in A} l(f(w)) \cdot \mu(w).$
进一步，最小平均长度为平均长度的理论极限，
$L(\mu) = \inf\{ \overline{l}(\mu, f) : f: A \to S(B) \text{ is a uniquely decipherable code} \}.$
下面我们证明，Shannon熵给出了最小平均长度的最佳估计。设为EIS，并且。我们有
$-\sum_{w \in A} \mu(w)\log_b\mu(w) \leq L(\mu) < -\sum_{w \in A} \mu(w)\log_b\mu(w) + 1.$
当时，
$H(\mu) \leq L(\mu) < H(\mu) + 1,$
其中，称为Shannon熵
- 由上面的笔记，
  $L(\mu) = \inf\bigg\{ \sum_{w \in A} m(w) \cdot \mu(w) : m: A \to \mathbb{Z}_+,\; \sum_{w \in A} b^{-m(w)} \leq 1 \bigg\}.$
- 证明左侧不等式：
  - 对任意 $m: A \to \mathbb{Z}_+$ 满足 $\sum_{w \in A} b^{-m(w)} \leq 1$ ，定义
    $\nu(w) = \frac{b^{-m(w)}}{\sum_{w \in A} b^{-m(w)}}.$
  - 由
    $m(w) = -\log_b\bigg(\sum_{w \in A} b^{-m(w)}\bigg) - \log_b\nu(w) \geq -\log_b\nu(w),$
    可得
    $\begin{equation*}\begin{split} \sum_{w \in A} m(w) \cdot \mu(w) &\geq -\sum_{w \in A} \mu(w)\log_b\nu(w) \\ &\geq -\sum_{w \in A} \mu(w)\log_b\mu(w), \end{split}\end{equation*}$
    其中，最后一个不等式可由Jensen不等式应用于 $\log_bx$ 得到，
    $-\sum_{w \in A} \mu(w)\log_b\bigg(\frac{\nu(w)}{\mu(w)}\bigg) \geq -\log_b\bigg(\sum_{w \in A} \mu(w)\frac{\nu(w)}{\mu(w)}\bigg) = 0.$
  - 对所有的 $m$ 取下确界，左侧不等式成立
- 证明右侧不等式：
  - 取 $m: A \to \mathbb{Z}_+$ 满足
    $m(w) - 1 < -\log_b\mu(w) \leq m(w),\; w \in A.$
  - 那么，
    $\sum_{w \in A} b^{-m(w)} \leq \sum_{w \in A} \mu(w) = 1,$
    并且
    $\begin{equation*}\begin{split} L(\mu) &\leq \sum_{w \in A} m(w) \cdot \mu(w) \\ &< \sum_{w \in A} \mu(x)[1 - \log_b\mu(x)] \\ &= -\sum_{w \in A} \mu(x)\log_b\mu(x) + 1. \end{split}\end{equation*}$