离散无失真信源编码定理

定长编码定理

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

R = \frac{K}{L} lo g_{2} m \geq H (X) + ϵ, ϵ > 0

R 定义为信息率

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

反之，当

\frac{K}{L} lo g_{2} m \leq H (X) - 2 ϵ, ϵ > 0

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

编码效率

η = \frac{H ( X )}{R} = \frac{H ( X )}{\frac{K}{L} lo g m} = \frac{H ( X )}{H ( X ) + ϵ}

可以证明，只要：

L \geq \frac{σ [ I ( a _{i} )]}{ϵ ^{2} δ}

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

变长编码定理

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

码字平均长度

\frac{L H ( X )}{lo g _{2} m} \leq \overline{K} \leq \frac{L H ( X )}{lo g _{2} m} + 1

码字平均信息率：

H (X) \leq R = \frac{K}{L} lo g_{2} m \leq H (X) + ϵ

判断码字是否能分离

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

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

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

m 元长度为 $k_{i}$ 的异前置码存在的充要条件是

i = 1 \sum n m^{- k_{i}} \leq 1

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

三种编码方式

所有信源符号按照概率从大到小的顺序排好序

香农编码

香农编码的编号是从 $p (a_{0}) = 0$ 开始，使用累加概率（加到 j-1 而不是 j）

- lo g_{2} p (a_{i}) \leq k_{i} < 1 - lo g_{2} p (a_{i})

最终的编码过程通过截取二进制的小数后 $k_{i}$ 位来实现

每次截取的时候都不损失的时候效率最高

from math import *
 
a = [0.2, 0.19, 0.18, 0.17, 0.15, 0.1, 0.01]
 
a = sorted(a, reverse=True)
print("H:", sum([-i*log2(i) for i in a]))
 
now = 0
for i in a:
    l = ceil(-log2(i))
    binary_representation = f"{floor(now * (2**l)):b}"
    print(i, binary_representation.zfill(l), l, sep='\t')
    now = now + i

费诺编码

按照编码进制数分组，每一组概率尽可能相等，从而划分码元。

一般来说效率比香农高，在每次分组的时候都能分成两个相等的情况效率最高

哈夫曼编码

从两个最小的开始构造哈夫曼树，读取码字的时候，需要从根向叶子节点读取，此时编码为可分离的异前置码

赫夫曼编码并不唯一，合并后的新符号排在靠前的位置可以使重复编码次数变少，短码得到充分利用。

在赫夫曼编码中，当多个符号的概率相等时，合并顺序会影响码长的分布。若合并后的信源符号被优先排列在缩减序列的前面，后续合并步骤中这些符号会被更早处理，从而可能生成更短的码字。这种策略通过减少再次合并的次数，优化了码长分配的紧凑性。

🪴 Cyril

探索

无失真离散信源编码

目录