第五章 无失真信源编码

第五章无失真信源编码5.1信源编码的相关概念5.2定长码及定长编码定理5.3变长码及变长编码定理5.4变长码的编码方法5.5实用的无失真信源码方法5.1信源编码的相关概念5.1.1编码器信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为码序列，对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码，完成编码功能的器件，称为编码器。接收端有一个译码器完成相反的功能。信源编码器的输入是信源符号集，共有q个信源符号。同时存在另一个符号集，称为码符号集，共有r个码符号，码符号集中的元素称为码元或码符号，编码器的作用就是将信源符号集Si中的符号变换成由个码符号组成的一一对应的码符号序列。编码器输出的码符号序列称为码字，并用来表示，它与信源符号之间是一一对应的关系，如图5.1所示。12{,,}qSsss12{,,}rXxxx,1,2,isiqil,1,2,,iwiq,1,2,isiq码字的集合C称为码，即。信源符号对应的码字包含个码符号，称为码字长度，简称码长。所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总是希望把信源所有的信息毫无保留地传递到接收端，即实现无失真传递，所以首先要对信源实现无失真编码。12{,,,}qCisiwilil图5.1信源编码器信源编码有以下3(1)根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。将要讲述的香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。(2)变换编码先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。(3)识别编码无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。5.1.2码的分类1.分组码和非分组码定义5.1将信源符号集中的每个信源符号固定地映射成一个码字，这样的码称为分组码。用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非分组码，又称为树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。2.奇异码与非奇异码定义5.2若一种分组码中的所有码字都不相同，则称此分组码为非奇异码，否则称为奇异码。isiw3.唯一可译码与非唯一可译码定义5.3任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码。唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。4.即时码与非即时码定义5.4无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。定义5.5设为一码字，对于任意的，称码符号序列的前j个元素定理5.1一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。即时码可以用树图来构造．图5.2是一个二元即时码的树图．12,liiiiwxxx1jl12,liiixxx图5.2二元即时码的树图树是没有回路的图，所以它也是由节点和弧构成的．树中最顶部的节点称为根节点，没有子节点的节点称为叶子节点。所有根节点的子节点称为一阶节点，所有一阶节点的子节点称为二阶节点，依此类推。阶节点最多有个。节点的阶次又称为节点的深度。综上所述，可将信源编码作如下分类：nnr码非分组码（树码）分组码（块码）奇异码非奇异码非唯一可译码唯一可译码即时码非即时码5.2定长码及定长编码定理若对一个有q个信源符号的信源S进行定长编码，那么信源S存在唯一可译定长码的条件是(5.1)其中，r是码符号集中的码元数，l是定长码的码长。如果对信源S的N次扩展信源进行定长编码，若要编得的定长码(5.2)其中，q是信源S的符号个数，是信源S的N次扩展信源的符号个数，r是码符号集X的码符号数。lqrNSNlqrNqNS定长编码的信息传输效率是很低的。提高信息传输效率的方法有：方法1考虑符号之间的依赖关系，对信源S的扩展信源进行编码。方法2对于概率等于0或非常小的符号序列不予编码。定理5.2离散无记忆信源的熵为H(S)，若对信源长为N的序列进行定长编码，码符号集X中有r个码符号，码长为l，则对于任意，只要满足则当N足够大时，可实现几乎无失真编码，即译码错误概率δ任小；反之，如果则不可能实现几乎无失真编码，即当N足够大时，译码错误概率为1。0()loglHSNr()2loglHSNr定理5.2是在离散平稳无记忆信源的条件下证明的，但它同样适合于平稳有记忆信源，只要将式中H(S)改为极限熵即可，条件是有记忆信源的极限熵和极限方差定长信源编码定理给出了定长编码时每个信源符号最少所需的码符号的理论极限，该极限值由H(S)决定。定义5.6设熵为H(S)的离散无记忆信源，若对信源的长为N的符号序列进行定长编码，码符号集中码符号个数为r，设码字长为l，定义比特/信源符号为编码速率，它表示平均每个信这时，定理5.2的条件可表述为R′≥H(S)+ε，即编码速率大于信源的熵才能实现几乎无失真编码。为了衡量编码效果，引进编码效率。()HS()HS2()SloglRrN定义5.7定义为编码效率由定理5.2可得最佳编码效率为，所以在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率η和允许错误概率的关系为：当允许错误概率越小，编码效率又要高，那么信源符号序列长度N必须越长．在实际情况下，要实现几乎无失真的定长编码，N需要的长度将会大到难以实现。()()logHSHSlRrN(),0()HSHS1()HSEP2222[()][()]()(1)iiDIsDIsNHS5.3变长码及变长编码定理5.3.1Kraft不等式和McMillan不等式定理5.3设信源符号集为，码符号集为，对信源进行编码，得到的码为，码长分别为。即时码存在的充要条件是这称为Kraft不等式。由Kraft不等式可知，给定r和q，只要允许码字长度可以足够长，则码长总可以满足Kraft不等式而得到即时码，Kraft不等式指出了即时码的码长必须满足的条件．12{,,}qSsss12{,,}rXxxx12,,qC12,,qlll11iqlir(5.11)对于唯一可译码，该不等式又称为McMillan不等式。定理5.4r为码符号个数，为码字长度，q为信源符号个数。定理5.4指出了唯一可译码中r、q、之间的关系，如果满足这个不等式的条件，则一定能够构成至少一种唯一可译码，否则，无法构成唯一可译码．它给出了唯一可译变长码的存在性。另外，从定理5.3和定理5.4可以得到一个重要的结论，即任何一个唯一可译码均可用一个相同码长的即时码来代替，因为即时码很容易用树图法构造，因此要构造唯一可译码，只要构造即时码就可以了。11iqlir(5.12)il5.3.2唯一可译码的判别准则A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判断码C的唯一可译性．此算法的原理如下所示：其中都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时一定是的前缀，而的尾随后缀一定是另一码字的前缀；而的尾随后缀又1A2A3mAA3nBB2B1B,iiAB1B1A1A2B2B设C为码字集合，按以下步骤构造此码的尾随后缀集合F(1)考查C中所有的码字，若是的前缀，则将相应的后缀作为一个尾随后缀码放入集合(2)考查C和两个集合，若是的前缀或是的前缀，则将相应的后缀作为尾随后缀码放入集合(3)即为码C(4)若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F定理5.5一个码是唯一可译码的充要条件是的并集中没有C中的码字。iWjW0FiFiWCiiWFiiWFjWC1iFiiFF12,,FF5.3.3无失真变长编码定理定义5.8编码后的码字分别为，各码字相应的码长分别为因为是唯一可译码，信源符号和码字一一对应，则定义此码的平均码长其中，表示每个信源符号平均需用的码元数。当信源给定时，信源熵H(S)就确定了，而编码后每个信源符号平均用个码元来变换，故平均每个码元载荷的信息量即编码后信源的信息传输率。1212()()()qqsssSPpspsps12,,q()qiiiLpsl码符号/信源符号L(5.20)L定义5.9如果传输一个码符号平均需要t秒时间，则编码后信源每秒钟提供可以看出，越小，则越大，信息传输率就越高，因此我们感兴趣的码是使平均码长最短的码。定义5.10对于给定的信源和码符号集，若有一个唯一可译码，其平均码长小于所有其他唯一可译码，则称这种码为紧致码或最佳码。()()HSRHXL比特/码符号(5.21)()ttHSRL(5.22)LtRLL定理5.6若一个离散无记忆信源S，熵为H(S)，用拥有r个码符号的对S进行无失真编码，则总可以找到一种唯一若熵以r进制为单位，则式(5.23)可写成另外还可以看到平均码长的极限值与无失真定长信源编码定理中的12,,,rXxxx()()1loglogHSHSLrr(5.23)()()1rrHSLHS(5.33)5.3.4香农第一编码定理定理5.7设离散无记忆信源S的信源熵H(S)，它的N次扩展信源，其熵。并用码符号对信源进行编码，总可以找到一种唯一可译码，使信源S中每个信源符号所需或者写成定理5.6可以看作定理5.7在N=1时的特殊情况。定理5.7是香农信息论的主要定理之一。12,,,NnSsss()NHS12,,,rXxxxNS(5.34)()()1loglogNLHSHSrNrN1()()NrrLHSHSNN(5.35)定义5.11编码后信道的信息传输率这里，，所以无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源(信道的输入)尽可能为等概率分布，使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到信道容量，实现信源与信道理想的统计匹配。这就是香农第一定理的()logNLHSLNrlogRr()HSRL比特/码符号(5.43)比特/信源符号码符号/信源符号()HSL为了衡量各种编码是否已达到极限情况，我们定义变长码的编码定义5.12设对信源S进行无失真编码所得到的平均码长为，则为编码效率，对同一信源来说，码的平均码长越短，越接近极限，信道的信息传输率越高，越接近无噪无损信道的信道容量，这时η也越接近于1，所以用码的效率η来衡量各种编码的优劣。L()rLHS()rHSL(5.44)1L()rHS另外，为了衡量各种编码与最佳码的差距，引入码的剩余度的概定义5.13为码的剩余度。在二元无噪无损信道中r=2，，所以在二元无噪无损信道注意它们数值相同，单位不同．η是个无单位的比值，而R的单位是比特/码符号。(5.45)()11rHSL()HSL()HSRL5.4变长码的编码方法本章介绍的变长码的常见编码方法，如香农编码、香农-费诺-埃利斯编码、霍夫曼编码、费诺编码均为匹配编码，也称统计编码，都是通过使用较短的码字来给出现概率较高的信源符号编码。而出现概率较小的信源符号用较长的码字来编码，从而使平均码长最短，达到最佳编码的目的。下面介绍这几种方法：5.4.1香农编码香农码的方法