在允许一定程度失真的情况下,信源所需输出的信息率是可以压缩的。下面以具体实例加以证明,设信源X有2n种不同的符号,即X:{a1,a2,…,an-1,an,an+1,…,a2n},且该信源为等概信源,即有

若规定失真度为汉明失真度,即

如要求从平均的意义上不允许有失真,即允许平均失真度D=0,则必须用图9.2所示无噪信道进行传输,其平均交互信息量

图9.2　无噪信道

图9.3　有噪信道

由于这个信道的传递概率p(aj/ai)等于零或1,所以噪声熵H′(Y/X)一定等于零,则平均交互信息量

其中,随机变量Y的概率分布

则随机变量Y的熵

由式(9.9)可得,这个信道的平均交互信息量

式(9.8)和式(9.10)表明,正因为允许失真D=1/2,在满足保真度准则 ≤D的条件下,信道所需传递的平均交互信息量可从不允许失真,即D=0时的I(X;Y)=log2n下降到I′(X;Y)。

下面给出一个重要定理,不做证明

定理9.1　若信源X给定,则平均交互信息量I(X;Y)是信道转移概率P(Y/X):{p(bj/ai)(i=1,2,…,r;j=1,2,…,s)}的∪型凸函数。

式(9.11)所示R(D)称为给定信源X在规定失真度d(ai,bj)(i=1,2,…,r;j=1,2,…,s)、允许平均失真度为D时的信息率——失真函数。

下面讨论R(D)函数的定义域

1.Dmin和R(Dmin)

平均失真度D是信道转移概率的函数,也就是试验信道的函数,如何选择试验信道,使平均失真度 达到最小值?

定理9.2　设给定信源X的概率分布在P(X):{p(ai)(i=1,2,…,r)},规定失真度d(ai,bj)(i=1,2,…,r;j=1,2,…,s)。则允许平均失真度D的最小值

【证明】在图9.1所示通信系统中,设给定信源X的概率分布P(X):{p(ai)(i=1,2,…,r)},规定失真度

其失真矩阵为

现在的问题,就是以什么原则来选择合适的试验信道,使式(9.14)中的每一项都能取得最小值。

式(9.14)中的第i(i=1,2,…,r)项为

其中

是式(9.13)规定的失真矩阵[D]中的第i(i=1,2,…,r)行的s个元素。可以肯定,这s个元素中必有最小值。把这个最小值记为

这个最小值可能只有一个,也可能有若干个相同的最小值。设第i(i=1,2,…,r)行的第j′1,j′2,…,j′s列元素都是相同的最小值,即

其中,Ji:{j′1,j′2,…,j′s}

式(9.15)中的s个传递概率

是要寻找的试验信道的信道矩阵[P]中的第i(i=1,2,…,r)行的s个元素,是式(9.15)中为了求得最小值而可变动的因素。显然,为了使式(9.15)取得最小值,必须遵循这样的原则来选择试验信道的信道矩阵[P]中的第i(i=1,2,…,r)行的s个传递概率p(bj/ai)(j=1,2,…,s),这个原则就是:

按式(9.18)所示原则选择试验信道的信道矩阵[P]中的第i(i=1,2,…,r)行s个元素,式(9.15)可改写为

因为式(9.18)所示原则的实质,就是通过选择试验信道的信道矩阵[P]中的第i行的s个元素,保留失真矩阵[D]中第i(i=1,2,…,r)行中的最小值d(ai,bj),去掉所有比 d(ai,bj)大的元素,所以式(9.19)所得值,一定是式(9.14)中第i(i=1,2,…,r)项中的最小值。

把式(9.18)所示原则用于式(9.14)中r项的每一项,则可得到能使其每一项都取得最小值的试验信道的信道矩阵[P]中r行、s列的(r×s)个全部元素,即得到能使平均失真度 达到最小值的试验信道的(r×s)阶信道矩阵[P],从而由式(9.14)求得平均失真度的最小值

【证明】(1)充分性的证明

而第k(k=1,2,…,s)列中所有(r-1)个其他元素均等于零,即

这时,“在得知bk的前提下,推测al”的后验概率

而“在得知bk的前提下,推测ai(i≠l)”的(r-1)个后验概率

则试验信道的疑义度(www.daowen.com)

从而,通过试验信道的平均交互信息量

这表明,若人们规定的失真矩阵[D]中,每列只有一个最小值,所有满足保真度准则=Dmin的试验信道的平均交互信息量I(X;Y),均等于信源X的信息熵H(X)。根据信息率——失真率函数的定义,即证得

这样,定理的充分性就得到了证明。

(2)必要性的证明

若允许失真度D选取其最小值Dmin,且离散无记忆信源X的信息率——失真函数R(Dmin)等于信源X的信息熵H(X),即

下面再给出两个定理,证明请参考相关文献。

定理9.4　若离散无记忆信源X的信息熵为H(X),则R(Dmin)＜H(X)的充分必要条件是,规定的失真矩阵[D]的s列中,有些列存在两个或两个以上的最小值。

【例9.4】设给定信源X的信源空间为

其中,0＜p,q＜1;p+q=1

规定失真度为汉明失真度,即失真矩阵为

又因为式(9.39)所示的信道矩阵[P]每列只有一个非零元素1,所以

由式(9.40),得

2.Dmax和R(Dmax)

定理9.6　设给定信源X的概率分布P(X):{p(ai)(i=1,2,…,r)},规定失真度d(ai,bj)(i=1,2,…,r;j=1,2,…,s),则允许平均失真度D的最大值。

【证明】在图9.1所示通信系统中,当输入随机变量X和输出随机变量Y之间统计独立,即对所有的i(i=1,2,…,r)和j(j=1,2,…,s)都有

在式(9.45)中,对于每一个j(j=1,2,…,s)都有一个相应的

其中,

则式(9.48)可以改写为

由式(9.45)可知,要取式(9.45)的最小值,必须选择适当的p(b1),p(b2),…,p(bs)。由式(9.44)可知,选择p(bj)(j=1,2,…,s)就是选择适当的试验信道。若在式(9.44)所示的总的前提下,采用

则一定能使式(9.45)取得最小值,得

式(9.52)表明,对于给定信源X和规定的失真度,最大允许失真度

是由信源X的概率分布p(ai)(i=1,2,…,r)和规定的失真度d(ai,bj)(i=1,2,…,r;j=1,2,…,s)所确定的。

定理9.7　给定信源X的信息率——失真函数R(D)=0的充分必要条件是,允许失真度D≥Dmax。

【证明】(1)充分性证明。

根据信息率——失真函数R(D)的定义,即证得

这样,定理的充分性得到了证明。

(2)必要性证明。

对概率分布为P(X):{p(ai)(i=1,2,…,r)}的给定信源X和规定的失真度d(ai,bj)(i=1,2,…,r;j=1,2,…,s),若有

则满足保真度准则≤D的试验信道的平均交互信息量I(X;Y)=0,即输入随机变量X和输出随机变量Y之间一定统计独立,即一定有

试验信道的平均失真度

由式(9.47)可知

由式(9.59)和式(9.60)即可证得

最后以定理形式给出R(D)函数的数学特性,证明略。

定理9.8　给定信源X的信息率——失真函数R(D)是允许失真度D的∪型凸函数。

定理9.9　给定信源X的信息率——失真函数R(D)是允许失真度D的单调递减函数。

定理9.10　给定信源X的信息率——失真函数R(D)是允许失真度D的连续函数。