离散无记忆源.ppt
《离散无记忆源.ppt》由会员分享,可在线阅读,更多相关《离散无记忆源.ppt(31页珍藏版)》请在三一文库上搜索。
1、离散无记忆源,字母表A=a1,aK,概率分别为p1,pK,长为L的源输出序列uL=u1,uL,共有KL种序列 码符号字母表B=b1,bD,以码符号表示源输出序列,D元码 等长D元码,不等长D元码的个数 单义可译码,每个消息都至少有一个码字与之对应。 单义等长可译码存在充要条件DNKL 由此可得,NLlogK/logD,DMS的等长编码,NlogDLH(U) H(U)是统计平均值,L达到无限时,一个具体的源输出序列的平均每符号的信息量才等于H(U) 选L足够长,使 NlogDLH(U)+eL L趋向于无穷,eL趋向于0,保证不降低效率。不能保证单义可译,但可以保证非单义可译引起的误差可以渐进的任
2、意小。 如何证明?,弱、强e典型序列集,定义3.2.1:令H(U)是集U, p(ak)的熵,e是正数,集合,定义为给定源U输出的长为L的典型序列集。,定义3.2.2:令H(U)是集U, p(ak)的熵,e是正数,集合,弱e-典型序列集,定义为给定源输出的长为L的e典型序列集,其中Lk 是在L长序列中符号ak出现的次数,强e-典型序列集,例3.2.2,典型二项序列出现的概率:,当L足够大,,信源划分定理,定理3.2.1:给定信源U, p(ak)和e0,当L,PrT(L, e)1,或对所有e0,存在有正整数L0,使得当LL0时有,信源划分定理,系1:特定典型序列出现的概率 若uLTU(L,e),则
3、,信源划分定理,典型序列的数目: 系2:当L足够大时,对于给定的信源和e0,典型序列的个数TU(L,e)满足,信源划分定理,信源消息可以分为2组:(渐进等同分割性) 1、典型序列 高概率集,渐进等概序列,AEP序列 2、非典型序列 低概率集,编码速率和等长编码定理,编码速率:R=(1/L)logM=(N/L)logD, M为码字总数 可达速率:对于给定信源和编码速率R以及任意e0,若有L0,以及编译码方法,使得LL0,错误概率小于e,R是可达的 等长编码定理: RH(U),R是可达的,RH(U),R是不可达的 编码效率:h=H(U)/R,平均码长,几个定义,唯一可译码 逗点码,无逗点码 字头或
4、前缀 异字头码或异前缀码 树码,满树,非满树,全树 树码构造异字头码,ShannonFano编码 异字头码可以通过树图构成,D元码 将信源符号按出现概率从大到小排列 每次信源符号化为概率近似相等的D个子集 这样可以保证D个码元近似等概,每个码字承载的信息量近似最大,码就近似最短。 理想情况I(ak)=nklogD, p(ak)=D-nk,异字头码存在的充分必要条件,Kraft不等式 定理3.3.1: 长度为n1,n2,nk的D元异字头码存在的充分必要条件是:,异字头码不唯一,且满足上式的码不一定是异字头码,唯一可译码,定理3.3.2:唯一可译码必然满足Kraft不等式 系:任一唯一可译码可用各
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 记忆
链接地址:https://www.31doc.com/p-2595948.html