信源码

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

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

层级的证明机制 ​

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

可复算例：平均长度 ​

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

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

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

两个严格反例 ​

集合 $\{0,01,10\}$ 的三个码字互异，所以码非奇异；但码流 010 可解析为 0|10 或 01|0，因此不是唯一可译。集合 $\{0,01\}$ 是唯一可译的，却不是前缀码：0 是 01 的前缀，读到 0 时还不能立即输出。它的唯一性可从右向左验证：每个 1 必须与前一个 0 配成 01，其余 0 各自成码字，因而合法码流没有第二种分解。于是三层条件不能混用。

空码字需要另查传输约定。集合 $\{\epsilon \}$ 在集合意义上前缀自由，但即使源只有符号 $a$，令 $c(a)=\epsilon$ 也会使 $c^{\ast }(a)=c^{\ast }(aa)$，不满足本页的未知长度串联唯一可译性。只有外部已给定符号数或约定恰发送一个源块时，单一可能消息才可用空字表示；该外部信息不计入这里的码长。若另有码字，空字还会成为它的前缀。码本、概率模型和文件头的传输成本也不包含在 $L(c)$ 中，短消息时这些开销可能主导。

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

前缀码理路前缀码Prefix-free code码字互不为前缀并保留单射源标签的编码；正码长时可即时译码。提供即时解析，Kraft–McMillan 不等式刻画整数码长的可行性，Huffman 算法理路Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。在已知有限分布的逐符号前缀码中最小化 $L(c)$。无噪声编码定理理路无噪声编码定理Source coding theorem · Noiseless coding theorem独立同分布信源的无损压缩平均码率可以逼近但不能低于其熵。再把对象换成长块，说明每符号平均长度可以逼近熵。

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

完整文件长度的另一条计数边界 ​

平均码长 $L(c)$ 针对给定映射和分布，不是完整文件长度。若一个编码器从文件本身学习码表，又只发送码字而不传表，译码端缺少恢复映射的信息。把全部可供译码的信息合在一起，才得到一个完整的编码函数 $E$；无损要求存在 $D$ 使 $D(E(x))=x$，因此 $E$ 必须单射。

固定输入位长 $n\ge 1$，共有 $2^n$ 个输入，而所有长度严格小于 $n$ 的二进制串总共只有

所以任何覆盖全部 $n$ 位串的完整无损编码，都不可能让每个输入严格变短；至少一个输出长度不小于 $n$。这条有限计数结论甚至不要求逐符号、前缀或概率假设，也不与特定分布的平均节省冲突。若把码表或外部共享信息藏在另一个通道里，就改变了这里“全部描述”的计费对象。

可实际复算的例子是五字节 ABABA。为A、B、EOF取规范码 0,10,11，正文只用7位，加EOF后9位；但完整HUF1文件理路压缩流封装与完整成本Compressed stream framing · 压缩文件的终止与填充把模型、有效位、EOF、guard和字节填充写成可检查文件语法，核算短文件的实际总长及拒绝路径。还需要14字节固定头、9字节码长表和7位字节填充，总共25字节。这里原文件40位、完整编码200位；“正文只用7位”与“这个短文件变大”同时成立。若事先共享码表，可在多条消息间摊销描述，但必须说明共享信息和消息边界的来源。

压缩流终点实验提供真实HUF1/ARC1文件和逐符号解码证据；它把模型成本、结束事件、有效位及寄存器尾位分账，不改变本页的非奇异、唯一可译、前缀自由层级。