失真信源编码 - 2013年最新信息论与编码（李梅 李亦农）课件

1、第五章：无失真信源编码一、信源编码的相关概念二、定长码及定长信源编码定理三、变长码及变长信源编码定理四、变长码的编码方法五、实用的无失真信源编码方法第五章：无失真信源编码 信源编码的作用： 使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息； 在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。 以提高通信有效性为目的。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均码长。1. 信源编码概述一、信源编码的相关概念第五章：无失真信源编码 信源编码理论是信息论的一个重要分支，其理论根底是信源编码的两个定理：无失真信源编码定理限失真信源编

2、码定理 本章主要介绍无失真信源编码，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相匹配的码。 1. 信源编码概述续1一、信源编码的相关概念第五章：无失真信源编码 信源的统计剩余度主要决定于以下两个因素 ：1无记忆信源中，符号概率分布的非均匀性；2有记忆信源中，符号间的相关性及符号概率分布的非均匀性。 1. 信源编码概述续2怎样压缩信源的冗余度？1) 去除码符号间的相关性。2) 使码符号等概分布。一、信源编码的相关概念第五章：无失真信源编码2. 信源编码器模型信宿信道信源编码器译码器YXSS 信源编码：将信源符号序列按一定的数学规律映射成码符号序列的过程。 图1 信源编码器模型一

3、、信源编码的相关概念第五章：无失真信源编码 将信源符号集中的符号 或者长为N的信源符号序列映射成由码符号 组成的长度为 的一一对应的码符号序列 。编码器码字2. 信源编码器模型续1一、信源编码的相关概念信源符号sip(si)码1码2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例: 5.1第五章：无失真信源编码2. 信源编码器模型续2一、信源编码的相关概念第五章：无失真信源编码3. N次扩展码一、信源编码的相关概念第五章：无失真信源编码3. N次扩展码续1二次扩展信源符号 二次扩展码码字一、信源编码的相关概念编码器输出

4、的码符号序列 称为码字；长度 称为码字长度，简称码长；全体码字的集合C称为码。假设码符号集合为X=0,1，那么所得的码字都是二元序列，称为二元码。第五章：无失真信源编码4. 关于编码的一些术语一、信源编码的相关概念将信源符号集中的每个信源符号 固定的映射成某一个码字 ，这样的码称为分组码。 假设一个码中所有码字的码长都相等，那么称为定长码； 否那么为变长码。第五章：无失真信源编码5. 奇异性假设一个码中所有码字互不相同，那么称为非奇异码；否那么为奇异码。信源符号si码1码2s1s2s3s401100110100001一、信源编码的相关概念第五章：无失真信源编码6. 唯一可译性 假设任意一串有限

5、长的码符号序列只能被唯一地译为对应的信源符号序列，那么称此码为唯一可译码。信源符号si码1码2码3s1s2s3s401100110100001010110111一、信源编码的相关概念 唯一可译码应当满足的条件码字与信源符号一一对应2) 不同的信源符号序列对应不同的码字序列1) 6. 唯一可译性续1第五章：无失真信源编码一、信源编码的相关概念第五章：无失真信源编码6. 唯一可译性续2例1：1)奇异码11译码奇异码一定不是唯一可译码一、信源编码的相关概念第五章：无失真信源编码6. 唯一可译性续32)非奇异码01 00 00 100 10 00 01 0译码译码一、信源编码的相关概念第五章：无失真信

6、源编码6. 唯一可译性续43)等长码非奇异码0 0 0 1 1 0 1 1唯一可译码译码一、信源编码的相关概念第五章：无失真信源编码6. 唯一可译性续54)唯一可译码1 001为非即时码1 1 0 1 0 0 1 0 0 0一、信源编码的相关概念第五章：无失真信源编码6. 唯一可译性续65)1 0 1 0 0 1 0 0 0 1唯一可译码0 1即时为即时码任何一个码字不是其它码字的前缀一、信源编码的相关概念第五章：无失真信源编码7. 即时码 假设某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码，那么称此码为即时码。 问题： 1) 判断下面的码是否即时码？010110111

