2015秋.信息论.第5章限失真信源编码

1、第第5 5章章 限失真信源编码限失真信源编码 无论是无噪信道还是有噪信道，只要信息传输 率R小于信道容量C，总可以找到一种编码方法， 使得编码后的信息传输率R任意接近信道容量 C，且由于信道所产生的错误译码概率任意小。 反之，如果R大于C，在任何信道上都不可能 实现译码错误概率任意小的无失真的传输。 在信道传输信息时，是否必须完全无失真呢？ 很多情况下，不可能不可能进行无失真信源编 码 如，连续信源的熵 H 为无限大 很多应用中，没必要没必要进行无失真信源编 码 如，人眼所能分辨的灰度级 、颜色都是有 限的. 人耳仅能感受 几百Hz十几KHz 的声音信号。 为什么研究 限失真信源编码？ 4 图

2、像压缩 8K10K14K 在实际生活中，通常总是要求在保证一定质量的前提 下，在信宿端近似地再现信源输出的信息，或者说， 在保真度准则下允许信源输出存在一定的失真。 对于给定的信源（熵H(X)，在允许的失真条件下，信 源熵所能压缩的极限（信息率失真R(D)）理论值是多 少，如何计算，是本章要讨论的问题。 信息率失真理论研究的是信源熵压缩问题，但采用了 研究信道的方法，即在数学上将信源熵压缩看成通过 一个信道，寻找在保真度准则下的最小的平均互信息。 信息率失真理论是信号量化、模数转换、频带压缩和 数据压缩的理论基础，在图像处理、数字通信等领域 得到广泛应用。 6 信信 源源 信信 宿宿 试验信道

3、试验信道 X Y (| )p y x 7 主要内容 1 失真测度失真测度 2 信息率失真函数信息率失真函数 3 限失真信源编码定理和逆定理限失真信源编码定理和逆定理 4 信息率失真函数的计算信息率失真函数的计算 8 5.1 失真测度 9 ( , ) d x yxy表示源符号 与码符号 之间失真的程度。 1. 0, ( , ) 1. if xy d x y if xy 常见失真函数： 汉明失真： ， ， 2 2. ( ,).d x yyx 平方失真： （） n 图像处理中，常用平方误差和绝对误差度量失真 ( , ) xy d x y失真函数 信源发出符号 ，接收端收到符号 的失真，可用一个非负函

4、数 来定量描述，称为。 5.1.1 失真函数 3. ( ,)d x yyx 绝对失真： 10 ArBs若源符号集 包含 个符号，码符号集 包含 个符号， 11121 21222 12 (,) (,) (,) . (,) (,) (,) . (,) . (,), (,) . (,) ij s s rrrs d a brs d a bd a bd a b d a bd a bd a b d d a bd a bd a b 有个： 失真矩阵失真矩阵 12 12 ()()()( ) r r aaaX p ap ap ap x 12 12 Y ()()()( ) s s bbb p bp bp bp y

5、 11 AB1,., ,ABr例： 设源符号集 和码符号集 满足 0 1 1 1 1 0 1 1 1 1 1 0 . . . d L 2 ()() ijij d abab，平方失真矩阵 2 2 222 0 1 4 (r-1) 1 0 1 (r-2) (r-1) (r-2) (r-3) 0 . . . d L 汉明失真矩阵 () ijij d abab，绝对失真矩阵 0 1 2 r-1 1 0 1 r-2 r-1 r-2 r-3 0 . . . d L 011 101 110 r=3时 014 101 410 012 101 210 12 0 10, ,1 (0,0)(1,1)0 (0,1)(1

6、,0)1 (0, )(1, )1/ 2 XY dd dd dd 例： 二元删除信道：，。 失真函数定义为 1 0 1 2 1 1 0 2 d 0 1 0 1 13 1212 1 (,.,)(,.,) , 1 ( , )(,). NN N Nii i xxxxyyyyN xy dx yd xy N 设与分别为长度为 的源字 和码字 与 之间的矢量失真函数为 rr rr r r 矢量失真函数矢量失真函数： 11121 21222 12 (,), (,) . (,) (,), (,) . (,) (,), (,) . (,) N N NNNN s s N rrrs d x yd x yd x y d

