块编码

• 参考：拆分-第5章-概率

• 动画：manim community

现在需要设计一个用于传输学生成绩的信源，符号是 A、B、C、D 和 E。怎么设计更高效呢？

在编码信息时，表示每个符号所需的位数应尽可能接近符号数量的对数（以2为底），即log2​(n)。这可以确保存储和传输的效率。

如果我们使用固定长度编码，每个符号需要用相同的位数表示。我们需要3位来表示每个符号（因为22=4 不够， 23=8 才够）。然而，3比特是多余的。因为假设我们不知道每个符号出现的概率，熵最多为 log2​(5)≈2.32 比特。

如果我们将符号分组，可以有效提升编码效率。

例如，将两个符号一起编码，则有5×5=25种符号组合，我们需要5位来表示这25种组合（因为24=16 不够， 25=32 才够）。在这里，5位用于2个符号，平均每个符号 2.5 位。

该表格完整地涵盖了从符号"AA"到符号"EE"的所有组合，及其相应的二进制编码。

如果将三个符号一起编码，则有5×5×5=125种符号组合，我们需要7位来表示这125种组合（因为26=64 不够， 27=128 才够）。在这里，7位用于3个符号，平均每个符号 2.33 位。

log2​(5)≈2.32 位是每个符号所需的理论最小平均位数。用3位表示单个符号时，效率要低得多（3位对比2.32位）。通过符号分组，效率有所提高：

• 2个符号：每个符号2.5位（更接近2.32）

• 3个符号：每个符号2.33位（更接近2.32）

对比可知，通过将符号分组并作为一个单元进行编码，我们可以更接近每个符号所需的理论最小平均位数。

这种方法允许更高效的编码，特别是当符号数量不是2的幂时。

然而，上述编码方式假设成绩是均匀分布的，但实际上成绩分布是有规律的。那么，有没有更高效的编码方式呢？