2.4 限失真信源编码定理

之前讨论的都是无失真编码，为了达到无失真，往往需要花费巨大的代价，同时，在很多种情况下，人们并不需要完全的无失真，接近信源发出的消息就能够满足要求。例如，在一块较小的手机屏幕上，2K分辨率和1K分辨率对于人眼来说并没有多大区别；用普通耳机听音乐，高品质音乐和稍低品质的音乐对人的耳朵来讲差别也不是很大；看电影时，由于人眼的视觉暂留特点，每秒24帧图像和36帧图像观看感受差别不是很大。但是数据量却差别很大。这就是说，在许多应用场景下，失真是可以允许的，可以节约很多成本，并大大提高通信的效率。但是在允许失真的前提下，这个失真度如何把握？如何对失真进行描述？信息率失真函数回答了这些问题。香农提出的限失真编码定理定量地描述了失真，研究了信息率和失真之间的关系，已经成为量化、数据转换等现代通信技术的理论基础。本节简单介绍相关理论的基本原理，以方便读者后续章节的学习。

2.4.1 信息率失真函数

实际应用中，信号有一定程度的失真是可以容忍的。但是当失真超出某一限度后，信息质量将严重受损，甚至无法使用。要规定失真限度，必须先有一个定量的失真测度。因此引入了失真函数的概念。

1.失真函数

设离散无记忆信源X，X={x₁，…，x_r}，其概率分布为P（x）=[P（x₁），…，P（x_r）]。信源符号通过信道传输到某接收端，接收端的接收变量Y={y₁，…，y_s}。如图2-3所示。

对应于每一对（x，y），指定一个非负的函数

为单个符号的失真函数（失真度），用来测量信源发出一个符号x_i，在接收端收到一个符号y_j所引起的误差和失真。

很明显，如果x_i=y_j，说明发送和接收之间没有失真，故d（x_i，y_j）=0，反之，如果x_i≠y_j，则意味着出现了失真，d（x_i，y_j）的值不为0。

由于信道输入符号集X={x₁，…，x_r}有r种符号，输出符号集Y={y₁，…，y_s}有s种符号，因此d（x_i，y_j）就有r×s个。按照x_i（i=1，…，r）和y_j（j=1，…，s）的对应关系，排列为一个r×s矩阵，得到

称之为失真矩阵D。

接下来看几个常见的失真函数。

（1）汉明失真

信源和信宿的符号集合相同，每个符号的交叉传输概率相等，就是说当再现的接收符号与发送的信源符号相同时（i=j），不存在失真，失真度为0；当接收符号与发送符号不同时，失真存在并且都为常数1。即

那么它的失真矩阵为r×r矩阵

该矩阵具有对称性，用汉明矩阵来度量失真的信源称为离散对称信源。

当r=2时，则为二进制删除信道，有

它表示发送信源符号0（1）同时接收符号也是0（1）时，认为无失真，反之，发送0（1），接收1（0），则认为有失真并且两种错误等同。

【例2-4】设信道输入X={0，1}，输出Y={0，1，2}，失真函数为d（0，0）=d（1，1）=0，d（0，1）=d（1，0）=1，d（0，2）=d（1，2）=0.6，求D。

【解】

该信道为一个二元删除信道。

接下来将单符号失真函数推广到长度为N的信源符号序列失真函数。设信源输出符号序列X=X₁X₂…X_N，其中每个随机变量都取值于同一符号集X={x₁，…，x_r}，因此共有r^N个不同的信源符号序列x_i，接收符号序列为Y=Y₁Y₂…Y_N，同样其中每个随机变量都取值于同一个符号集Y={y₁，…，y_s}，一共有s^N个不同的接收符号序列y_j。由此可以得出如下定义：

设发送序列为X={x₁，…，x_r}，接收序列为Y={y₁，…，y_s}，那么定义序列的失真度为

即信源序列的失真度等于序列中对应单个符号失真度之和，不同的（x_i，y_j），其对应的d（x_i，y_j）也不同，矩阵形式的D（N）为r^N×s^N矩阵。

【例2-5】设信源输出序列X=X₁X₂X₃，其中每个随机变量均取值于X={0，1}。经过信道传输后的输出为Y=Y₁Y₂Y₃，其中每个随机变量都取值于Y={0，1}。定义失真函数d（0，0）=d（1，1）=0，d（0，1）=d（1，0）=1，求失真矩阵D（N）。

【解】根据序列失真函数定义，可以得到：

以此类推，可以得到失真矩阵为

（2）平方误差失真

失真函数定义为

其中i，j=1，2，…，r。其失真矩阵为

这意味着幅度差值大要比幅度差值小所引发的失真更严重。

【例2-6】设信道r=s=3，输入X={0，1，2}，输出Y={0，1，2}，求平方误差失真矩阵D。

【解】

2.平均失真度与保真度准则

