无噪声编码定理

零错误变长码给每个源块一个码字，平均长度受熵下界控制；对数概率向上取整只多花不到一 bit/块。固定长度码没有能力给所有低概率块都分配索引，于是只编码承载绝大多数质量、大小约为 $2^{nH}$ 的集合，并把其余块计作错误。

这两个版本的“无损”量词不同：变长版本对每个正概率块都可逆但统计平均长度；固定长度版本固定每块资源但允许小概率失败。把它们合成一句“熵就是压缩长度”会丢掉码型、误差与块长。

证明机制 ​

变长 converse 将码长的 Kraft 和归一化成分布，再用 KL 非负性得到 $L_n\ge H(X^n)$；Shannon 长度满足 $2^{-\ell (x^n)}\le P_X^n(x^n)$，故 Kraft 和至多一，并由取整直接得到上界。

固定长度 achievability 使用AEP公理库渐近等分性质Asymptotic equipartition property · AEP离散无记忆源的长序列每符号信息量几乎必然收敛到熵。：为弱典型集公理库弱典型集Typical set · Weak typical set · Weakly typical set单位自信息接近熵、总概率趋近一的弱典型序列集合。内的块编号，典型集大小在 $R>H(X)$ 时最终不超过 $2^{nR}$，错误只发生在非典型集，故趋于零。Converse 可用 Fano 不等式：若 ${\hat{X}}^n$ 是译码结果，则

除以 $n$ 并令错误趋零，即得 $R\ge H(X)$。

可复算例：Bernoulli$(0.9)$ ​

单字母熵为

二符号的任何单符号二元前缀码都需要长度 $(1,1)$，所以平均仍为 $1$ bit/符号。对 $n=100$ 的超符号使用 Shannon 码，定理直接给

这展示了块编码如何摊薄整数开销。固定长度版本若选 $R=0.5>H(X)$，只保证存在一列错误趋零的码；它没有从这条不等式自动给出 $n=100$ 时的错误率。

边界与失败情形 ​

零错误固定长度码必须覆盖整个支持。只要 Bernoulli 参数在 $(0,1)$，长度 $n$ 的支持仍有 $2^n$ 个块，所以零错误固定速率不能低于 $1$ bit/符号；低到 $H(X)$ 需要变长平均，或固定长度下容许渐近消失的错误。

有记忆源通常应把 $H(X_1)$ 换成熵率

并补充平稳、遍历或信息稳定性条件。未知分布、码本传输、计算复杂度、随机访问和格式头也不属于基本定理的成本模型。

Huffman 编码公理库Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。精确优化已知有限分布的逐符号前缀码，块 Huffman 与算术编码则减少整数冗余。允许重构失真后，极限由率失真函数公理库率失真函数Rate-distortion function在允许期望失真不超过 D 时，所有重构信道互信息的下确界。取代熵。

若压缩结果还要通过噪声信道，问题转到信道容量公理库信道容量Channel capacity对输入分布最大化输入与输出互信息所得的每次使用信息率。与有噪信道编码定理公理库有噪信道编码定理Noisy-channel coding theorem · Channel coding theorem低于离散无记忆信道容量的速率可实现任意小错误概率，而高于容量的速率不能可靠传输。：源每符号需要多少 bit 与信道每次使用能可靠承载多少 bit 是两项不同的资源率。