7、 xyd xyd xy d d xyd xyd xy r rr rr r rrrrrr rrrrrr MMMM 矢量失真矩阵矢量失真矩阵 例7.1.2 假定离散矢量信源N=3，输出矢量序列为X=X1X2X3， 其中Xi的取值为0,1；经信道传输后的输出为Y=Y1Y2Y3， 其中Yi的取值为0,1。定义失真函数 0 0110 01101 dd dd ， ， 求矢量失真矩阵。 112233 1 11 ( , )(,)(,)(,)(,) 3 N Nii i dx yd xyd xyd xyd xy N r r 3 11 000,0000,00,00,00000 33 dddd 3 111 000,0

8、010,00,00,1001 333 dddd 3 01121223 10212132 12012312 21103221 1 122301123 21321021 23121201 32212110 D 5.1.2 平均失真 16 () (,) ()(|) (,). ijij ij ijiij ij DE dp x yd xy p xp yxd xy 信源特性 单个符号的 失真函数 试验信 道特性 11 11 (,) NN N Niii ii DE dE d xyD NN ：矢矢量量平平均均失失真真 失真函数的数学期望称为平均失真。 失真函数选为汉明失真，假定允许的失真限度D*=1/2， 试

9、分析信息可压缩的程度。 Ar若源符号集 包含2 个符号， 122 111 ( ) 222 r aaa X p x rrr 若进行二进制无失真 信源编码，平均每个 符号至少需要log(2r) 个码元。若采用编码 方案 2 11 ()(|)(,) rr ijiij ij DE dp ap aad aa 22 11 ()(|)(,)()1 / 2* rr iriiri irir p ap aad aap aD 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 . 1 1 1 1 . . . . . . . 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0

10、0 1 . 0 0 0 0 1 1 (/) . . . . . . . . . ji p aa 123r 1 2 r r+1 r+2 2r a a a a a a a a a . a . . 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 . 0 0 0 0 1 1 (/) . . . . . . . . . ji p aa 信息传输率： ( ;)()(/) ( )(/)( ) I Y XH XH X Y H YH YXH Y 112 ( ;)log(2 )log() 221 1 log(2 )log(1) 2 rrr I Y Xr rrr r rr r 如果有k+1个

11、符号的编码相同，则 1 ( ;)log(2 )log(1)()(/) 2 k I Y XrkH XH X Y r 121 1111 ( ) 2222 rr aaaa Y r p y rrrr 信源的信息传输率的压缩程度： 1 12log(2 )log(2 )log(1) 2 1 log(1)(/) 2 k RRrrk r k kH X Y r 信息率失真允许失真 所需信息率 上例中的编码方案只是满足失真限度条 件的一种，并没有最大限度地压缩信息 率，还存在其他的编码方案能够满足失 真限度。 那么，在给定失真条件下，信息率压缩 的极限值是多少呢？ 信息率失真函数给出了压缩下界。 21 5.2 信

12、息率失真函数 (): ( | ): DD DDD DBBp y xDD D 允许的试验信道 满足保真度准则的所有信道 称为失真度 允许信道，记为，即 。 允允许许信信道道 信源信源 试验信道试验信道 X Y (| )p y x 信宿信宿 D DD ：如果预先规定的平均失真度为 ，则称信源压缩后 的平均失真度 不大于 的准则为保真度准则。 保保真真度度准准则则 (|): Dji Bp yxDD对于离散无记忆信道，。 5.2.1 D允许信道（试验信道） 22 信源信源 试验信道试验信道 X Y (| )p y x 信宿信宿 (; ) * DD I X Y 从接收端的角度，在满足希望需要再现 信源信