7、 2) 等长码是否即时码？一、信源编码的相关概念第五章：无失真信源编码7. 即时码续1 唯一可译码成为即时码的充要条件： 定理5.1 一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。一、信源编码的相关概念信源概率pi 编 码编码编码编码编码s11/2000000s21/401011001s31/810100110011s41/811101111101117. 即时码续2第五章：无失真信源编码一、信源编码的相关概念消息00001001000001001110000101011000111001101010010001111110111110101101101110001

8、0011101101111001101010111111117. 即时码续3第五章：无失真信源编码一、信源编码的相关概念第五章：无失真信源编码8. 即时码的构造方法用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所有的码字都安排在终端节点上就可以得到即时码。一、信源编码的相关概念8. 即时码的构造方法续1 0101010100010011一阶节点二阶节点三阶节点0101100110101111第五章：无失真信源编码一、信源编码的相关概念第五章：无失真信源编码8. 即时码的构造方法续2一、信源编码的相关概念用树图法可以方便地构造即时码。树中每个中间节点都伸出1至r个树枝，将所

9、有的码字都安排在终端节点上就可以得到即时码。每个中间节点都正好有r个分枝的树称为整树满树。所有终端节点的阶数都相等的树为完全树第五章：无失真信源编码8. 即时码的构造方法续3一、信源编码的相关概念第五章：无失真信源编码图2 各类码之间的关系8. 即时码的构造方法续4一、信源编码的相关概念1. 唯一可译定长码存在的条件对于定长码，非奇异码一定是唯一可译码。所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个码字 一一对应。设信源符号集中共有 个符号， ， 码符号集中共有 种码元， ， 定长码码长为 , 那么要满足非奇异性必然有该条件是必要条件，而不是充分条件。第五章：无失真信源编码二、定长

10、码及定长信源编码定理1. 唯一可译定长码存在的条件续1如果对N次扩展信源 进行定长编码，要满足非奇异性，须满足条件 其中当r=2 时，第五章：无失真信源编码二、定长码及定长信源编码定理当N=1时，1. 唯一可译定长码存在的条件续2例2：英文字母表中，每一字母用定长编码转换成二进制表示，码字的最短长度是多少？解：信源符号数码符号数第五章：无失真信源编码二、定长码及定长信源编码定理 p(sj) I(sj)/N s1= s1 s1 1/4 1s2= s1 s2 1/8 1.5s3= s1 s3 1/16 2s4= s1 s4 1/16 2s5= s2 s1 1/8 1.5s6= s2 s2 1/16

11、 2s7= s2 s3 1/32 2.5s8= s2 s4 1/32 2.5 p(sj) I(sj)/Ns9 = s3 s1 1/16 2s10= s3 s2 1/32 2.5s11= s3 s3 1/64 3s12= s3 s4 1/64 3s13= s4 s1 1/16 2s14= s4 s2 1/32 2.5s15= s4 s3 1/64 3s16= s4 s4 1/64 3N=2 H(S) = 1.75 第五章：无失真信源编码2. 定长信源编码定理二、定长码及定长信源编码定理定理5.3.1 设离散平稳无记忆信源的熵为H(S), 假设对N次扩展信源 进行定长编码，那么对于任意 0，只要满

12、足 那么当N足够大时，可实现几乎无失真编码，即译码错误概率 PE 为任意小；反之，那么不可能实现无失真编码， 如果 当N足够大时，译码错误概率 PE 为1。2. 定长信源编码定理续1第五章：无失真信源编码 定长编码定理同样也适用于离散平稳有记忆信源，差异是要将信源熵 改为极限熵 。二、定长码及定长信源编码定理可以验证，对定长信源编码来说，要想实现无失真信源编码，N常常要取非常大的值。这在实际应用中很难实现。2. 定长信源编码定理续2第五章：无失真信源编码当r=2时二、定长码及定长信源编码定理第五章：无失真信源编码2. 定长信源编码定理续3定义： 为编码信息率 定义： 为编码效率。 比特/信源符

13、号比特/信源符号比特/信源符号二、定长码及定长信源编码定理第五章：无失真信源编码2. 定长信源编码定理续4根据编码效率的定义，最正确编码效率为：在方差和信源熵的条件下，信源符号序列长度N与最正确编码效率和允许编码错误概率 之间的关系为：二、定长码及定长信源编码定理例 5.2如果对信源符号采用定长二元编码，要求编码效率=90%，允许错误概率 ，求所需信源序列长度N。 例5.3 设离散无记忆信源 , 要求 求N。 第五章：无失真信源编码2. 定长信源编码定理续5二、定长码及定长信源编码定理1. Kraft不等式和McMillan不等式第五章：无失真信源编码Kraft定理：即时码存在的充要条件是Mc

