第4章 信源压缩编码原理 4.1 信源编码的基本原理 4.1.1 信源研究内容 4.1.2 信源编码器 4.1.3 码的类型 4.1.4 Kraft不等式 4.1 5 惟一可译码判别准则 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.1 信源编码的基本原理,4.1.1 信源研究内容 信息论对信源研究的内容包括3个方面： (1)信源的建模 信源输出信号的数学描述已有成熟的理论随机过程，一般的随机过程理论并不涉及和讨论信号中所携带的信息，而信息论所关心的中心内容则是信号中携带的信息。 (2)信源输出信号中携带信息的效率的计算 在信息论中，信源输出信号所携带信息的效率是用熵率或冗余度来表示的。 (3)信源输出信息的有效表示 一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地表示信源输出的信息是人们感兴趣的问题，这就是信源编码的问题。,信源,信源编码器,信道,信源译码器,信宿,4.1.2 信源编码器 为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，这样信息传输系统模型变为图4-1所示。,图4-1 简化信息系统传输模型,概念 信源符号 二元信源 n元信源 码符号集,码符号 码元 码字 码组 码长,二元码 r元码 等长码 变长码 非奇异码,奇异码 惟一可译码 非惟一可译码 即时码 非即时码,4.1.3 码的类型 若码符号集中符号数等于2称为二元码，等于3称为三元码，等于r称为r元码。若一组码中所有码字的码长都相同，称为等长码,否则称为变长码。若码组中所有码字都不相同则称为非奇异码，否则称为奇异码。,表4-1 信源X对应的不同码字,表4-1中码1的编码为等长码，其它的几种编码皆为变长码。码3有两个符号的编码相同，码3是奇异码，而码1、码2和码4都为非奇异码。 若每个码符号的传输时间都相同则称为同价码，否则称为非同价码。 信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应，而且同时还要求信源的N个符号组成的序列所代表的消息，与之相对应的码字组成的码字序列也必须一一对应。只有这样，才能保证任何一个码字或码字序列唯一地翻译成相对应的信源符号或符号序列，达到无失真传递信源发出的消息的目。无失真信源编码必须具有这种单义可译性,单义可译的码称为单义可译码，也称为惟一可译码。 例如码字0，10，11是一种惟一可译码。因为任意一串有限长码序列，例如100 111 000，只能被分割成10，0，11，10，0，0。任何其他分割法都会产生一些非定义的码字。非奇异码中有非惟一可译码和惟一可译码。,惟一可译码中又分为非即时码和即时码；如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。 表4-1中码2是非即时码，而码4是即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码。即时码又称为非延长码，若码组中，没有任何完整的码字是其它码字的前缀则称为异前缀码(或前缀条件码），表4-1中的码1和码4都是前缀条件码。 在惟一可译变长码中，人们需要的是在译码时无需参考后续的码符号就能立即做出判断的一类即时码。,4.1.4 Kraft不等式 在数学上表达码字可分离的充要条件，即著名Kraft不等式。 定理4-1 对于n元信源编m元码，其码长分别为l1, l2，ln，则即时码存在的充要条件 式（4-1）称克拉夫特（Kraft）不等式。 式（4-1）是1949年由L.G.Kraft提出的，所以称克拉夫特（Kraft）不等式，Kraft不等式指出了即时码的码长必须满足的条件。后来在1956年由麦克米伦（B.McMillan）证得对于惟一可译码也满足此不等式，1961年卡拉什（J.karuSh)简化了麦克米伦的证明方法。这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件，而是惟一可译码的码长也必须满足克拉夫特不等式，所以在码长选择的条件上，即时码与惟一可译码是一致的。,如表4-1中，m2，n4。 对码1有l12,l22,l32,l42，则： 满足式（4-1），则此码长的编码可能是惟一可译码。 对码2有 l11,l22,l32,l42，则： 不满足式（4-1）则此码长编码不能构成惟一可译码。 对码4有l11,l22,l33,l44，则： 满足式（4-1），则此码长的编码可能是惟一可译码。,表4-1 信源X对应的不同码字,4.1 5 惟一可译码判别准则 惟一可译码的判断步骤： (1)观察是否是非奇异码，若是奇异码则一定不是惟一可译码； (2)计算是否满足Kraft不等式，若不满足一定不是惟一可译码； (3)将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是惟一可译码； (4)用Sardinas和Patterson设计的判断方法：计算出码组中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码。 上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是否是惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。该准则是萨得纳斯(AASardinas)和彼得森(GWPatterson)于1957年设计出来的.,4.1.6 即时码的树图构造 树图法是构造即时码的一种简单方法。树是n个结点的集合，这n个结点中有且仅有一个作为根的结点，其余的结点可分为m个互不相交的子集，每个子集本身又是一棵树，称为根的子树，也叫根的树枝数。 树图与信源符号编码之间对应关系： 树根 码字的起点 树的度 码的进制数 分支结点 码的符号的一部分 终端结点 待编码符号 满树 等长码 非满树 变长码,构造树图的要点是： (1)最上端为树根A，从根出发向下伸出树枝，树枝总数等于码符号数r，树枝的尽头为节点。 (2)从每个节点再伸出r枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的节点称为中间节点。一直继续进行，直至都不能伸枝为止。 用码树进行信源符号编码时，将待编码的字符作为终端结点，构造码树；然后按一定规则给每个树枝分配一个码符号；最后将从根到终端结点的路径上的码符号依次相连，作为该终端结点所表示的字符的编码。 码树可用于信源符号的编码，也可用于译码。,0,0,0,0,1,1,1,1,(a),图5-2 例5-2 两种霍夫曼编码,4.2 无失真信源编码原理,4.2.1 等长码及其编码定理 4.2.2 变长码的平均码长及编码效率 对n元基本离散信源，设编码后各码字的码长分别为l1 ,l2 ,，ln,则定义码的平均码长度为 编码的效率为,4.2.3 变长码的特点 1使信道复杂化 2容易产生溢出或取空错误 3差错的扩散 4.2.4 变长信源编码定理 用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？下面的定理将回答这个问题。 定理4-3一个熵为H（U）的基本离散无记忆信源U，若用m元码对其进行变长编码，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足 此编码定理给出了最佳变长码的平均码长的上限和下限。定理表明码字的平均长度不能小于极限H(U)/lbm，否则惟一可译码不存在。,实际上，信源U发出的消息，往往不是信源U的单个符号，而是由单个符号组成的序列来表示。倘若信源发出的消息由N个符号组成，则每一条消息都可看作信源U的N次扩展信源的某一个“符号” ，因此在构造即时码时，如不把信源U的单个符号作为编码对象，而直接把扩展信源的某一个输出 “符号” 作为编码对象，使码字与一一对应，能否使信源U每个符号所需要的平均码符号数，即平均码长有所下降?也就是说，能否用扩展信源的手段，达到数据压缩的目的?下面讨论这个问题。 定理4-4无失真变长信源编码定理（香农第一定理）离散无记忆信源U的N次扩展信源UN，其熵为H(UN)，用 m元码对信源UN进行编码，总可以找到一种编码方法，构成惟一可译码，使信源U中每个信源符号所需的平均码长满足：,4.3 限失真信源编码原理,在实际生活中，信宿一般并不要求完全无失真地恢复消息。通常总是要求在保证一定质量(一定保真度)的条件下近似地再现原来的消息，也就是允许有一定的错误(失真)存在。 在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，即最少需要多少比特数才能描述信源。也就是，在允许一定程度失真的条件下，如何能快速地传输信息。这就是本节将讨论的问题。,4.3.1失真函数及保真度准则 由于只涉及信源编码问题。所以可以将信道编码和译码看成是信道的一部分。这样接收者收到消息后所产生的失真（或误差）只是由信源编码带来的。从直观感觉可知，若允许失真越大，信息传输率可越小; 若允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真（或误差）是有关的。为了定量地描述信息传输率和失真的关系，可以略去广义的无扰信道，所谓广义无扰信道是指，把信道编码、信道、信道译码这三部分看成一个没有任何干扰的广义信道。这样通信系统可简化成如图4-4所示。,图4-4 简化的通信系统,信源,信源编码,广义无扰信道,信道,信源译码,U,V,P(v|u),1基本离散信源失真 设离散无记忆信源： 信源符号通过信道传输到接收端，则接收端接收量为： 对应于一对（u,v），定义一个非负函数： i1，2，n；j1，2，m 称此函数为失真函数（或称单个符号失真度）。,失真函数 有 个，这 个非负的 函数可以排成矩阵形式，即： 称它为失真矩阵。 失真函数应尽可能符合信宿的主观特性；也就是主观上的失真感觉应与失真函数的值相对应。设x为信源输出信息，y为信宿收到信息，则常用失真函数有： 均方失真：d(x,y) 绝对失真：d(x,y)|xy| 相对失真：d(x,y)|xy|/|x| 汉明失真：d(x,y)(x,y),例4-4二元对称信源，信源U0，1，接收变量 V0,1在汉明失真定义下，失真函数为： d (0,0)d(1,1)0 d(0,1)d(1,0)1 失真矩阵 例4-5设信源 U0,1,接收变量V0,1,2,定义失真函数为： d(0,0)d(1,1)0, d(0,1)d(1,0)1, d(0,2)d(1,2)0.5 失真矩阵,0 1,0 1,0 1 2,0 1,因为信源U和信宿接收量V都是随机变量，因此单个符号失真度也是随机变量。那么，现在定义传输一个符号引起的平均失真，即信源平均失真： 式中: ui 信源输出符号，i1，2，n； vj信宿接收符号；j1,2,，m； p(vj|ui)广义无扰信道传递概率。 单个符号的失真度描述了某个信源符号通过传输后失真的大小，对于不同的信源符号和不同的接收符号，其值是不同的。但平均失真度已对信源和信道进行了统计平均，所以此值是描述某一信源在某一广义无扰信道（或称为试验信道）传输下的失真大小，是从总体上描述整个系统的失真情况。,例4-7等概信源，通过信道转移概率矩阵P的信道传输，失真测度为均方失真测度，求平均失真。信道转移概率矩阵为 解:由失真定义得失真矩阵 平均失真,0 1 2,0 1 2,2.N次扩展信源失真 N次无记忆扩展信源失真度（失真函数） N次扩展信源平均失真