《信息理论与编码》课程教学课件（讲稿）第4章 离散无记忆信源无失真编码 4.3 定长编码定理和定长编码方法 4.4 变长编码定理（香农第一定理）

4.3定长编码定理和定长编码方法1、对信源输出的符号序列进行编码对信源U的XUW编码器DMS单个符号f[w,W2,"wg)(uu,"u)(2进行编码X(x)对信源U的N长符号串XUNW编码器进行编码DMSf(aaa)(wW2,sw)()VX对扩展信源a,=unui2""-uin(x]uin,iz,uinE(uj,uz,,u)UN的单个符号进行编码

1 4.3 定长编码定理和定长编码方法 1、对信源输出的符号序列进行编码 DMS 编码器 f 1 2 { , , , } u u uq 1 2 { , , , }r x x x U W 1 2 { , , , } w w wq X X 1 2 { , , , }r x x x DMS 编码器 f 1 2 { , , , } N q    1 2 { , , , }r x x xW N U 1 2 { , , , } N q w w w X X 1 2 { , , , }r x x x 对信源U的 单个符号 进行编码 对信源U的 N长符号串 进行编码 对扩展信源 UN的单个符 号进行编码 i i i iN  u u u 1 2 1 2 1 2 , , , { , , , } u u u u u u i i iN q 

2、定长编码定理XUNW编码器DMSf(aa,a)w,w2,.swan](x,x)X(x]r进制定长编码，码长为l，可用的码字数目：rlnHmax(U)logqNH.max(U)唯一可译>rN≥g—一logrlogrH(U)信息传输率R=H(X)bit/码元=ININH(X)H(U)编码效率ne=Hx(X)logrN

2 2、定长编码定理 r 进制定长编码, 码长为lN , 可用的码字数目： N l r l N N 唯一可译 r q  max max log ( ) ( ) log log N r l q H U H U N r r    信息传输率 编码效率 ( ) ( ) / N H U R H X l N   max ( ) ( ) ( ) log c N H X H U H X l r N    bit/码元 DMS 编码器 f 1 2 { , , , } N q    1 2 { , , , }r x x xW N U 1 2 { , , , } N q w w w X X 1 2 { , , , }r x x x

定长无失真编码定理：用r元符号表对离散无记忆信源U的N长符号序列进行定长编码，N长符号序列对应的码长为In，若对于任意小的正数，有不等式：H(U)+8== H,(U)+e'NNlogr就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若H(U)-28 - H,(U)-2e'1Nlogr就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。3

3 定长无失真编码定理：用r元符号表对离散 无记忆信源U的N长符号序列进行定长编码，N 长符号序列对应的码长为lN，若对于任意小的正 数ε，有不等式: 就几乎能做到无失真编码，且随着序列长度N的 增大，译码差错率趋于0。反过来，若 就不可能做到无失真编码，且随着N的增大，译 码差错率趋于1。 ( ) ( ) log N r l H U H U N r        ( ) 2 ( ) 2 log N r l H U H U N r       

3、定长编码方法（例）对U的单个符号进行2进u.u,uzusu.usuU1111111Pu制定长编码。2622232425262码元集：X={0,1)log7INlogq解：I=2.8码元/符号Nlog2logrU:uuzusUusueu取1=3W:00101001110010111011163H(U) =-EP(u,)log P(u,) bit/符号：32i=l63H(U)32【==3码元/符号65.625%Ne=Tlogr3×log2提高编码效率的方法：对符号串进行编码；引入一定的失真

4 3、定长编码方法（例） 1 2 3 4 5 6 7 2 3 4 5 6 6 1 1 1 1 1 1 1 2 2 2 2 2 2 2 U u u u u u u u U P                对U 的单个符号进行2进 制定长编码。 码元集：X={0, 1} 取l = 3 1 2 3 4 5 6 7 : : 001 010 011 100 101 110 111 U u u u u u u u W 7 1 63 ( ) ( )log ( ) 32 i i i H U P u P u      63 32 ( ) 65.625% log 3 log 2 c H U l r     l l   3  bit/符号 码元/符号 log log7 2.8 log log 2 N l q l N r 解：     码元/符号 提高编码效率的方法：对符号串进行编码；引入一定的失真

4.4变长编码定理（香农第一定理）无失真变长编码定理：用r元符号表对离散无记忆信源U的N长符号串进行变长编码，记N长符号串对应的平均码长为，那么，要做到无失真编码，平均码长必须满足：N≥ H,(U)N另一方面，一定存在唯一可译码，其平均码长l1满足: 兴<H,(U)+--NNN趋于无穷时平均码长和编码效率的极限：H(U)H,(U)lim llim=100%==H(U)limJimne=limN-8NN-8N-l logr2-N-00

5 4.4 变长编码定理(香农第一定理) 无失真变长编码定理：用r元符号表对离散无记 忆信源U的N长符号串进行变长编码，记N长符 号串对应的平均码长为 ，那么，要做到无失 真编码，平均码长 必须满足： 另一方面，一定存在唯一可译码，其平均码长 满足： ( ) N r l H U N  1 ( ) N r l H U N N   N l N l N l N趋于无穷时平均码长和编码效率的极限： lim lim ( ) N r N N l l H U   N   ( ) ( ) lim lim lim 100% log r c N N N H U H U l r l       