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\le H(X)\le {\log }_{2}n$，当且仅当各符号概率相等时，熵达到最大值 ${\log }_{2}n$。

而对于一个加密算法而言，熵越大，破解难度越大。假设有一个映射 $P\to 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)$，则对于任意$\epsilon >0$，存在一个信源编码，其平均码长$\overline{L}$满足：