第五章 无失真信源编码

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章：无失真信源编码,一、信源编码的相关概念,二、定长码及定长信源编码定理,三、变长码及变长信源编码定理,四、变长码的编码方法,五、实用的无失真信源编码方法,第五章：无失真信源编码,信源编码的作用：,使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；,在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。,以提高通信有效性为目的,。通常通过,压缩信源的冗余度,来实现。采用的一般方法是压缩每个信源符号的平均码长,。,1. 信源编码概述,一、信源编码的相关概念,第五章：无失真信源编码,信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：,无失真信源编码定理,限失真信源编码定理,本章主要介绍,无失真信源编码,，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相匹配的码。,1. 信源编码概述（续1）,一、信源编码的相关概念,第五章：无失真信源编码,信源的统计剩余度主要决定于以下两个因素,：,1,）无记忆信源中，符号概率分布的非均匀性；,2,）有记忆信源中，符号间的相关性及,符号概率分布的非均匀性,。,1. 信源编码概述（续2）,怎样压缩信源的冗余度？,1),去除码符号间的相关性。,2),使码符号等概分布。,一、信源编码的相关概念,第五章：无失真信源编码,2. 信源编码器模型,信宿,信道,信源,编码器,译码器,Y,X,S,S,信源编码：将信源符号序列按一定的数学规律映射成码符号序列的过程。,图1 信源编码器模型,一、信源编码的相关概念,第五章：无失真信源编码,将信源符号集中的符号,（或者长为,N,的信源符号序列）映射成由码符号,组成的长度为,的一一对应的码符号序列,。,编码器,码字,2. 信源编码器模型（续1）,一、信源编码的相关概念,信源符号,s,i,p,(,s,i,),码1,码2,s,1,p,(,s,1,)=1/2,00,0,s,2,p,(,s,2,)=1/4,01,01,s,3,p,(,s,3,)=1/8,10,001,s,4,p,(,s,4,)=1/8,11,111,第五章：无失真信源编码,2. 信源编码器模型（续2）,一、信源编码的相关概念,第五章：无失真信源编码,3. N次扩展码,一、信源编码的相关概念,第五章：无失真信源编码,3. N次扩展码（续1）,二次扩展信源符号,二次扩展码码字,一、信源编码的相关概念,编码器输出的码符号序列 称为,码字,；长度,称为,码字长度,，简称,码长,；全体码字的集合,C,称为,码,。,若码符号集合为,X,=0,1,，,则所得的码字都是二元序列，称为,二元码,。,第五章：无失真信源编码,4. 关于编码的一些术语,一、信源编码的相关概念,将信源符号集中的每个信源符号 固定的映射成某一个码字,，这样的码称为,分组码,。,若一个码中所有码字的码长都相等，则称为,定长码,；,否则为,变长码,。,第五章：无失真信源编码,5. 奇异性,若一个码中所有码字互不相同，则称为,非奇异码,；,否则为,奇异码,。,信源符号,s,i,码1,码2,s,1,s,2,s,3,s,4,0,11,00,11,0,10,00,01,一、信源编码的相关概念,第五章：无失真信源编码,6. 唯一可译性,若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为,唯一可译码,。,信源符号,s,i,码1,码2,码3,s,1,s,2,s,3,s,4,0,11,00,11,0,10,00,01,0,10,110,111,一、信源编码的相关概念,唯一可译码应当满足的条件,码字与信源符号一一对应,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. 唯一可译性（续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,111,2),等长码是否,即时码？,一、信源编码的相关概念,第五章：无失真信源编码,7. 即时码（续1）,唯一可译码成为即时码的充要条件,：,定理,5.1,一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。,一、信源编码的相关概念,信源,概率,p,i,编 码,编码,编码,编码,编码,s,1,1/2,00,0,0,0,0,s,2,1/4,01,0,1,10,01,s,3,1/8,10,1,00,110,011,s,4,1/8,11,10,11,111,0111,7. 即时码（续2）,第五章：无失真信源编码,一、信源编码的相关概念,消息,000,010,0,1,00,00,010,011,10,00,01,01,011,000,1110,0110,10,100,100,011,1111,0111,110,101,101,101,1100,0100,1110,110,111,100,1101,0101,1111,111,7. 即时码（续3）,第五章：无失真信源编码,一、信源编码的相关概念,第五章：无失真信源编码,8. 即时码的构造方法,用树图法可以方便地构造即时码。树中每个中间节点都伸出,1,至,r,个树枝，,将所有的码字都安排在终端节点上,就可以得到即时码。,一、信源编码的相关概念,8. 即时码的构造方法（续1）,0,1,0,1,0,1,0,1,00,010,011,一阶节点,二阶节点,三阶节点,0,1,0,1,100,110,101,111,第五章：无失真信源编码,一、信源编码的相关概念,第五章：无失真信源编码,8. 即时码的构造方法（续2）,一、信源编码的相关概念,用树图法可以方便地构造即时码。树中每个中间节点都伸出,1,至,r,个树枝，将所有的码字都安排在终端节点上就可以得到即时码。,每个中间节点都正好有,r,个分枝的树称为,整树（满树）。,所有终端节点的阶数都相等的树为,完全树,第五章：无失真信源编码,8. 即时码的构造方法（续3）,一、信源编码的相关概念,第五章：无失真信源编码,图2 各类码之间的关系,8. 即时码的构造方法（续4）,一、信源编码的相关概念,1. 唯一可译定长码存在的条件,对于定长码，非奇异码一定是唯一可译码。,所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个码字 一一对应。,设信源符号集中共有,个符号， ， 码符号集中共有,种码元， ， 定长码码长为,则要满足非奇异性必然有,该条件是必要条件，而不是充分条件。,第五章：无失真信源编码,二、定长码及定长信源编码定理,1. 唯一可译定长码存在的条件（续1）,如果对,N,次扩展信源 进行定长编码，要满足非奇异性，须满足条件,其中,当,r,=2,时，,第五章：无失真信源编码,二、定长码及定长信源编码定理,当,N,=1时,，,1. 唯一可译定长码存在的条件（续2）,例2：英文字母表中，每一字母用定长编码转换成二进制表示，码字的最短长度是多少？,解：,信源符号数,码符号数,第五章：无失真信源编码,二、定长码及定长信源编码定理,p,(,s,j,),I,(,s,j,)/N,s,1,=,s,1,s,1 1/4 1,s,2,=,s,1,s,2 1/8 1.5,s,3,=,s,1,s,3 1/16 2,s,4,=,s,1,s,4 1/16 2,s,5,=,s,2,s,1 1/8 1.5,s,6,=,s,2,s,2 1/16 2,s,7,=,s,2,s,3 1/32 2.5,s,8,=,s,2,s,4 1/32 2.5,p,(,s,j,),I,(,s,j,)/N,s,9,=,s,3,s,1 1/16 2,s,10,=,s,3,s,2 1/32 2.5,s,11,=,s,3,s,3 1/64 3,s,12,=,s,3,s,4 1/64 3,s,13,=,s,4,s,1 1/16 2,s,14,=,s,4,s,2 1/32 2.5,s,15,=,s,4,s,3 1/64 3,s,16,=,s,4,s,4 1/64 3,N=2,H,(,S,第五章：无失真信源编码,2. 定长信源编码定理,二、定长码及定长信源编码定理,定理,5.3.1,设离散平稳无记忆信源的熵为,H,(,S,),若对,N,次扩展信源 进行定长编码，则对于任意,0,，只要满足,则当,N,足够大时，可实现几乎无失真编码，即译码错误概率,P,E,为任意小；反之，则不可能实现无失真编码，,如果,当,N,足够大时，译码错误概率,P,E,为,1,。,2. 定长信源编码定理（续1）,第五章：无失真信源编码,定长编码定理同样也适用于离散平稳有记忆信源，差别是要将信源熵 改为极限熵 。,二、定长码及定长信源编码定理,可以验证，对定长信源编码来说，要想实现无失真信源编码，,N,常常要取非常大的值。这在实际应用中很难实现。,2. 定长信源编码定理（续2）,第五章：无失真信源编码,当,r=,2时,二、定长码及定长信源编码定理,第五章：无失真信源编码,2. 定长信源编码定理（续3）,定义： 为,编码信息率,定义： 为,编码效率,。,比特/信源符号,比特/信源符号,比特/信源符号,二、定长码及定长信源编码定理,第五章：无失真信源编码,2. 定长信源编码定理（续4）,根据,编码效率的,定义,，,最佳编码效率为：,在已知方差和信源熵的条件下，信源符号序列长度,N,与最佳编码效率,和允许编码错误概率,之间的关系为：,二、定长码及定长信源编码定理,例,如果对信源符号采用定长二元编码，要求编码效率,=90%，允许错误概率 ，求所需信源序列长度,N,。,例5.3 设离散无记忆信源 , 要求,求,N,。,第五章：无失真信源编码,2. 定长信源编码定理（续5）,二、定长码及定长信源编码定理,1. Kraft不等式和McMillan不等式,第五章：无失真信源编码,Kraft,定理：即时码,存在,的充要条件是,McMillan,定理：唯一可译码,存在,的充要条件是,三、变长码及变长信源编码定理,1. Kraft不等式和McMillan不等式（续1）,任何一个唯一可译码均可用一个相同码长的即时码来代替。,上述定理是存在性定理：,当满足,Kraft,（或,McMillan,）,不等式时，必然可以构造出即时码（或唯一可译码），否则不能构造出,即时码（或唯一可译码）。,该定理不能作为判断一种码是否是即时码（或唯一可译码）的判断依据。,第五章：无失真信源编码,三、变长码及变长信源编码定理,信源符号,s,i,符号出现的概率,码1,码2,码3,码4,s,1,0,0,1,1,s,2,11,10,10,01,s,3,00,00,100,001,s,4,11,01,1000,0001,1. Kraft不等式和McMillan不等式（续2）,第五章：无失真信源编码,1/2,1/4,1/8,1/8,三、变长码及变长信源编码定理,2. 变长唯一可译码判别方法,步骤：,1.,构造,F,1,：考察,C,中所有码字，如果一个码字是另一个码字的前缀，则将后缀作为,F,1,中的元素。,2.,构造,：将,C,与 比较。如果,C,中有码字是 中元素的前缀，则将相应的后缀放入 中；同样 中若有元素是,C,中码字的前缀，也将相应的后缀放入 中。,3.,检验,：,1)如果 是空集，则断定码,C,是唯一可译码，退出循环；,2)反之，如果 中的某个元素与,C,中的某个元素相同，则断定码 不是唯一可译码，退出循环。,3)如果上述两个条件都不满足，则返回步骤2。,第五章：无失真信源编码,三、变长码及变长信源编码定理,2. 变长唯一可译码判别方法（续）,C,F,1,F,2,F,3,F,4,F,5,a d eb de b,ad,c bb cde bcde,ad,abb,bad,deb,bbcde,例,：,结论：,F,5,中包含了,C,中的元素，因此该变长码不是唯一可译码。,第五章：无失真信源编码,问题： 判断 C=1,10,100,1000是否是唯一可译码？,三、变长码及变长信源编码定理,3.紧致码平均码长界限定理,码符号/信源符号,平均码长,对于给定的信源和码符号集，若有一个唯一可译码，其平均长度 小于所有其他唯一可译码，则称这种码为,紧致码,或,最佳码,。,第五章：无失真信源编码,三、变长码及变长信源编码定理,3.紧致码平均码长界限定理（续1）,紧致码平均码长界限定理,：,设离散无记忆信源的熵为,H,(,S,),，用,r,个码符号进行编码，则总可找到一种无失真信源编码，构成唯一可译码，使其平均码长满足：,第五章：无失真信源编码,三、变长码及变长信源编码定理,定理5.6 紧致码平均码长界限定理,3.紧致码平均码长界限定理（续2）,第五章：无失真信源编码,三、变长码及变长信源编码定理,3.紧致码平均码长界限定理（续3）,第五章：无失真信源编码,平均码长=下限值时,三、变长码及变长信源编码定理,3.紧致码平均码长界限定理（续4）,第五章：无失真信源编码,三、变长码及变长信源编码定理,4.无失真变长信源编码定理,香农第一定理（变长无失真信源编码定理）：,设离散无记忆信源的熵为,H,(,S,),，,它的,N,次扩展信源为,，,对扩展信源,进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足：,当 时，有,第五章：无失真信源编码,三、变长码及变长信源编码定理,证明：,4.无失真变长信源编码定理（续1）,第五章：无失真信源编码,三、变长码及变长信源编码定理,把香农第一定理推广到一般离散信源，有,并且,4.无失真变长信源编码定理（续2）,第五章：无失真信源编码,三、变长码及变长信源编码定理,bit,/信源符号,码符号/信源符号,=,bit,/码符号,信息传输率(码率),r,进制单位/信源符号,码符号/信源符号,4.无失真变长信源编码定理（续3）,第五章：无失真信源编码,编码效率,三、变长码及变长信源编码定理,例5.5 设离散无记忆信源 , 求,R、,及扩展信源的,R、 。,4.无失真变长信源编码定理（续4）,第五章：无失真信源编码,三、变长码及变长信源编码定理,第五章：无失真信源编码,1. 香农码,编码步骤如下：,将信源符号按概率从大到小顺序排列，为方便起见，令,2.,按下式计算第,i,个符号对应的码字的码长（要取整）,3.,计算第,i,个符号的累加概率,4.,将累加概率变换成二进制小数，取小数点后,l,i,位数作为第,i,个符号的码字。,四、变长码的编码方法,1. 香农码（续1）,例5.6 对如下信源编码:,第五章：无失真信源编码,四、变长码的编码方法,信源符号,符号概率,累加概率,码长,码字,s,1,0.20,0,2.34,3,000,s,2,0.19,0.2,2.41,3,001,s,3,0.18,0.39,2.48,3,011,s,4,0.17,0.57,2.56,3,100,s,5,0.15,0.74,2.74,3,101,s,6,0.10,0.59,3.34,4,1110,s,7,0.01,0.99,6.66,7,1111110,1. 香农码（续2）,第五章：无失真信源编码,四、变长码的编码方法,1. 香农码（续3）,平均码长,信源熵,结论：,1),2) 香农码是即时码，但冗余度稍大，不是最佳码。,编码效率,第五章：无失真信源编码,四、变长码的编码方法,2. 香农-费诺-埃利斯编码,第五章：无失真信源编码,四、变长码的编码方法,1、不用对信源符号按概率大小排序。,2、直接计算修正的累加概率,3、计算码长,2. 香农-费诺-埃利斯编码（续1）,第五章：无失真信源编码,四、变长码的编码方法,3. Huffman码,将信源符号按概率从大到小的顺序排列，令,给两个概率最小的信源符号,s,n,-1,和,s,n,各分配一个码元,“,0”,和“,1”,，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含,(,n,1),个信源符号的新信源。称为,信源的第一次缩减信源,，用,S,1,表示。,将缩减信源,S,1,的符号仍按概率从大到小顺序排列，,重复步骤,2,，得到只含,(,n,2),个符号的缩减信源,S,2,。,重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为,1,。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,编码步骤如下：,第五章：无失真信源编码,四、变长码的编码方法,3. Huffman码（续1）,第五章：无失真信源编码,四、变长码的编码方法,0,1,0,1,0,1,0,1,3. Huffman码（续2）,第五章：无失真信源编码,四、变长码的编码方法,0,1,0,1,0,1,0,1,码符号/信源符号,3. Huffman码（续3）,第五章：无失真信源编码,四、变长码的编码方法,0,1,0,1,0,1,0,1,码符号/信源符号,3. Huffman码（续4）,第五章：无失真信源编码,四、变长码的编码方法,讨论：,1) 两种方法平均码长相等。,2) 计算两种码的码长方差：,第二种方法编出的码码字长度变化较小，便于实现。,3. Huffman码（续5）,第五章：无失真信源编码,四、变长码的编码方法,3. Huffman码（续6）,离散信源如下:,解：编码过程略，Huffman编码结果如下：,第五章：无失真信源编码,四、变长码的编码方法,3. Huffman码（续7）,平均码长为,信源熵为,编码效率为,第五章：无失真信源编码,四、变长码的编码方法,3. Huffman码（续8）,注意,：霍夫曼编码后的码字不是惟一的。,1）每次对缩减信源两个概率最小的符号,分配“0”或“1”码元是任意的,，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长,l,i,不变，平均码长也不变，所以没有本质区别；,2）缩减信源时，,若合并后的概率与其他概率相等，这几个概率的次序可任意排列,，但得到的码字不相同,对应的码长也不相同,但平均码长也不变。,第五章：无失真信源编码,四、变长码的编码方法,定理,5.8,霍夫曼码是紧致码,0,1,0,1,0,1,0,1,1,01,000,001,1,00,01,3. Huffman码（续9）,第五章：无失真信源编码,四、变长码的编码方法,假定缩减后信源为 共有,m,个元素。,缩减后信源为 共有,m,+1个元素。,其中第,k,个元素码长 ,概率为,最短,则缩减前,4. r 元霍夫曼码,第五章：无失真信源编码,四、变长码的编码方法,0,1,2,0,1,2,0,1,2,4. r 元霍夫曼码（续1）,第五章：无失真信源编码,四、变长码的编码方法,4. r 元霍夫曼码（续2）,第五章：无失真信源编码,四、变长码的编码方法,5. Fano码,编码步骤如下：,将概率按从大到小的顺序排列，令,将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。,给每一组分配一位码元“,0”,或“,1”,。,将每一分组再按同样方法划分，重复步骤,2,和,3,，直至概率不再可分为止。,第五章：无失真信源编码,四、变长码的编码方法,5. Fano码（续1）,例,第五章：无失真信源编码,四、变长码的编码方法,5. Fano码（续2）,解：,信源,符号,符号,概率,第一次分组,第一次分组,第一次分组,第一次分组,码字,码长,0.20,0,0,00,2,0.19,1,0,010,3,0.18,1,011,3,0.17,1,0,10,2,0.15,1,0,110,3,0.10,1,0,1110,4,0.01,1,1111,4,第五章：无失真信源编码,四、变长码的编码方法,5. Fano码（续3）,平均码长为,信源熵为,编码效率为,第五章：无失真信源编码,四、变长码的编码方法,5. Fano码（续4）,四、变长码的编码方法,香农码、Huffman码、Fano码总结,香农码、费诺码、,霍,夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩。,香农码编码结果唯一，但在很多情况下编码效率不是很高。,费诺码和,霍,夫曼码的编码方法都不唯一。,费诺码比较适合于对分组概率相等或接近的信源编码。,霍,夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码。,第五章：无失真信源编码,四、变长码的编码方法,首先是速率匹配问题,其次是差错扩散问题,第三是,霍,夫曼码需要查表来进行编译码。,信源统计特性未知时，怎么办？可采用所谓通用编码的方法。,Huffman码编码应用中的一些问题,第五章：无失真信源编码,0,1 0,0 0,0 1,0,0 1,0 0,0 0,1 0,译码,译码,四、变长码的编码方法,第五章：无失真信源编码,五、实用的无失真信源编码方法,游程编码,第五章：无失真信源编码,五、实用的无失真信源编码方法,游程编码（续1）,BBBBBBBBBBXXXXXXXXXAAAAAAUUUUUUUUUUUUU,符号码,标识码,游程长度,编码： B#10X#9A#6U#13,对于黑、白二值文件:,1、黑白游程总是交替出现，可以规定第一游程为白游程。,2、不同游程长度出现的概率不同，对游程长度进行编码采用霍夫曼编码，概率大的编长码，概率小的编短码。,第五章：无失真信源编码,五、实用的无失真信源编码方法,游程编码（续2）,第五章：无失真信源编码,五、实用的无失真信源编码方法,73,白游程,=64+,9,：,11011,10100,00110101,010,110101,011,0011,000000000001,0,白,1,黑,15,白,4,黑,77,白,5,黑,压缩比,=1728/47=36.7:1,结尾码,组合基干码,第五章：无失真信源编码,五、实用的无失真信源编码方法,算术编码,10001001,第五章：无失真信源编码,五、实用的无失真信源编码方法,算术编码（续1）,第五章：无失真信源编码,五、实用的无失真信源编码方法,算术编码（续2）,第五章：无失真信源编码,五、实用的无失真信源编码方法,LZW,编码,输入符号序列：ABCABDABCAAAABBBABCABCA,前缀 尾字符,序号,0X000,0X041,0X0FF,0X100,0X101,0X102,0X103,0X104,0X105,0X106,0X107,0X108,0X109,0X10A,0X10B,0XFFF,Q(FFF),Q(FFF) A,Q(FFF),A(041) B,B C,C A,AB D,D A,AB C,CA A,A A,AA B,B B,BB A,ABC A,第五章：无失真信源编码,五、实用的无失真信源编码方法,LZW编码（续1）,