无噪声编码定理

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

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

证明机制 ​

变长 converse 将码长的 Kraft 和归一化成分布，再用KL 非负性理路KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。得到 $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 不等式理路Fano 不等式Fano's inequality用估计错误概率上界条件熵，从而把信息不足转化为推断下界。：若 ${\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 是两项不同的资源率。

若两个编码器分别看到相关源，而译码器同时收到两边描述，独立编码并不要求分别支付两个边缘熵。Slepian–Wolf 定理理路Slepian–Wolf 分布式无损压缩定理Slepian-Wolf theorem两个相关离散无记忆源分别编码、共同译码时，条件熵与联合熵精确给出无损压缩速率区域。以两个条件熵下界和一个联合熵总率界刻画可达区域；随机分箱让译码器利用相关性，而编码器运行时仍无须互看数据。

算术编码区间理路算术编码的区间与可译性Arithmetic coding · 算术区间编码按条件概率嵌套半开区间，从整个二进制小区间包含关系构造可译码字，给出ABABA的有理数轨迹。把已知或共同预测的条件概率逐步变成嵌套区间；有限精度实现理路整数算术编码与延迟位Finite-precision arithmetic coding · Integer arithmetic coding · Arithmetic coder renormalization以闭整数区间实现E1/E2/E3重归一化，精确规定频数上界、初始填位、underflow延迟位与终止。另行承担整数舍入、延迟位和终止。二者接在本页熵界之后，而不是把渐近存在性换成任意短文件必然变小的承诺。完整文件实验把模型表、EOF、guard和填充一并计入，可检验理论码长与实际字节数之间的接口。