.信源编码的基本理论研究与应用摘要关键字前言信息论的理论定义是由当代伟大的数学家美国贝尔实验室杰出的科学家香农在他1948 年的著名论文通信的数学理论所定义的,它为信息论奠定了理论基础。后来其他科学家,如哈特莱、维纳、朗格等人又对信息理论作出了更加深入的探讨。使得信息论到现在形成了一套比较完整的理论体系。信息通过信道传输到信宿的过程即为通信,通信中的基本问题是如何快速、准确地传送信息。要做到既不失真又快速地通信,需要解决两个问题：一是不失真或允许一定的失真条件下,如何提高信息传输速度如何用尽可能少的符号来传送信源信息；二是在信道受到干扰的情况下,如何增加信号的抗干扰能力,同时又使得信息传输率最大如何尽可能地提高信息传输的可靠性。 实际的信源虽然多种多样,但可归纳为图像、语音、文字、数据等。其中图像、语音常表现为时间连续的随机波形,可通过采样变换成随机的时间序列。无论那种类型的信源,信源符号之间总存在相关性和分布的不均匀性,使得信源输出符号序列的统计特性,寻找合适的方法把信源输出符号序列变换为最短的码字序列。 信源编码的基本途径有两个,一是编码后使序列中的各个符号之间尽可能地互相独立,即解除相关性；二是使编码后各个富豪出现的概率尽可能相等,即均匀化分布。 目前去除信源符号之间冗余度的有效方法包括预测编码和变化编码,去除信源符号概率分布冗余度的主要方法是统计码。上述方法已经相当成熟,在实际中得到了广泛应用,并被有关压缩编码的国际标准所采用。1.1 信源编码的基本原理 信源研究内容信息论对信源研究的内容包括3个方面： 信源的建模 信源输出信号的数学描述已有成熟的理论随机过程,一般的随机过程理论并不涉及和讨论信号中所携带的信息,而信息论所关心的中心内容则是信号中携带的信息。 信源输出信号中携带信息的效率的计算 在信息论中,信源输出信号所携带信息的效率是用熵率或冗余度来表示的。 信源输出信息的有效表示 一般地,信源输出信号中携带信息的效率并不很高,如何用适当的信号有效地表示信源输出的信息是人们感兴趣的问题,这就是信源编码的问题。 信源编码器 为了简化问题,研究无失真编码时,只考虑信源和信宿两个主要因素,这样信息传输系统模型变为图1-1所示。 信源译码器信道信宿信源编码器信源图1-1 相关概念设信源U发出n种不同的符号,其符号集为U=u1,u2,un,其中 ui称为信源符号,若信源符号集中符号数等于2称为二元信源,等于3称为三元信源,等于n称为n元信源。 又若信道的输人符号集为X=a1,a2,ar。信源编码问题,就是用信道的输人符号集X=a1,a2,ar作为码符号集,其中aii1,2,r称为码符号或码元,用码符号集中的码符号,对信源U的每一种不同的符号进行一一对应变换,构成由码符号组成的序列,即码字。 所有码字的集合称为码组w=w1,w2,wn；码字中所用的码符号的个数称为码长。 1.1.4 码的类型若码符号集中符号数等于2称为二元码,等于3称为三元码,等于r称为r元码。若一组码中所有码字的码长都相同,称为等长码,否则称为变长码。若码组中所有码字都不相同则称为非奇异码,否则称为奇异码。 符号码1码2码3码4a00001b01101101c100000001d1101110001表1-1信源X对应的不同码字表1-1中码1的编码为等长码,其它的几种编码皆为变长码。码3有两个符号的编码相同,码3是奇异码,而码1、码2和码4都为非奇异码。 若每个码符号的传输时间都相同则称为同价码,否则称为非同价码。 信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应,而且同时还要求信源的N个符号组成的序列所代表的消息,与之相对应的码字组成的码字序列也必须一一对应。只有这样,才能保证任何一个码字或码字序列唯一地翻译成相对应的信源符号或符号序列,达到无失真传递信源发出的消息的目。无失真信源编码必须具有这种单义可译性,单义可译的码称为单义可译码,也称为惟一可译码。 例如码字0,10,11是一种惟一可译码。因为任意一串有限长码序列,例如100 111 000,只能被分割成10,0,11,10,0,0。任何其他分割法都会产生一些非定义的码字。非奇异码中有非惟一可译码和惟一可译码。 惟一可译码中又分为非即时码和即时码；如果接收端收到一个完整的码字后,不能立即译码,还需等下一个码字开始接收后才能判断是否可以译码,这样的码叫做非即时码。 表1-1中码2是非即时码,而码4是即时码。码4中只要收到符号1就表示该码字已完整,可以立即译码。即时码又称为非延长码,若码组中,没有任何完整的码字是其它码字的前缀则称为异前缀码或前缀条件码,表1-1中的码1和码4都是前缀条件码。在惟一可译变长码中,人们需要的是在译码时无需参考后续的码符号就能立即做出判断的一类即时码。 Kraft不等式在数学上表达码字可分离的充要条件,即著名Kraft不等式。 定理1-1 对于n元信源编m元码,其码长分别为l1, l2,ln,则即时码存在的充要条件： 式1-1称克拉夫特Kraft不等式。 式1-1是1949年由L.G.Kraft提出的,所以称克拉夫特Kraft不等式,Kraft不等式指出了即时码的码长必须满足的条件。后来在1956年由麦克米伦B.McMillan证得对于惟一可译码也满足此不等式,1961年卡拉什J.karuSh简化了麦克米伦的证明方法。这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件,而是惟一可译码的码长也必须满足克拉夫特不等式,所以在码长选择的条件上,即时码与惟一可译码是一致的。 惟一可译码判别准则惟一可译码的判断步骤：观察是否是非奇异码,若是奇异码则一定不是惟一可译码；计算是否满足Kraft不等式,若不满足一定不是惟一可译码；将码画成一棵树图,观察是否满足即时码的树图的构造,若满足则是惟一可译码；用Sardinas和Patterson设计的判断方法：计算出码组中所有可能的尾随后缀集合F,观察F中有没有包含任一码字,若无则为惟一可译码；若有则一定不是惟一可译码。 上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是否是惟一可译码的方法,所以可以跳过前三个步骤直接采用该判断法。该准则是萨得纳斯和彼得森于1957年设计出来的. 1.2 无失真信源编码原理变长码的平均码长及编码效率对n元基本离散信源,设编码后各码字的码长分别为l1 ,l2 ,ln,则定义码的平均码长度为 编码的效率为 变长码的特点 1使信道复杂化 2容易产生溢出或取空错误 3差错的扩散 变长信源编码定理 用变长码实现无失真编码时,平均码长越短越好,那么平均码长的极限是多少？下面的定理将回答这个问题。定理1-3一个熵为HU的基本离散无记忆信源U,若用m元码对其进行变长编码,则总可找到一种无失真编码方法,构成惟一可译码,使其平均码长满足 此编码定理给出了最佳变长码的平均码长的上限和下限。定理表明码字的平均长度不能小于极限H/lbm,否则惟一可译码不存在。 实际上,信源U发出的消息,往往不是信源U的单个符号,而是由单个符号组成的序列来表示。倘若信源发出的消息由N个符号组成,则每一条消息都可看作信源U的N次扩展信源的某一个符号 ,因此在构造即时码时,如不把信源U的单个符号作为编码对象,而直接把扩展信源的某一个输出 符号 作为编码对象,使码字与一一对应,能否使信源U每个符号所需要的平均码符号数,即平均码长有所下降?也就是说,能否用扩展信源的手段,达到数据压缩的目的?下面讨论这个问题。定理1-4无失真变长信源编码定理香农第一定理离散无记忆信源U的N次扩展信源UN,其熵为H,用 m元码对信源UN进行编码,总可以找到一种编码方法,构成惟一可译码,使信源U中每个信源符号所需的平均码长满足： 1.3 限失真信源编码原理失真函数及保真度准则 由于只涉及信源编码问题。所以可以将信道编码和译码看成是信道的一部分。这样接收者收到消息后所产生的失真或误差只是由信源编码带来的。从直观感觉可知,若允许失真越大,信息传输率可越小; 若允许失真越小,信息传输率需越大。所以信息传输率与信源编码所引起的失真或误差是有关的。为了定量地描述信息传输率和失真的关系,可以略去广义的无扰信道,所谓广义无扰信道是指,把信道编码、信道、信道译码这三部分看成一个没有任何干扰的广义信道。这样通信系统可简化成如图1-2所示。 信译编码信道信源信源编码广义无扰信道图1-4 简化的通信系统.1基本离散信源失真设离散无记忆信源：信源符号通过信道传输到接收端,则接收端接收量为：对应于一对,定义一个非负函数： 称函数为失真函数或称单个符号失真度。 失真函数 有个,这 个非负的函数可以排成矩阵形式,即： 称为失真矩阵。 失真函数应尽可能符合信宿的主观特性；也就是主观上的失真感觉应与失真函数的值相对应。设x为信源输出信息,y为信宿收到信息,则常用失真函数有：均方失真：绝对失真：相对失真：汉明失真： 因为信源U和信宿接收量V都是随机变量,因此单个符号失真度也是随机变量。那么,现在定义传输一个符号引起的平均失真,即信源平均失真： 式中:信源输出符号,i1,2,n；信宿接收符号；j1,2,m；p广义无扰信道传递概率。 单个符号的失真度描述了某个信源符号通过传输后失真的大小,对于不同的信源符号和不同的接收符号,其值是不同的。但平均失真度已对信源和信道进行了统计平均,所以此值是描述某一信源在某一广义无扰信道或称为试验信道传输下的失真大小,是从总体上描述整个系统的失真情况。.2. N次扩展信源失真N次无记忆扩展信源失真度失真函数 1-