信源编码定理

Template:AboutTemplate:NoteTA 在信息论中，香农的信源编码定理（或无噪声编码定理）确立了数据压缩的限度，以及香农熵的操作意义。

信源编码定理表明（在极限情况下，随着独立同分布随机变量数据流的长度趋于无穷）不可能把数据压缩得码率（每个符号的比特的平均数）比信源的香农熵还小，又不丢失信息。但是有可能使码率任意接近香农熵，且损失的概率极小。

码符号的信源编码定理把码字的最小可能期望长度看作输入字（看作随机变量）的熵和目标编码表的大小的一个函数，给出了此函数的上界和下界。

陈述

信源编码是从信息源的符号（序列）到码符号集（通常是bit）的映射，使得信源符号可以从二进制位元（无损信源编码）或有一些失真（有损信源编码）中准确恢复。这是在数据压缩的概念。

信源编码定理

在信息论中，信源编码定理非正式地陈述为：

Template:Mvar 个熵均为 Template:Math 的独立同分布的随机变量在 Template:Math 时，可以很小的信息损失风险压缩成多于 Template:Math bit；但相反地，若压缩到少于 Template:Math bit，则信息几乎一定会丢失。

码符号的信源编码定理

令 Template:Math 表示两个有限编码表，并令 Template:Math 和 Template:Math （分别）表示来自那些编码表的所有有限字的集合。

设 Template:Mvar 为从 Template:Math 取值的随机变量，令 Template:Math 为从 Template:Math 到 Template:Math 的唯一可译码，其中 Template:Math。令 Template:Mvar 表示字长 Template:Math 给出的随机变量。

如果 Template:Math 是对 Template:Mvar 拥有最小期望字长的最佳码，那么(Shannon 1948)：

$\frac{H(X)}{{\log }_{2}a}\le 𝔼S<\frac{H(X)}{{\log }_{2}a}+1$

证明：码符号的信源编码定理

对于 Template:Math 令 Template:Math 表示每个可能的 Template:Math 的字长。定义 $q_i=a^{-s_i}/C$，其中 Template:Mvar 会使得 Template:Math。于是

$\begin{array}{cc}H(X)& =-\sum _{i=1}^n{p}_i{\log }_2{p}_i\\ & \le -\sum _{i=1}^n{p}_i{\log }_2{q}_i\\ & =-\sum _{i=1}^n{p}_i{\log }_2{a}^{-s_i}+\sum _{i=1}^n{p}_i{\log }_{2}C\\ & =-\sum _{i=1}^n{p}_i{\log }_2{a}^{-s_i}+{\log }_{2}C\\ & \le -\sum _{i=1}^n-s_i{p}_i{\log }_{2}a\\ & \le 𝔼S{\log }_{2}a\\ \end{array}$

其中第二行由吉布斯不等式推出，而第五行由克拉夫特不等式推出：

$C=\sum _{i=1}^n{a}^{-s_i}\le 1$

因此 Template:Math.

对第二个不等式我们可以令

$s_i=\lceil -{\log }_a{p}_i\rceil$

于是

$-{\log }_a{p}_i\le s_i<-{\log }_a{p}_i+1$

因此

$a^{-s_i}\le p_i$

并且

$\sum a^{-s_i}\le \sum p_i=1$

因此由克拉夫特不等式，存在一种有这些字长的无前缀编码。因此最小的 Template:Mvar 满足

$\begin{array}{cc}𝔼S& =\sum p_i{s}_i\\ & <\sum p_i(-{\log }_a{p}_i+1)\\ & =\sum -p_i\frac{{\log }_2{p}_i}{{\log }_{2}a}+1\\ & =\frac{H(X)}{{\log }_{2}a}+1\\ \end{array}$