《信息论第5章 信源编码》由会员分享，可在线阅读，更多相关《信息论第5章 信源编码（49页珍藏版）》请在金锄头文库上搜索。
1、第五章 信源编码,问题,对信源有两个重要问题,信源输出的信息量的度量问题；,如何更有效地表示信源输出的问题；,信源输出的符号序列，经过信源编码，变换成适合信道传输的符号序列，同时，在不失真或允许一定失真的条件下，用尽可能少的码符号来传递信源消息，提高信息传输的效率。,5.1 编码的定义,概述,信源编码是以提高通信的有效性为目的编码。 通常通过压缩信源的冗余度来实现。,信源编码,无失真信源编码,限失真信源编码,统计匹配编码,据信源符号的概率不同，编码的码长不同。概率大的信源符号编的码字短，使平均马场最短 ，达到压缩信源冗余度的目的,5.1 编码的定义,编码的定义,将信源符号序列按一定的数学规律映
2、射成码符号序列的过程是信源编码过程，完成编码功能的器件就是编码器。,信源,编码器,信道,码表,X,Y,编码器的作用是将信源符号集X中的符号变换成由码符号组成的一一对应的输出符号序列,编码器的输出称为码字，码字的集合称为码，信源符号对应码字需的码符号的个数表示码字长度，简称码长。,分组码才有对应的码表,5.1 编码的定义,举例怎么用编码器实现对信源符号的编码,信源的概率空间为 把信源符号编码为适合二元信道的二元码。二元信道是数字通信中最常用的一种新到，它的码符号集为0，1。,解：将信源通过一个二元信道传输，就必须把信源符号si变换成由0，1符号组成的码符号序列，即进行编码。可以用不同的二元码符号
3、序列与信源符号 一一对应，就得到不同的码。,定长码,变长码,5.1 编码的定义,码的分类,分组码和非分组码 分组码(块码):将信源符号集中的每个信源符号固定映射成一个码字 ，这样的码称为。 非分组码(树码):树码编码器输出的码符号通常与编码器的所有输入的信源符号都有关,5.1 编码的定义,码的分类,奇异码和非奇异码 若一种分组码中所有码字都不相同，也即信源符号和码字一一对应，则称为非奇异码，否则为奇异码。,奇异码,非奇异码,5.1 编码的定义,码的分类,唯一可译码和非唯一可译码 任意有限长的码元序列，只能唯一地分割成一个个码字，便是唯一可译码。,奇异码,非奇异码,EG: 10000100 由码
4、2产生(10,0,0,01,00)产生的码流，译码时可有多种分割方法，产生歧义。,唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。,一个分组码，若对以任意有限的整数N，其N次扩展码均维非奇异，则为唯一可译码 。,5.1 编码的定义,码的分类,即时码和非即时码 无须考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码 称为 即时码。,奇异码,非奇异码,定理：一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其它码字的前缀。,即时码,非即时码,5.1 编码的定义,码的分类,码,非分组码,分组码,奇异码,非奇异码,非唯一可译码,唯一可译码,即时码,非即时码,5.1 编码的
5、定义,树图,树根码字的起点 树枝数码的进制数 节点码字或码字的一部分 终端节点码字 节数码长 非满树变长码 满树等长码,根节点,终端节点,中间节点,一阶节点有最多r个； N阶节点最多有rN个；,若制定某个N阶节点为终端节点，表示一个信源符号，则该节点就不再延伸，相应的码字即为从树根到此端点的树枝标号序列，其长度为N。为即时码。,0,0,0,1,1,1,1,1,01,001,0001,5.1 编码的定义,克拉夫特Kraft不等式,举例,用二进制对符号集a1,a2,a3,a4进行编码，对应的码长分别为K1=1，K2=2，K3=2，K4=3，问是否存在满足这种Ki的唯一可译码？,解：据克劳夫特不等式
6、得 因此，不存在满足这种Ki的唯一可译码,其中：m是进制数； n是信源符号数；,各码字的长度Ki应符合：,该不等式是唯一可译码存在的必要条件，不是唯一可译码的必要条件。,5.1 编码的定义,定长码及定长信源编码定理,若要实现无失真编码，所编的码必须是唯一可译码。,5.2 无失真信源编码,若定长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码，定长非奇异码一定是唯一可译码。,若对信源S的N次扩展信源进行定长编码，信源的符号个数qN满足：,若对一个有q个信源符号的信源S进行编码，信源S存在唯一可译定长码的条件q rl，其中r是码符号集中的码元数，l是定长码的码长。,取对数,对于定长唯一可译
7、码，平均每个原始信源符号至少需要码符号的个数,英文电报信源有32个符号，对每一个符号进行二元编码，,每个英文电报符号至少要用5bit二元符号进行编码才能得到唯一可译码。,q=32,r=2,分析：考虑到符号出现的概率以及符号之间的相关性后，实际平均每个英文电报符号所提供的信息量约1.4bit，远小于5bit，因此定长编码后，每个码字只载1.5bit信息，5个二进制符号最大能载5bit信息 ，因此，定长编码的信息传输效率低。,解决方案: (1)对于不会出现的符号序列不予编码，这样不会造成误差； (2)对于概率非常小的信源符号序列不予编码，这样可能会造成一定误差，但当信源符号序列N足够大，误差概率非
8、常小,定长信源编码所需码长的理论极限值定长信源编码定理,5.2 无失真信源编码,英文电报信源有32个符号，对每一个符号进行二元编码，,每个英文电报符号至少要用5bit二元符号进行编码才能得到唯一可译码。,q=32,r=2,分析：考虑到符号出现的概率以及符号之间的相关性后，实际平均每个英文电报符号所提供的信息量约1.4bit，远小于5bit，因此定长编码后，每个码字只载1.5bit信息，5个二进制符号最大能载5bit信息 ，因此，定长编码的信息传输效率低。,解决方案: (1)对于不会出现的符号序列不予编码，这样不会造成误差； (2)对于概率非常小的心愿符号序列不予编码，这样可能会造成一定误差，但
9、当信源符号序列N足够大，误差概率非常小,定长信源编码所需码长的理论极限值定长信源编码定理,由于英文信源的极限熵H 1.4bit/信源符号，所以码长l满足l/N 1.4，即平均每个英文符号只需要近似1.4个二元码符号来表示，从而提高了信息传输效率,5.2 无失真信源编码,定长编码定理,由L个符号组成的，每个符号的熵为HL(X)的无记忆平稳信源符号序列(X1,X2,Xl,XL)，可用KL个符号Y1,Y2,Yk,YKL (每个符号有m中可能值)进行定长编码。,同样适用于平稳有记忆信源，将式中的H(S)改称极限熵即可。,5.2 无失真信源编码,5.2 无失真信源编码,编码效率,5.2 无失真信源编码,
10、举例,举例,5.2 无失真信源编码,变长码及变长信源编码定理,？什么样的码是唯一可译码或即时码？ Kraft不等式和McMillan不等式给出了即时码和唯一可译码的码长条件。,非奇异码,唯一可译码,唯一可译码,即时码,克拉夫特Kraft不等式,McMillan不等式,单个符号变长编码定理,离散平稳无记忆序列变长编码定理,M进制码元作变长编码， 序列长度为L个信源符号,编码效率,码的剩余度：,编码效率：,衡量各种编码方法与最佳码的差距,在二元无噪无损信道中：,在二元无噪无损信道中信息传输率：,单位是比特/码符号,无单位,举例,将信道中平均每个符号所能传送的信息量定义为信道的信息传输率R,编码效率
11、：信源的平均符号熵是采用了平均符号码长来编码后得到的效率。,二元码编码后的信息传输率和编码效率在数值上是相等的,比 较,若对这一信源采用定长二元码编码，要求编码效率达到96%，允许译码错误概率,定长码需要的信源序列长，使得码表很大，且总存在译码差错；而变长码编码效率达到96%时，只需要L=2，而且可实现无失真编码，编码后的信息传输率R也越来越接近无噪 无损二元信道的信道容量C=1bit/符号,通过对扩展信源进行编码，可以提高编码后的信道的信息传输率,最佳变长编码,香农编码方法 费诺编码方法 哈夫曼编码方法,5.2 无失真信源编码,凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码
12、字集合称为最佳变长码。 下面介绍几种最佳变长编码均为统计匹配编码，都是对出现概率较高的信源符号编短码，而对出现概率较小的信源符号编长码，从而使平均码长最短，达到最佳编码的目的。,香农编码,设有离散无记忆信源,香农编码方法的步骤,按信源符号的概率从大到小的顺序排队设,按下式依次计算每个信源符号的二元码码长,为了变成唯一可译码，计算第i个消息的累加概率,将累加概率变成二进制小数，取小数点后 数作为第i各信源符号的码字,举例,设有一单符号离散无记忆信源,试对该信源编二进制香农码。,解答：,费诺编码,按信源符号的概率从大到小的顺序排队,将依次排列的信源符号按概率值分为两大组，使两大组概率之和近似相同，
13、并对各组赋予一个二进制码元”0”和”1”；依次重复上述操作，直到每个组只剩下一个信源符号为止。,信源符号所对应的码字即为费诺码。,编码步骤如下：,举例与香农编码例子相同,费诺码比香农码的平均码长小，消息传输速率大，编码效率高！,哈夫曼编码,按信源符号的概率从大到小的顺序排队,编码步骤如下：,取两个概率最小的字母分别配以”0”和”1”两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队；对重排后的两个概率最小符号重复上述操作。依次重复上述操作，直到最后两个符号配以0和1为止。,从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。,举例与香农编码
14、例子相同,0,1,0,1,0,1,0,1,0,1,0,1,每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。,总结,比 较,上述几种编码都是针对离散无记忆信源的单个信源符号的编码，因此在编码时没有考虑信源符号之间的相关性。 霍夫曼码是最佳码，但实际使用时霍夫曼编码的设备还是比较复杂的。一般只适用于已知其统计特性的信源。若信源的统计特性不知或发生变化时，则采用所谓的通用编码方法。,霍夫曼编码,游程编码,基本原理：用一个符号值或串长表示连续出现的信源符号(这些连续出现的信源符
15、号构成了一段连续的“游程”)，使码符号序列长度少于原始信源符号序。,符号码,标识码,游程长度,举例：二元序列000101110010001 变换成游程序列31132131 0游程和1游程是交替出现的,范围：游程编码只适用于二元序列，对于多元信源，一般不直接利用游程编码。,5.3 常用信源编码方法简介,算术编码,编码基本思路：从全序列出发，将各信源序列的概率映射到0，1区间上，使每个序列对应着区间内的一点，也就是一个二进制的小数。这些点把0，1区间分成许多小段，每段的长度等于某一序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率编码的目的。,5.3 常用信源编码方法简介
16、,举例：,5.3 常用信源编码方法简介,第一个符号a1的概率区间,前两个符号a1a3的概率区间,符号a1a3a4的概率区间,设N长信源符号序列s的概率p(s)和累积概率F(s); 递推出N+1长信源符号序列sr的概率p(sr)和累积概率F(sr);r为新添加的符号,LZW编码,对于统计特性不可知时，需要用到具有自适应性能的通用编码方法，LZW编码就是一种基于字典的编码方法。,5.3 常用信源编码方法简介,LZW编码步骤如下： 1、初始化字典，读入一个字符放入W中。 2、读入一个字符K： 1不存在字符K可读：输出W对应的字码。结束编码。 2WK在字典中：将K加入到W末尾。 3WK不在字典中：将字码W输出，然后将WK加入字典，并令W为K。,LZW编码,LZW解码步骤如下： 1、初始化字典，读入一个字码W。 2
