信源码 | Codeboy's Blog

形式陈述

设源字母表为有限集合 $\mathcal X$ ，码字母表为 $\mathcal D$ ，其中 $|\mathcal D|=D\ge2$ 。逐符号变长信源码是映射

c:\mathcal X\longrightarrow\mathcal D^*,

把每个源符号映成有限字。码长 $\ell(x)=|c(x)|$ 是非负整数；若源符号服从分布 $P_X$ ，平均码长为

L(c)=\mathbb E[\ell(X)]=\sum_xp(x)\ell(x).

把 $c$ 按串联扩张为

c^*(x_1\cdots x_m)=c(x_1)\cdots c(x_m).

无失真逐符号码有三层常用条件：

它们满足严格层级

\text{前缀自由}\Longrightarrow \text{唯一可译}\Longrightarrow \text{非奇异},

反向一般都不成立。在标准串联模型中，前缀码与即时码是同一个层级，而不是两层不同条件。

长度 $n$ 的块码改用 $c_n:\mathcal X^n\to\mathcal D^*$ ，其每源符号平均长度是 $L_n/n$ 。单符号码长必须取整数，但块平均 $L_n/n$ 可以逐渐逼近非整数极限。

直觉

固定长度码给每个符号同样多的位置；变长码则让高概率符号走短路径、低概率符号走长路径，从而降低分布加权的平均长度。节省的前提是串联后仍能恢复边界与原符号，否则“短”只是把歧义藏进码流。

块码把 $n$ 个源符号视为一个超符号。虽然每个块码字长度仍为整数，除以 $n$ 后的整数舍入开销只有 $O(1/n)$ ；这正是单符号与渐近源编码结论之间的桥梁。

前缀码从左到右遇到第一个完整码字时就能确定首符号，删去它后归纳解析余串，因此唯一可译。唯一可译当然要求长度一的源串映射互异，所以必然非奇异。下面的反例说明两条逆命题都失败。

例子与边界

对概率 $(0.4,0.3,0.2,0.1)$ 的符号 $a,b,c,d$ ，取

c(a)=0,\quad c(b)=10,\quad c(c)=110,\quad c(d)=111.

码长为 $(1,2,3,3)$ ，平均长度

L=0.4(1)+0.3(2)+0.2(3)+0.1(3)=1.9\ \text{bit/符号}.

同一映射用于另一分布时，平均长度会改变；码本本身不带“1.9 bit”这一属性。

集合 $\{0,01,10\}$ 的三个码字互异，所以码非奇异；但码流 010 可解析为 0|10 或 01|0，因此不是唯一可译。集合 $\{0,01\}$ 是唯一可译的，却不是前缀码：0 是 01 的前缀，读到 0 时还不能立即输出。于是三层条件不能混用。

空码字只适合单符号源；若还有另一代码字，空字会成为它的前缀并让任意串联产生歧义。码本、概率模型和文件头的传输成本也不包含在 $L(c)$ 中，短消息时这些开销可能主导。

若源有记忆，逐符号码忽略跨符号相关性；若允许重构误差，目标也不再是唯一恢复，而要另行指定失真度与容许失真。两种改变都超出这里的无失真逐符号层级。

推论与应用

前缀码提供即时解析，Kraft–McMillan 不等式刻画整数码长的可行性，Huffman 算法在已知有限分布的逐符号前缀码中最小化 $L(c)$ 。无噪声编码定理再把对象换成长块，说明每符号平均长度可以逼近熵。

有损源编码、通用编码和有记忆信源仍沿用“编码器—译码器—性能准则”的框架，但分别要补上失真、未知分布或熵率假设；不能把逐符号 Huffman 的结论直接搬过去。

参考资料

Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, §§5.1–5.4.
Robert G. Gallager, Information Theory and Reliable Communication, Wiley, 1968, §§3.2–3.4.
Claude E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal 27, 1948, Part I, §§9–10.