Week 1

信息消息信号

信息的度量：信息量

信息量定义：对发生概率为$p(X)$的事件$X$，其信息量定义为：

$I(X)=-\log _2 p(X)$

抛硬币：$p(X)=\frac{1}{2}$，信息量：$I(X)=-\log _2 \frac{1}{2}=1 \; \mathbb{bit}$

简单说，对于bit由于只有01两种状态，故对于一个概率为1/2的事件，其信息量为1bit，而对于概率为1的事件，其信息量为0bit，$-\log _2 0.001 \approx 9.97bit$。

信息量与熵

熵：平均信息量

定义

设概率为$p(x)$,则熵定义为：

$H(X)=-\sum_{x \in X} p(x) \log _2 p(x)$

如果是确定性事件 $P(x)=1$ ，则$H(X)=-1 \times \log _2 1=0$，没有不确定性。

e.g.1：抛硬币：$H(X)=-\frac{1}{2} \log _2 \frac{1}{2}-\frac{1}{2} \log _2 \frac{1}{2}=1 \; \mathbb{bit}$ 信息熵最大

e.g.2: $p(x)=\frac{1}{6}$，熵：

$H(X)=-6 \times \frac{1}{6} \log _2 \frac{1}{6}=\log _2 6 \approx 2.585 \; \mathbb{bits}$

离散变量计算：

$H(X)=-\sum_{i=1}^{n} p(x_i) \log _2 p(x_i)$

对于一个二元信源，如果横轴是概率 $P$，纵轴是熵 $H$，则曲线近似于一个对称轴为 $P = 0.5$ 的抛物线，在 $P = 0$ 和 $P = 1$ 时，熵为0，在 $P = 0.5$ 时，熵最大为1。

对于一个n元信源，熵取值范围为 $0 \leq H(X) \leq \log _2 n$，当且仅当各符号概率相等时，熵达到最大值 $\log _2 n$。

而对于一个加密算法而言，熵越大，破解难度越大。假设有一个映射 $P \rightarrow C$，其中$P$为明文，$C$为密文，显然在为双射时，即每个明文对应唯一密文时，熵最大。

互信息

定义：

$I(X ; Y)=\sum_{x \in X} \sum_{y \in Y} p(x, y) \log _2 \frac{p(x, y)}{p(x) p(y)}$

信源编码

信息压缩

香农第一定律

信源编码定理

设信源$X$的熵为$H(X)$，则对于任意$\varepsilon>0$，存在一个信源编码，其平均码长$\bar{L}$满足：