《信息理论与编码》课程教学资源（复习小结）第四章 离散无记忆信源无失真编码

第 4 章基本概念1.信源编码f信源编码是一一对应的变换或映射f，它把信源U输出的符号u，变换成码元序列w,：f:u,→w,，i=1,2,q码元序列w,称为码字，所有码字组成的集合W={wi,W2，"w,)称为码或码字集。2.平均码长1：T-2p(uy.码元/符号i=l3.无失真编码是保摘的：i=1,2,.qP(w)= P(u)4. 编码效率n。：H(U)ne=Tlogr5.码的穴余度%。：6.唯一可译码（UDC)：由该码的码字组成的任意有限长码字序列都能恢复成唯一的信源序列。7.Kraft不等式：非续长码和UDC存在的充要条件是2rs18.定长编码定理用r元符号表对离散无记忆信源U的N长符号序列进行定长编码，N长符号序列对应的码长为lN，若对于任意小的正数ε，有不等式>H(U)+8N-logr就几乎能做到无失真编码，且随着序列长度N的增大，译码差错率趋于0。反过来，若<H(U)-2Nlogr就不可能做到无失真编码，且随着N的增大，译码差错率趋于1。9.变长编码定理用r元符号表对离散无记忆信源U的N长符号序列进行变长编码，记N长符号序列对应的平均码长为1，那么，要做到无失真编码，平均码长必须满足≥H,(U)N另一方面，一定存在唯一可译码，其平均码长满足<H,(U)+1NN10.信源序列长度N趋于无穷时平均码长的极限：=H,(U)lim / =lim*N→00N→N11.最佳编码：使平均码长达到最小的编码，编出的码称为最佳码。12.变长编码方法：霍夫曼编码、费诺编码以及香农编码，其中霍夫曼编码是最佳编码。13.实用编码方法：游程编码、算术编码以及基于字典的编码。1

1 第 4 章基本概念 1. 信源编码 f 信源编码是一一对应的变换或映射 f ，它把信源U 输出的符号ui 变换成码元序列 wi ： f ：ui →wi ，i q =1,2, ,  码元序列 wi 称为码字，所有码字组成的集合 1 2 { , , } W ww w =  q 称为码或码字集。 2. 平均码长 l ： 1 ( ) q i i i l Pu l = = ∑ 码元/符号 3. 无失真编码是保熵的： ( ) () Pw Pu i i = i q =1,2, ,  4. 编码效率ηc : ( ) log c H U l r η = 5. 码的冗余度 c γ ： 6. 唯一可译码（UDC）：由该码的码字组成的任意有限长码字序列都能恢复成唯一的信 源序列。 7. Kraft 不等式：非续长码和 UDC 存在的充要条件是 1 1 i q l i r − = ∑ ≤ 8. 定长编码定理 用 r 元符号表对离散无记忆信源U 的 N 长符号序列进行定长编码，N 长符号序列对应 的码长为 Nl ，若对于任意小的正数ε ，有不等式 ( ) log Nl H U N r + ε ≥ 就几乎能做到无失真编码，且随着序列长度 N 的增大，译码差错率趋于 0。反过来，若 ()2 log Nl H U N r − ε ≤ 就不可能做到无失真编码，且随着 N 的增大，译码差错率趋于 1。 9. 变长编码定理 用 r 元符号表对离散无记忆信源U 的 N 长符号序列进行变长编码，记 N 长符号序列对 应的平均码长为 Nl ，那么，要做到无失真编码，平均码长必须满足 ( ) N r l H U N ≥ 另一方面，一定存在唯一可译码，其平均码长满足 1 ( ) N r l H U N N < + 10. 信源序列长度 N 趋于无穷时平均码长的极限： lim lim ( ) N r N N l l HU →∞ →∞ N = = 11. 最佳编码：使平均码长达到最小的编码，编出的码称为最佳码。 12. 变长编码方法：霍夫曼编码、费诺编码以及香农编码，其中霍夫曼编码是最佳编码。 13. 实用编码方法：游程编码、算术编码以及基于字典的编码