信源编码定理

信源编码定理是信息论的一项基础性成果，确定了离散信源能够以多高的效率进行表示。它确立了信息熵作为在指定解码条件下进行压缩时，每个信源符号所需比特数的极限。克劳德·香农在其 1948 年的论文《通信的数学理论》中提出了这一定理。该定理有几种密切相关的表述，分别适用于精确恢复的变长编码和错误概率趋于零的定长编码。区分这些表述对于理解定理的适用范围至关重要。(people.math.harvard.edu)

信源模型与熵

在基本模型中，信源独立地产生符号 $X_1,X_2,\ldots$，这些符号在有限字母表 $\mathcal X$ 上服从相同的概率分布 $p$。每个符号都是一个随机变量。由于先前的符号不会影响后续符号出现的概率，这种信源称为无记忆信源。其熵为

其中约定 $0\log_2 0=0$。熵是自信息 $-\log_2p(X)$ 的期望值。它衡量的是平均不确定性，而非消息的含义或用途。对于独立符号，联合熵满足 $H(X_1,\ldots,X_n)=nH(X)$。(people.math.harvard.edu)

若 $m$ 个符号服从均匀分布，其熵为 $\log_2m$。符号出现的概率不相等时，通常可以缩短平均表示长度：常见符号可以分配较短的码字，罕见符号则分配较长的码字。该定理精确表达了这一直观认识，但并不要求每一条消息都变得更短。(isl.stanford.edu)

精确恢复的变长编码

对于无损数据压缩，解码器必须精确恢复编码前的输入。若码字的任意串接都只有一种解释，则该符号编码是唯一可译码。前缀码满足更强的条件：任何码字都不是另一个码字的前缀；因此，解码这类码字时无需等待后续码字。(ocw.mit.edu)

令 $\ell(x)$ 表示分配给符号 $x$ 的二进制码字长度，并令

表示其期望长度。任何唯一可译的二进制符号编码都满足 $L\ge H(X)$，并且存在满足以下条件的前缀码：

对于出现概率为正的符号，选择 $\ell(x)=\lceil-\log_2p(x)\rceil$，即可得到上述上界。这些码长满足克拉夫特–麦克米伦不等式，从而保证存在相应的前缀码。(ocw.mit.edu)

将 $n$ 个独立符号组成的块进行编码，可以实现满足以下条件的期望块码长 $L_n$：

因此，由码字长度必须为整数而产生的额外开销，按每个符号计算可以任意小。这一结果针对的是各条消息的平均情况：出现概率极低的块可能需要长得多的码字。(web.stanford.edu)

错误概率趋于零的定长编码

另一种表述将每个块 $X^n=(X_1,\ldots,X_n)$ 编码为 $M_n$ 条消息中的一条。其码率约为每个信源符号 $(\log_2M_n)/n$ 比特。解码器输出估计值 $\widehat X^n$，块错误概率为

对于有限字母表上的无记忆信源，任何码率 $R>H(X)$ 都允许构造一系列编码，使 $P_e^{(n)}\to0$。反之，要使错误概率趋于零，渐近码率必须至少为 $H(X)$。因此，熵是可实现码率的下确界；一般而言，该定理并不保证在恰好等于这一边界的码率下，错误概率也能趋于零。(isl.stanford.edu)

与精确恢复的变长编码不同，这种表述允许某些块无法被正确恢复，但要求这些块的总概率趋于零。如果要求定长编码能够区分每一个可能的块，那么起决定作用的将是字母表中具有非零概率的符号数量，而不只是按概率加权得到的熵。(ocw.mit.edu)

典型序列与证明

证明的核心思想是渐近均分性质。对于独立同分布的符号，由大数定律可得

这里的收敛是依概率收敛。因此，绝大部分概率质量集中在一个典型集中，其中各序列的概率近似为 $2^{-nH(X)}$。(theory.stanford.edu)

给定一个很小的容差 $\varepsilon>0$，将满足以下条件的块定义为典型块：

典型块的数量至多为 $2^{n(H(X)+\varepsilon)}$，因此，标识一个典型块大约需要 $nH(X)$ 比特。非典型块的总概率趋于零。反之，当 $R<H(X)$ 时，仅有 $2^{nR}$ 条消息的编码无法区分足够多的典型块，也就无法正确恢复覆盖大部分概率质量的块。这些计数论证既说明了相应码率的可实现性，也揭示了压缩的极限。(theory.stanford.edu)

算法与推广

对于已知的有限概率分布，霍夫曼编码能在所有二进制前缀码中使期望长度最小。将其用于块编码时，可以逼近熵界，但可能出现的块的数量会迅速增长。算术编码提供了一种顺序编码的替代方法，无需显式构造庞大的块编码树。该定理给出的是一个极限，而不是某种唯一的压缩算法，其本身也不保证较低的计算复杂性。(ocw.mit.edu)

对于有记忆信源，相关的量通常是熵率：

对于有限字母表上的平稳遍历信源，相应的编码结论以这一熵率代替单符号熵。因此，符号之间的依赖关系可以提供压缩机会，而将符号视为相互独立的模型无法利用这些机会。(people.math.harvard.edu)

信源编码应与有噪信道编码定理加以区分。信源编码去除统计冗余；信道编码则引入结构化冗余，以保障传输可靠性。两者的极限分别由信源熵和信道容量描述。如果允许受控的重建失真，则应采用率失真理论；它研究的码率约束不同于精确恢复或渐近无差错恢复的码率约束。(people.math.harvard.edu)

参考来源

1. A Mathematical Theory of Communicationpeople.math.harvard.edu
2. Lecture 2: Basic Information Theoryisl.stanford.edu
3. Chapter 2: Coding for Discrete Sourcesocw.mit.edu
4. 441S16: Course Notesocw.mit.edu
5. Information and Entropyocw.mit.edu
6. Probability - Lossy Compressiontheory.stanford.edu
7. Lecture 17: Huffman Codingocw.mit.edu
8. The role of the asymptotic equipartition property in noiseless source codingcollaborate.princeton.edu