3.3 信息率—失真理论

本节将从信息论的角度，对在有信息损失情况下数据压缩的理论极限做较为严谨的讨论。有信息损失情况下的数据压缩，就是将信源输出的数据转化为简化的或压缩的版本，而它的逼真度的损失不超出某一容限。它属于信源编码的范畴。

3.3.1 通信系统的一般模型

图3-3为常见的简单通信系统模型。我们将信道编、译码器归入信道，所以信道可以看成是无噪声的。

设信源产生离散随机过程｛Ur｝，r＝－∞，…，－2，－1，0，1，2，…，∞，即随机变量序列。u是信源符号U的样，u∈A，A是信源符号集。信源的特征可以用符号集A以及相应的概率分布表示。A可以是实数集，有限集，波形集，二维空间的亮度分布集，等等。概率特征可记为p，它是一族N维概率密度或分布函数。对信源还可能有平稳、遍历、独立、限功率等制约。

设信源为恒速率信源，它每Ts秒产生A的一个符号，即信源符号率Rs为1/Ts。信源编码器将每个长度为N的信源符号组编为K个编码符号组成的码字，编码符号取自于符号集E，我们将该码字姑且称为编码码字。若E中包含a个符号，则可能构成的编码码字数M＝aK。设信道为恒速率数字信道，它的传输率为Rc＝1/Tc，即每Tc秒传输一个编码符号。信源译码器将信道输出还原为长N的、其形式可以为信宿接受的符号组，该符号组称为还原码字。由于编码码字数为M，还原码字数也为M。还原码字串成随机过程｛Vr｝，v是V的样，v∈B。B可以等于A，也可以不同于A。为了使全系统有协同的符号流量，须使，即在信源产生N个符号的期间，信道传输K个符号，同时译码器输出N个符号。这将保证｛Vr｝与｛Ur｝有相同的符号率，只不过通常二者之间存在迟延而已。

如果编码器是数据压缩设备，则定义压缩率（或称码的符号压缩率）ξ＝K/N＝Ts/Tc＝Rc/Rs，即每个信源符号平均所需的编码符号数。

前面已说明，信道可以是无噪声的，因此可以认为信源序列｛Ur｝直接由编、译码器映射为信宿序列｛Vr｝。假设A中有l个符号，则可能出现的信源符号组u有lN种。如前所述，不论B是否与A相等，构成信宿序列的还原码字vm只有M种。为了达到压缩的目的，需要M＜lN。显然，用M种码字代表lN种信源符号组（二者长度均为N）有可能损失信息。

从信息论的观点，逼真度的损失可以用失真来度量。定量地表征失真的是失真函数d（u，v），它是一个二元函数，它确定在信宿用v代替信源输出u时失真的大小。所以，d（u，v）常为非负的实数集内的一个数值。由于U和V都是随机量，d（u，v）也是随机量，因此通常须定义平均失真：

这里〈 〉是在U∈A和V∈B上的数学期望。再考虑到信源输出和信宿输入均为随机序列，可定义长度为N的符号组的平均失真为

对于不同的r，dr（·）可以相同，也可以不同。我们将这种以单符号失真来衡量逼真度的准则记为Fd。

数据压缩的最基本问题是，在给定的一类编码器GE和一类译码器GD下，可能达到的最佳性能，或最小平均失真有多大。最小平均失真由下式计算：

其中下确界inf是在给定类的所有编、译码器上确定的。因为编、译码器的构造受到实际的限制，所以没有采用极小值，而取下确界。所谓某一类编、译码器是以它们的复杂性或压缩要求，或其他约束条件来划分的，例如，可以指所有的M级的量化器、所有的长度一定和符号集大小一定的分组码，或给定形式且输出熵受约束的所有的时不变滤波器等。

上述基本问题也可以逆向提出，即在给定一定的逼真度，或平均失真不超出D的条件下，所需传输的最低信息率（按每信源符号计）有多大，从而再据此设计编、译码器。信息论的有关基本定理是从这个角度出发的，因为这样的命题更结合实际，也更严谨。

3.3.2 信息率—失真函数

信息率—失真理论，简称率失真理论，是信息论的一个分支，它研究信源的熵超过信道容量时出现的问题。香农在1948年的《通信的数学理论》中开始涉及这一问题，而Berger 1971年所著的《信息率失真理论》给读者提供了这方面的系统知识。

根据3.3.1节的讨论，设信源输出被分割成长度为N的符号组。我们希望每一个符号组（或向量）u∈AN通过编、译码被变换为一个在意义下最佳的v∈BN（即使为最小），其中u表示（u1，…，uN），v表示（v1，…，vN）。

对于给定的信源，p（u），u∈AN是确定的。对于每个指定的条件概率分布P（v|u），u∈AN，v∈BN，可以得到信宿的概率分布为

而UN和VN间的互信息为

