第4章离散无记忆信源无失真编码信源编码概论4.1码的唯一可译性4.24.3定长编码定理和定长编码方法4.4变长编码定理4.5变长编码方法4.6几种实用的无失真信源编码
第4章 离散无记忆信源无失真编码 4.1 信源编码概论 4.2 码的唯一可译性 4.3 定长编码定理和定长编码方法 4.4 变长编码定理 4.5 变长编码方法 4.6 几种实用的无失真信源编码
4.1信源编码概论1、基本概念信源信源U10信道信道信XYW信宿W信道编码译码编码译码源噪声等效无噪信道·传输之前的两次变换：信源编码、信道编码·传输之后的两次反变换：信道译码、信源译码采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范围之内，因此，图中虚框部分可近似地视为一个等效的无损确定信道，简称为无噪信道，这是我们讨论信源编码
2 4.1 信源编码概论 •传输之前的两次变换：信源编码、信道编码。 •传输之后的两次反变换：信道译码、信源译码。 •采取适当信道编码和译码措施后，可使信道传 送的差错率降到允许的范围之内，因此，图中 虚框部分可近似地视为一个等效的无损确定信 道，简称为无噪信道，这是我们讨论信源编码 的前提。 1、基本概念 噪声 信 道 信源 X 编码 信 源 信 宿 等效无噪信道 信源 译码 信道 编码 信道 译码 U W Y W ˆ U ˆ
信源信源W信#W0信U无损确定信道编码译码源宿（等效）信源编码分类：无失真编码、有失真编码。无失真编码：只对信源的允余度进行压缩，不改变信源的炳，又称穴余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符号序列有失真编码：又称熵压缩编码，将在第6章讨论。无失真信源编码的作用：（1）符号变换：使信源的输出符号与信道的输入符号相匹配；（2）允余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于100%。3
3 •信源编码分类：无失真编码、有失真编码。 •无失真编码：只对信源的冗余度进行压缩，不改 变信源的熵，又称冗余度压缩编码，它能保证码 元序列经译码后能无失真地恢复成信源符号序列. •有失真编码：又称熵压缩编码,将在第6章讨论。 无损确定信道 （等效） U 信源 编码 信 源 W 信 宿 信源 译码 W U ˆ 无失真信源编码的作用： （1）符号变换：使信源的输出符号与信道的输 入符号相匹配； （2）冗余度压缩：使编码之后的新信源概率分 布均匀化，信息含量效率等于或接近于100%
2、编码器模型码WUW编码器信源码字集Wf(uuz,"ug)(w,w2"w,)码字wX码元集X信源编码f：一一对应码元x的变换。f :u,→w,，i=1,2,q·码长l：码字w所含码元的个数。单位：码元/符号定长码（FLC,FixedLengthcode)：码中所有码字均有相同的码长l；否则称为变长码(VLC,VariableLengthcode)P(w,),=亡P(u,），码元/符号爱长i=P(u,)=1码元/符号
4 2、编码器模型 •码长l i ：码字wi 所含码元的个数。单位：码元/符 号 •定长码(FLC, Fixed Length code) ：码中所有码字 均有相同的码长l ；否则称为变长码(VLC, Variable Length code)。 •平均码长： 码W 码字集W 码字wi 码元集 X 码元xi 编码器 { , , , } u u u 1 2 q f 1 2 { , , , }r x x x U W 1 2 { , , , } w w wq X 信 源 信源编码 f ：一一对应 的变换。 : , 1,2, , i i f u w i q 1 1 ( ) ( ) q q i i i i i i l P w l P u l 码元/符号 定长码： 1 ( ) q i i l P u l l 码元/符号
例：编码UW设DMS的概率空间为：编码器信源f[u][u u, u, u?[w,w2,.w)(uuz,ug)[P]-[1/2 1/4 1/81/8]X[0,1]对其单个符号进行二进制编码。f(u)=w=00,l=2f(u)=W=0,l=1f2(u)=Wz=10, =2f(uz)=W, =01,l, =2f:f:f(u)=W,=110,1,=3f(u)=W,=10,l,=2f(u)=W4=11l,14=3f(u)=W4=11,14=2T=P(u,),=x1+×2+-×3+-×3P(u,),=×2+=×2+88A一-×22+X88.1=1.75码元/符号=2码元/符号编码策略：经常出现（概率大）的符编码策略：采用等长的码字号采用较短的码字，不经常出现（概率小）的符号采用较长的码字
5 例：编码 设DMS的概率空间为: 1 2 3 4 U 1 2 1 4 1 8 1 8 U u u u u P 对其单个符号进行二进制编码。 2 1 1 1 2 2 2 2 2 2 3 3 3 2 4 4 4 ( ) 0 , 1 ( ) 10 , 2 : ( ) 110 , 3 ( ) 111, 3 f u w l f u w l f f u w l f u w l 4 1 1 1 1 1 ( ) 2 2 2 2 2488 2 i i i l P u l 4 1 1 1 1 1 ( ) 1 2 3 3 2 4 8 8 1.75 i i i l P u l 1 1 1 1 1 2 2 2 1 1 3 3 3 1 4 4 4 ( ) 00 , 2 ( ) 01 , 2 : ( ) 10 , 2 ( ) 11 , 2 f u w l f u w l f f u w l f u w l 码元/符号 码元/符号 编码策略：经常出现(概率大)的符 号采用较短的码字，不经常出现 (概率小)的符号采用较长的码字 。 编码策略：采用等长的码字。 编码器 f 1 2 { , , , } u u uq {0 1} ， U W 1 2 { , , , } w w wq X 信 源
3、编码器的输出XUW编码器信源f[ww2""w,](u,uz,u)(xx)X[x2,]f是一一P(w,)= P(u,)bit/码字或bit/符H(W)=H(U)IV对应的映射i=1,2,q号H(W)H(U)新信源X：H(X)=bit/码元1编码后的信息率R：平均一个码元携带的信息量。H(W)H(U)R= H(X)=bit/码元11平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息
6 3、编码器的输出 f 是一一 对应的映射 P w P u i i i q ( ) ( ) 1,2, , H W H U ( ) ( ) bit/码字或bit/符 号 H W H U H X l l ( ) ( ) 新信源X ： ( ) bit/码元 编码后的信息率R：平均一个码元携带的信息量。 H W H U H X l l ( ) ( ) ( ) bit/码元 平均码长越小，每个码元携带的信息量就越 多，传输一个码元就传输了较多的信息。 R X { , , , } 1 2 r x x x 编码器 f 1 2 { , , , } u u uq 1 2 { , , , }r x x x U W 1 2 { , , , } w w wq X 信 源
4、编码效率UXW信源编码器f[w,2'wg?(uu,,"su,)(xx)X[x,,]为了衡量编码效果，定义编码效率：编码后的实际信息率与编码后的最大信息率之比。H(U)/H(U)RH(X)ne-RHTlogr(X)logrmax2注：编码效率实际上也是新信源X的信息含量效率或炳的相对率，新信源的允余度也是码的余度：。=1-ne
7 4、编码效率 为了衡量编码效果，定义编码效率：编码 后的实际信息率与编码后的最大信息率之比。 max max ( ) ( ) ( ) ( ) log log c R H X H U l H U R H X r l r 注：编码效率实际上也是新信源X 的信息含量 效率或熵的相对率。 新信源的冗余度也是码的冗余度： 1 c c X { , , , } 1 2 r x x x 编码器 f 1 2 { , , , } u u uq 1 2 { , , , }r x x x U W 1 2 { , , , } w w wq X 信 源