限失真信源编码

信息论的旅程本章将着重讨论允许一定失真的条件下可把信源信 息压缩到什么程度。

第七章 限失真信源编码三、信源的输出中含 有多少信息？四、传输信息的最高速 率（信道容量）2009-12-22五、无失真信源编码 六、有噪信道编码 九、实际信道编码方法七、限失真信源编码2主要内容1.1 概述 失真产生的原因信道噪声的干扰使得信息传输过程会产生差错； 当信息传输率超过信道容量时，必然产生差错； 信源熵是信源无失真压缩的极限，若再继续压缩 则会带来失真。

基本概念1. 概述 1. 概述 2. 系统模型 2. 系统模型失真测度 信息率失真函数 限失真信源编码定理3失真存在的合理性信宿的灵敏度和分辨率是有限的，不要求绝对无 失真； 允许失真的存在，可以提高信息传输率，从而降 低通信成本。

41.1 概述（续）1.2 系统模型 – 只讨论信源编码问题信源 编码 信道 编码 信道 干扰 信道 译码 信源 译码无失真信源压缩的极限：信源的信息熵 本章的研究内容在允许一定程度失真的条件下，能够把信 源信息压缩到什么程度，即最少需要多少 比特才能描述信源。

研究方法用研究信道的方法，来研究有失真信源压 缩问题。

5信源X 试验信道P(Y | X )Y 失真信源无失真 信源编码信道 编码61主要内容失真函数 d (x, y )2.1 失真测度 – 失真函数基本概念非负函数；函数形式可根据需要定义 1. 失真函数 1. 失真函数 2. 平均失真 2. 平均失真 定量描述发出符号与接收符号之间的差异 （失真）x2 L ⎡ X ⎤ ⎡ x1 ⎢ P ⎥ = ⎢ p(x ) p(x ) L ⎣ ⎦ ⎣ 1 2 xn ⎤ p(xn )⎥ ⎦失真测度信息率失真函数 限失真信源编码定理7Y : {y1 , y 2 , L , y m }失真矩阵⎡ d (x1,y1 ) d ( x1,y2 ) L d ( x1,ym )⎤ ⎢d ( x ,y ) d ( x ,y ) L d ( x ,y )⎥ 2 2 2 m ⎥ D=⎢ 2 1 ⎢ M ⎥ M M ⎢ ⎥ d (xn ,y1 ) d ( xn ,y2 ) L d ( xn ,ym )⎦ ⎣82.1 失真测度 – 失真函数（续）常用的失真函数有： （1） 汉明失真2.1 失真测度 – 失真函数 – 例题例7.1 设信道输入 X = {0,1}，输出 Y = {0, ?,1} ，规定失 真函数 d(0, 0) = d(1, 1) = 0， d(0, 1) = d(1, 0) = 1， d(0, ?) = d(1, ?) = 0.5，求 D 。

第6章 限失真信源编码一、例题：【例6.1】 二元对称信源，信源{0,1}U =，接收变量{0,1}V =，在汉明失真定义下，失真函数为：(0,0)(1,1)0d d ==，(0,1)(1,0)1d d ==其失真矩阵为0110⎡⎤=⎢⎥⎣⎦D 容易看出：对于离散对称信源，其汉明失真矩阵D 为一个方阵，且对角线上的元素为零，即：0111101111011110⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦D【例6.2】 信源U ＝{0,1,2}，接收变量V ＝{0,1,2},失真函数为2(,)()i j i j d u v u v =-，求失真矩阵。

由失真定义得：d (0,0)＝d (1,1)＝d (2,2)＝0d (0,1)＝d (1,0)＝d (1,2)＝d (2,1)＝1 d (0,2)＝d (2,0)＝4所以失真矩阵D 为14101414⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦D【例 6.3】 离散无记忆信源输出二维随机序列12()U U =U ，其中(1,2)i U i =取自符号集{0,1}，通过信道传输到信宿，接收N 维随机序列12()V V =V ，其中(1,2)i V i =取自符号集{0,1}，定义失真函数(0,0)(1,1)0(0,1)(1,0)1d d d d ====求符号序列的失真矩阵。

