信息论

大约 3 分钟

熵

信源熵（平均不确定度）： $H_{s}=-\sum _{i=1}^{n}p_{i}\log _{d}p_{i}$

条件熵（已知 X，关于 Y）： $\mathrm {H} (X|Y)=-\sum _{i,j}p(x_{i},y_{j})\log {p(x_{i}|y_{j})}=-\sum _{i,j}p(x_{i},y_{j})\log {\frac {p(x_{i},y_{j})}{p(y_{j})}}$

联合熵（X 和 Y 同时发生）： $\mathrm {H} (X|Y)=-\sum _{i,j}p(x_{i},y_{j})\log {p(x_{i},y_{j})}$

$H(X,Y) = H(X) + H(Y | X) = H(Y)+ H(X |Y)$

互信息代表随机变量彼此之间的相关性。

$I(X;Y)=\sum _{y\in Y}\sum _{x\in X}p(x,y)\log {\left({\frac {p(x,y)}{p(x)\,p(y)}}\right)},\,\!$

关于熵和互信息之间的关系只需要记下这张图：

信道容量： $\ C=max _{p(x)}I(X;Y)$ ，一般可以拿 $I(X;Y)$ 来变形

单位时间信道容量： $C_t=C/t$

BSC 信道（二进制对称 DMC 信道）： $C=1-H(ε)$ bit （ε 为转移概率）

二元擦除信道（两个输入的擦除是改到同一个值）： $C=1-a$ bit （a 为擦除概率）

定义如果信道转移矩阵的任何两行互相置换，任何两列也互相置换，那么称该信道是对称的。如果转移矩阵的每一行都是其他每行的置换，而所有列的元素 sum 相等，则称这个信道是弱对称的。

对于弱对称信道，C=log (Y 的取值个数) - H(转移矩阵的一行)

和信道：指在任一单位时间内随机地选用任一个而不能同时选用多个的信道。和信道中 $C=log(\sum 2^{C_i})$

(M, n) 码指的是 X 的 (码本长度，序列长度)。

定长编码
- 无失真： $R>H(X)$
- 输出信息率（码率）： $R=log m\cdot$ (编码后长度/编码前长度)，其中 m 为进制数
- 编码效率 $\eta=\frac{H(X)}R$

信道编码定理：对于离散无记忆信道，小于信道容量 C 的所有码率都是可达的。

Haffman 编码：构建 Haffman Tree 即可，非常简单。每次取两个最小的节点组成新的子树。约定每次概率较大的分配 0，较小的分配 1。
算术编码：直接把整个输入的消息编码为一个数
- 先对输入符号的概率进行估计
- 按照估计概率之比，对 0-1 的区间进行切分
- 每次取实际信息的一个符号，在符号对应的区间继续按照相同的比例切分
- 切分全部结束后，任取最终区间内的一点即为编码结果。最终可以将此小数转为整数；也可以转为二进制。

连续变量的熵 $h(X)=-\int_S f(x)log f(x)dx$

正态分布熵： $h(N(\mu,\sigma^2))=\frac12log(2\pi e \sigma^2) \ bits$

一般功率要求 $\frac1n\sum x_i^2\le P$

高斯信道： $Z_i\sim\mathcal{N}(0, N)$

$EX^2=P, EY^2=N$

$h(Y)\le\frac12log2\pi e(P+N)$

$h(Z)=\frac12log2\pi eN$

$C=\frac12log(1+\frac{P}{N})$ ，最大值在 $X\sim\mathcal{N}(0, P)$

并联高斯信道容量 = sum