第八章 限失真信源编码 8.1设信源X 的概率分布P(X):{p(α1), p(α2), …,p(αr ) },失真度为d (αi , βj )≥0,其中 (i=1,2,…,r;j=1,2,…,s).试证明: ∑==r i j i j i b a d a p D 1 min )},(min ){( 并写出取得min D 的试验信道的传输概率选取的原则,其中 ))}/(,),/(),/({min ),(min 21i S i i j j i j a 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 1 max ∑==r i j i i j b 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][1 0 00 0)1(0)0(),(min )()1(max 21min max min min 2 1 min ==∴====++=? ?? ???=' ===-===∴====?? ?? ??===?+?==∑∑==ωω ω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 j j i j i i j i j i j i j i j i 此时故此时或的信道矩阵 则满足保真度＝最小允许失真度：
7.1 设输入符号集为}1 ,0{=X ，输出符号集为}1 ,0{=Y 。定义失真函数为 1 )0,1()1,0(0)1,1()0,0(====d d d d 试求失真矩阵D 。 解： 041 041041041),(min )(43 0411********),()(min min min max =?+?+?+?=== ?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 7.2 设输入符号集与输出符号集为}3 ,2 ,1 ,0{==Y X ，且输入信源的分布为 )3 ,2 ,1 ,0( 4 1 )(===i i X p 设失真矩阵为 []????? ???? ???=01 11 101111011110d 求D max 和D min 及R(D)。 解： 041 041041041),(min )(43 0411********),()(min min min max =?+?+?+?=== ?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 因为n 元等概信源率失真函数： ?? ? ??-??? ??-+-+=a D a D n a D a D n D R 1ln 11ln ln )( 其中a = 1, n = 4, 所以率失真函数为： ()()D D D D D R --++=1ln 13 ln 4ln )( 7.3 利用R(D)的性质，画出一般R(D)的曲线并说明其物理含义？试问为什么R(D)是非负且非增的？ 解： 函数曲线：
第五章无失真信源编码定理与编码 5．1．1 信源编码和码的类型 1．信源编码 2．码的类型 若码符号集中符号数r=2称为二元码，r=3称为三元码，……，r元码。 若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。 若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。 若每个码符号x i∈X的传输时间都相同则称为同价码，否则称为非同价码。 若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号序列则称为唯一可译码，否则称为非唯一可译码。 若分组码中，没有任何完整的码字是其他码字的前缀，则称为即时码(又称非延长码或前缀条件码)，否则称为延长码。 本章主要研究的是同价唯一可译码。 5．1．2 即时码及其树图构造法 即时码(非延长码或前缀条件码)是唯一可译码的一类子码。 即时码可用树图法来构造。构造的要点是： (1)最上端为树根A，从根出发向下伸出树枝，树枝总数等于r，树枝的尽头
为节点。 (2)从每个节点再伸出r枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。一直继续进行，直至都不能伸枝为止。 (3)每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。 即时码可用树图法来进行编码和译码。 从树图可知，即时码可以即时进行译码。 当码字长度给定，即时码不是唯一的。 可以认为等长唯一可译码是即时码的一类子码。 5．1．3 唯一可译码存在的充要条件 (1)对含有q个信源符号的信源用含r个符号的码符号集进行编码，各码字的码长为l1，l2，…，l q的唯一可译码存在的充要条件是，满足Kraft不等式 5．1．4 唯一可译码的判断法 唯一可译码的判断步骤： 首先，观察是否是非奇异码。若是奇异码则一定不是唯一可译码。 其次，计算是否满足Kraft不等式。若不满足一定不是唯一可译码。 再次，将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是唯一可译码。 或用Sardinas和Patterson设计的判断方法：计算出分组码中所有可能的尾
第6章 限失真信源编码 一、例题： 【例6.1】 二元对称信源，信源{0,1}U =，接收变量{0,1}V =，在汉明失真定义下，失真函数为： (0,0)(1,1)0d d ==，(0,1)(1,0)1d d == 其失真矩阵为 011 0??=? ??? D 容易看出：对于离散对称信源，其汉明失真矩阵D 为一个方阵，且对角线上的元素为零，即： 011110111 1011 1 1 0?? ??????=???????? 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)＝0 d (0,1)＝d (1,0)＝d (1,2)＝d (2,1)＝1 d (0,2)＝d (2,0)＝4 所以失真矩阵D 为 141 014 1 4?? ??=?????? 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)1 d d d d ==== 求符号序列的失真矩阵。 解： 由N 维信源序列的失真函数的定义得 1 1(,)(,)(,) ,k k N N N i j i j k d d d u v N αβ=== ∈∈∑u v u U v V 所以 [][]1(00,00)(0,0)(0,0)0211(00,01)(0,0)(0,1)2 2 N N d d d d d d =+== += 类似计算其他元素值，得到信源序列的失真矩阵为 11012211012211102211102 2 N ??????????=? ?????????? ? D 【例6.4】 设信源符号有8种，而且等概率，即1()8 i P u = 。失真函数定义为 0(,)1i j i j d u v i j =?=?≠? 假如允许失真度12 D =，即只要求收到的符号平均有一半是正确的。我们可以设想这 样的方案： 方案一：对于1234,,,u u u u 这四个信源符号照原样发送，而对于5678,,,u u u u 都以4u 发送。如图6.1(a )所示。 方案二：对于1234,,,u u u u 这四个符号照原样发送，而对于5678,,,u u u u 分别以 1234,,,u u u u 发送。如图6.1(b )所示。