13、息所必须获得的平均信息量 的条件 最小 下， ，即最小。 ( | ),(; )*Dp y xI X Y如果在 失真允许信道中，找到使得达到最小 值，即找到最“好”的编解码方法。 * 限失真信源压缩问题就是对给定的信源，在满足保真度准则 的前提下，使信息传输率尽可能小。 23 信息率失真函数信息率失真函数 (率失真函数率失真函数) ( | ) ()min (;) D P y xB R DI X Y 对离散无记忆信源： (|) 11 (|) ()min()(|)log () jiD rs ji iji P yxB ij j p yx R Dp xp yx p y 5.2.2 信息率失真函数的定义

14、在D允许信道BD中寻找一个信道p(Y/X)，使给定的信源经过 此信道传输时，其信道传输率I(X;Y)达到最小，这个最小值 定义为 对于给定的信源，在满足保真度准则的前提下，信息率失 真函数R(D)，是信息率允许压缩到的最小值。 信道容量信道容量率失真函数率失真函数 24 ( ) ( | ) max (; ) ( )min (; ) D P x P y xB CI X Y R DI X Y 信道容量: 信息率失真函数: 信道固定,信源分布可变信源固定,失真度固定，信道可变 选择信源，使得互信息最大最大 选择试验信道，使得互信息最小最小 为了充分利用特定信道， 使传输的信息量最大 为了在一定的失真

15、条件下，尽可能 用最少的码符号来传送信源消息 信道编码定理：R R R R( (D D) ) 25 5.2.3 率失真函数的性质 R(D) D 0 H(x) DmaxD* R(D*) ( | ) ()min (;) D P y xB R DI X Y ( )R D max 在(0,D)上严格递减函数3. D max max R(D): 0 () :0 ,()0 H X D DDR D ). 2(R DD是关于的下凸函数 1. 11121 21222 12 (,) (,) . (,) (,) (,) . (,) . (,), (,) . (,) s s rrrs d x yd x yd x y

16、d xyd xyd xy d d xyd xyd xy D=0 r R(D) D 0 H(x) DmaxD* R(D*) （3） （4） ,11 11 ( ,) ( ,)() (/) ( ,) () () ( ,) rs ijijijiij X Yij rs ijij ij Dp a b d a bp a p ba d a b p a p b d a b max 11 11 1 min() () ( ,) min()() ( ,) min() ( ,) rs ijij ij sr jiij ji r iij j i Dp a p b d a b p bp a d a b p a d a b 1

17、2 12 ( ) 33 aa X p x 01 10 D max 11 12 12 min()() ( ,) 1212 min( )01()10 3333 21 min( )() 33 sr jiij ji Dp bp a d a b p bp b p bp b max1 11111 min( )0 33333 Dp b 例： R(D) D 0 H(x) DmaxD* R(D*) 32 5.3 限失真信源编码定理和逆定理 12 12 12 ij . , () () . () n . yn YnMY N N M xxxX n Pp xp xp x yyy x 设离散 长无记忆信源为 接收端 长序

18、列为Y=, 信源发送序列 和接收序列 均为 长序列， 称 是长度为 、码字数目为的分组码， 中的元素称为码字。 (,), ikjk d xy如果单字符失真函数为则矢量传输时的失真函数为 n 1 1 (,)(,) n ijikjk k dxyd xy n 信源信源 试验信道试验信道 X Y (| )p y x 信宿信宿 33 信源编码这样进行： 当信源发送序列xi时，就从分组码Y中选取一个使失真最小的 码字。 nn (,)min(,) j iij yY dx Ydxy 分组码Y的平均失真度为 nn 1 ( )()(,) N ii i dYp x dx Y 如果 n ( )dYD 则称分组码Y是满足保真度准则D的允许码。对于包含M个码 字，码长为n的分组码（M，n）其最大信息传输率为 R=(logM)/n. 即 2 nR M 信源信源 试验信道试验信道 X Y (| )p y x 信宿信宿 34 12 12 . , (,), () () . () ( ), 0,0,()(, ) N ikjk N n xxxX d xy Pp xp xp x R D DDM n nR ：设离散 长无记忆信源为 单字符失真函数为 给定单字符失真度下的信息率失真函数为则对于任意的