4-无失真信源编码及其定理

第四章无失真信源编码4.1编码器及码的分类4.2等长码4.4等长信源编码定理4.5变长码4.6变长信源编码定理4.7霍夫曼码和其它编码方法4.8几种实用的无失真信源编码小结第四章无失真信源编码本章的重、难点内容1、理解等长码和等长信源编码定理2、理解和掌握变长码及变长码编码定理3、理解Huffman编码、费诺码、香农码4、了解几种实用的无失真信源编码方法，包括（MH编码、算术编码、LZ码）第四章无失真信源编码编码的意义：通信的基本问题：如何高速、高质地传送信息。高速和高质＝鱼和熊掌。编码讨论的问题：（1）质量一定，如何提高信息传输速度（提高编码效率或压缩比）----信源编码（本章讨论问题）（2）信道传输速度一定，如何提高信息传输质量（抗干扰能力）----信道编码（下一章讨论）引言信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。引言信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。引言信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。引言信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。4.1编码器及码的分类编码：信息的组织方式编码的实质：对信源的原始符号按一定的数学规则进行变换。编码的目的：信源编码：提高信息传输的有效性信道编码：提高信息传输的可靠性本章不考虑干扰问题4.1编码器及码的分类无失真编码器结构框图几个术语：信源符号：信源输入码符号(码元)：12{,,...,}qSSSS12{,,...,}rXxxx编码器12:{,,...,}qC{,,...,}qSSSS12{,,...,}rXxxx4.1编码器及码的分类码字Wi：由xj(j=1,2,…,r)组成的长度为li的序列，Wi与si一一对应。码字长度(码长)：Wi的长度li编码器：将信源符号si变换成Wi的设备信源编码信源编码：把信源符号si映射为码字Wi的过程。无失真编码：映射是一一对应、可逆的。信源编码基本思想：尽可能缩短出现概率大的信源符号的码字4.1编码器及码的分类码的分类二元码：若码符号集X＝{0，1}，所得码字为一些二元序列，则称二元码。[在二元信道中传输]等长码（固定长度码）：若一组码中所有码字的长度都相同(即li=l,i=1,…,q)，则称为等长码。变长码：不满足等长码条件的码组称为变长码。4.1编码器及码的分类非奇异码：若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列，不同信源符号可分辨)，则称为非奇异码。奇异码：反之，若码组中含有相同的码字则为奇异码。同价码：若码符号集X：{x1,x2,…,xr}中每个码符号所占的传输时间都相同，则所得的码为同价码。4.1编码器及码的分类码的N次扩展码：信源符号出现概率码1码2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111信源码字信源码字信源码字a100＝W1W1=B1a5...010＝W2W1=B1.......a16....111111=W4W4=B16a2001＝W1W2=B2a30001＝W1W3=B3a40111＝W1W4=B44.1编码器及码的分类惟一可译码：若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（单义可译码）。否则就称为非惟一可译码或非单义可译码。表1中码1是惟一可译码，而码2是非惟一可译码。因为对于码2，其有限长的码符号序列能译成不同的信源符号序列。如码符号序列0010，可译成s1s2s1或s3s1，就不惟一了。问题：怎样才能做到无失真编码即惟一可译码？4.2等长码若要实现无失真编码，不但要求信源符号si与码字Wi是一一对应的，而且要求码符号序列的反变换也是惟一的。即所编的码必须是惟一可译码。对于等长码来说，若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。等长非奇异码一定是惟一可译码。信源符号码1码2s10000s20111s31010s41111非奇异码唯一可译码奇异码非惟一可译码4.2等长码等长编码惟一可译的必要条件：其中：q为信源符号数,r为符号集中的码元数,l为码长。例如：若信源符号数q＝4，进行二元等长编码，则码符号个数为r＝2。信源S存在惟一可译等长码的条件是码长l≥2。若q＝8，r＝2，l≥3。Nlqr4.2等长码对两边取对数得平均每个信源符号所需的码符号个数上式表明：对于等长惟一可译码而言，平均每个信源符号至少需要用logq／logr个码符号来表示。即：每个信源符号所需最短码长为logq／logr个。loglogNqlrlogloglqNrNlqr4.2等长码当r=2(二元码)时logr=1,上式变成上式表明：对于二元等长惟一可译码，平均每个信源符号至少需要用logq个码符号来变换。或：对信源进行二元等长不失真编码时，每个信源符号所需的极限值为logq个。loglqN4.2等长码当考虑到符号之间的依赖关系或关联性时，可以从N次扩展信源中去掉一些符号，使得总符号数小于，这样使编码所需码字个数大大减少，因此平均每个信源符号所需的码符号个数就可以大大减少，从而提高传输效率。当N足够长后，这种误差概率可以任意小，做到几乎无失真编码。等长编码定理给出了信源进行等长编码所需码长的理论极限值。Nq4.4等长信源编码定理定理4.3(等长信源编码定理):一个熵为H(S)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中选取l个码元组成。对于任意ε＞0，只要满足：则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。反之，若当N足够大时，译码错误概率近似为1,不可能实现无失真编码。()loglHSNr()2loglHSNr4.4等长信源编码定理说明：定理4.3是在平稳无记忆离散信源的条件下得出，但它同样适合于平稳有记忆信源。当进行二元编码时，r＝2，则：一般情况下，信源符号并非等概率分布，且符号之间有很强的关联性，故信源的熵H(S)logq。()lHSN等长编码时平均每个信源符号所需的二元码符号的理论极限loglqN信源等概分布时4.4等长信源编码定理从定理4.3可知，在等长编码中每个信源符号平均所需的二元码符号可大大减少，从而使编码效率提高。定理4.3中的条件式可改写成：()log()loglHSlrNHSNr长为l的码符号序列所能载荷的最大信息量长为N的信源序列平均携带的信息量4.4等长信源编码定理所以等长编码定理告诉我们：只要码字传输的信息量大于信源序列携带的信息量，总可实现几乎无失真编码。令它是编码后平均每个信源符号能载荷的最大信息量，称为编码信息率。可见，当编码信息率大于信源的熵时，才能实现几乎无失真编码。为衡量编码效果，引入编码效率。log()lrHSNloglRrN4.4等长信源编码定理称为编码效率。由定理4.3可得最佳等长编码的效率为：如果自信息的方差和ε均为定值时，只要N足够大，编码错误就可以小于任一正数δ。也即要求误差小于δ时，()()logHSHSlRrN()1()0()HSHSHS()iDIs4.4等长信源编码定理信源序列长度N必须满足：该式给出了在已知方差和信源熵的条件下，信源序列长度N与最佳编码效率和允许错误概率的关系。允许错误概率越小，编码效率要求越高，则信源序列长度N就必须越长。实际情况下，要实现几乎无失真的等长编码，N需要非常大。2222()()()(1)iiDIsDIsNHS4.4等长信源编码定理例设离散无记忆信源信源熵自信息方差若对信源S采用等长二元编码，要求编码效率η=0.96，允许错误概率12,31(),44ssSPs134()log4log0.811()443HSbitsymbol2221222()(log)()3311(log)(log)(0.811)0.47154444iiiiDIsppHS5104.4等长信源编码定理则得即序列长度达4130万以上，这在实际中很难实现。因此，一般来说，当N有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无失真编码。下面介绍变长码，及其编码定理。272250.4715(0.96)4.1310(0.811)0.0410N4.5变长码4.5.1惟一可译变长码与即时码等长码仅当N很大才会有较高的编码效率；变长码往往在N不很大时就可编出效率很高而且无失真的码。等长码：非奇异惟一可译变长码：任意有限长N次扩展码是非奇异惟一可译4.5变长码即时码：在译码时无需参考后续的码符号就能立即作出判断，译成对应的信源符号的惟一可译码码4以“1”作为结束符号，起到逗号的作用，又称为逗点码。逗点码是一种即时码。信源符号出现概率码1码2码3码4s1s2s3s41/21/41/81/80110011010000111010010001010010001非惟一可译奇异码非惟一可译非奇异码惟一可译非奇异码惟一可译非奇异码4.5变长码定义：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字都不是另一个码字的前缀，则称为即时码也称非延长码或前缀条件码。所有码非奇异码惟一可译码即时码4.5变长码4.5.2即时码的树图构造法构造即时码的一种简单方法是树图法。信源符号码4s1s2s3s41010010001根：树的最上端树枝的个数为r，r=2为二元码树01001111010010001码4的树图ABCD中间节点（空心）节点：树枝的终端，从节点生出树枝，每个节点伸出r个枝终端节点（实心）码字：从根到终端节点对应的码符号，又称树叶4.5变长码按树图法构成的码一定满足即时码的充要条件，因为从根到叶所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前缀的限制。该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0，100，111，1010，10114.5变长码码树的性质：任一即时码都可用树图表示。当码字长度给定，即时码不是惟一的。整树：每个节点上都有r个分枝。非整树：至少有一个节点上没有r个分枝的树。4.5.4惟一可译变长码的判断法结论：不能用Kraft不等式，只能根据定义判断码C是否是惟一可译码。依据：非惟一可译变长码有限长的码符号序列能译成两种不同的码字序列。惟一可译变长码判别：将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字时，码C为惟一可译变长码。4.5.4惟一可译变长码的判断法构成集合F的方法：首先，观察码C中最短的码字是否是其他码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。依此下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随后缀产生为止。接着，按照上述步骤将次短的码字直至所有码字可能产生的尾随