《李梅李亦农《信息论基础教程》课件教案无失真信源编码》由会员分享，可在线阅读，更多相关《李梅李亦农《信息论基础教程》课件教案无失真信源编码（86页珍藏版）》请在金锄头文库上搜索。
1、第五章：无失真信源编码,一、信源编码的相关概念,二、定长码及定长信源编码定理,三、变长码及变长信源编码定理,四、变长码的编码方法,五、实用的无失真信源编码方法,第五章：无失真信源编码,信源编码的作用：使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。,以提高通信有效性为目的。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均码长。,1. 信源编码概述,一、信源编码的相关概念,第五章：无失真信源编码,信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理： 无失真信源编码
2、定理 限失真信源编码定理,本章主要介绍无失真信源编码，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相匹配的码。,1. 信源编码概述（续1）,一、信源编码的相关概念,第五章：无失真信源编码,信源的统计剩余度主要决定于以下两个因素 ：1）无记忆信源中，符号概率分布的非均匀性；2）有记忆信源中，符号间的相关性及符号概率分布的非均匀性。,1. 信源编码概述（续2）,怎样压缩信源的冗余度？ 1) 去除码符号间的相关性。 2) 使码符号等概分布。,一、信源编码的相关概念,第五章：无失真信源编码,2. 信源编码器模型,信宿,信道,信源,编码器,译码器,Y,X,S,S,信源编码：将信源符号序列
3、按一定的数学规律映射成码符号序列的过程。,图1 信源编码器模型,一、信源编码的相关概念,第五章：无失真信源编码,将信源符号集中的符号 （或者长为N的信源符号序列）映射成由码符号 组成的长度为 的一一对应的码符号序列 。,编码器,码字,2. 信源编码器模型（续1）,一、信源编码的相关概念,例: 5.1,第五章：无失真信源编码,2. 信源编码器模型（续2）,一、信源编码的相关概念,第五章：无失真信源编码,3. N次扩展码,一、信源编码的相关概念,第五章：无失真信源编码,3. N次扩展码（续1）,一、信源编码的相关概念,编码器输出的码符号序列 称为码字；长度 称为码字长度，简称码长；全体码字的集合C
4、称为码。 若码符号集合为X=0,1，则所得的码字都是二元序列，称为二元码。,第五章：无失真信源编码,4. 关于编码的一些术语,一、信源编码的相关概念,将信源符号集中的每个信源符号 固定的映射成某一个码字 ，这样的码称为分组码。,若一个码中所有码字的码长都相等，则称为定长码；否则为变长码。,第五章：无失真信源编码,5. 奇异性,若一个码中所有码字互不相同，则称为非奇异码； 否则为奇异码。,一、信源编码的相关概念,第五章：无失真信源编码,6. 唯一可译性,若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为唯一可译码。,一、信源编码的相关概念,唯一可译码应当满足的条件,码字与
5、信源符号一一对应,2) 不同的信源符号序列对应不同的码字序列,1),6. 唯一可译性（续1）,第五章：无失真信源编码,一、信源编码的相关概念,第五章：无失真信源编码,6. 唯一可译性（续2）,例1：,1),奇异码,11,译码,奇异码一定不是唯一可译码,一、信源编码的相关概念,第五章：无失真信源编码,6. 唯一可译性（续3）,2),非奇异码,0,1 0,0 0,0 1,0,0 1,0 0,0 0,1 0,译码,译码,一、信源编码的相关概念,第五章：无失真信源编码,6. 唯一可译性（续4）,3),等长码,非奇异码,0 0 0 1 1 0 1 1,唯一可译码,译码,一、信源编码的相关概念,第五章：无
6、失真信源编码,6. 唯一可译性（续5）,4),唯一可译码,1 0,0,1,为非即时码,1 1 0 1 0 0 1 0 0 0,一、信源编码的相关概念,第五章：无失真信源编码,6. 唯一可译性（续6）,5),1 0 1 0 0 1 0 0 0 1,唯一可译码,0 1,即时,为即时码,任何一个码字不是其它码字的前缀,一、信源编码的相关概念,第五章：无失真信源编码,7. 即时码,若某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码，则称此码为即时码。,问题：1) 判断下面的码是否即时码？ 0 10 110 1112) 等长码是否即时码？,一、信源编码的相关概念,第五章：无失真信源
7、编码,7. 即时码（续1）,唯一可译码成为即时码的充要条件：定理5.1 一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。,一、信源编码的相关概念,7. 即时码（续2）,第五章：无失真信源编码,一、信源编码的相关概念,7. 即时码（续3）,第五章：无失真信源编码,一、信源编码的相关概念,第五章：无失真信源编码,8. 即时码的构造方法,用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端节点上就可以得到即时码。,一、信源编码的相关概念,8. 即时码的构造方法（续1）,00,010,011,一阶节点,二阶节点,三阶节点,100,110,
8、101,111,第五章：无失真信源编码,一、信源编码的相关概念,第五章：无失真信源编码,8. 即时码的构造方法（续2）,一、信源编码的相关概念,用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端节点上就可以得到即时码。 每个中间节点都正好有r个分枝的树称为整树（满树）。 所有终端节点的阶数都相等的树为完全树,第五章：无失真信源编码,8. 即时码的构造方法（续3）,一、信源编码的相关概念,第五章：无失真信源编码,图2 各类码之间的关系,8. 即时码的构造方法（续4）,一、信源编码的相关概念,1. 唯一可译定长码存在的条件,对于定长码，非奇异码一定是唯一可译
9、码。 所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个码字 一一对应。 设信源符号集中共有 个符号， ， 码符号集中共有 种码元， ， 定长码码长为 , 则要满足非奇异性必然有,该条件是必要条件，而不是充分条件。,第五章：无失真信源编码,二、定长码及定长信源编码定理,1. 唯一可译定长码存在的条件（续1）,如果对N次扩展信源 进行定长编码，要满足非奇异性，须满足条件,其中,当r=2 时，,第五章：无失真信源编码,二、定长码及定长信源编码定理,当N=1时，,1. 唯一可译定长码存在的条件（续2）,例2：英文字母表中，每一字母用定长编码转换成二进制表示，码字的最短长度是多少？,解：,信源
10、符号数,码符号数,第五章：无失真信源编码,二、定长码及定长信源编码定理,N=2 H(S) = 1.75,第五章：无失真信源编码,2. 定长信源编码定理,二、定长码及定长信源编码定理,定理5.3.1 设离散平稳无记忆信源的熵为H(S), 若对N次扩展信源 进行定长编码，则对于任意 0，只要满足 则当N足够大时，可实现几乎无失真编码，即译码错误概率 PE 为任意小；反之，则不可能实现无失真编码，如果 当N足够大时，译码错误概率 PE 为1。,2. 定长信源编码定理（续1）,第五章：无失真信源编码,定长编码定理同样也适用于离散平稳有记忆信源，差别是要将信源熵 改为极限熵 。,二、定长码及定长信源编码
11、定理,可以验证，对定长信源编码来说，要想实现无失真信源编码，N常常要取非常大的值。这在实际应用中很难实现。,2. 定长信源编码定理（续2）,第五章：无失真信源编码,当r=2时,二、定长码及定长信源编码定理,第五章：无失真信源编码,2. 定长信源编码定理（续3）,定义： 为编码信息率定义： 为编码效率。,比特/信源符号,比特/信源符号,比特/信源符号,二、定长码及定长信源编码定理,第五章：无失真信源编码,2. 定长信源编码定理（续4）,根据编码效率的定义，最佳编码效率为：在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率和允许编码错误概率 之间的关系为：,二、定长码及定长信源编码定理,
12、例 5.2,如果对信源符号采用定长二元编码，要求编码效率=90%，允许错误概率 ，求所需信源序列长度N。,例5.3 设离散无记忆信源 , 要求 求N。,第五章：无失真信源编码,2. 定长信源编码定理（续5）,二、定长码及定长信源编码定理,1. Kraft不等式和McMillan不等式,第五章：无失真信源编码,Kraft定理：即时码存在的充要条件是McMillan定理：唯一可译码存在的充要条件是,三、变长码及变长信源编码定理,1. Kraft不等式和McMillan不等式（续1）,任何一个唯一可译码均可用一个相同码长的即时码来代替。上述定理是存在性定理：当满足Kraft（或McMillan）不等
13、式时，必然可以构造出即时码（或唯一可译码），否则不能构造出即时码（或唯一可译码）。该定理不能作为判断一种码是否是即时码（或唯一可译码）的判断依据。,第五章：无失真信源编码,三、变长码及变长信源编码定理,1. Kraft不等式和McMillan不等式（续2）,第五章：无失真信源编码,1/2,1/4,1/8,1/8,三、变长码及变长信源编码定理,2. 变长唯一可译码判别方法,步骤：,1.构造F1 ：考察 C中所有码字，如果一个码字是另一个码字的前缀，则将后缀作为F1 中的元素。 2.构造 ：将C 与 比较。如果 C 中有码字是 中元素的前缀，则将相应的后缀放入 中；同样 中若有元素是 C 中码字的
14、前缀，也将相应的后缀放入 中。 3.检验 ：1)如果 是空集，则断定码 C 是唯一可译码，退出循环；2)反之，如果 中的某个元素与 C中的某个元素相同，则断定码 不是唯一可译码，退出循环。3)如果上述两个条件都不满足，则返回步骤2。,第五章：无失真信源编码,三、变长码及变长信源编码定理,2. 变长唯一可译码判别方法（续）,例5.4 ：,结论：F5中包含了C中的元素，因此该变长码不是唯一可译码。,第五章：无失真信源编码,问题： 判断 C=1,10,100,1000是否是唯一可译码？,三、变长码及变长信源编码定理,3.紧致码平均码长界限定理,码符号/信源符号,平均码长,对于给定的信源和码符号集，若有一个唯一可译码，其平均长度 小于所有其他唯一可译码，则称这种码为紧致码或最佳码。,第五章：无失真信源编码,三、变长码及变长信源编码定理,3.紧致码平均码长界限定理（续1）,紧致码平均码长界限定理：设离散无记忆信源的熵为H(S)，用r 个码符号进行编码，则总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足：,第五章：无失真信源编码,三、变长码及变长信源编码定理,定理5.6 紧致码平均码长界限定理,3.紧致码平均码长界限定理（续2）,第五章：无失真信源编码,三、变长码及变长信源编码定理,
