编码理论第4章

第4章信源压缩编码原理

4.1信源编码的基本原理

4.1.1信源研究内容

4.1.2信源编码器

4.1.3码的类型

4.1.4Kraft不等式

4.15惟一可译码判别准则

4.1.6即时码的树图构造4.2无失真信源编码原理

4.2.1等长码及其编码定理

4.2.2变长码平均码长及编码效率

4.2.3变长码的特点

4.2.4变长信源编码定理4.3限失真信源编码原理

4.3.1失真函数及保真度准则

4.3.2信息率失真函数

4.3.3信息率失真函数定义域及性质

4.3.4离散信源信息率失真函数计算

4.3.5保真度准则下的信源编码定理编码理论第4章第4章信源压缩编码原理

4.1信源编码的基本原理4.1.1信源研究内容信息论对信源研究的内容包括3个方面：

(1)信源的建模信源输出信号的数学描述已有成熟的理论——随机过程，一般的随机过程理论并不涉及和讨论信号中所携带的信息，而信息论所关心的中心内容则是信号中携带的信息。

(2)信源输出信号中携带信息的效率的计算在信息论中，信源输出信号所携带信息的效率是用熵率或冗余度来表示的。

(3)信源输出信息的有效表示一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地表示信源输出的信息是人们感兴趣的问题，这就是信源编码的问题。编码理论第4章信源信源编码器信道信源译码器信宿4.1.2信源编码器为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，这样信息传输系统模型变为图4-1所示。图4-1简化信息系统传输模型概念信源符号二元信源n元信源码符号集码符号码元码字码组码长

二元码r元码等长码变长码非奇异码奇异码惟一可译码非惟一可译码即时码非即时码编码理论第4章

设信源U发出n种不同的符号，其符号集为U={u1,u2,…,un},其中ui称为信源符号，若信源符号集中符号数等于2称为二元信源，等于3称为三元信源，…，等于n称为n元信源。又若信道的输人符号集为X={a1,a2,…,ar}。信源编码问题,就是用信道的输人符号集X={a1,a2,…,ar}作为码符号集，其中ai（i＝1，2，…，r）称为码符号或码元，用码符号集中的码符号,对信源U的每一种不同的符号进行一一对应变换，构成由码符号组成的序列，即码字。所有码字的集合称为码组w={w1，w2，…，wn}；码字中所用的码符号的个数称为码长。编码理论第4章4.1.3码的类型若码符号集中符号数等于2称为二元码，等于3称为三元码，…，等于r称为r元码。若一组码中所有码字的码长都相同，称为等长码,否则称为变长码。若码组中所有码字都不相同则称为非奇异码，否则称为奇异码。符号码1码2码3码4a00001b01101101c100000001d1101110001表4-1信源X对应的不同码字编码理论第4章

表4-1中码1的编码为等长码，其它的几种编码皆为变长码。码3有两个符号的编码相同，码3是奇异码，而码1、码2和码4都为非奇异码。若每个码符号的传输时间都相同则称为同价码，否则称为非同价码。信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应，而且同时还要求信源的N个符号组成的序列所代表的消息，与之相对应的码字组成的码字序列也必须一一对应。只有这样，才能保证任何一个码字或码字序列唯一地翻译成相对应的信源符号或符号序列，达到无失真传递信源发出的消息的目。无失真信源编码必须具有这种单义可译性,单义可译的码称为单义可译码，也称为惟一可译码。例如码字{0，10，11}是一种惟一可译码。因为任意一串有限长码序列，例如100111000，只能被分割成10，0，11，10，0，0。任何其他分割法都会产生一些非定义的码字。非奇异码中有非惟一可译码和惟一可译码。编码理论第4章

