离散无失真信源编码定理

编码必存在理论下限：

$$K{\log }_{2}m\ge LH(X)$$

定长编码定理

有一个消息队列，每个符号熵 H，序列长 L，之后我们对这个消息编码，码序列有 m 个符号，长度 K：

$$R=\frac{K}{L}{\log }_{2}m\ge H(X)+ϵ,ϵ>0$$

R 定义为信息率，衡量平均每个原始信源符号在编码后所占用的编码空间，或者每个信源符号分配到的编码比特数

当 L 足够大的时候，必可让译码差错小于任意正数 $\delta$

反之，当

$$\frac{K}{L}{\log }_{2}m\le H(X)-2ϵ,ϵ>0$$

译码差错一定为有限值，当 L 足够大的时候，译码必定出错

编码效率

$$\eta =\frac{H(X)}{R}=\frac{H(X)}{\frac{K}{L}\log m}=\frac{H(X)}{H(X)+ϵ}$$

可以证明，只要：

$$L\ge \frac{\sigma [I(a_i)]}{{ϵ}^2\delta }$$

(上面是方差）那么，译码差错率一定小于任意正数 $\delta$

变长编码定理

对离散无记忆信源，消息长度 L，符号熵为 H(X)，对其进行 m 元变长编码，一定存在无失真的信源编码方法：

码字平均长度

$$\frac{LH(X)}{{\log }_{2}m}\le \overline{K}\le \frac{LH(X)}{{\log }_{2}m}+1$$

码字平均信息率：

$$H(X)\le R=\frac{\overline{K}}{L}{\log }_{2}m\le H(X)+ϵ$$

判断码字是否能分离

0 01 011 0111 这个看起来能够分离，不过要看后面一个，译码到当前位置的时候是不能做判断的（可分离，有延迟）

0 10 110 1110 这个就能只用看到当前位置就可以译码了（可分离，即时码，异前置码）

异前置码任何一个码字都不是其他码字的头部

$$\sum _{i=1}^n{m}^{-k_i}\le 1$$

• $n$ 信源符号的总数
• $m$ 编码使用的符号集合大小
• $k_i$ 第 $i$ 个信源符号对应码字的长度

这里取等表示的是每一个码字都放在叶子节点，即满树的情况（克拉夫特不等式）