因为p（u）是给定的，互信息量将随P（v/u）而改变，而p（v/u）反映了编、解码器的性能。现在可以提出这样一个问题，如果将平均失真限制在一个规定值D以下，I（UN；VN）至少要多大？也就是说，还原码字中至少要包含信源符号组的多少信息才能满足≤D？为了回答这一问题，需要定义信源[A，p]相对于Fd的率失真函数R（D），即

其中PD是满足的所有条件概率分布P（v/u）的集合，即

当信源为平稳、无记忆时，（3-21）式可以简化为

这就是说，为了使失真度不大于D，信源序列传送给信宿的最小平均信息率是R（D）。这个函数既依赖于信源的统计特性，也依赖于失真的度量，同时与编、解码器的类型p（v/u）有关。R（D）是在失真不大于D的情况下，对信源信息率压缩的理论极限。

可以证明，尽管在（3-21）式用min，而不用inf，R（D）是存在的；同时，R（D）在定义域内是单调递减的下凸函数。关于R（D）的其他性质，可参阅文献。对于离散信源，R（D）一般如图3-4示，其中H（p）为熵函数。

3.3.3 限失真信源编码定理

在实际的通信系统中，用来传送信源信息的信息率远大于R（D）函数所规定的值。那么，这个极限值是否能够达到或接近呢？下面介绍的编码定理将回答这个问题。

用G表示解码还原的字集G＝｛v1，v，…，vM｝，称G为长度N、字数为M的还原码，G的元素称为（还原）码字。现在用G对信源[A，p]的输出进行编、译码，即每个长度为N的信源符号组被映射为某一码字v∈G，以使dN（u，v）为最小，记此最小值为

G的平均失真为

式中，〈〉p表示在p（u）上的平均。因此，d（G）是随机产生的信源符号组u＝（u1，…，uN）以G中最近码字为近似时所产生的失真的统计平均值。

字数为M、长为N的还原码G的信息率通常定义为

这是显而易见的，因为还原码字v只有M种可能值，其最大可能信息率为log2M（bit/码字）。如果d（G）≤D，称G是D容许的。将字数最少的D容许码记为M（N，D）。

有了这些预备知识，我们可以给出如下的信源编码定理和它的逆定理，定理的证明可参考文献。

正定理 对于给定平稳离散无记忆信源[A，p]和单符号逼真度准则Fd，设相对于Fd的[A，p]的率失真函数为R（·）。那么，给定任意ε＞0和D≥0，可以找到正整数N，以使一个长度为N的（D＋ε）容许码存在，且其信息率R≤R（D）＋ε。也就是说，在N充分大时，以下不等式成立：

换句话说，失真接近于D、而信息率任意接近于R（D）的码是存在的。

逆定理 不存在信息率小于R（D）的任何D－容许码，即对于所有的N下式成立：

简单地说，当失真为D时，信息率不能小于R（D）。

现在考虑信源编码正、逆定理如何用于图3-3所示的系统。假设对这个系统的要求是信宿相对于Fd以失真D＋ε还原平稳离散无记忆信源[A，p]。编码器可以用（D＋ε）容许码，将每个长度为N的信源输出序列u映射为一个码字v，以使dN（u，v）为最小。因为正定理保证R＜R（D）＋ε，所以只要信道容量（以每信源符号计）满足

C＞R（D）＋ε（3-30）

编码器的输出就可以在译码器中以任意小的差错概率还原。图3-3中信道（可能包含信道编、译码器）输入、输出的符号则是无关紧要的，因为经过传输所增加的失真度为任意小，所以全系统仍以失真度D＋ε工作。另外，每个信源序列u映射为码字v是确定性的，所以信源译码器放在信道输出对上述结果并不产生影响。由此，可得下面的信息传输定理：

正定理 对于ε＞0，前述离散无记忆信源可以在容量C＞R（D）＋ε的任何离散无记忆信道的输出端还原，而失真度为D＋ε。

逆定理 前述离散无记忆信源不可能在信道容量C＜R（D）的任何离散无记忆信道的输出以失真D还原。

这两个定理表明，信源和信宿间在限失真D下的通信，要求信道容量为R（D）既是必要的，也是充分的。若一个系统在信道容量C＝R（D）时可使平均失真等于D，则这个系统是理想的。在理想系统中，信源编码和信道编码可以完全分开处理。信源编码在给定的信源和逼真度准则下谋求最佳码，而不管信道结构，只要容量相等，任何信道都可以应用。信源编码器的输出的熵在码字充分长时趋近于信道容量。根据信源的渐近等分性（AEP），在信源序列长度无限增大时，所有典型序列的概率和趋近于1，且每个序列的概率接近于相等，所以编码器输出的码字也是接近于等概率的（可以舍弃那些总概率接近于零的非典型序列）。当然，这里已经应用了遍历性，通常我们假设所讨论的信源是遍历的。这样，就允许信道编码器针对这些典型序列工作，而不管信源的细节；它只需建立信源码字和信道码字之间的一一对应关系。

以上的讨论只涉及平稳离散无记忆信源。对于其他信源的率失真理论，有兴趣的读者请参阅文献。