惟一可译码中又分为非即时码和即时码；如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。表4-1中码2是非即时码，而码4是即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码。即时码又称为非延长码，若码组中，没有任何完整的码字是其它码字的前缀则称为异前缀码(或前缀条件码），表4-1中的码1和码4都是前缀条件码。在惟一可译变长码中，人们需要的是在译码时无需参考后续的码符号就能立即做出判断的一类即时码。编码理论第4章4.1.4Kraft不等式在数学上表达码字可分离的充要条件，即著名Kraft不等式。

定理4-1

对于n元信源编m元码，其码长分别为l1,l2，…，ln，则即时码存在的充要条件式（4-1）称克拉夫特（Kraft）不等式。式（4-1）是1949年由提出的，所以称克拉夫特（Kraft）不等式，Kraft不等式指出了即时码的码长必须满足的条件。后来在1956年由麦克米伦（B.McMillan）证得对于惟一可译码也满足此不等式，1961年卡拉什（J.karuSh)简化了麦克米伦的证明方法。这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件，而是惟一可译码的码长也必须满足克拉夫特不等式，所以在码长选择的条件上，即时码与惟一可译码是一致的。编码理论第4章如表4-1中，m＝2，n＝4。对码1有l1＝2,l2＝2,l3＝2,l4＝2，则：满足式（4-1），则此码长的编码可能是惟一可译码。对码2有l1＝1,l2＝2,l3＝2,l4＝2，则：不满足式（4-1）则此码长编码不能构成惟一可译码。对码4有l1＝1,l2＝2,l3＝3,l4＝4，则：满足式（4-1），则此码长的编码可能是惟一可译码。符号码1码2码3码4a00001b01101101c100000001d1101110001表4-1信源X对应的不同码字编码理论第4章4.15惟一可译码判别准则惟一可译码的判断步骤：(1)观察是否是非奇异码，若是奇异码则一定不是惟一可译码；(2)计算是否满足Kraft不等式，若不满足一定不是惟一可译码；(3)将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是惟一可译码；(4)用Sardinas和Patterson设计的判断方法：计算出码组中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码。上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是否是惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。该准则是萨得纳斯(A．A．Sardinas)和彼得森(G．W．Patterson)于1957年设计出来的.编码理论第4章4.1.6即时码的树图构造树图法是构造即时码的一种简单方法。树是n个结点的集合，这n个结点中有且仅有一个作为根的结点，其余的结点可分为m个互不相交的子集，每个子集本身又是一棵树，称为根的子树，也叫根的树枝数。树图与信源符号编码之间对应关系：树根码字的起点树的度码的进制数分支结点码的符号的一部分终端结点待编码符号满树等长码非满树变长码编码理论第4章构造树图的要点是：

(1)最上端为树根A，从根出发向下伸出树枝，树枝总数等于码符号数r，树枝的尽头为节点。

(2)从每个节点再伸出r枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的节点称为中间节点。一直继续进行，直至都不能伸枝为止。用码树进行信源符号编码时，将待编码的字符作为终端结点，构造码树；然后按一定规则给每个树枝分配一个码符号；最后将从根到终端结点的路径上的码符号依次相连，作为该终端结点所表示的字符的编码。码树可用于信源符号的编码，也可用于译码。编码理论第4章00001111(a)图5-2例5-2两种霍夫曼编码编码理论第4章4.2无失真信源编码原理4.2.1等长码及其编码定理4.2.2变长码的平均码长及编码效率对n元基本离散信源，设编码后各码字的码长分别为l1,l2,…，ln,则定义码的平均码长度为编码的效率η为编码理论第4章4.2.3变长码的特点

1．使信道复杂化

2．容易产生溢出或取空错误

3．差错的扩散4.2.4变长信源编码定理用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？下面的定理将回答这个问题。定理4-3一个熵为H（U）的基本离散无记忆信源U，若用m元码对其进行变长编码，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足此编码定理给出了最佳变长码的平均码长的上限和下限。定理表明码字的平均长度不能小于极限H(U)/lbm，否则惟一可译码不存在。

编码理论第4章

实际上，信源U发出的消息，往往不是信源U的单个符号，而是由单个符号组成的序列来表示。倘若信源发出的消息由N个符号组成，则每一条消息都可看作信源U的N次扩展信源的某一个“符号”，因此在构造即时码时，如不把信源U的单个符号作为编码对象，而直接把扩展信源的某一个输出“符号”作为编码对象，使码字与一一对应，能否使信源U每个符号所需要的平均码符号数，即平均码长有所下降?也就是说，能否用扩展信源的手段，达到数据压缩的目的?下面讨论这个问题。定理4-4无失真变长信源编码定理（香农第一定理）离散无记忆信源U的N次扩展信源UN，其熵为H(UN)，用m元码对信源UN进行编码，总可以找到一种编码方法，构成惟一可译码，使信源U中每个信源符号所需的平均码长满足：编码理论第4章4.3限失真信源编码原理

