资源描述
2 1 10 )()( xpxp ji ji ij xx xx d 当 当 , , 1 0 例:若有一个离散、等概率单消息(或无记忆)二元信源: ,且采用汉明距离作为失真度量标准:即 有一具体信源编码方案为: N个码元中允许错一个码元,实现时 N个码元仅 送 N-1个,剩下一个不送,在接收端用随机方式决定(为掷硬币方式)。 阴影范围表示实际信源编码方案 与理论值间的差距,我们完全可以 找到更好,即更靠近理论值,缩小 阴影范围的信源编码,这就是工程 界寻找好的信源编码的方向和任务。 1( ) ( ) ( ) 2R D H H D 二元信源的理论信息率失真函数 ( ) 1 2R D D 二元信源的实际信息率失真函数 例:设信源具有一百个以等概率出现的符号 a1, a2, , a99, a100,并以每 秒发出一个符号的速率从信源输出。试求在允许失真度 D 0.1条件下,传输这 些消息所需要的最小信息率。 信源 a1, a2,., a99, a100 试验信道 p(yj|xi) 无扰离散 信道 失真信源 a1 a100 a1 a90 (a) 解:在不失真传输条件下的信息率 R为: 因为允许失真度 D 0.1,可设想信源 100个符号经过假想的试验 信道只输出 a1, a2, , a89, a90,即输出 90个符号,而余下的 a91, , a100 都用 a90代替 ( ) l o g 1 0 0 6 .6 4 4 1 HXR b bit/s X Y a1 a2 a90 a91 a100 a90 a2 a1 除 a1, a2, , a89, a90对应位置上的元素为 0外,其余元素 为 1或 ( 假想试验信道传输概率 P(yj|xi)为零时,所对应的 dij 为无限大) 1 2 90 91 92 10 0 1 2 90 91 92 100 0 0 0 1 1 1 a a a a a a a a aD a a a 失 真 矩 阵 : 该失真信源的组合方案的平均失真函数为: 2211 )|()()|()( )|()( YX ijiji YX ijiji XY ijiji dxyPxPdxyPxP dxyPxPd 上式中: X1 Y1 a1, a2, , a89, a90,属于不失真的符号集合, 对应 dij 0,其中 i,j 1, 2, , 90 X2 a91, , a100, Y2 a90,属于失真集合,对应 dij 1,其中 i 91, 91, , 100, j 90 据题意, P(xi) 1/100( i 1, 2, , 100) 所以得平均失真函数: 可见,这样设想的失真信源的组合方案能满足对失真度的要 求。 22 ( ) ( | ) 1 1 0 1 1 0 . 1 100 i j i i j XY d P x P y x d 该试验信道为无噪有损信道,即 H(Y|X)=0,所以 R=I(X;Y)=H(Y)-H(Y|X)=H(Y) 在试验信道的输出端 Y, a1, a2, , a89的出现概率仍为 1/100,而 a90的出现概率 P(a90) 11/100,可知相应的信息传输速 率为: 89 90 1 90 11 ( ) l o g ( ) l o g ( ) ( ) 1 1 1 1 0 0 8 9 l o g 1 0 0 l o g 1 0 0 1 0 0 1 1 l o g 1 0 0 0 . 1 1 l o g 1 1 6 . 2 6 4 ( / ) i i i R P a P a P a P a b i t s 比较 R与无失真传输条件下的信息率 R ,可知在 D 0.1的 条件下,所需信息率减小了 6.644 6.264 0.38 bit/s。 同理,在 D 0.5的条件下 (假定后 50个符号均产生失真,这后 50个符号均用 a50来代替 )信息率 R”为: 49 50 1 50 11 ( ) l o g ( ) l o g ( ) ( ) 1 5 1 1 0 0 4 9 l o g 1 0 0 l o g 1 0 0 1 0 0 5 1 l o g 1 0 0 0 . 5 1 l o g 5 1 3 . 7 5 1 ( / ) i i i R P a P a P a P a b i t s 与无失真传输条件下的信息率 R想比较减小 6.644 3.751 2.893 bit/s。 信道容量与信息率失真函数的比较 (1) 求极值问题 平均互信息 I(X;Y)是信源概率分布 p(xi)(i=1,2, n)或概率 密度函数 p(x)的上凸函数。根据上凸函数定义,如果 I(X;Y)在定 义域内对 p(xi)或 p(x)的极值存在,则该极值一定是极大值。信 道容量就是在固定信道情况下,求平均互信息极大值的问题, 即 I(X;Y)又是信道转移概率分布 p(yj/xi)(i=1,2, n;j=1,2, m)或条 件概率密度函数 p(y/x)的下凸函数,因此在满足保真度准则条 件下, I(X;Y)对 p(yj/xi)或 p(y/x)的条件极值若存在,则一定是极 小值。信息率失真函数就是在试验信道(满足保真度准则的信 道)中寻找平均互信息极小值的问题,即 ( | ) ( ) m i n ( ; )j i DP y x PR D I X Y ()m a x ( ; )ipxC I X Y 信道容量与信息率失真函数的比较 信道容量与信息率失真函数的比较 (2)特性 信道容量 C一旦求出后,就只与信道转移概率 p(yj/xi)或条件概 率密度 p(y/x)有关,反映信道特性,与信源特性无关;由于平均 互信息与信源的特性有关,为了排除信源特性对信道容量的影 响,采用的做法是在所有的信源中以那个能够使平均互信息达 到最大的信源为参考,从而使信道容量仅与信道特性有关,信 道不同, C亦不同。 信息率失真函数 R(D)一旦求出后,就只与信源概率分布 p(xi) 或概率密度函数 p(x)有关,反映信源特性,与信道特性无关。 由于平均互信息与信道的特性有关,为了排除信道特性对信息 率失真函数的影响,采用的做法是在所有的信道中以那个能使 平均互信息达到最小的信道为参考,从而使信息率失真函数仅 仅与信源特性有关,信源不同, R(D)亦不同。 (3) 解决的问题 信道容量是为了解决通信的可靠性问题,是信息传输的理 论基础,通过信道编码增加信息的冗余度来实现; 信息率失真函数是为了解决通信的有效性问题,是信源压 缩的理论基础,通过信源编码减少信息的冗余度来实现。 例:删除信源 X取值 【 0, 1】 , Y取值 【 0, 1, 2】 。而失真矩阵为 求 Dmin。 m in 1 ( ) m i n ( , ) ( ) 0 0 nn i i j ij ii D p x d x y p x 满足最小失真度的试验信道是个无噪无损信道,转移矩阵为 1 0 0 0 1 0Q 在这个无噪无损信道中,可得 ( ; ) ( )I X Y H X ( / )( 0 ) m i n ( ; ) ( )Dp y x PR I X Y H X 例: 例:已知信源的消息集合 X中包含 x0和 x1两个消息,并设它们的概率为 P(X1) p 1/2, P(X2) 1 p, 而信宿符号集合 Y也包含两个符号 y0和 y1 ,失真矩 阵为 ,试求 Dmax 0 0 1110 0100 dd ddD 解:接收符号 y0的平均失真函数 为: 接收符号 y1的平均失真函数 为: 因为 p K4 K8,进制 n越小,压缩比 K越大; 随着允许失真度 D的增加,压缩比 K随之增加,但相对关系不变 引用拉氏乘子法。约束条件为下列 (n+1)组等式: R(D)的参量表达式 求互信息 的极小值。 jjii j jiijij q PPpPqI log);( 1 ( 1 ) 1 , , 1 , 2 i ji ij ij m ji j D d p P d n P i i n 组 约 束 对 例:设要把 16个等概率出现的消息构造成线性分组码,设信息位为 k,校验位 为 r,码子长度为 n=k+r。 解:从题意可知, 16 2k , k 4。 为了纠正一个错误, r 2,即 n 4+2 6。这种编码方式不行,校验矩阵 H只有 2行, 6列,无法排出各不相同的 6列。 6列各不相同,主要目的是使校正子 s能 定出错误位置进行纠正 若 r 3,可排出( 7, 4)分组码的校验矩阵 H: 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 H m 1 m 2 m 3 m 4 p 1 p 2 p 3 行 1 行 2 行 3 如消息为 1010,则从上列关系可得出: 即可得码字为 1010010 m 1 m 2 m 3 m 4 p 1 p 2 p 3 m 1 m 2 m 3 m 4 p 1 p 2 p 3 m 1 m 2 m 3 m 4 p 1 p 2 p 3 1 0 1 0 p 1 p 2 p 3 1 + 0 + 1 = 0 = p 1 1 0 1 0 p 1 p 2 p 3 1 + 0 + 0 = 1 = p 2 1 0 1 0 p 1 p 2 p 3 1 + 1 + 0 = 0 = p 3 该码编码方法如下: 下表列出了( 7, 4)码的 24 16个码字 m 1 m 2 m 3 m 4 p 1 p 2 p 3 汉 明 距 离 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 4 3 4 4 4 4 4 4 4 4 4 3 3 3 7 u u 1 u 1 1 v 1 u 1 1 1 v 1 对于纠错,从表中看出最小汉明距离 dmin 3 故根据式 ,该码能纠正 个错误 如接收矢量 r (1010111),则 由 s可知,发送矢量应为 (1000111) 2 1m i n dt 1 2 13 t 111 110 1 0 1 ( 1 0 1 0 1 1 1 ) 0 1 1 100 0 1 0 0 0 1 ( 1 0 1 ) T S r H 左 面 开 始 第 三 位 是 错 的
展开阅读全文