资源描述：
《信息论讲义-第五章(13讲)new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、信息理论基础信息理论基础第13讲北京航空航天大学201教研室陈杰回顾1.编码器—信源符号集S=(s,s,…s)12q—码符号集X=(x,x…x)12r—代码组(SourceCode)C=(W,W,…W)12q—码字(Codeword)W=(x,x,…x)il1l2li2.分组码—奇异性(Non-singular)—唯一可译性(Uniquelydecodable)—即时码(Instantaneous)2回顾AllcodesNon-singularcodesUniquelydecodablecodesInstantan
2、eouscodesFigure5.1.Classesofcodes3回顾3.定长编码3.1唯一可译定长码例:logqLqlog+1>l=≥英文字符数q=27,logrNrlog且logq=4.754bit2信源熵H(S)=4.03bit,编码速率取编码速率R=log2qLrlogRq=≥log则编码效率η=85%N编码效率HS()HS()η=≤Rqlog4回顾3.定长编码3.2定长码编码定理(1)正定理：DIs[()]Lrlogp≤ip→0RH=≥+()SεE2ENNε(2)逆定理：Lrlogp≥−12−Nεp→1
3、RH=≤−()2SεEEN5回顾3.定长编码1−η3.2定长码编码定理ε=H()sη根据正定理，令p<δEDIs[()]DIs[()]iip≤<δN≥E22NεεδLrlogHS()Hs()RH=≥+()Sε≤Nη=RHs()+εDIs[()]2iηN≥⋅22HS()(1)−ηδ65.4变长码•引入1.变长码无需很长的码长就能实现高效率的无失真信源编码2.变长码必须是唯一可译码，才能实现无失真编码3.变长码是唯一可译码的充要条件：(1)非奇异码(2)任意有限次扩展码是非奇异码4.变长码必须即时码75.4.1码的分类
4、和主要编码方法信源编码方法：⑴匹配编码：概率大的信源符号，代码长度短；反之，代码长度长⑵变换编码：从一种空间变换成另一种空间，然后进行编码⑶识别编码：对有标准形状的文字、符号和数据进行编码85.4.2克拉夫特不等式和麦克米伦不等式定理：设信源符号集为S=(s,s,…，s)，码符号集12q,为X=(x,x,…x)，对信源进行编码，代码组12rC=(W,W,…W)，相应码长分别l,l,…l，12q12q即时码存在（唯一可译码存在）的充要条件为：q−li∑r≤1i=195.4.2克拉夫特不等式和麦克米伦不等式释：(1)克
5、拉夫特(Kraft)不等式为即时码存在充要条件(2)麦克米伦(McMilan)不等式为唯一可译码存在充要条件(3)该定理不能作为判别一种码是否为即时码（唯一可译码）的判据(4)当码字长度和码符号满足该不等式时，必可构造出即时码（唯一可译码）105.4.3唯一可译码判别准则•唯一可译码：如果一个分组码对于任意有限的整数N，其N次扩展码均为非奇异码，则为唯一可译码•唯一可译码的充要条件：（见书上128页）115.4.4变长信源编码定理1.码平均长度离散无记忆信源为⎡ss12?sq⎤[]SP=⎢⎥p()()sps?p()
6、s⎣12q⎦编码后的码子WW,,,?W12ql,l,?,l码字的长度12q因为是唯一可译码，s和W一一对应iips()=pW()iiqq则码字平均长度为L==∑∑pWl()iipsl()iiii==11125.4.4变长信源编码定理释：(1)L是每个信源符号编码需要的平均码符号个数；(2)编码后，每个信源符号s平均用L个码符i号来表示，平均每个码符号携带的信息量是信道的信息传输率H(s)R=H(X)=bit/码符号L(3)若传输一个码符号需要t秒，则每秒传输率为1H(s)Rt=R=bit/秒tL故LRt信息传输率高
7、135.4.4变长信源编码定理2.紧致码定义：对于某一个信源和某一码符号集，若有一个唯一可译码，其平均码长度L小于所有其它唯一可译码的平均码长度，则称该码为紧致码（也称最佳码）•释：无失真信源编码核心问题是寻找紧致码145.4.4变长信源编码定理3.定理：（平均码长下界）设离散无记忆信源⎡ss12?sq⎤[]SP=⎢⎥p()()sps?p()s⎣12q⎦的信源熵为H(S)，用码符号集X={x,x,?,x}进行12q编码，则存在一种编码方式构成唯一可译码，平均码长L满足H(S)H(S)≤L<1+logrlogr155
8、.4.4变长信源编码定理HS()释：(1)L的极限值为，即下界；小于Llogr下界，则唯一可译码不存在log()ps(2)当选择时i，才能达到下界l=−ilogr(3)紧致码平均码长不一定达到下界(4)达到下界的唯一可译码是紧致码H(S)(5)紧致码最短码长L=logr165.4.4变长信源编码定理4变长无失真信源编码定理（香农第一定理）定理：设离散无记忆信