在实际生活中，信宿一般并不要求完全无失真地恢复消息。通常总是要求在保证一定质量(一定保真度)的条件下近似地再现原来的消息，也就是允许有一定的错误(失真)存在。在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，即最少需要多少比特数才能描述信源。也就是，在允许一定程度失真的条件下，如何能快速地传输信息。这就是本节将讨论的问题。编码理论第4章失真函数及保真度准则由于只涉及信源编码问题。所以可以将信道编码和译码看成是信道的一部分。这样接收者收到消息后所产生的失真（或误差）只是由信源编码带来的。从直观感觉可知，若允许失真越大，信息传输率可越小;若允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真（或误差）是有关的。为了定量地描述信息传输率和失真的关系，可以略去广义的无扰信道，所谓广义无扰信道是指，把信道编码、信道、信道译码这三部分看成一个没有任何干扰的广义信道。这样通信系统可简化成如图4-4所示。图4-4简化的通信系统信源信源编码广义无扰信道信道信源译码UVP(v|u)编码理论第4章1．基本离散信源失真设离散无记忆信源：信源符号通过信道传输到接收端，则接收端接收量为：对应于一对（u,v），定义一个非负函数：

i＝1，2，…，n；j＝1，2，…，m

称此函数为失真函数（或称单个符号失真度）。编码理论第4章

失真函数有个，这个非负的函数可以排成矩阵形式，即：称它为失真矩阵。失真函数应尽可能符合信宿的主观特性；也就是主观上的失真感觉应与失真函数的值相对应。设x为信源输出信息，y为信宿收到信息，则常用失真函数有：均方失真：d(x,y)＝绝对失真：d(x,y)＝|x－y|

相对失真：d(x,y)＝|x－y|/|x|

汉明失真：d(x,y)＝δ(x,y)＝编码理论第4章[例4-4]二元对称信源，信源U＝{0，1}，接收变量V＝{0,1}在汉明失真定义下，失真函数为：d(0,0)＝d(1,1)＝0d(0,1)＝d(1,0)＝1失真矩阵[例4-5]设信源U＝{0,1},接收变量V＝{0,1,2},定义失真函数为：

d(0,0)＝d(1,1)＝0,d(0,1)＝d(1,0)＝1,

d(0,2)＝d(1,2)＝0.5失真矩阵010101201编码理论第4章

因为信源U和信宿接收量V都是随机变量，因此单个符号失真度也是随机变量。那么，现在定义传输一个符号引起的平均失真，即信源平均失真：式中:ui—信源输出符号，i＝1，2，…，n；vj—信宿接收符号；j＝1,2,…，m；p(vj|ui)—广义无扰信道传递概率。单个符号的失真度描述了某个信源符号通过传输后失真的大小，对于不同的信源符号和不同的接收符号，其值是不同的。但平均失真度已对信源和信道进行了统计平均，所以此值是描述某一信源在某一广义无扰信道（或称为试验信道）传输下的失真大小，是从总体上描述整个系统的失真情况。编码理论第4章[例4-7]等概信源，通过信道转移概率矩阵P的信道传输，失真测度为均方失真测度，求平均失真。信道转移概率矩阵为解:由失真定义得失真矩阵平均失真012012编码理论第4章2.N次扩展信源失真N次无记忆扩展信源失真度（失真函数）N次扩展信源平均失真度：若平均失真度不大于所允许的失真D，即：

（4-41）称式（4-41）为保真度准则。

N

次扩展信源的保真度准则是平均失真度不大于允许失真ND，即：

(4-42)编码理论第4章[例4-8]二元等概离散无记忆信源，信道矩阵为

