信息论.第4章无失真信源编码.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,1,第四章,无失真信源编码,即时码可用树图来构造,克拉夫特,不等式和,麦克米伦,不等式,设信源符号集为,S=,(,s,1,s,2,s,q,),，码符号集,为,X=,(,x,1,x,2,x,r,),，对信源进行编码，代码组,为,C=,(,w,1,w,2,w,q,),，相应码长分别,l,1,l,2,l,q,，,即时码存在,（,唯一可译码存在,）的充要条件为：,克拉夫特,证明不等式为即时码存在的充要条件；,麦克米伦,证明不等式为唯一可译码存在的充要条件。,2,简,单信源,S,存,在唯一可译定长码的条件为,：,3,N,次扩展信源,S,N,存在唯一可译定长码的条件为：,定长信源编码,定理,设有离散无记忆信源，熵为,H,(,S,),，若对信源的长为,N,的符号序列进行定长编码，设码字是从,r,个码符号集中选取,L,个码元构成，对于,0,只要满足,则当,N,足够大时，可实现译码错误概率任意小的等长编码，近似无失真编码。,反之，若 满足,则当,N,足够大时，译码错误概率趋于,1,。,4,信,源编码效率,编码速率：对于定长编码，编码速率定义为,编码效率：,5,变,长无失真信源编码定理,（香农第一定理）,设离散无记忆信源,其信源熵为,H,(,S,),，它的,N,次扩展信源,S,N,为,扩展信源熵为,H,(,S,N,),，,6,用,码符号集,X,=(,x,1,x,r,),对,S,N,编码，则总可以找到一种编码方法，构成唯一可译码，使信源,S,中的一个信源符号所需要的码字平均长度满足,当 时，,，是 对应的码字长度,7,编,码速率、编码效率、剩余度,(1),编码速率：变长编码的编码速率为,(2),编码效率：编码效率定义为,(3),剩余度：变长码的剩余度为,8,思路：出现较频繁的符号分配较短的码字,算法：,步骤,1,：以降序排列符号概率,p(s,i,)(i=1,2,q),，并把它们作为树的叶节点。,步骤,2,：当存在一个以上的节点时：,(a),找到具有最小概率的两个节点，并任意地分配,1,和,0,给这两个节点。,(b),合并这两个节点形成一个新的节点，它的概率是这两个合并节点的概率之和。返回步骤,1,。,步骤,3,：对于每个符号，通过跟踪从对应的叶节点到树的顶端所分配的比特来确定它的码字。叶节点的比特是该码字的最后一个比特。,9,哈夫曼编码,10,本章要求,掌握唯一可译码、即时码概念，唯一可译码、即时码存在的充要条件，唯一可译码判别准则。,理解定长信源编码定理。,掌握变长信源编码定理。,掌握二进制哈夫曼编码方法。,