信源编码与编码定理讲稿.ppt

信源编码与编码定理第一页，讲稿共四十二页哦第五章第五章：无失真信源编码无失真信源编码 5.1 编码问题的一般概念与定义编码问题的一般概念与定义(General Concepts and Definitions for Coding)所谓编码即信号的变换，或信号形式的变换。(signal transform or signal form transform)“通信的根本问题是将信源的输出经信道传输后在接收端(信宿)精确地或近似地重现出来。”这就是通信的本质，能在宿端再现发端的信号，所以信号形式上的变换就是通信的核心问题。变换(transform)称为编码(encoding)反变换(inverse-transform)则称为解(译)码(decoding)所有编码手段无外乎为了四个目的：.有效性(effectiveness)、.可靠性(reliability)、.安全性(security)、.经济性(economically)、第二页，讲稿共四十二页哦5.1 编码问题的一般概念与定义.解决有效性问题的编码信源编码(Source coding)亦称压缩编码(Compressed coding),所谓信源编码是指在无失真，或在有失真的条件下，如何利用尽可能少的符号来表述信源发出的消息。很显然，这种编码在于压缩信息的冗余度。根据编码的前提条件，信源编码又分为两类：无失真信源编码(Source coding without distortion)这种编码是一种可逆性编码(invertible coding)，即编码后的码字序列再经解码处理后，可无失真地恢复出原来的消息或消息序列。显然对于离散信源来说才有可能实现这种可逆编码，所以无失真信源编码仅适用离散信源。第三页，讲稿共四十二页哦5.1 编码问题的一般概念与定义 限失真信源编码(Source coding with finite distortion)此编码方式不能构成可逆编码，即编码后的码字序列经解码(反变换)处理后，所恢复的消息序列与发端的原消息序列存在有一定的失真。这种编码适合于连续信源模拟信号的编码，因为对连续信源的信号无论做何种处理，都无法避免信息的损失。比如语音信号，即使采用64Kbit/s以上的速率量化，也会有相当的信息产生丢失，只不过有时人耳察觉不到而已。实际工程中失真大量存在，而且在允许失真的限度下进行编码处理对于大多数用户都是可以接受的。因此对于信息量无限大的连续变量来说，按照熵编码的原则压缩，信息丢失的程度应该是最小。限失真信源编码的方法有很多，而且随信源的特性不同也有其不同的压缩模式。但它们都没有达到Shannon所给出的理论极限。第四页，讲稿共四十二页哦5.1 编码问题的一般概念与定义.解决可靠性问题的编码信道编码信道编码(Channel coding)亦称纠错编码。此类编码方式的目的，主要是解决如何充分地利用信道的能力来可靠地传输信息。我们把这种增加信道中抗干扰能力的编码称为信道编码。它所采用的处理方针恰恰与信源编码中压缩冗余的方针正好相反，是充分利用原有冗余度和进一步扩展冗余度的方针。所以这种编码技术是以牺牲传输的有效性为代价来提高传输的可靠性。.解决安全性问题的编码密码密码(Cryptography)这里的编码方法主要是为了解决信息传输过程中的安全性问题。即为使授权用户(empower-user)尽可能无失真地接收信息；而对于非授权用户(empower-user),则不允许其获取信息。第五页，讲稿共四十二页哦5.1 编码问题的一般概念与定义 .解决传输经济性问题的编码调制与复用调制与复用 (modulation&multiplex)是指为了充分利用信道，进一步提高通信系统的通信能力和降低通信成本而采用的编码技术。这类编码技术不仅广泛地应用于通信网络中，而且在计算机网络和有线电视网中也有大量的使用。这种编码技术大体分为这几类：时分复用与时分多址接入技术时分复用与时分多址接入技术(TDM&TDMA)频分复用与频分多址接入技术频分复用与频分多址接入技术(FDM&FDMA)码分复用与码分多址接入技术码分复用与码分多址接入技术(CDM&CDMA)波分复用波分复用(WDM)空分复用空分复用(SDM)统计复用统计复用(Statistical multiplex)第六页，讲稿共四十二页哦5.1 编码问题的一般概念与定义 以上四类编码技术都有其专门的学科论述，而信息论中仅定性、定量地给出各种编码方法的理论极限和性能界限。这些都是以极限定理的方式给出，因此它们就预示着在每一种具体的编码方法实现之前，就可给出它的实现前提和最好目标或可实现性。所以信息论中的编码定理，大多是我们用以评估系统优劣的界限；或估计系统是否值得改善的尺度；以及用以比较系统目标的最佳性或可实现性。总之学习信息论就是为了掌握这些性能界限；应用编码定理来评估实际问题。而具体的编码技术应在其它相应的专业课程来解决。第七页，讲稿共四十二页哦5.1 编码问题的一般概念与定义一、编码器与解码器一、编码器与解码器(encoder&decoder)编码器就是将消息符号序列变换成码字序列的装置(器件)，而解码器则是相应的反变换装置(或器件)。EncoderDecoder而码字序列可由K个码字所组成，则两种序列的个数分别为：编码器的输入是消息符号序列，其中符号的取值集合为S:；如果给定一个码字符号集合则编码器的输出可以由码字符号构造出一个码字序列与输入的消息符号序列相对应。设消息序列由L个符号构成 ，才可能产生一一对应的映射关系,形成可逆编码。则不可能实现无失真编码,只能实现有失真编码。第八页，讲稿共四十二页哦5.1 编码问题的一般概念与定义 例例5-1.如果消息符号为一如果消息符号为一16进制符号集合，若采用二进制码进制符号集合，若采用二进制码字符号，来对其进行可逆编码时需要码字长度如何？字符号，来对其进行可逆编码时需要码字长度如何？题解：如果信源所发的消息是以两个如果信源所发的消息是以两个16进制符号组成的序列，即所谓信源的进制符号组成的序列，即所谓信源的二次扩展，我们称为并源处理：二次扩展，我们称为并源处理：Combined Source Processing 则此刻的则此刻的码字序列的长度正是一个字节码字序列的长度正是一个字节(byte)长度。长度。第九页，讲稿共四十二页哦5.1 编码问题的一般概念与定义二、分组码二、分组码(块码块码)与非分组码与非分组码(序列码序列码)（Block code&Non-block code=Sequence code）以上例子中的码字序列均有一个固定字长，我们称为定长码字。(Fixed-length code word)如果码字长度不是一个固定的常数，我们则称为码字为变长码字。(Variable-length code word)无论是定长码，还是变长码它们均属于所谓分组码，因其特征是每一个码字都有一个有限的字长 l，所以分组码亦称为块码结构。还有一类码字是没有特定的字长，它是一个无限长或相当长的码字序列，不能按一个个的码字进行编译码，而是随消息序列按边输入边输出的机制实现编译码。这类编码方法称为非分组码 序列码序列码，如算术码等。第十页，讲稿共四十二页哦5.1 编码问题的一般概念与定义三、码树结构三、码树结构(Code Tree Structure)RootNodeBranchJoint branch0 1111111000000101 一个码树，从根部可分出m个分枝(或树叶leaf),这相对于m进制码。如果从根部开始，对于每个节点上引出的分枝都分配一个代码，则由根出发到任意一个终端节点，形成一联枝。若将一联枝的所有分枝的代码组合则形成码字序列。如果所有的联枝其长度相同，称为整树结构整树结构。由整树中可以得到定长码字，反之将得到变长码字。第十一页，讲稿共四十二页哦5.1 编码问题的一般概念与定义四、四、满树原则满树原则(Full Tree Principle)01200112201201122 比较以上两码树其相互差别在于从任意一节点出发能否保证其后续的枝数一定是m枝(相对于m进制码)。满足这一原则为满树结构，否则为非满树结构(non-full tree structure)。Full Tree Principle:其中k表示为中间节点的个数；N表示码树的联枝数或码字个数。满数满数结构结构非满数结构非满数结构第十二页，讲稿共四十二页哦5.1 编码问题的一般概念与定义 显然，任何一个二进制码字序列，其码树一定符合满 树结构，因为给定一个N，总可以找得到k个中间节点来满足满树原则：如果满树结构与整数结构相同时,有 其中，L是联枝串接的分枝数，k是中间节点个数。任何一个整树都符合满树结构，但任意的满树却不一定满足整树结构。由于整树的联枝长度相同，故此码树对应定长编码；而符合满树原则但又不是整树的结构常用于对应变长编码。第十三页，讲稿共四十二页哦5.1 编码问题的一般概念与定义000111222012Root书中图书中图5.3有误应符有误应符合整树定义。合整树定义。N=r112000000001111111222222220第十四页，讲稿共四十二页哦第五章第五章：无失真信源编码无失真信源编码 5.2 定长定长编码及定长编码定理编码及定长编码定理 (The Fixed-length Coding and its Theorem)前面我们已经推出利用定长编码实现可逆编码的条件是：Where K is the code length.因为定长编码可以实现一一对应的无失真编码，但是这时却没有实现信源编码的主要目的压缩消息序列的冗余度，甚至编码后的码字序列还可能增加新的冗余。那么如何采用定长编码来达到压缩的目的，这是我们这节重点概念。在第二章中已知道这样的结论：第十五页，讲稿共四十二页哦5.2 定长编码及定长编码定理定长编码及定长编码定理 上式表明对信源特性了解越多，则所需传输的信息量就越少。因此我们对Hm感兴趣，若把L个消息符号排成一个序列，不论其是否有记忆，只要统计出Hm的值，就对压缩序列的冗余有利。我们可以仅从符号间相互独立的序列中看到这一特点。从数学的大数定律中可以证明这样一个结论，如果对L个消息符号可构成无记忆序列，则按每一个序列的出现概率可将所有序列分成两大类：一类是高概率序列类高概率序列类；另一类是低概率序列类低概率序列类。所谓高概率序列是指属于此集合的元素，大体上将以几乎相同的概率出现。一般称为渐近等概率集合渐近等概率集合，记AL。而且L越大这种等等概率特性越明显概率特性越明显。另一类集合中的序列，它的出现概率很低，几乎为零。所以我们把这一部分序列集合称为低概率集合低概率集合，记为第十六页，讲稿共四十二页哦5.2 定长编码及定长编码定理定长编码及定长编码定理 例例52.设 如一个小盒子中装有100枚围棋子，其中75枚为白色棋子，25枚为黑色棋子。如果将100只同样比例的围棋子盒子倒入一大盒子中搅匀，问若随机性的装一小盒子围棋子，这盒棋子全是白色的概率是多少？若全是黑色棋子的概率又是多少？解：解：根据数学中的大数定律，落入高概率类集合的事件数目为：第十七页，讲稿共四十二页哦5.2 定长编码及定长编码定理定长编码及定长编码定理 这就是说如果给定了，总可以找到一个L 使得落入两个概率类集合的序列各有自己的出现概率。而落入渐近等概率集合的序列个数将是一个常数：第十八页，讲稿共四十二页哦5.2 定长编码及定长编码定理定长编码及定长编码定理 给出此例并不是希望大家掌握计算序列概率的方法，而是要大家了解定长编码达到压缩的目的。因为消息序列中的个数为：且且，显然，如果采用一一对应的定长编码策略，仅对渐进等概率集合中的消息序列一一对应的编码；而对那些几乎不出现的序列，不给分配码字序列，这样编码的出错概率将会控制到 以下。如果认为这样的失真还不够小，可以增加L的值，使得 足够小。因此无失真定长编码的理论是建立在误差概率几乎为零的意义下的无失真结果。即保证对于高概率类序列集合中的每一消息序列都能实现一一对应的编码，而且由于：这就体现出定长编码压缩序列冗余的效果。第十九页，讲稿共四十二页哦5.2 定长编码及定长编码定理定长编码及定长编码定理 介绍定长编码极限定理：设消息序列：和码字序列：再设：第二十页，讲稿共四十二页哦5.2 定长编码及定长编码定理定长编码及定长编码定理定理的含义：定理的含义：对于任何给定的 ，只要满足不等式的条件，则当L足够大时，就一定可以实现无失真编码，即Pe。逆定理：逆定理：如果不满足第一个不等式，而满足第二个不等式，则编码一定会产生失真，而且当L 时出错概率Pe将很快接近于1。例例53.一幅黑白图象信号，若每一行有一幅黑白图象信号，若每一行有100个象素点，个象素点，每个象素点的黑白灰度级为每个象素点的黑白灰度级为8；则对每一行；则对每一行100个点所构成的个点所构成的象素序列进行编码。即：象素序列进行编码。即：如果每一个象素点的分布于其位置无关这是一个无记忆序列。如果每一个象素点的分布于其位置无关这是一个无记忆序列。再举一例看其压缩比。第二十一页，讲稿共四十二页哦5.2 定长编码及定长编码定理定长编码及定长编码定理 由于需要编码的序列个数仅占原来序列的 分之一。即冗余度压缩掉 倍，但这仅是理论上的推导，实际上很难完成。因为不可能将所有的渐近等概率序列一一列出来，进行编码或存储到计算机内存中形成码书实现解码。所以这是定长编码的缺陷，一般我们常选用变长编码的方法。第二十二页，讲稿共四十二页哦第五章第五章：无失真信源编码无失真信源编码 5.3 变长变长编码及变长编码定理编码及变长编码定理 (The Variable-length Coding and its Theorem)一、变长码字的唯一可分码条件(The uniquely decodable condition for V-L coding)先看一个变长码字的例子：先看一个变长码字的例子：例例5411011111101/8S4111100011/8S300101001/4S2100001/2S1C4C3C2C1出现概率信源符号11X X00 0非既时码非既时码译码演示译码演示即时码第二十三页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 以上四种变长码方案中的后两种码字属于唯一可分码，即不用码字分隔符就能自行分隔解码。但这两者之间也有差别，C3属于即时码即时码(instantaneous code);而 C4属于非即时码非即时码(non-instantaneous code),它在解码时往往需要等后续码字出现时才能正确解码，因此效率不如前者高。为了得出最佳变长码，我们比较变长码的特点：1.高概率符号对应于短码字；低概率符号对应于长码字。高概率符号对应于短码字；低概率符号对应于长码字。2.无需额外的分隔符就可构成无需额外的分隔符就可构成唯一可分码唯一可分码(Uniquely-decodable code)异前置码异前置码(prefix code):即任何码字都不能成为其它码字的前缀。满足这样条件的变长码一定是唯一可分码唯一可分码，而且还是即时码即时码。下面给出变长码的唯一可分性的充分必要条件(sufficient and necessary condition)：二、二、Krafts 不等式(Krafts Inequality)用码树可以导出码字的唯一可分离性的充要条件是：第二十四页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 这里，Ki 表示第i i种码字的长度；m为m进制下码字符号的取值数。证明证明：设Ki的最大值为N，对于N节的整树来说，它的总联枝数为 ,如果对于一个Ki 长的码字来说，则它所对应的码树中的一个联枝的最终节点之后的 个分枝将不能再用，否则将不满足异前缀的条件。因此总共不用的枝数为：010101两边除以 则得：第二十五页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 以上证明的是 Krafts 不等式是满足码字可分离的必要条件。下面证明它的充分条件。若设不等式成立,则不等式(2)也一定成立。如果将满足不等式的一组码长为 的码字，在一个N节码树上按 找联枝，则我们一定可以找出符合 关系的码树，且保证每一个长度为 的联枝的终点没有后续分枝。这就保证了这套码字的唯一可分离性，即充分条件成立。010101010110111 所以Krafts 不等式是满足码字唯一可分离性的充要条件。第二十六页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 三三、最佳变长码(The Optimal Codes)对于变长编码而言，是否一定存在有一个最佳方案或称有一套最佳码字?即这套码字是满足唯一可分性中平均码长最短，而且是即时码。这个问题是信息论所应该讨论的问题。如果考虑一般性，设信源的消息符号序列为独立序列。为证明其编码的压缩性，可取N个码字来作为上述消息序列的变长码。则用Ki表示第i个码字的长度，可以采用以下原则来规定Ki的取值：第二十七页，讲稿共四十二页哦 5.3 变长编码及变长编码定理注意：取整的概念是为了适应码长Ki是一个整数的事实。第二十八页，讲稿共四十二页哦 5.3 变长编码及变长编码定理而平均每一个消息符号的平均码长为：而平均每一个消息符号的平均码长为：第二十九页，讲稿共四十二页哦 5.3 变长编码及变长编码定理四、变长编码定理(The variable-length coding theorem).按消息符号的变长编码定理按消息符号的变长编码定理(Theorem to the source letters)对于熵为H(S)的离散无记忆信源：若用m进制下的码字符号对该信源实现变长编码，则一定存在着一种唯一可分码，使其平均码长满足：反之，不满足上述不等式则一定会产生编码失真！反之，不满足上述不等式的平均序列码长 ，则一定会导致失真。.按消息符号序列的变长编码定理按消息符号序列的变长编码定理(The Variable-Length Coding Theorem to Sequences of L Source Letters)第三十页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 五、某些常用的变长编码方法(Some V-L coding methods)(1).Shannons algorithm:.把信源所给出的N个消息符号，按其概率递减顺序排列：.计算第 i 个消息的累加概率；(Cumulative Probability).将累加概率转换成二进制数；如0.5=0.1(二);0.25=0.01(二).按Shannons 公式 求出每一个码字的长度 ；.根据 取二进制的累加概率小数点之后的 位作为Shannons 码字。第三十一页，讲稿共四十二页哦 5.3 变长编码及变长编码定理例例55.Shannon 变长码变长码111105.1111010.960.04111015.1110100.910.05110115.1101100.850.0611004.1100000.780.0710104.101010.680.110014.100100.580.10113.011000.40.18002.0000000.4codewordki (二二)PiSi第三十二页，讲稿共四十二页哦 5.3 变长编码及变长编码定理(2).最佳变长码字Huffmans algorithm 在概率已知的前提下，可以证明Huffman 方法是最佳编码法，因为目前还没有一种变长编码方法可以超出Huffman 方法的编码效率。所以最佳变长码字就是 Huffman codeword.下面给出二元 Huffman 变长编码的编码步骤：第三十三页，讲稿共四十二页哦 5.3 变长编码及变长编码定理2.对概率最小的两个消息符号分别分配码字符号“1”和 “0”，分配原则应保持一致，如概率大的事件都是“1”。3.将最小的两个消息概率相加并且以相加后的概率之和重新参加概率排队；4.重复上述步骤(2,3);直至概率之和为1；5.从树根开始顺序地依次取出Huffman码字。下面以前题为例，按下面以前题为例，按Huffman编码步骤完成二元最佳编码步骤完成二元最佳变长编码：变长编码：例例5-6.二元二元Huffman编码方法图示：编码方法图示：1.把N个消息符号按其概率递减的顺序排列；第三十四页，讲稿共四十二页哦010.370.601101.0=root 5.3 变长编码及变长编码定理0.180.040.050.060.070.10.10.4010.09010.13010.190.2310Huffmans codes10010110000010001010001000011第三十五页，讲稿共四十二页哦 5.3 变长编码及变长编码定理00000001111111 显然从码树中可以看出Huffman码字一定是最佳变长码，而且编码法则简单易行。第三十六页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 定理：在已知概率的前提下，利用Huffman 编码方法所编制出 的变长码字，其编码效率一定是最优；即平均码长最短。证明：证明：按Huffman 编码法则1.则则,且且，设设（根据变长编码原则）（根据变长编码原则）如果，将已编出的任意两个码字与所对应的消息符号互换，如果，将已编出的任意两个码字与所对应的消息符号互换，而其余则不变，即：而其余则不变，即：第三十七页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 显然，当随意改动显然，当随意改动Huffman码字时，都将使得平均码长增加码字时，都将使得平均码长增加,最好最好情况下，最多不变；情况下，最多不变；即以上等号成立的条件。即以上等号成立的条件。因此因此,Huffman 是效率最高的变长编码。是效率最高的变长编码。证毕证毕 则,第三十八页，讲稿共四十二页哦 5.3 变长编码及变长编码定理(3).多元Huffman编码方法(Huffman coding for multi-element)我们已经讨论过满树原则：N=m+k(m-1)由于二进制码字序列一定符合满树原则，所以我们不必讨论它的最佳性。但是对于多元来说(如m进制下的码字符号)，则不一定都满足满树原则。如上题中消息符号数，在三进制码字中就有：所以为了符合满树原则，我们特增加以虚拟事件，设其概率为零，来参加算法中的概率排队，从而得到最佳的变长码字。例例5-7.还以上题为例，按三进制码字序列进行还以上题为例，按三进制码字序列进行Huffman 编码：编码：第三十九页，讲稿共四十二页哦 5.3 变长编码及变长编码定理0.180.040.050.060.070.10.10.40.00120.090120.222100.382101.0Root01011122122200201202第四十页，讲稿共四十二页哦 5.3 变长编码及变长编码定理 000011112222C1C2C3C4C5C6C7C8C9Q.E.D.第四十一页，讲稿共四十二页哦第五章(结束)第四十二页，讲稿共四十二页哦