离散信源的限失真信源编码.ppt
离散信源的限失真信源编码现在学习的是第1页，共15页 设离散信源的符号集合设离散信源的符号集合X Xaa1 1，a a2 2，a aNN，且各个符号都在信道上，且各个符号都在信道上传输；信宿收到的符号集合传输；信宿收到的符号集合Y Ybb1 1，b b2 2，b bNN 若若X X和和Y Y消息符号集合相同，即消息符号集合相同，即X XY Yaa1 1，a a2 2，a aNN 当信源发出符号当信源发出符号X X a ai i ，而信宿收到符号，而信宿收到符号Y Y a aj j时，失真函数时，失真函数d(d(x xi i,y yj j)为：为：d(d(x xi i,y yj j)d(d(x x,y y)|)|x x a ai i ,y y a aj j 简化起见，简化起见，d(d(x xi i,y yj j)简写成简写成 d dij ij i ij j时，时，x x和和y y的消息符号都是的消息符号都是a ai i，收发之间没有失真，收发之间没有失真，d dij ij 0 0 ij ij时，发出符号时，发出符号a ai i，收到，收到a aj j，传输时出现失真，传输时出现失真，d dij ij 00 一般一般d dij ij值的大小表示失真的程度，表征了接收消息值的大小表示失真的程度，表征了接收消息y yj j与发送消息与发送消息x xi i之间之间的定量失真度的定量失真度d dij ij0 i0 ij j0 ij0 ij现在学习的是第2页，共15页 若若X X和和Y Y集合都由集合都由N N个不同符号构成的，那么可组成个不同符号构成的，那么可组成N N2 2个不同的个不同的(i,j)(i,j)对，对，相对应的失真函数也有相对应的失真函数也有N N2 2个个 d dij ij表示方法有两种，一是失真矩阵表示方法有两种，一是失真矩阵D D，二是消息传输图，二是消息传输图例：已知例：已知X XY Yaa1 1，a a2 2，且有，且有d d11 11d d22220 0，d d1212d d21211 1，用两种方法表，用两种方法表示失真函数示失真函数 解：失真矩阵解：失真矩阵D D为：为：消息传输图为：消息传输图为：现在学习的是第3页，共15页 为了估计全体信源发出的消息符号与接收符号之间的失真程度为了估计全体信源发出的消息符号与接收符号之间的失真程度,需要计算需要计算各个失真函数的统计平均值各个失真函数的统计平均值(数学期望数学期望)。平均失真函数定义为：。平均失真函数定义为：若若X X和和Y Y都是都是n n维矢量消息的集合，也可以定义两个矢量消息之维矢量消息的集合，也可以定义两个矢量消息之间的失真函数为：间的失真函数为：其平均失真函数为：其平均失真函数为：该式中该式中 是是n n维矢量的第维矢量的第r r个分量上的平均失真函数个分量上的平均失真函数现在学习的是第4页，共15页 二二.信息率失真函数信息率失真函数 当给定信源的各符号概率分布时，若要求平均失真函数不超过某个给定的当给定信源的各符号概率分布时，若要求平均失真函数不超过某个给定的值值D(D(即即D D为允许失真度为允许失真度)，这就需要对假想的试验信道的传输概率，这就需要对假想的试验信道的传输概率P(P(y yj j|x xi i)施施加一定的限制加一定的限制 先把先把P(P(y yj j|x xi i)集合的各种可能值代入式集合的各种可能值代入式 求出各个求出各个 ，再根据，再根据 ，把，把P(P(y yj j|x xi i)分成两类分成两类 的一类用的一类用P PD D表示，表示，P PD D是能使实际失真在允许失真度范围内的是能使实际失真在允许失真度范围内的那些假想试验信道的那些假想试验信道的P(P(y yj j|x xi i)的一类称为禁用集合的一类称为禁用集合现在学习的是第5页，共15页例：设信源具有一百个以等概率出现的符号例：设信源具有一百个以等概率出现的符号a a1 1，a a2 2，a a9999，a a100100，并以每秒发出一个符号的速率从信源输出。试求在允许失真度并以每秒发出一个符号的速率从信源输出。试求在允许失真度D D0.10.1条件条件下，传输这些消息所需要的最小信息率下，传输这些消息所需要的最小信息率 解：在不失真传输条件下的信息率解：在不失真传输条件下的信息率R R为：为：因为允许失真度因为允许失真度D D0.10.1，可设想信源，可设想信源100100个符号经过假想的试验个符号经过假想的试验信道只输出信道只输出a a1 1，a a2 2，a a8989，a a9090，即输出，即输出9090个符号，而余下的个符号，而余下的a a9191，a a100 100 都用都用a a9090代替代替 失真矩阵失真矩阵D D为：为：bit/sbit/s现在学习的是第6页，共15页 除除a a1 1，a a2 2，a a8989，a a9090对应位置上的元素为对应位置上的元素为0 0外，其余元素为外，其余元素为1 1或或，假想试验信道传输概率假想试验信道传输概率P(P(y yj j|x xi i)为零时，所对应的为零时，所对应的d dij ij为无限大为无限大 这个失真信源的组合方案的平均失真函数为：这个失真信源的组合方案的平均失真函数为：现在学习的是第7页，共15页 上式中上式中X X1 1Y Y1 1aa1 1，a a2 2，a a8989，a a9090，属于不失真的符号集合，属于不失真的符号集合，对应对应d dij ij0 0，其中，其中i,ji,j1 1，2 2，9090 X X2 2aa9191，a a100100，Y Y2 2aa9090，属于失真集合，对应，属于失真集合，对应d dij ij1 1，其中，其中i i9191，9292，100100，j j9090 据题意，据题意，P(P(x xi i)1/1001/100，i i1 1，2 2，100100 所以，有：所以，有：可见，这样设想的失真信源的组合方案能满足对失真度的要求可见，这样设想的失真信源的组合方案能满足对失真度的要求 在试验信道的输出端，在试验信道的输出端，a a1 1，a a2 2，a a8989的出现概率仍为的出现概率仍为1/1001/100,而而a a9090的的出现概率出现概率P(aP(a9090)11/10011/100现在学习的是第8页，共15页 所以，相应的信息率为：所以，相应的信息率为：比较比较 R R与与 R R,可知在可知在D D0.10.1的条件下，信息率可减小，减小了的条件下，信息率可减小，减小了6.6446.6446.2646.2640.38 bit/s0.38 bit/s 同理，在同理，在D D0.50.5的条件下的条件下(假定假定5050个符号产生失真个符号产生失真)信息率信息率R”R”为：为：信息率可减小信息率可减小 6.6446.6443.7513.7512.893 bit/s2.893 bit/sbit/sbit/sbit/sbit/s现在学习的是第9页，共15页 信息率失真函数信息率失真函数R(D)R(D)定义为：定义为：在给定信源消息的概率分布在给定信源消息的概率分布P(P(x xi i)及平均失真函数允许值及平均失真函数允许值D D的条件下，的条件下，传输这些信源消息，并使失真程度在允许范围内时，所需要的信息率的最传输这些信源消息，并使失真程度在允许范围内时，所需要的信息率的最小值小值，其定义式为：，其定义式为：R(D)R(D)又称作率失真函数又称作率失真函数信息率失真函数与信道容量的关系：信息率失真函数与信道容量的关系：信源与信道的对偶关系反映在信息率失真函数与信道容量之间的对信源与信道的对偶关系反映在信息率失真函数与信道容量之间的对偶关系。信道容量偶关系。信道容量C C是给定信道传输概率集合（或信道矩阵）的条件下，是给定信道传输概率集合（或信道矩阵）的条件下，信道所允许的最大信息传输速率。也就是说，信道容量信道所允许的最大信息传输速率。也就是说，信道容量C C是在给定传输是在给定传输特性的条件下，平均互信息量特性的条件下，平均互信息量I I（X X；Y Y）在信源消息概率矢量上的一个）在信源消息概率矢量上的一个极大值。信息率失真函数极大值。信息率失真函数R R（D D）是在给定信源消息概率分布的条件下，）是在给定信源消息概率分布的条件下，I I（X X；Y Y）在试验信道的信道传输概率矢量）在试验信道的信道传输概率矢量P(P(y yj j|x xi i)上一个极小值上一个极小值现在学习的是第10页，共15页三三.限失真信源编码定理限失真信源编码定理(香农第三定理香农第三定理)限失真信源的信息率用限失真信源的信息率用R(D)R(D)描述，所采用的信道的信道容量为描述，所采用的信道的信道容量为C C时，若时，若CR(D)CR(D)时，则限失真信源的有效性编码存在；反之，若时，则限失真信源的有效性编码存在；反之，若CR(D)C DD Dmax max 也有也有R(D)R(D)0 0现在学习的是第12页，共15页 X X和和Y Y相互独立的条件下，对各个相互独立的条件下，对各个x xi i，有，有P(P(y yj j|x xi i)P(P(y yj j)，这时平均失，这时平均失真函数可写成：真函数可写成：因为当因为当D DD Dmaxmax时，有时，有R(D)R(D)0 0 所以，所以，D Dmaxmax应在满足应在满足I(XI(X；Y)Y)0 0的条件下，取的条件下，取Y Y集合中所有集合中所有 值中的最值中的最小值，故定义小值，故定义D Dmaxmax为：为：例：已知信源的消息集合例：已知信源的消息集合X X中包含中包含x x0 0和和x x1 1两个消息，并设它们的概率为两个消息，并设它们的概率为P(P(X X1 1)p 1/2，P(P(X X2 2)1 1p，而信宿符号集合而信宿符号集合Y Y也包含两个符号也包含两个符号y y0 0和和y y1 1 ，失真矩阵为，失真矩阵为 ，试求，试求D Dmaxmax现在学习的是第13页，共15页 解：接收符号解：接收符号y y0 0的平均失真函数的平均失真函数 为：为：接收符号接收符号y y1 1的平均失真函数的平均失真函数 为：为：因为因为p 1/2 所以所以现在学习的是第14页，共15页 3.3.在在(0(0，D Dmaxmax)范围内，范围内，R(D)R(D)是是D D上的凹函数上的凹函数 4.R(D)4.R(D)是是D D上的单调递减的连续函数上的单调递减的连续函数现在学习的是第15页，共15页
