信源编码的基本理论研究报告及应用

信源编码的根本理论研究与应用【摘要】、广 、.前言信息论的理论定义是由当代伟大的数学家美国贝尔实验室出色的科学家香农在他 1948 年的著名论文?通信的数学理论?所定义的，它为信息论奠定了理论根底。后来其他科学家，如哈特莱、维纳、朗格等人又对信息理论作出了更加深入的探讨。使得信息论到现在形成了一套比拟完整的理论体系 。信息通过信道传输到信宿的过程即为通信， 通信中的根本问题是如何快速、 准确地传送信息。 要做到既不失真又快速地通信， 需要解决两个问题： 一是不失真或允许一定的失真条件下， 如何提高信息传输速度 如何用尽可能少的符号来传送信源信息 ；二是在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大如何尽可能地提高信息传输的可靠性 。实际的信源虽然多种多样，但可归纳为图像、语音、文字、数据等。其中图像、 语音常表现为时间连续的随机波形， 可通过采样变换成随机的时间序列。 无论那种类型的信源， 信源符号之间总存在相关性和分布的不均匀性， 使得信源输出符号序列的统计特性， 寻找适宜的方法把信源输出符号序列变换为最短的码字序列。信源编码的根本途径有两个， 一是编码后使序列中的各个符号之间尽可能地互相独立， 即解除相关性； 二是使编码后各个富豪出现的概率尽可能相等， 即均匀化分布。目前去除信源符号之间冗余度的有效方法包括预测编码和变化编码， 去除信源符号概率分布冗余度的主要方法是统计码。 上述方法已经相当成熟， 在实际中得到了广泛应用，并被有关压缩编码的国际标准所采用。1.1 信源编码的根本原理1.1.1 信源研究容信息论对信源研究的容包括3个方面：(1)信源的建模信源输出信号的数学描述已有成熟的理论一一随机过程，一般的随机过 程理论并不涉及和讨论信号中所携带的信息，而信息论所关心的中心容那么 是信号中携带的信息。(2清源输出信号中携带信息的效率的计算在信息论中，信源输出信号所携带信息的效率是用嫡率或冗余度来表示的。(3清源输出信息的有效表示一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地表示信源输出的信息是人们感兴趣的问题，这就是信源编码的问题。1.1.2 信源编码器为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，这样信息传输系统模型变为图1-1所示。信源U1U2r信 源 编 码 器w1a1w2a2-信道.It，信 源 译 码 器1信宿iun: :wnar1.图1-11.1.3 相关概念 设信源U发出n种不同的符号，其符号集为 U=u1,u2,un,其中ui称为信源符号，假设信源符号集中符号数等于2称为二元信源，等于3称为三元信源，等于n称为n元信源。又假设信道的输人符号集为X=a1,a2,ar。信源编码问题，就是用信道的输人 符号集X=a1,a2,ar作为码符号集，其中aii=1, 2,，门称为码符号或码元，用码符号集中的码符号，对信源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 都是前缀条件码。在惟一可译变长码中，人们需要的是在译码时无需参考后续的码符号就能立即做出判断的一类即时码。1.1.5 Kraft 不等式在数学上表达码字可别离的充要条件，即著名 Kraft 不等式。定理1-1对于n元信源编m元码，其码长分别为11,12,ln,那么即时码存在的充要条件：n(1-1) m1i1i1式1-1称克拉夫特Kraft 不等式。式1-1是1949年由L.G.Kraft提出的，所以称克拉夫特Kraft不等式，Kraft 不等式指出了即时码的码长必须满足的条件。后来在1956 年由麦克米伦B.McMillan证得对于惟一可译码也满足此不等式，1961年卡拉什J.karuSh)简化了麦克米伦的证明方法。 这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件， 而是惟一可译码的码长也必须满足克拉夫特不等式， 所以在码长选择的条件上，即时码与惟一可译码是一致的。1.1.6 惟一可译码判别准那么惟一可译码的判断步骤：(1)观察是否是非奇异码，假设是奇异码那么一定不是惟一可译码；(2)计算是否满足Kraft 不等式，假设不满足一定不是惟一可译码；(3)将码画成一棵树图，观察是否满足即时码的树图的构造， 假设满足那么是惟一可译码；(4)用Sardina矫口 Patterson设计的判断方法：计算出码组中所有可能的尾随后缀集 合F,观察F中有没有包含任一码字，假设无那么为惟一可译码；假设有那么一 定不是惟一可译码。上述判断步骤中Sardina手口 Patterson设计的判断方法是能确切地判断出是否是 惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。该准那么是萨得纳斯(A. A. Sardinas)口彼得森(G. W. Patterson方1957年设计出来的.1.2 无失真信源编码原理1.2.1 变长码的平均码长及编码效率对n元根本离散信源，设编码后各码字的码长分别为l1 ,l2，ln,那么定义码的平均码长度为nLp(ui)li(码符合/信源符号)(1-2)i 1编码的效率讷(1-3)Hm(U)1.2.3 变长码的特点1 .使信道复杂化2 .容易产生溢出或取空错误3 .过失的扩散1.2.4变长信源编码定理用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？ 下面的定理将答复这个问题。定理1-3 一个嫡为HU的根本离散无记忆信源U,假设用m元码对其进展变 长编码，那么总可找到一种无失真编码方法， 构成惟一可译码，使其平均码长满 足H(U) L HUJ 1lbmlbm(1-4)此编码定理给出了最正确变长码的平均码长的上限和下限。定理说明码字的平均长度不能小于极限H(U)/lbm,否那么惟一可译码不存在。实际上，信源U发出的消息，往往不是信源 U的单个符号，而是由单个符号 组成的序列来表示。倘假设信源发出的消息由N个符号组成，那么每一条消息都可看作信源U的N次扩展信源的某一个“符号，因此在构造即时码时，如 不把信源U的单个符号作为编码对象，而直接把扩展信源的某一个输出“符号作为编码对象，使码字与一一对应，能否使信源 U每个符号所需要的平均 码符号数，即平均码长有所下降 他就是说，能否用扩展信源的手段，到达数据 压缩的目的正面讨论这个问题。定理1-4无失真变长信源编码定理香农第一定理离散无记忆信源U的N次扩展信源UN,其嫡为H(UN),用m元码对信源UN进展编码，总可以找到一 种编码方法，构成惟一可译码，使信源 U中每个信源符号所需的平均码长满足：H(U) Ln H(U) 1lbm N 1bm5) N1.3限失真信源编码原理1.3.1失真函数及保真度准那么由于只涉及信源编码问题。所以可以将信道编码和译码看成是信道的一 局部。这样接收者收到消息后所产生的失真或误差只是由信源编码带来的。 从直观感觉可知，假设允许失真越大，信息传输率可越小；假设允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真 或误差是有关 的。为了定量地描述信息传输率和失真的关系，可以略去广义的无扰信道，所谓 广义无扰信道是指，把信道编码、信道、信道译码这三局部看成一个没有任何干 扰的广义信道。这样通信系统可简化成如图1-2所示。P(V|U)图1-4简化的通信系统1.3.1.1.根本离散信源失真设离散无记忆信源：Uu1u2 unP(U) p(Ui)p(U2)p(un)信源符号通过信道传输到接收端，那么接收端接收量为:VVlV2VmP(V)P(Vl) P(V2)P(Vm)对应于一对(u,v),定义一个非负函数:(1-6)d(U,Vj) 0i=1,2, . ,n; j=1,2,m称(1-6而数为失真函数或称单个符号失真度。失真函数d(u i ,v j)有n m个，这n m个非负的函数可以排成矩阵形式，即:d(u1,v1)d(u1,V2) . d(u1,Vn)d(u2,v1) d(u2,2) . d(u2,Vn) _Dj =(1-7)d(Un,V1) d(Un,V). d(u n,Vn)称(1-7历失真矩阵。失真函数应尽可能符合信宿的主观特性；也就是主观上的失真感觉应与失真函数的值相对应。设x为信源输出信息，y为信宿收到信息，那么常用失真函数有:均方失真：d (x,y)=(x-y) 2绝对失真：d(x,y)=|x-y|相对失真:d (x,y)=|x-y|/|x|汉明失真d(x,y)=0 x=y1 x y因为信源U和信宿接收量V都是随机变量，因此单个符号失真度也是随机变量。那么，现在定义传输一个符号引起的平均失真，即 信源平均失真：_ n mDP(Ui)P(Vj Ui)d(Ui，Vj)(1-8)1 1 j 1式中：Ui信源输出符号，i=1, 2,，n； Vi一信宿接收符号；j = 1,2，m； p(vj| ui)广义无扰信道传递概率。单个符号的失真度描述了某个信源符号通过传输后失真的大小，对于不同的信源符号和不同的接收符号，其值是不同的。但平均失真度已对信源和信道进展 了统计平均，所以此值是描述某一信源在某一广义无扰信道或称为试验信道 传输下的失真大小，是从总体上描述整个系统的失真情况。1.2.2.2. N次扩展信源失真N次无记忆扩展信源失真度失真函数Nd(S,Y)d(Sl,y。(1-9)l 1N次扩展信源平均失真度：D(N) Ed(S,Y)S,Yp(S,Y)d(S,Y)S,Yp(S) P(Y S) d(S,Y)(1-10)假设平均失真度不大于所允许的失真 D,即:1-11称式1-11为保真度准那么。N次扩展信源的保真度准那么是平均失真度不大于允许失真ND,即:(1-12) D ( N ) ND1.3.2 信息率失真函数在满足保真度准那么下，寻找信源必须传输给信宿的信息率R的下限值。从接收端来看，就是在满足保真度准那么下，寻找再现信源消息所必须获得的 最低平均信息量。而接收端获得的平均信息量可用平均互信息 I (U; V)来表示, 这就变成了在满足保真度准那么的条件下，寻找平均互信息I(U； V)的最小值。 这个最小值就是在满足保真度准那么条件下，信源必须传输的最小平均信息 量。即：1-13R(D户 min I(U;V)p(Vj |Ui ) Bd称1-13式R(D)为信息率失真函数或率失真函数,R(D)单位同互信息 量单位一样。N次扩展信源的信息率失真函数 Rn (D):RN1(D)= min I(S;Y)p(Y|SBnd1.3.3 信息率失真函数定义域及，隹质1. R(D)的定义域(Dmin,Dmax)(1)Dmin 和 R(DmC一般，当给定信源U,P段失真矩阵，信源的最小平均失真度为平均失真 最小值：Dminminp(5)p(Vj Ui)d(Ui,Vj)nmp(Ui)min p(Vj Ui)d(Ui,Vj)i 1j 11-15选择这样的试验信道，当i=1, 2,，r时，它满足p(vj ui) 1所有dui, v)最小值的Vj VVj1 jjp( vj ui) 0 d (Ui，Vj)最小俏的 Vj V1-16那么可得信源的最小平均失真度为nDminp(u) mjn d(u,v)p(ui) min d (ui, vj)1-17Ui 1j允许失真度D是否能到达零，这与单个符号的失真函数有关，只有当失真矩阵 中每行至少有一个零元素时，信源的平均失真度才能到达零值。 否那么，信源的 最小平均失真度不等于零值。在实际情况中，一般Dmin =0。另外，假设Dmin 0 时，可以适当改变单个符号的失真度，使Dmin=0。而对信息率失真函数来说，它只是起了坐标平移作用。所以，可以假设 Dmin=0而不失其普遍性。这时R(0) H(U)DmaX口 R( Dmax)根据信息率失真函数 RD的定义，R(D)函数是在保真度准那么下，平均 交互信息量的最小值。因为平均交互信息量是非负的，具最小包等于零。所以， 把能使平均交互信息量为零的最小平均失真度定义为最大允许失真度。当平均交互信息量为零时，信道的输入随机变量U和输出随机变量V之间一定统计独立，即有p(Vj；U)p(Vj)(i由佃原做大周度公加)(1-8)式可知，这时平均失真度的最小值 n mDminmlin、p(Ui)p(Vj . Ui)d(Ui ,Vj)P(vj Ui) i 1 j 1jmin P(Vj)minP(Vj )n m p(Ui)p(Vj)d(Ui,Vj) i 1 j 1 mnP(Vj)p(Ui)d(Ui,Vj)j 1i 11-18np(Ui)d(Ui，Vj)i 1假设取最小值 时，显然一定能使平均失真度(1-17成得到最小值，这样可以得到最大允许失真度nDmaxDminminp(Ui)d(Ui,Vj)(1-9)j i 1根据最大允许失真度 的定义和(1-19成可知，在信源U给定，失真矩阵规定的前提下，假设允许失真度选择为最大允许失真度,那么满足保真度准那么的试验信道必须同时满足p(Vj Ui) p(Vj) i 1,2,n;j 1,2,., m np(Vj) 1p(Ui)d(Ui,Vj) (j 1,2，,m)取最小俏i 1 np(Vj) 0p(Ui)d(Ui,Vj) (j 1,2，,m)不取最小俏i 1这时的信源U的信息率失真函数RDR( Dmin ) 0应用二元等概离散无记忆信源，信道矩阵为3 14 4P= 4 41 23 3失真测度为汉明失真测度，求：平均失真及2次扩展信源的单个符号平均失真？解:由式1-8可计算得p(Ui)p(Vj Ui)d(u,Vj)724UiUiU1U21144U2U1U2U21144二维扩展信源概率分布9U2P(U2)二次扩展信道矩阵V1V2 V2V13316166112121612122299v2v212122124由此得二次扩展信源失真矩阵，将其除 2得单个符号失真矩阵为v1v1V1V2v2v1 v2v2U1U100.50.5D2(S,Y) U1U20.501u2u10.510U2U210.50.510.50.50由1-8式得二次扩展信源平均失真D(2)p(S) p(Y S) d(S,Y)S,Y7240,10,1,2删除信源u取值于，v取值于,而失真矩阵为0 1D ij =101212求：Dm.及其对应的信道 解：由式1-17X知最小允许失真度为minp(Ui)min d(Ui,vj)p(Ui)?0由式1-16得满足最小允许失真度的试验信道是一个无噪无损的试验信道，信道矩阵为1 0 0 P=0 1 0可以看出，假设取允许失真度D Dmin 0 ，月融集合中只有这个信道是惟一可取的实验信道、也就是无失真对应的编码。设二元离散信源U 01P(U) 11 一 ,一一r 其中 一，规定失真函数为汉明失真度时，求Dmax及对应的信道。2解：由1-18式得最大允许失真度Dmax min ?0 (1)?1; ?1 (1)?0 mjn (1)； ,j 2jj由此式得此时的试验信道的信道矩阵：0 1 P0 1_nDmax DminminP(Ui)d(ui,Vj)j i 1