解： 由N 维信源序列的失真函数的定义得11(,)(,)(,),kk NN N i j i j k d d d uv Nαβ===∈∈∑u v u U v V所以[][]1(00,00)(0,0)(0,0)0211(00,01)(0,0)(0,1)22N N d d d d d d =+==+=类似计算其他元素值，得到信源序列的失真矩阵为110122110122111022111022N⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦D【例6.4】 设信源符号有8种，而且等概率，即1()8i P u =。

失真函数定义为0(,)1i j i jd u v i j =⎧=⎨≠⎩假如允许失真度12D =，即只要求收到的符号平均有一半是正确的。

第八章 限失真信源编码8.1设信源X 的概率分布P(X):{p(α1), p(α2), …,p(αr ) },失真度为d (αi , βj )≥0,其中 (i=1,2,…,r;j=1,2,…,s).试证明:∑==ri j i ji b a d a p D 1min )},(min ){(并写出取得min D 的试验信道的传输概率选取的原则,其中))}/(,),/(),/({min ),(min 21i S i i jj i ja b p a b p a b p b a d =(证明详见:p468-p470)8.2设信源X 的概率分布P(X):{p(α1), p(α2), …,p(αr ) },失真度为d(αi , βj )≥0,其中 (i=1,2,…,r;j=1,2,…,s).试证明:}),()({min 1max ∑==ri j i i jb a d a p D并写出取得max D 的试验信道传递概率的选取原则. (证明详见:p477-p478)8.5设二元信源X 的信源空间为:-1)( 1 0X:][X ⎩⎨⎧•ωωX P P令ω≤1/2,设信道输出符号集Y:{0,1},并选定汉明失真度.试求:(1) D min ,R(D min ); (2) D max ,R(D max );(3) 信源X 在汉明失真度下的信息率失真函数R(D),并画出R(D)的曲线; (4) 计算R(1/8). 解：{}{}{}{}0)()(0);()1()}0();1({min )1,1()1()1,0()0(;)0,1()1()0,0()0(min ),()(min )2()()()/()(min );(min )0()(0)/(),2,1(1)/(0)/(100110][10 000)1(0)0(),(min )()1(max 21min max min min 21min ==∴====++=⎭⎬⎫⎩⎨⎧='===-===∴====⎥⎦⎤⎢⎣⎡===•+•==∑∑==ωωωR D R Y X I p p p d p d p d p d p b a d a p D D H X H Y X H X H Y X I R D R Y X H i a b p a b p P D D p p b a d a p D jji j i i j i j i j i j i j i 此时故此时或的信道矩阵则满足保真度＝最小允许失真度：⎩⎨⎧≥<≤-=-=-=∴---=ωωωωD D D H H D R D H H D H X H D R r D D H X H D R 00 )()()()()()()()()1log()()()(,)3(即对此信源下离散信源在汉明失真度由上，可得R(D)曲线如下:(4)R(1/8)=H(ω)-H(1/8)= H(ω)-0.5436 bit/symble 8.6一个四进展等概信源41 41 41 41 )( 3 2 1 0U :][U ⎪⎩⎪⎨⎧•U P P接收符号集V:{0,1,2,3},其失真矩阵为:⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0111101111011110]D [ (1) D min ,R(D min ); (2) D max ,R(D max );(3) 试求R(D), 并画出R(D)的曲线(去4到5个点). 解:{}{}{}symble/bit 2)41,41,41,41()()/()(min );(min )0()(0)/(),4,3,2,1(1)/(0)/(1000010*********][0min 00)3(0)2(0)1(0)0(),(min )(min },{:)1(min 4121===-===∴====⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡===•+•+•+•==∑=H U H Y U H U H Y U I R D R Y U H i u b p u b p P D D p p p p b u d u p D b b Y i j i j i j i j i 故此时或的信道矩阵则满足保真度＝最小允许失真度：设输出符号集DH(0maxsymble/bit 0)43(,43 ;symble /bit 208.0)21(,21 ;symble /bit 792.0)41(,41 ;symble /bit 258.1)81(,81 ;symble /bit 2)0(,0:43 0430 3log )(2)(3log )(23log )()()()1log()()()(,)3(0)()(0);(,4343,43,43,43min ),()(min )2(max 41min max ==========⎪⎪⎩⎪⎪⎨⎧≥<≤--=--=--=∴---===∴==⎭⎬⎫⎩⎨⎧=⎭⎬⎫⎩⎨⎧='=∑=R D R D R D R D R D D D D D H D R D D H D D H U H D R r D D H X H D R R D R Y X I Y U b u d u p D D ji j i i j 可计算得即对此信源下离散信源在汉明失真度故相互独立、此时ω可得R(D)曲线如下:8.7某二进制信源:⎪⎩⎪⎨⎧• 21 21 )( 1 0U :][U U P P其失真矩阵为:⎥⎦⎤⎢⎣⎡=0010][1 0 a a D (1) 试求D min ,R(D min );(2) 试求D max ,R(D max ); (3) 试求R(D);D2{}{}{}{}⎪⎪⎩⎪⎪⎨⎧≥<≤-=-=-=∴---==∴---≥-=-+=-+≤====∴=====∴==⋅⋅=++=⎭⎬⎫⎩⎨⎧='====-===∴====⎥⎦⎤⎢⎣⎡===•+•==∑∑∑∑∑∑∑≠≠≠====2 020 )(1)()(1)()()()1log()()()};(min{)()1log()()()/()();()1log()()1log()()/(:,,)()/()/()(),()/()()3(0)2a()(0);(,Y 2a)}0(a );1(a {min )1,1()1()1,0()0(;)0,1()1()0,0()0(min ),()(min )2(bit/symble 12log )()/()(min );(min )0()(0)/(),2,1(1)/(0)/(1001][ 0min 00)1(0)0(),(min )(min },{;)1(2121max 21min max min 2121a D a D d D H D R aDH a D H U H D R r dDd D H U H Y U I D R D r aDa D H U H Y U H U H Y U I r aDa D H r P P H Y U H aP D D aP p u p a D ub p p a b p a p a b u d u b p u p D R D R Y U I U p p d p d p d p d p b u d u p D D U H Y U H U H Y U I R D R Y U H i u b p u b p P D D p p b u d u p D b b Y e e ee ji i e i ji i j ei ji i j i i j j i i j i j ji j i i j i j i j i j i j i 即对此信源得定义域中选取适当值可在由费诺不等式则时当失真度满足保真度准平均失真度相互独立、此时故此时或的信道矩阵则满足保真度＝最小允许失真度：设输出符号集8.8对于离散无记忆信源U,其失真矩阵[D]中,如每行至少有一个元素为零,并每列最多只有一个元素为零,试证明R(D)=H(U).8.9试证明对于离散无记忆信源,有R N (D)=NR(D),其中N 为任意正整数,D>D min . 8.10某二元信源X 的信源空间为:-1 )( X:][X 21⎩⎨⎧•ωωX P a a P其中ω<1/2,其失真矩阵为:⎥⎦⎤⎢⎣⎡=0d d 0][D(1) 试求D min ,R(D min ); (2) 试求D max ,R(D max ); (3) 试求R(D);(4) 写出取得R(D)的试验信道的各传输概率;(5) 当d=1时,写出与试验信道相对应得反向试验信道的信道矩阵. 解:{}{}{}{}⎪⎩⎪⎨⎧≥<≤-=-=∴---==∴---≥-=-+=-+≤====∴=====∴==⋅=⋅⋅=++=⎭⎬⎫⎩⎨⎧='===-===∴====⎥⎦⎤⎢⎣⎡===•+•==∑∑∑∑∑∑∑≠≠≠====ωωωωωωωd D d D dD H H D R dDH H D R r dDd D H X H Y X I D R D r dDd D H X H Y X H X H Y X I r dDd D H r P P H Y X H dP D D dP p a p d D a b p p a b p a p d b a d a b p a p D R D R Y X I p p p d p d p d p d p b a d a p D D H X H Y X H X H Y X I R D R Y X H i a b p a b p P D D p p b a d a p De e ee ji i e i ji i j ei ji i j i i j j i i j i jji j i i j i j i j i j i j i00 )()()()()()()1log()()()};(min{)()1log()()()/()();()1log()()1log()()/(:,,)()/()/()(),()/()()3(0)()(0);(,Y X d )1(d )}0(d );1(d {min )1,1()1()1,0()0(;)0,1()1()0,0()0(min ),()(min )2()()()/()(min );(min )0()(0)/(),2,1(1)/(0)/(1001][ 0min 00)1(0)0(),(min )(min )1(2121max 21min max min 21即对此信源得定义域中选取适当值可在由费诺不等式则时当失真度满足保真度准平均失真度相互独立、此时故此时或的信道矩阵则满足保真度＝最小允许失真度：.,""487)()()/()();()( ]log )1log()1[()]()([ ]log )()1log()1)((log )()1log()1)(([ )]/(log )/()()/(log )/()( )/(log )/()()/(log )/()([ )/(log )/()()/(12222)1()()/()()/(22)()/()()/(222)1()()/()()/(122)()/()()/(2)1)(1()/()()(222)1(2)/()()(:2222222][:)();()4(2122112222221212121211111121212222222222222212121222121212222111111212222222221112222222222222矩阵再由反推正向信道传输矩阵反向信道求出或者直接按照课本实际上是先根据参数法检验阵为时的试验信道的信道矩取得p dDH H Y X H X H Y X I dDH dDd D d D d D y p y p dDd D y p d D d D y p d D d D y p d D d D y p y x p y x p y p y x p y x p y p y x p y x p y p y x p y x p y p b a p b a p b p Y X H d D D d D d d Dd Dd d d D Dd Dd d d y p x y p x p y x p d D Dd D d d d D d D d D Dd y p x y p x p y x p d D Dd D d Dd Dd d d D Dd y p x y p x p y x p d D Dd D d d D d D d D Dd d y p x y p x p y x p D d Dd d D D x y p x p y p D d Dd Dd Dd d d D Dd d D d D d D Dd d x y p x p y p Dd Dd d d D Dd Dd d d Dd Dd d d D Dd d D d D d D Dd d D d D d D Dd d P D R Y X I i j j i j i j i i i i i i X -=-=∴=+--⋅+-=+--++---=+++-=-=-=---+--++---===------===--+----==-=---+--==---=--+==--=+----+-+--==⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡+--++--+-------+--=∑∑∑∑====ωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωωω⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--==d D dD d D d DP d Y 11][:1,)5(反向试验的信道矩阵为时与试验信道相对应的由上面8.14设离散无记忆信源:⎪⎩⎪⎨⎧• 31 31 31 )( u uU :][U 321U P u P其失真失真度为汉明失真度.(1) 试求D min ,R(D min ),并写出相应试验信道的信道矩阵; (2) 试求D max ,R(D max ), 并写出相应试验信道的信道矩阵;(3) 若允许平均失真度D=1/8,试问信源[U ·P]的每一个信源符号平均最少由几个二进制码符号表示? 解:{}{}{}.9164.0symble/bit 9164.081)81(3log )81(,8131 0310 )(3log )()(3log 2log )()()()1log()()()(,)3(0)31()(0);(3131;31;31min )}();());({min ),()(min )2(symble /bit 585.13log )()/()(min );(min )0()(0)/(,),3,2,1(1)/(0)/(100010001][ 000)(0)(0)(),(min )()1(max 32131min max min min 32131min 个二进制码符号来表示均最少可以用则信源的每一个符号平时即对此信源下离散信源在汉明失真度此时则此时设输出符号集合或的信道矩阵则满足保真度＝最小允许失真度：=--==⎪⎪⎩⎪⎪⎨⎧≥<≤--=--=--=∴---===∴==⎭⎬⎫⎩⎨⎧==⎭⎬⎫⎩⎨⎧='====-===∴====⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡===•++•+•==∑∑==H R D D D D D H D R DD H D D H U H D R r D D H X H D R R D R Y U I u p u p u p b a d a p D D U H Y U H U H Y U I R D R Y U H Y i u b p a b p P D D u p u p u p b u d u p D jj i j i i j i j i j i j i j i8.15设二元信源X 的信源空间为:-1)( u uU :][U 21⎩⎨⎧•ωωU P P(ω<1/2),其失真度为汉明失真度.若允许平均失真度D=ω/2,试问每一个信源符号平均最少需要几个二进制码符号表示? 解:.)21()()3(21)2log()2(21)1log()1(log 21)21()()21(2100 )()()()()()()()()1log()()()(,个二进制码符号来表示需要每个信源符号平均最少时即对此信源下离散信源在汉明失真度ωωωωωωωωωωωωωωωωωH H H H R D D D D H H D R D H H D H U H D R r D D H X H D R -∴----+----=-==∴⎩⎨⎧≥<≤-=-=-=∴---=。