信息论导论-第3章-2013

第3章离散信源无失真编码赵宏志2013年3月《信息论导论》2复习

信息熵的含义离散平稳无记忆信源马尔可夫信源3信源发出的消息需要传输或存储才能发挥作用，而对于传输或存储来说，现在二进制信号最具优势。信息传输的3个关键要求：效率、可靠、安全第3章离散信源无失真编码为了满足信道特性，往往需要将n元的信源符号序列变换为m元(现在一般为二元)的信源码序列，这一过程就是信源编码。4②怎样有效地利用码字的每一个比特去携带信息，即在编码过程中怎样用最少的比特数去表示信源的信息熵？①怎样保证编码和译码过程不丢失信息，即怎样实现无失真编码？③无失真编码的具体方法？第3章离散信源无失真编码信源编码的3个问题是：5第3章的主要内容与课时一、无失真编码的基本思路二、无失真编码定理三、香农编码四、霍夫曼编码6一、无失真编码的基本思路先看一个单符号离散信源无失真编码的例子：其信息熵7无失真编码的含义：保证符号元与码字一一对应，此时用码序列表示的信源信息熵保持不变。最简单的无失真编码：4-2进制变换，即该编码的码长K=2，码字的每一个比特携带信息的效率即编码效率一、无失真编码的基本思路思考：效率可以再提高吗？8为了压缩比特数，可以考虑对信源符号进行不等长编码，如码字的比特数中约有17.6%未携带信息，属于冗余比特，传输效率不高。但该编码不能实现无失真译码，即不能保证符号元与码字的一一对应。一、无失真编码的基本思路可以无失真译码吗？9其平均码长一种能保证符号元与码字一一对应的不等长编码为编码效率与第一种编码相比，码字压缩了0.3个比特，编码效率提高了14.5%。一、无失真编码的基本思路10进一步，如果对该信源的二次扩展信源进行无失真编码，一种能保证符号序列元与码字一一对应的不等长编码为一、无失真编码的基本思路11其平均码长编码效率一、无失真编码的基本思路12与第二种编码相比，码字又压缩了约0.04个比特，编码效率提高了2.1%。总结该例子，有以下几点结论与问题：①一般采用不等长编码，使平均码长接近信息熵，从而在无失真前提下提高编码效率；编码的基本原则是大概率符号元编成短码，小概率符号元编成长码。一、无失真编码的基本思路13②由于码长不等，如何保证接收端从码序列中唯一地分割出对应与每一个符号元的码字，以实现无失真译码？③对符号序列进行组(block)编码有助于使平均码长接近信息熵，但平均码长能否无限接近信息熵，从而使编码效率趋近1？如果能，对序列长度有什么要求？一、无失真编码的基本思路引发的问题14第3章的主要内容与课时一、无失真编码的基本思路二、无失真编码定理三、香农编码四、霍夫曼编码15二、无失真编码定理1、异前置码如果所采用的不等长编码使接收端能从码序列中唯一地分割出对应与每一个符号元的码字，则称该不等长编码为单义可译码。单义可译码中，如果能在对应于每一个符号元的码字结束时立即译出的称为即时码，如果要等到对应与下一个符号元的码字才能译出的称为延时码。16码A--不是单义可译码，它有二义性码B和码C才是单义可译码；码B是延时码，它需等到对应与下一个符号元的码字开头0才能确定本码字的结束，存在译码延时，只有码C才是即时码。二、无失真编码定理17从树根开始到每一个终节点的联枝代表一个码字，故相应的异前置码码C的特点是：任何一个码字都不是其他码字的前缀，因此将该码称为异前置码。异前置码可以用树图来构造：一个三元码树图二、无失真编码定理18码C所对应的二元码树图m元长度为ki,i=1,2,…,n的异前置码存在的充分必要条件是：该充要条件称为克拉夫特(Kraft)不等式。二、无失真编码定理19设m元异前置码第i个码字的长度为ki,i=1,2,…,n考虑一个N级满树，在第N级共有mN个节点，在第ki级共有mki个节点。根据异前置码的定义，第i个码字后的节点不能再用，故第N级不能用的节点数为mN-ki构造异前置码的码树图第N级上总共不能用的节点总数二、无失真编码定理20【无失真编码定理】如果N维离散平稳信源的平均符号熵为HN(X1X2…XN)，对信源符号序列进行m元不等长组编码，一定存在一种无失真编码方法，当N足够大时，使得每个信源符号所对应码字的平均比特数式中，ε为任意给定的小正数。二、无失真编码定理21Kraft不等式设不等长组编码对应于符号元ai=xi1xi2…xiN的码字长度为ki说明该编码是异前置码【无失真编码定理】的证明22其平均码长【无失真编码定理】的证明23无失真编码定理又叫香农第一定理，该定理从理论上阐明了编码效率的理想无失真编码的存在性.【无失真编码定理】的证明24无失真编码的代价是取无限长的符号序列进行组编码，即只有N→∞时可见，极限熵H∞是一个界限，通常也称为(信源编码的)香农界。二、无失真编码定理25刚才讨论了一般的离散平稳信源，对其他已学过的离散信源，根据无失真编码定理可得出什么结论呢？N维离散平稳无记忆信源m阶马尔科夫信源二、无失真编码定理26N维离散平稳无记忆信源由于其平均符号熵HN(X1X2…XN)=H(X)式中，ε为任意给定的小正数。此时香农界为H(X)。二、无失真编码定理故对信源符号序列进行m元不等长组编码，一定存在一种无失真编码方法，当N足够大时，使得每个信源符号所对应码字的平均比特数27m阶马尔科夫信源(m<N),N足够大时，平均符号熵HN(X1X2…XN)=Hm+1式中，ε为任意给定的小正数。此时香农界为Hm+1。二、无失真编码定理对信源符号序列进行m元不等长组编码，一定存在一种无失真编码方法，使得每个信源符号对应码字的平均比特数28平稳无记忆信源的香农界H(X)大于m阶马尔科夫信源的香农界Hm+1，而m阶马尔科夫信源的香农界Hm+1又大于一般平稳信源的香农界H∞。因此，对离散平稳信源进行无失真编码，每个信源符号所对应码字的平均比特数平稳无记忆信源最多，m阶马尔科夫信源次之，一般平稳信源最少。二、无失真编码定理29一、无失真编码的基本思路二、无失真编码定理三、香农编码四、霍夫曼编码第3章的主要内容与课时30三、香农编码设离散信源香农编码是一种采用异前置码的m进制编码方法。不失一般性，设p(x1)>p(x2)>…>p(xn)，且31①将符号元xi按概率进行降序排列；②令p(x0)=0，计算第i个码字的累加概率③确定第i个码字的码长ki，ki为满足下列不等式的最小整数：④将pa(xi)用二进制表示，取小数点后ki位作为符号元xi的码字。三、香农编码—编码步骤32例1，对单符号离散信源编二进制香农码，并计算其编码效率。解：①将xi按概率进行降序排列xip(xi)pa(xi)ki码字x10.5x20.3x30.15x40.05三、香农编码—举例33②令p(x0)=0，计算第i个码字的累加概率pa(x1)=0pa(x2)=0+0.5=0.5pa(x3)=0.5+0.3=0.8pa(x4)=0.8+0.15=0.95③确定第i个码字的码长ki：三、香农编码34④将pa(xi)用二进制表示，取小数点后ki位作为xi的码字pa(x1)=0.0=(0.0)2→0pa(x2)=0.5=(0.10)2→10pa(x3)=0.8=(0.110…)2→110pa(x4)=0.95=(0.11110…)2→11110三、香农编码35xip(xi)pa(xi)ki码字x10.5010x20.30.5210x30.150.83110x40.050.95511110三、香农编码36三、香农编码37例2，分别对下列单符号离散信源和该信源的二次扩展信源编二进制香农码，并计算其编码效率。解：⑴对单符号离散信源编码pa(x1)=0pa(x2)=0+0.5=0.5pa(x3)=0.5+0.3=0.8三、香农编码38pa(x1)=0.0=(0.0)2→0pa(x2)=0.5=(0.10)2→10pa(x3)=0.8=(0.110…)2→110三、香农编码39xip(xi)pa(xi)ki码字x10.5010x20.30.5210x30.20.83110三、香农编码40⑵对二次扩展信源编码将符号元ai按概率进行降序排列pa(a1)=0pa(a2)=0+0.25=0.25pa(a3)=0.25+0.15=0.4pa(a4)=0.4+0.15=0.55三、香农编码41pa(a5)=0.55+0.1=0.65pa(a6)=0.65+0.1=0.75pa(a7)=0.75+0.09=0.84pa(a8)=0.84+0.06=0.9pa(a9)=0.9+0.06=0.96三、香农编码42三、香农编码43pa(a1)=0.0=(0.00)2→00pa(a2)=0.25=(0.010)2→010pa(a3)=0.4=(0.011…)2→011三、香农编码44pa(a4)=0.55=(0.1000…)2→1000pa(a5)=0.65=(0.1010…)2→1010pa(a6)=0.75=(0.1100)2→1100pa(a7)=0.84=(0.11010…)2→11010pa(a8)=0.9=(0.11100…)2→11100pa(a9)=0.96=(0.11101…)2→11101aip(ai)pa(ai)ki码字a10.250200a20.150.253010a30.150.43011三、香农编码45a40.10.5541000a50.10.6541010a60.090.7541100a70.060.84511010a80.060.9511100a90.040.96511101三、香农编码46三、香农编码47DavidAlbertHuffman(August9,1925–October7,1999)四、霍夫曼编码1944年毕业于俄亥俄州立大学电子工程系，毕业后服役于美国海军，大黄蜂号航母，兵种：厨师。1949年获得俄亥俄州立大学电子工程系硕士学位；1953年获MIT电子工程系博士学位。1953年博士毕业后留校任教；1967年起任教于加州大学圣克鲁兹分校，直至1994年退休。霍夫曼一生建树很多，主要贡献有信息论、编码、雷达信号设计、逻辑电路设计。他最著名的霍夫曼编码来自于硕士期间的某门课程的期末考试报告。霍夫曼从未为他的成就申请专利，座右铭“Myproductsaremystudents”48四、霍夫曼(Huffman)编码设离散信源霍夫曼编码也是一种采用异前置码的m进制编码方法。不失一般性，设p(x1)>p(x2)>…>p(xn)，且霍夫曼编码的编码效率高于香农编码。49①将符号元按概率进行降序排列；②为概率最小的符号元分配一个码元1，概率次小的符号元分配一个码元0；③将概率最小的两个符号元合并成一个新的符号元，用两者概率之和作为该新符号元的概率；重复以上三个步骤，直到最后合并出一个以1为概率的符号元，结束编码。四、霍夫曼(Huffman)编码--编码步骤50例1，对单符号离散信源编二进制霍夫曼码，并计算其编码效率。解：①将符号元按概率进行降序排列符号元概率x10.5x2x3x40.30.150.05四、霍夫曼(Huffman)编码5110②为概率最小的符号元分配一个码元1，概率次小的符号元分配一个码元0；符号元概率x10.5x2x3x40.30.150.05③将概率最小的两个符号元合并成一个新的符号元，用两者概率之和作为该新符号元的概率；0.2x´3四、霍夫曼(Huffman)编码52重复以上三个步骤，直到最后合并出一个以1为概率的符号元，结束编码。符号元概率x10.5x2x´30.30.2100.5x´2符号元概率x10.5x´20.5101x´1四、霍夫曼(Huffman)编码53码字码长符号元概率x10.5x2x3x40.30.150.050.20.511110000101101111233显然，所编霍夫曼码构成二元码树，为异前置码。四、霍夫曼(Huffman)编码—整个过程54四、霍夫曼(Huffman)编码55例2，分别对下列单符号离散信源和该信源的二次扩展信源编二进制霍夫曼码，并计算其编码效率。解：⑴对单符号离散信源编码符号元概率x10.6x2x30.30.10.410110码字码长01011122四、霍夫曼(Huffman)编码56四、霍夫曼(Huffman)编码57⑵对二次扩展信源编码将符号元ai按概率进行降序排列霍夫曼编码过程为四、霍夫曼(Huffman)编码580.040.071111000符号元概率a10.36a2a3a40.180.180.09a50.06a6a70.060.03a80.03a90.010.12010.160.3610100.28100.6410四、霍夫曼(Huffman)编码590.040.071111000符号元概率a10.36a2a3a40.180.180.09a50.06a6a70.060.03a80.03a90.010.12010.160.3610100.28100.6410码字码长100001000101010010111010110110134634546010100四、霍夫曼(Huffman)编码60四