14、Millan定理：唯一可译码存在的充要条件是三、变长码及变长信源编码定理1. Kraft不等式和McMillan不等式续1 任何一个唯一可译码均可用一个相同码长的即时码来代替。 上述定理是存在性定理： 当满足Kraft或McMillan不等式时，必然可以构造出即时码或唯一可译码，否那么不能构造出即时码或唯一可译码。 该定理不能作为判断一种码是否是即时码或唯一可译码的判断依据。第五章：无失真信源编码三、变长码及变长信源编码定理信源符号si符号出现的概率码1码2码3码4s10011s211101001s30000100001s41101100000011. Kraft不等式和McMillan不等式

15、续2第五章：无失真信源编码1/21/41/81/8三、变长码及变长信源编码定理2. 变长唯一可译码判别方法步骤：1.构造F1 ：考察 C中所有码字，如果一个码字是另一个码字的前缀，那么将后缀作为F1 中的元素。2.构造 ：将C 与 比较。如果 C 中有码字是 中元素的前缀，那么将相应的后缀放入 中；同样 中假设有元素是 C 中码字的前缀，也将相应的后缀放入 中。3.检验 ： 1)如果 是空集，那么断定码 C 是唯一可译码，退出循环； 2)反之，如果 中的某个元素与 C中的某个元素相同，那么断定码 不是唯一可译码，退出循环。 3)如果上述两个条件都不满足，那么返回步骤2。 第五章：无失真信源编码

16、三、变长码及变长信源编码定理2. 变长唯一可译码判别方法续C F1 F2 F3 F4 F5a d eb de b adc bb cde bcdeadabbbaddebbbcde例5.4 ：结论：F5中包含了C中的元素，因此该变长码不是唯一可译码。第五章：无失真信源编码问题： 判断 C=1,10,100,1000是否是唯一可译码？三、变长码及变长信源编码定理3.紧致码平均码长界限定理码符号/信源符号 平均码长 对于给定的信源和码符号集，假设有一个唯一可译码，其平均长度 小于所有其他唯一可译码，那么称这种码为紧致码或最正确码。 第五章：无失真信源编码三、变长码及变长信源编码定理3.紧致码平均码长界

17、限定理续1 紧致码平均码长界限定理： 设离散无记忆信源的熵为H(S)，用r 个码符号进行编码，那么总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足： 第五章：无失真信源编码三、变长码及变长信源编码定理定理5.6 紧致码平均码长界限定理3.紧致码平均码长界限定理续2第五章：无失真信源编码三、变长码及变长信源编码定理3.紧致码平均码长界限定理续3第五章：无失真信源编码平均码长=下限值时三、变长码及变长信源编码定理3.紧致码平均码长界限定理续4第五章：无失真信源编码三、变长码及变长信源编码定理4.无失真变长信源编码定理 香农第一定理变长无失真信源编码定理： 设离散无记忆信源的熵为 H(S

18、) ，它的N次扩展信源为 ，对扩展信源 进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足： 当 时，有第五章：无失真信源编码三、变长码及变长信源编码定理证明：4.无失真变长信源编码定理续1第五章：无失真信源编码三、变长码及变长信源编码定理 把香农第一定理推广到一般离散信源，有并且4.无失真变长信源编码定理续2第五章：无失真信源编码三、变长码及变长信源编码定理bit/信源符号码符号/信源符号= bit/码符号信息传输率(码率)r进制单位/信源符号码符号/信源符号4.无失真变长信源编码定理续3第五章：无失真信源编码编码效率三、变长码及变长信源编码定理 例5.5 设离散无记忆信源 ,

