信息论基础及应用第5章　信息率失真函数和限失真信源编码

第5章　信息率失真函数和限失真信源编码信息论基础及应用5.1.1系统模型和失真测度■试验信道输入：X，值域为符号集A:{a1,a2,…,ar}试验信道输出：Y，值域为符号集B:{b1,b2,…,bs}■X的概率分布为P(x)或P(ai),(i=1,2,…,r)Y的概率分布为P(y)或P(bj),(j=1,2,…,s)5.1.1系统模型和失真测度■d(ai,bj)——发出符号ai，收到bj所引起的误差或失真。其值的大小代表失真的大小；为0没有失真。 ■失真矩阵D定义为： ■失真函数人为规定，取决于实际需要、引起的损失和风险等。 定义5.1　对于每一对(ai,bj)，指定一个非负函数称d(ai,bj)为单个符号的失真度或失真函数。5.1.1系统模型和失真测度■汉明失真矩阵D为r阶方阵：■汉明失真认为：◆当接收与发送相同时，无失真和错误，失真度d(ai,bj)=0；◆当接收与发送不同时，存在失真，且失真相同，常取值为1。 定义5.2　离散对称信道（r=s）中，汉明失真定义为5.1.1系统模型和失真测度【例】二元对称信道（r=s=2），信源X的符号集为A:{0,1}，接收变量Y的符号集为B:{0,1}。◆在汉明失真定义下，失真矩阵为即：5.1.1系统模型和失真测度 定义5.3　对于每一对(ai,bj)，指定一个非负函数称d(ai,bj)为单个符号的平方误差失真度或平方误差失真函数。【例】三元对称信道（r=s=3），信源X和接收变量Y的符号集为A,B:{0,1,2}。◆在平方误差失真定义下，失真矩阵为5.1.1系统模型和失真测度 定义5.4　删除信道（s=r+1）中，接收符号bs是删除符号，则删除失真定义为【例A】二元删除信道（r=2，s=3），信源X的值域A:{0,1}，接收Y的值域B:{0,1,?}。◆在删除失真意义下，可得失真矩阵为:即：5.1.1系统模型和失真测度■D是：信源统计特性P(ai)（信源编码时，一般认为已知）、试验信道转移特性P(bj|ai)（由信源编码算法确定）、失真度d(ai,bj)（根据问题，人为给定）的函数。■当d(ai,bj),P(ai)确定后，D是P(bj|ai)（编码算法）的函数。 定义5.5平均失真度定义为单个符号失真度d(ai,bj)的数学期望，即5.1.1系统模型和失真测度■规定离散信源符号的平均失真度D′小于所允许的失真D，即：则D是允许失真的上界，并称上式为保真度准则。5.1.1系统模型和失真测度■单符号信源的失真度和平均失真度的概念推广——N维信源符号序列的失真函数。■信源端N维符号序列：X=(X1,X2,…,XN),共有rN种序列分量Xi的值域：A:{a1,a2,…,ar}信源端输出的N维随机事件：■收信端N维符号序列：Y=(Y1,Y2,…,YN),共有sN种序列分量Yi的值域：B:{b1,b2,…,bs}收信端输出的N维随机事件：5.1.1系统模型和失真测度 定义5.6N维序列失真度定义为序列失真矩阵为5.1.1系统模型和失真测度【例】信源序列X=(X1,X2,X3)，其分量的值域为A:{0,1}，经信道输出为序列Y=(Y1,Y2,Y3)，其分量的值域为B:{0,1}，◆汉明失真函数时，则由序列失真度定义可得◆同理可计算其它序列的失真度，◆序列失真矩阵D(N)为：5.1.1系统模型和失真测度 定义5.7N维信源符号序列的平均失真度定义为 定义5.8N维信源的平均失真度（单个符号的平均失真度）定义为■P(αi)——N维信源X的统计特性P(αiβj)——N维X和Y的联合概率P(βj|αi)——试验信道转移特性5.1.1系统模型和失真测度■可证明，信源和信道皆无记忆时，有：Dk——信源序列第k个分量的平均失真度■如果信源平稳、信道平稳，则：即离散无记忆平稳信源通过离散无记忆平稳信道，则其信源序列平均失真度等于单个符号平均失真度的N倍。■相应的保真度准则为：注：注意区分Dk和DN的不同。5.1.2　信息率失真函数的定义 定义5.9满足保真度准则的信道称为许可试验信道，所有许可试验信道的集合用BD表示。对于离散单符号信源和信道，有对于离散无记忆N次扩展信源和信道，有5.1.2　信息率失真函数的定义 定义5.10在满足保真度准则的许可试验信道的集合BD中，平均互信息最小值定义为信息率失真函数（率失真函数）：（离散单符号信源）（N次扩展信源）■可证明，信源和信道均为无记忆时，有：注：在信源概率分布、单个符号的失真度相同的条件下，对于不同的N，RN(D)是不同的。■由于平均互信息是下凸函数，率失真函数一定存在。5.1.2　信息率失真函数的定义■信道容量和信息率失真函数具有对偶性。（1）信道容量是指在信道固定前提下，选择一种信源概率分布P(ai)使信息传输率最大（求极大值）。是信道可靠传输的最大信息传输率。（2）信息率失真函数是在信源固定，满足保真度准则D′≤D条件下的信息传输率的最小值，是满足给定失真度条件下信源可以压缩的程度。5.1.2　信息率失真函数的定义■结论：（1）信道容量与信源无关，是信道特性的参量，不同的信道其信道容量不同。（2）信息率失真函数与信道无关，是信源特性的参量，不同的信源其信息率失真函数不同。■研究信道容量，使传输的信息量最大，错误概率任意小，以提高通信的可靠性。这是信道编码问题。■研究信息率失真函数，使信源输出的信息率尽可能小，以提高通信的有效性。这是信源编码问题。5.1.3　信息率失真函数的性质■由性质5.1的证明知，失真矩阵中每行至少有一个零元素时，信源的平均失真度Dmin=0，否则Dmin>0。■一般Dmin=0，表示信源不允许任何失真存在，R(0)=H(X)。■可证明，只有当失真矩阵中每行至少有一个零元素，并且每列最多只有一个零元素时，R(0)=H(X)。5.1.3　信息率失真函数的性质【续例A】求二元删除信道的信源的最小允许失真度。失真矩阵定义为:◆由性质5.1可知，最小允许失真度为◆满足条件的试验信道是一个无噪无损的试验信道，信道转移概率矩阵为：◆上述信道表征的是一一对应编码，此时5.1.3　信息率失真函数的性质【例】设信源X为：信宿Y的值域为B:{b1,b2}。失真矩阵为：◆由性质5.1可知，最小允许失真度为◆由性质5.1证明中式（5.23）知，达到Dmin的信道必须满足：有无穷多组解。且：5.1.3　信息率失真函数的性质 性质5.2R(D)是平均失真度D的∪形凸函数（下凸函数），即设D1和D2是两个任意平均失真度，取和，则 性质5.3R(D)是(Dmin,Dmax)区间上的连续和严格单调递减函数5.1.3　信息率失真函数的性质■信息率失真函数R(D)的典型曲线图：（1）R(Dmin)和R(Dmax)决定了曲线的两个端点，（2）在Dmin和Dmax之间R(D)是单调递减的下凸函数。连续信源时，，曲线不与纵轴相交。5.1.3　信息率失真函数的性质■信息率失真函数的两点解释：（1）信息率失真理论解决的问题，是计算满足失真要求的最小信道容量或信息传输率，以达到降低信道的复杂度和通信成本的目的。（2）R(D)为单调减函数，故存在反函数，即失真率函数D(R)（distortion-ratefunction）定义◆D(R)的物理意义：固定平均互信息I(X;Y)，选择信道的转移概率P(bj|ai)，使平均失真D最小，5.2离散信源的信息率失真函数的计算■求解信息率失真函数的问题描述：（1）已知P(ai)和P(bj|ai)时，I(X;Y)可以表示为（2）计算R(D)的优化问题可以表述为■有多种求解方法：拉格朗日乘子法、变分法、凸规划方法等。■但是，得到显式解析表达式比较困难。通常只能用参量形式来表示。■也采用迭代算法用计算机求解函数。■利用信源和失真函数的对称性，也可以方便求解一类。5.2.1利用信源的对称性计算信息率失真函数【例】设信源X为：输出Y的值域为B:{b1,b2,b3}。失真矩阵为：求信息率失真函数R(D)。解（1）确定R(D)的定义域。计算Dmin和Dmax如下：5.2.1利用信源的对称性计算信息率失真函数（2）确定转移概率P(bj|ai)。由于，信源X等概分布（对称）、失真函数具有对称性，因此，可推断最佳的转移概率函数也将对称。设：因为：因此，对于任何有限平均失真，必须β=0。5.2.1利用信源的对称性计算信息率失真函数（3）确定转移概率P(bj|ai)与失真度D的关系。计算平均失真度：解出：α=1-D，允许失真为D的试验信道为（4）计算输出符号的概率为：（5）计算信息率失真函数R(D)5.2.1利用信源的对称性计算信息率失真函数【例】设X是r元等概信源，其值域为A:{a1,a2,…,ar}；输出符号集为Y，其值域为B:{b1,b2,…,br}；求汉明失真度时的信息率失真函数R(D)。解（1）依题意，信源概率分布：汉明失真度：（2）确定R(D)的定义域。计算Dmin和Dmax如下：5.2.1利用信源的对称性计算信息率失真函数（3）确定转移概率P(bj|ai)。由于，信源X等概分布、汉明失真函数具有对称性，因此，可推断最佳的转移概率函数也将对称。设：（4）确定转移概率P(bj|ai)与失真度D的关系。计算平均失真度：解出：α=1-D，允许失真为D的试验信道为5.2.1利用信源的对称性计算信息率失真函数（5）计算输出符号的概率为：（6）计算信息率失真函数R(D)*5.2.2离散信源信息率失真函数的参量表达式■R(D)的优化表述为：■分析：极值的约束条件有r+1个，1个是保真度准则（平均失真约束），r个转移概率归一化约束，以及转移概率的非负性约束。*5.2.2离散信源信息率失真函数的参量表达式■拉格朗日乘子法求解，步骤如下：（1）引进一个新函数：S,μi,(i=1,2,…,r)——拉格朗日乘子（待定常数）（2）求Φ的偏导数，并置为零◆上式与优化约束等式得联立方程式（共有r+1个方程），解出P(bj|ai)和S,μi。（3）由信息率失真函数的定义式，计算R(D)。*5.2.2离散信源信息率失真函数的参量表达式■参量S形式的R(D)和D(R)表达式：经推导，得S——保真度条件的拉格朗日乘子。*5.2.2离散信源信息率失真函数的参量表达式■给出当S取某一数值时，计算R(D)和D(R)的步骤：（1）由下式计算出λi,(i=1,2,…,r)；（2）由下式求解出P(bj),(j=1,2,…,s)；（3）计算：（4）计算：*5.2.2离散信源信息率失真函数的参量表达式■P(bj)不能为负，所以参量S的取值有一定限制。■可证明，参量S是信息率失真函数R(D)的斜率。即且斜率S必为非正的、且是D的递增函数。■在D=Dmin处，R(D)的斜率有可能为-∞；当D>Dmax时，R(D)=0，其斜率为0。即：S∈(-∞,0)*5.2.2离散信源信息率失真函数的参量表达式【例】设二元信源：输出Y的值域为B:{b1,b2}。求汉明失真度时的R(D)。解（1）确定R(D)的定义域。计算Dmin和Dmax如下：（2）计算λ1,λ2。由公式得：解得：*5.2.2离散信源信息率失真函数的参量表达式（3）计算输出符号概率：P(b1),P(b2)。由公式得：（4）计算失真率函数D(R)。由公式得由上式解得：*5.2.2离散信源信息率失真函数的参量表达式（5）计算信息率失真函数R(D)。由公式得即：◆D相同时，信源分布越均匀，R(D)越大，信源压缩的可能性越小。◆反之，信源分布越不均匀，R(D)越小，信源压缩的可能性越大。5.3.1连续信源的信息率失真函数与性质 定义5.11连续信源的平均失真度定义为N维连续信源的平均失真度定义为Di——第i个连续分量的平均失真度。■连续信源X，值域为实数域R，概率密度为p(x)输出连续变量Y，其值域也为实数域R。■在X和Y之间为一个试验信道，转移概率密度为p(y|x)，平均互信息为：5.3.1连续信源的信息率失真函数与性质■若N维连续信源的各分量取于同一连续信源，则有：5.3.1连续信源的信息率失真函数与性质 性质5.4连续信源的R(D)是非负的，其定义域为0≤Dmin≤D≤Dmax；D<Dmin时，R(D)无意义；D>Dmax时，R(D)=0；且 性质5.5连续信源的R(D)是平均失真度D的∪形凸函数（下凸函数）。 性质5.6连续信源的R(D)是(Dmin,Dmax)区间上的连续和严格单调递减函数。5.3.2　高斯信源的信息率失真函数■高斯信源是一种工程上、理论上都常用的连续信源，输出为独立、同分布高斯随机变量。■在一般失真函数下，其率失真函数也是很难求得的。在平方误差失真测度下，可得到简单的闭式表达式。5.3.2　高斯信源的信息率失真函数■R(D)的特点：（1）允许失真大，R(D)小；D=σ2时，R(D)=0。（2）当D=σ2/4时，R(D)=1bit/自由度；即在允许D≤σ2/4时，每样本最少需用一个二元符号传输，也就是说，连续信号的幅度只需要采用二值量化。5.3.3　连续信源的信息率失真函数的界■一般的连续信源，难以得到简明的R(D)函数的表达式。但可以得到R(D)函数的界。■表明，在平方误差失真准则下，高斯信源有最大的R(D)值。结论：从数据压缩的角度，高斯信源是最难压缩的。5.4　限失真信源编码定理 定理5.3离散无记忆平稳信源的信息率失真函数为R(D)，只要使信息传输率R满足R>R(D)，且失真度有限，当信源序列长度n足够长时，一定存在一种编码方法，其译码失真≤D+δ（δ是任意小的正数）。反之，若R<R(D)，则无论采用什么样的编码方法，其译码失真必大于D。■信息率失真理论的基本定理——Shannon第三编码定理。■定理严格地证实了R(D)函数是在允许失真为D条件下，每个信源符号能够被压缩的最低值。5.4　限失真信源编码定理■Shannon第三编码定理只是码的存在性定理。可以分正定理和逆定理。严格地分述如下：5.4　限失真信源编码定理 定理5.4（限失真信源编码正定理）离散无记忆平稳信源的信息率失真函数为R(D)，且失真度有限。对于任意的D≥0,ε>0,δ>0，以及任意足够长的码长n，则一定存在一种信源编码C，其码字个数为而编码后的平均失真度d(C)≤D+δ。（R(D)以h为底，h为编码进制数）5.4　限失真信源编码定理 定理5.5（限失真信源编码逆定理）不存在平均失真度为D，平均信息传输率R<R(D)的任何信源编码。即对任意码长n的信源编码，若码字个数一定有d(C)>D。■表明，如果编码后R<R(D)，就不能在保真度准则下再现信源的消息。