失真测度为汉明失真测度，求:平均失真及2次扩展信源的单个符号平均失真?解:由式（4-35）可计算得根据式（4-40）可得二次扩展信源平均失真编码理论第4章解2:二维扩展信源概率分布二次扩展信道矩阵由式（4-36）得二次扩展信源失真矩阵，将其除2得单个符号失真矩阵为由式（4-37）得二次扩展信源平均失真编码理论第4章信息率失真函数在满足保真度准则下，寻找信源必须传输给信宿的信息率R的下限值。从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息I(U；V)来表示，这就变成了在满足保真度准则的条件下,寻找平均互信息I(U；V)的最小值。这个最小值就是在满足保真度准则条件下，信源必须传输的最小平均信息量。即：

R（D）＝{I（U；V）}（4-43）称R(D)信息率失真函数（或率失真函数），R(D)单位同互信息量单位相同。N次扩展信源的信息率失真函数RN(D)：（4-44）编码理论第4章信息率失真函数定义域及性质1．R(D)的定义域

(1)和一般，当给定信源[U,P]及失真矩阵，信源的最小平均失真度为平均失真最小值：（4-49）选择这样的试验信道，当i=1，2，…，r时，它满足

（4-48）编码理论第4章

则可得信源的最小平均失真度为允许失真度D是否能达到零，这与单个符号的失真函数有关，只有当失真矩阵中每行至少有一个零元素时，信源的平均失真度才能达到零值。否则，信源的最小平均失真度不等于零值。在实际情况中，一般。另外，假如时，可以适当改变单个符号的失真度，使。而对信息率失真函数来说，它只是起了坐标平移作用。所以，可以假设而不失其普遍性。这时（4-50）编码理论第4章[例4-9]删除信源U取值于，V取值于，而失真矩阵为求：及其对应的信道。解：由式(4-50)可知最小允许失真度为

由式（4-49）得满足最小允许失真度的试验信道是一个无噪无损的试验信道，信道矩阵为可以看出，若取允许失真度，则集合中只有这个信道是惟一可取的实验信道、也就是无失真一一对应的编码。编码理论第4章(2)和根据信息率失真函数R（D）的定义，R(D)函数是在保真度准则下，平均交互信息量的最小值。因为平均交互信息量是非负的，其最小恒等于零。所以，把能使平均交互信息量为零的最小平均失真度定义为最大允许失真度。当平均交互信息量为零时，信道的输入随机变量U和输出随机变量V之间一定统计独立，即有。由信源平均失真度公式(4-35)式可知，这时平均失真度的最小值编码理论第4章若取最小值时,显然一定能使平均失真度(4-53)式得到最小值，这样可以得到最大允许失真度

(4-54)

根据最大允许失真度的定义和(4-54)式可知，在信源U给定，失真矩阵规定的前提下，若允许失真度选择为最大允许失真度,则满足保真度准则的试验信道必须同时满足这时的信源U的信息率失真函数编码理论第4章[例4-12]设二元离散信源其中，规定失真函数为汉明失真度时，求及对应的信道。解：由（4-54）式得最大允许失真度由（4-55）~（4-57）式得此时的试验信道的信道矩阵编码理论第4章2R(D).函数的性质无论是离散信源还是连续信源，信息率失真函数都有以下特性：(1)信息率失真函数满足

对于离散信源，只有当失真矩阵中每行至少有一个零元素，并每一列最多只有一个零元素时，才有

（2）下凸性信息率失真函数允许失真D的型凸函数。

(3）连续性信息率失真函数是D的连续函数。

(4)单调递减性

编码理论第4章4.3.4离散信源计算对基本离散信源，若规定失真函数为汉明失真度，其失真矩阵对于一般试验信道的信道矩阵其平均失真度编码理论第4章平均失真度就等于信道的平均错误传递概率，即有

(4-71)

所以在汉明失真度下，平均失真度等于信道的平均错误传送概率。这是汉明失真度下平均失真度的一般规律，也是汉明失真度下平均失真度的特点。所以在规定汉明失真度的前提下，若则满足保真度准则试验信道集合中的所有试验信道的平均错误传递概率都等于允许失真度D，即有则编码理论第4章

这个表达式在数学上与费诺不等式中的平均错误传递概率完全相同，所以由费诺不等式有所以在规定汉明失真度的前提下，满足保真度准则的试验信道的疑义度H(U︱V)的最大值是允许失真度D的函数。由此可得试验信道的平均交互信息量存在最小值，而且这个最小值一定也是允许失真度D的函数，即有