19、 求 R、及扩展信源的R、 。 4.无失真变长信源编码定理续4第五章：无失真信源编码三、变长码及变长信源编码定理第五章：无失真信源编码1. 香农码编码步骤如下：将信源符号按概率从大到小顺序排列，为方便起见，令 2. 按下式计算第i个符号对应的码字的码长要取整3. 计算第i个符号的累加概率4. 将累加概率变换成二进制小数，取小数点后li位数作为第i个符号的码字。四、变长码的编码方法1. 香农码续1例5.6 对如下信源编码:第五章：无失真信源编码四、变长码的编码方法信源符号符号概率累加概率码长码字s10.2002.343000s20.190.22.413001s30.180.392.483011s

20、40.170.572.563100s50.150.742.743101s60.100.593.3441110s70.010.996.66711111101. 香农码续2第五章：无失真信源编码四、变长码的编码方法1. 香农码续3 平均码长信源熵结论： 1) 2) 香农码是即时码，但冗余度稍大，不是最正确码。编码效率第五章：无失真信源编码四、变长码的编码方法2. 香农-费诺-埃利斯编码第五章：无失真信源编码四、变长码的编码方法1、不用对信源符号按概率大小排序。2、直接计算修正的累加概率3、计算码长 2. 香农-费诺-埃利斯编码续1第五章：无失真信源编码四、变长码的编码方法3. Huffman码将信

21、源符号按概率从大到小的顺序排列，令给两个概率最小的信源符号sn-1和sn各分配一个码元“0和“1，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。编码步骤如下：第五章：无失真信源编码四、变长码的编码方法3. Huffman码续1第五章

22、：无失真信源编码四、变长码的编码方法010101013. Huffman码续2第五章：无失真信源编码四、变长码的编码方法01010101码符号/信源符号3. Huffman码续3第五章：无失真信源编码四、变长码的编码方法01010101码符号/信源符号3. Huffman码续4第五章：无失真信源编码四、变长码的编码方法讨论：1) 两种方法平均码长相等。2) 计算两种码的码长方差：第二种方法编出的码码字长度变化较小，便于实现。3. Huffman码续5第五章：无失真信源编码四、变长码的编码方法3. Huffman码续6离散信源如下:解：编码过程略，Huffman编码结果如下：第五章：无失真信源编

23、码四、变长码的编码方法3. Huffman码续7平均码长为信源熵为编码效率为第五章：无失真信源编码四、变长码的编码方法3. Huffman码续8注意：霍夫曼编码后的码字不是惟一的。1每次对缩减信源两个概率最小的符号分配“0或“1码元是任意的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长li不变，平均码长也不变，所以没有本质区别；2缩减信源时，假设合并后的概率与其他概率相等，这几个概率的次序可任意排列，但得到的码字不相同,对应的码长也不相同,但平均码长也不变。第五章：无失真信源编码四、变长码的编码方法定理5.8 霍夫曼码是紧致码01010101101000001100013.

24、 Huffman码续9第五章：无失真信源编码四、变长码的编码方法假定缩减后信源为 共有m个元素。 缩减后信源为 共有m+1个元素。其中第k个元素码长 ,概率为最短那么缩减前4. r 元霍夫曼码第五章：无失真信源编码四、变长码的编码方法0120120124. r 元霍夫曼码续1第五章：无失真信源编码四、变长码的编码方法4. r 元霍夫曼码续2第五章：无失真信源编码四、变长码的编码方法5. Fano码编码步骤如下：将概率按从大到小的顺序排列，令将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。给每一组分配一位码元“0或“1。将每一分组再按同样方法划分，重复步骤2和3，直至概率不再可

25、分为止。第五章：无失真信源编码四、变长码的编码方法5. Fano码续1例第五章：无失真信源编码四、变长码的编码方法5. Fano码续2解：信源符号符号概率第一次分组第一次分组第一次分组第一次分组码字码长0.20000020.191001030.18101130.17101020.151011030.1010111040.01111114第五章：无失真信源编码四、变长码的编码方法5. Fano码续3平均码长为信源熵为编码效率为第五章：无失真信源编码四、变长码的编码方法5. Fano码续4四、变长码的编码方法香农码、Huffman码、Fano码总结香农码、费诺码、霍夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩。香农码编码结果唯一，但在很多情况下编码效率不是很高。费诺码和霍夫曼码的编码方法都不唯一。费诺码比较适合于对分组概率相等或接近的信源编码。霍夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。第五章：无失真信源编码四、变长码的编码方