d（x_i，y_j）只能表示两个特定符号x_i和y_j之间的失真，为了表示信道平均每传递一个符号所引起失真的大小，定义平均失真度为失真函数的数学期望，即d（x_i，y_j）在X和Y的联合概率空间P（X|Y）中的统计平均值：

其中，E[·]表示求期望。

如果已知信道传递概率为，按照数学期望的定义

可以看出，平均失真度描述了在平均意义上信源在某一信道传输下的失真大小。

上面是单符号信源的失真度和平均失真度。对于单符号离散无记忆信源X={x₁，…，x_r}，其N次扩展信源为X^N=X₁X₂…X_N，在信道中的传递作用相当于单符号离散无记忆信道的N次扩展信道，输出同样是一个随机变量序列Y^N=Y₁Y₂…Y_N。其输入有r^N个不同符号：

信道输出共有s^N个不同符号

那么N次扩展信道的失真函数为

其N次扩展信道的平均失真函数为

那么单个符号的平均失真度（信源平均失真度）为

当信源与信道都是无记忆时，N次扩展信源的平均失真度为

其中表示信源序列中第k个分量的平均失真度，如果信源是平稳信源，那么

于是

也就是说，离散无记忆平稳信源通过无记忆信道，其信源序列的平均失真度等于单个符号平均失真度的N倍。

如果平均失真度不大于所允许的失真D，称之为保真度准则。即：

同样，N维信源序列的保真度准则如下：

即离散无记忆N次扩展信源通过离散无记忆N次扩展信道的平均失真度不大于单符号信源通过单符号信道的平均失真度的N倍。

3.信息率失真函数

对于单符号信源和单符号信道在信源给定并定义了具体的失真函数以后，人们总希望在满足一定失真的情况下，使传送信源必须传给收信者的信息传输率R越小越好，从接收端来看，就是在满足保真度准则的条件下，寻找再现信源消息所需的最低平均信息量，即平均互信息I（X；Y）的最小值。设B_D是满足保真度准则的试验信道集合，由于平均互信息是信道传递概率）的下凸函数，因此在B_D集合中，极小值存在，这个最小量，即平均互信息I（X；Y）的最小值。设B_D是满足保真度准则的试验信道集合，由于平均互信息是信道传递概率P（y_j |x_i）的下凸函数，因此在B_D集合中，极小值存在，这个最小值就是在满足保真度准则的条件下，信源传输的最小平均信息量，称为信息率失真函数或者率失真函数。其表达式为

那么对于离散无记忆信源的N次扩展信源和离散无记忆信道的N次扩展信道，其信息率失真函数为

对于离散无记忆平稳信源，可以得到

研究信息率失真函数是希望在已知信源和允许失真度的条件下，使得信源必须传送给用户的信息量最小。这个问题就是在一定失真度条件下，尽可能用最少的码符号来传送信源消息，使信源消息尽快传送出去，以提高通信的有效性。

（1）离散信源的信息率失真函数

对于基本离散信源来说，求信息率失真函数与求信道容量类似，都是在有约束条件下求平均互信息极值的问题，区别在于不同的约束条件。信道容量是求平均互信息的条件极大值，而信息率失真函数是求平均互信息的条件极小值。

已知信源概率分布函数p（x_i）和失真函数d（x_i，y_i），在满足保真度准则的条件下，一般试验信道P_D当中选择，使平均互信息

值最小，并且使

以及

（2）连续信源的信息率失真函数

按照离散信源失真函数、平均失真函数和信息率失真函数的定义，定义连续信源平均失真度为

式中，d（x，y）为连续信源失真函数，p（x）为连续信源X的概率密度，）为信道传递式中，d（x，y）为连续信源失真函数，p（x）为连续信源X的概率密度，p（y|x）为信道传递概率密度。

平均互信息为

式中

并且

定义B_D是满足保真度准则的所有广义无扰信道集合，那么连续信源信息率失真函数为

式中，Inf指下确界，相当于离散信源中求极小值，连续集合中可能不存在极小值，但是一定存在下确界。所谓下确界，是在“下界”的基础上定义的，指的是任一数集E，我们称E的最大下界为E的下确界。

2.4.2 限失真信源编码定理

设离散无记忆信源的输出变量序列为X=（X₁X₂…X_L），该信源失真函数为R（D），并选定有限失真函数，对于任意允许平均失真度D≥0，和任意小的ε＞0，当信息率

只要信源序列长度L足够长，一定存在一种编码方法C，使其译码后的平均失真小于或等于D+ε，即

反之，若

则无论采用什么样的编码方法，其平均译码失真必大于D，即

这就是限失真信源编码定理，又称为保真度准则下的离散信源编码定理。该定理可以推广到连续平稳无记忆信源的情况，证明略。

可以看出，信息率失真函数R（D）是在允许失真度为D的情况下信源信息压缩的下限。当信源给定后，无失真信源压缩的极限值是信源熵H（S）；而限失真信源压缩极限值是信息率失真函数R（D）。