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

《信息论.第4章无失真信源编码.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、1第四章无失真信源编码即时码可用树图来构造克拉夫特不等式和麦克米伦不等式设信源符号集为S=(s1,s2,…,sq,)，码符号集为X=(x1,x2,…,xr)，对信源进行编码，代码组为C=(w1,w2,…,wq)，相应码长分别l1,l2,…,lq，即时码存在（唯一可译码存在）的充要条件为：克拉夫特证明不等式为即时码存在的充要条件；麦克米伦证明不等式为唯一可译码存在的充要条件。2简单信源S存在唯一可译定长码的条件为：3N次扩展信源SN存在唯一可译定长码的条件为：定长信源编码定理设有离散无记忆信源，熵为H(S)

2、，若对信源的长为N的符号序列进行定长编码，设码字是从r个码符号集中选取L个码元构成，对于>0只要满足则当N足够大时，可实现译码错误概率任意小的等长编码，近似无失真编码。反之，若满足则当N足够大时，译码错误概率趋于1。4信源编码效率编码速率：对于定长编码，编码速率定义为编码效率：5变长无失真信源编码定理（香农第一定理）设离散无记忆信源其信源熵为H(S)，它的N次扩展信源SN为扩展信源熵为H(SN)，6用码符号集X=(x1,…,xr)对SN编码，则总可以找到一种编码方法，构成唯一可译码，使信源S中的一个信源符

3、号所需要的码字平均长度满足当时，，是对应的码字长度7编码速率、编码效率、剩余度(1)编码速率：变长编码的编码速率为(2)编码效率：编码效率定义为(3)剩余度：变长码的剩余度为8思路：出现较频繁的符号分配较短的码字算法：步骤1：以降序排列符号概率p(si)(i=1,2,…,q)，并把它们作为树的叶节点。步骤2：当存在一个以上的节点时：(a)找到具有最小概率的两个节点，并任意地分配1和0给这两个节点。(b)合并这两个节点形成一个新的节点，它的概率是这两个合并节点的概率之和。返回步骤1。步骤3：对于每个符号，通过跟

4、踪从对应的叶节点到树的顶端所分配的比特来确定它的码字。叶节点的比特是该码字的最后一个比特。9哈夫曼编码10本章要求掌握唯一可译码、即时码概念，唯一可译码、即时码存在的充要条件，唯一可译码判别准则。理解定长信源编码定理。掌握变长信源编码定理。掌握二进制哈夫曼编码方法。