信息论与编码无失真信源编码.pptx

1第第4章章 无失真信源编码无失真信源编码信息论与编码 Information and Coding Theory 王永容王永容 机械与机械与电气工程学院气工程学院2信源编码信源编码信源编码是以信源编码是以提高通信的有效性提高通信的有效性为目的编码。为目的编码。通常通过压缩信源的冗余度来实现。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。同样多的信息用较少的码特数或信源的码率。同样多的信息用较少的码率来传送，使单位时间内传送的平均信息量增率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。加，从而提高通信的有效性。3信源编码的基本途径有两个：信源编码的基本途径有两个：使序列中的各个符号尽可能地互相使序列中的各个符号尽可能地互相独立，即独立，即解除相关性解除相关性；使编码中各个符号出现的概率尽可使编码中各个符号出现的概率尽可能地相等，即能地相等，即概率均匀化概率均匀化。4信源编码的基础是信息论中的两个编码定理：信源编码的基础是信息论中的两个编码定理：无失真信源编码定理无失真信源编码定理 限失真信源编码定理限失真信源编码定理 无失真信源编码无失真信源编码只适用于离散信源只适用于离散信源 对于连续信源，只能在失真受限制的情况下进对于连续信源，只能在失真受限制的情况下进行行限失真编码限失真编码下面介绍几种典型的离散信源编码方法。下面介绍几种典型的离散信源编码方法。5第第4 4章章 无失真信源编码无失真信源编码4.1 4.1 无失真信源编码的概念无失真信源编码的概念4.2 4.2 等长编码等长编码4.3 4.3 变长编码变长编码4.4 4.4 常用的变长编码算法常用的变长编码算法64.1 4.1 无失真信源编码的概念无失真信源编码的概念l信源信源符号符号(字母字母)集：集：Ss1,s2,sq.l码符号符号(字母、元字母、元)集：集：Aa1,a2,am.l编码函数函数f:将有限个信源将有限个信源符号符号变换成成有限个有限个码符号的函数符号的函数 用AN表示全体长度为N的信源符号序列构成的集合 u码字：wi=f(si)u码字wi的长度(码长)：li=l(wi)u码:C=wi=f(si)|siSN .74.1 4.1 无失真信源编码的概念无失真信源编码的概念uN=1时uf：无失真信源编码器8如何分离码字？如果0，01都是码字，译码时如何分离？94.1 4.1 无失真信源编码的概念无失真信源编码的概念l例例4-1 几个二元码几个二元码 信源符号信源符号 概率分布概率分布码码1:C1码码2:C2码码3:C3码码4:C4码码5:C5s1 0.5000011s2 0.250111101001s3 0.125100000100001s4 0.12511110110000001u码的扩展码的扩展 码C1的扩展:s1s3 00 10104.1 4.1 无失真信源编码的概念无失真信源编码的概念um元码:码符号集Aa1,a2,am.二元码:m=2,A0,1u等长码（定长码）:所有码字的码长相等.例:中文电报码是码长为4的等长的10元码 中0022;国0948;北0554;京0079.u变长码（非定长码）:码字的码长不相等.u非奇异码:s1,s2A,s1s2 f(s1)f(s2)否则，称为奇异码114.1 4.1 无失真信源编码的概念无失真信源编码的概念u唯一可译码:任意有限长的码元序列,只能被唯一地分割成一个一个的码字,则称为唯一可译码唯一可译码,或单义可译码或单义可译码.否则，就称为非唯一可译码,或非单义可译码.例：码4是唯一可译码:1000100 1000,100 码3是非唯一可译码:100010010,00,10,0 或10,0,01,00信源符号信源符号概率分布概率分布码码1:C1码码2:C2码码3:C3码码4:C4码码5:C5s1 0.5000011s2 0.250111101001s3 0.125100000100001s4 0.12511110110000001备注等长码非唯一可译非 唯一可译唯一可译及时码124.1 4.1 无失真信源编码的概念无失真信源编码的概念l即即时码:如果收到一个码字后,就能及时译出，则称为即即时码,也称为非延非延长码，或异前，或异前缀码.即没有任何完整的码字是其它码字的前缀。否则，就称为非即非即时码.例：码5是即时码,码4是非即时码.信源符号信源符号概率分布概率分布码码1:C1码码2:C2码码3:C3码码4:C4码码5:C5s1 0.5000011s2 0.250111101001s3 0.125100000100001s4 0.12511110110000001备注等长码非唯一可译非 唯一可译唯一可译及时码13l关系关系u即时码一定是唯一可译码u唯一可译码一定是非奇异码u定长的非奇异码一定是唯一可译码u非定长的非奇异码不一定是唯一可译码4.1 4.1 无失真信源编码的概念无失真信源编码的概念14第第4 4章章 无失真信源编码无失真信源编码4.1 4.1 无失真信源编码的概念无失真信源编码的概念4.2 4.2 等长编码等长编码4.3 4.3 变长编码变长编码4.4 4.4 常用的变长编码算法常用的变长编码算法154.2 等长编码等长编码l离散信源X的熵：H(X)l字母集:Ss1,s2,sq.l对信源输出的N个符号进行编码:共有qN个消息l码元集Aa1,a2,am.l长度为L的等长码：共有mL个可能码字l能正确译码的必要条件：(非奇异码)164.2 等长编码等长编码u编码速率（编码信息率）编码速率（编码信息率）:编码后每个信源符号所能承载的的最大信息量l编码效率编码效率u平均码长：平均码长：平均每个信源符号所需要的码符号个数u编码效率编码效率:174.2 等长编码等长编码l例例4-2 设一个离散信源的输出字母表有q=10个符号，将其编为无失真二元码，即m=2，求平均码长。184.2 等长编码等长编码l无失真编码无失真编码u假设信道无干扰u译码错误概率:Pe=PMMu无失真编码:译码错误概率Pe可以任意小.MWM信源信源编码信 道 信宿信源解码W194.2 等长编码等长编码l等等长信源信源编码定理定理u定理定理4-1(Shannon信源信源编码定理定理)设离散无记忆信源X的熵为H(X),若对长为N的信源符号序列进行等长编码,码长为L,码元符号个数为m.则对任意的 0,0,只要时,则译码差错概率一定是有限值(不可能实现无失真编码),而当N足够大时,译码错误概率近似等于1。则当N足够大时，必可使译码错误概率小于。反之，当204.2 等长编码等长编码l等等长信源信源编码定理定理u最佳等最佳等长编码:编码效率:214.2 等长编码等长编码l等长信源编码定理等长信源编码定理u设信源自信息方差为D(X)=DI(pi)，编码效率为,当允许译码错误概率Pe 时，有容许译码错误概率越小信源序列长度越大 编码效率越高22第第4 4章章 无失真信源编码无失真信源编码4.1 4.1 无失真信源编码的概念无失真信源编码的概念4.2 4.2 等长编码等长编码4.3 4.3 变长编码变长编码4.4 4.4 常用的变长编码算法常用的变长编码算法234.3 4.3 变长编码变长编码l字母集:Ss1,s2,sq.l信源X的概率分布：p(si)(i=1,2,q).l离散信源X的熵：H(X)l码元集Aa1,a2,am.l信源符号si的码字:wi=f(si)码字wi的长度为li(i=1,2,q)244.3 4.3 变长编码变长编码u编码速率编码速率:编码后每个信源符号所能承载的的最大信息量u编码效率编码效率:l不等长码的编码效率不等长码的编码效率u平均码长平均码长:u码的多余度（剩余度）码的多余度（剩余度）:254.3 4.3 变长编码变长编码l平均码长：平均每个信源符号所需的码元符号个数信源符号信源符号概率分布概率分布码码1:C1码码2:C2码码3:C3码码4:C4码码5:C5s1 0.5000011s2 0.250111101001s3 0.125100000100001s4 0.12511110110000001备注2非唯一可译非唯一可译唯一可译及时码平均码长21.51.51.8751.875264.3 4.3 变长编码变长编码l码树编码方法码树编码方法u三元树码：C=w1,w2,w11 w1=0,w2=11,w3=12,w4=20,w5=22,w6=100,w7=101,w8=102,w9=210,w10=211,w11=212.u树码一定是即时码011201201210202w2w3w1w4w10w5w9w8w7w6w110级节点级节点1级节点级节点2级节点级节点3级节点级节点274.3 4.3 变长编码变长编码l码树编码方法码树编码方法（1）树根编码的起点；（2）每一个中间节点树枝的个数编码的进制数；（3）树的节点编码或编码的一部分；（4）树的终止节点（端点、树叶）码；（5）树的节数码长；（6）码位于多级节点变长码；（7）码位于同一级节点码等长码；011201201210202w2w3w1w4w10w5w9w8w7w6w110级节点级节点1级节点级节点2级节点级节点3级节点级节点284.3 4.3 变长编码变长编码l克拉夫不等式克拉夫不等式(L.G.Kraft,1949)长度为l1l2,lr的m元即时码存在的充分必要条件是：l麦克米伦定理麦克米伦定理(麦克米伦麦克米伦:B.McMillan,1956).长度为l1,l2,lr的m元唯一可译码存在的充分必要条件是:294.3 4.3 变长编码变长编码l 例例信源符号信源符号概率分布概率分布码码1:C1码码2:C2码码3:C3码码4:C4码码5:C5s1 0.5000011s2 0.250111101001s3 0.125100000100001s4 0.12511110110000001备注2非唯一可译非唯一可译唯一可译及时码平均码长21.51.51.8751.87530判断以下码字是否可分离（唯一可译）？习题314.3 4.3 变长编码变长编码设离散信源X的熵为H(X),则其任意一个m元唯一可译码满足：同时存在m元唯一可译码，其平均长度满足：l单个符号单个符号不等长信源编码定理不等长信源编码定理324.3 4.3 变长编码变长编码设离散信源X的熵为H(X),其N次扩张信源为XN，将信源XN编为m元码，总存在唯一可译码f，使得信源X的每个符号所需的平均码长满足：l离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理 香农第一香农第一编码定理编码定理33第第4 4章章 无失真信源编码无失真信源编码4.1 4.1 无失真信源编码的概念无失真信源编码的概念4.2 4.2 等长编码等长编码4.3 4.3 变长编码变长编码4.4 4.4 常用的变长编码算法常用的变长编码算法344.4.1 香农编码香农编码设有离散无记忆信源设有离散无记忆信源351234香农编码方法的步骤香农编码方法的步骤按信源符号的概率从大到小的顺序排队不妨设不妨设36例例设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制香农码。试对该信源编二进制香农码。37编码过程编码过程（1）38394.1.2 费诺编码费诺编码对概率按m进行分组，使每组概率尽可能相等给每个分组分配一个码元对每个分组重复2、3步，直到不可分为止1234按信源符号的概率从大到小的顺序排队不妨设不妨设40设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制费诺码。试对该信源编二进制费诺码。例例41编码过程编码过程42 可以看出本例中费诺码有较高的编码效率。可以看出本例中费诺码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。费诺码比较适合于每次分组概率都很接近的信源。43将信源符号按概率由大到小顺序排队给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队给缩减信源中概率最小的符号各分配一个码元重复步骤2、3直至概率和为121434.4.3 赫夫曼编码赫夫曼编码44设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制哈夫曼码。试对该信源编二进制哈夫曼码。例例45编码过程编码过程464748说明：说明：Huffman码的编码方法不是唯一的。首先，每码的编码方法不是唯一的。首先，每次对缩减信源两个最小的符号分配次对缩减信源两个最小的符号分配“0”和和“1”码码元试任意的，所以可得到不同的码字。只要在元试任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体得到可分离码字。不同的码元分配，得到的具体码字不同，但码长，平均码长都不变，所以没有码字不同，但码长，平均码长都不变，所以没有本质区别。其次，若合并后的新符号的概率与其本质区别。其次，若合并后的新符号的概率与其他符号的概率相等，从编码的方法上来说，这几他符号的概率相等，从编码的方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，个符号的次序可任意排列，编出的码都是正确的，但得到的码字不同。不同的编法得到的码字长度但得到的码字不同。不同的编法得到的码字长度也不尽相同。也不尽相同。49 对信源进行缩减时，两个概率最小的符号合对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将此时将影响码字的长度，一般将合并的概率放合并的概率放在上面在上面，这样可获得，这样可获得较小的码方差较小的码方差。如下面的例子如下面的例子50例例 设有离散无记忆信源设有离散无记忆信源用两种不同的方法对其编二进制用两种不同的方法对其编二进制huffmanhuffman码码51方法一方法一方法二方法二52信源符号xi概率p(xi)码字Wi1码长Ki1码字Wi2码长Ki2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113两种不同的编码方法得到的码字和码长的对比两种不同的编码方法得到的码字和码长的对比53平均码长和编码效率平均码长和编码效率54两种编码方法编出的码字的码长方差比较两种编码方法编出的码字的码长方差比较55可以看出第二种编码方法的码长方差要小可以看出第二种编码方法的码长方差要小许多。这意味着第二种编码方法的码长变许多。这意味着第二种编码方法的码长变化较小，比较接近平均码长。由此可以得化较小，比较接近平均码长。由此可以得到一个结论到一个结论(怎样得到码方差较小的怎样得到码方差较小的huffmanhuffman编码编码)。56结论：结论：进进行行赫赫夫夫曼曼编编码码时时，为为得得到到码码方方差差最最小小的的码码，应应使使合合并并的的信信源源符符号号位位于于缩缩减减信信源源序序列列尽尽可可能能高高的的位位置置上上，以以减减少少再再次次合合并并的的次数，充分利用短码。次数，充分利用短码。574.4 4.4 常用的变长编码算法常用的变长编码算法l最佳不等长编码最佳不等长编码(最佳码最佳码)对于给定的信源和码元符号集，在其所有的唯一可译码中，平均长度最小的码称为最佳码最佳码，或紧致码紧致码。l字母集:Ss1,s2,sq.l信源X的概率分布：p(si)(i=1,2,q).l码元集Aa1,a2,am.l信源符号si的码字:wi=f(si)码字wi的长度为li(i=1,2,q)584.4 4.4 常用的变长编码算法常用的变长编码算法l习题习题 已知离散无记忆信源X为：求二进制香农码，二进制费诺码，二进制霍夫曼码，三进制霍夫曼码。594.4 4.4 常用的变长编码算法常用的变长编码算法信源X的熵:H(X)=2.61符号序列概率分布第1次分组第2次分组第3次分组第4次分组码字码长a1 0.200(0.57)0(0.2)002 a2 0.191(0.37)00103a3 0.1810113a4 0.171(0.43)0(0.17)102a5 0.151(0.26)01103a6 0.1010(0.10)11104a7 0.011(0.01)11114604.4 4.4 常用的变长编码算法常用的变长编码算法l习题习题 求以下信源X的霍夫曼码解：赋予码元解：赋予码元 614.4 4.4 常用的变长编码算法常用的变长编码算法解：解：写出码字 624.4 4.4 常用的变长编码算法常用的变长编码算法l习题习题 求以下信源X的三进制霍夫曼码634.4 4.4 常用的变长编码算法常用的变长编码算法符号序列符号序列概率分布概率分布123码字码字码长码长a0 a0 9/169/169/160101a0 a1 3/164/16017/16112a1 a0 3/16013/161003a1 a1 1/161013l例例4.10 设二元离散无记忆信源X的符号集为a0,a1,概率分布为：p0=0.75,p1=0.25,则 H(X)=0.75log0.75 0.25log0.25=0.811.对两个信源符号X2进行编码,则有644.4 4.4 常用的变长编码算法常用的变长编码算法l例例4.10 对三个信源符号X3进行编码654.4 4.4 常用的变长编码算法常用的变长编码算法l课堂练习课堂练习u已知离散无记忆信源X如下，求其三元霍夫曼码。并求其平均码长与编码效率。664.4 4.4 常用的变长编码算法常用的变长编码算法lLZ码码u1977年，齐费(J.Ziv,以色列)与兰佩尔齐(A.Lempel,以色列)提出LZ码，1978年进行改进，称为LZ78.u设信源符号集Ss1,s2,sq,输入信源符号序列为 u=u1 u2uL(uiS)u编码规则p分段：将符号序列u分成小段。分段原则:各小段尽可能短，且不相同.分成的小段称为短语短语.短语总数记为:M(u)p依次对每个短语编号：号码称为该短语的段号段号.p对每个短语编码:码字=除最后一符号后的短语段号编码+最后一符号的编码.单符号的段号码字为0.p如编为二进制码,则段号需要的长度为:n=logM(u),每个符号编码需要的长度为:logq.674.4 4.4 常用的变长编码算法常用的变长编码算法l例例4.12 设信源符号集S=a1,a2,a3,a4,信源序列为 u=a1a2a1a3a2a4a2a4a3a1a1a4.求LZ码.u分段:a1,a2,a1a3,a2a4,a2a4a3,a1a1,a4短语总数为:M(u)=7,段号编码长度为:n=log7=3.符号a1a2a3a4编码00011011段号段号短语短语编码编码1a1000 002a2000 013 a1a3001 104a2 a4010 115a2 a4a3100 106a1 a1001 007a4000 11u每个信源符号编码长度:log 4=2.u每个短语的码字长度为5.684.4 4.4 常用的变长编码算法常用的变长编码算法uLZ码性能p编、译码简单、速度快p符号序列越长，编码效率越高.当序列长度趋于无穷大时，平均码长趋于信源熵.p是一种简单的通用编码方法，与信源概率分布无关.p1984年韦尔奇(T.A.Welch)进行进一步改进，称为LZW算法,已成为计算机文件压缩标准算法.LZ77，LZ78,LZW几乎垄断了整个通用数据压缩领域.