信源编码的基本理论研究与应用

信源编码的基本理论研究与应用

【摘要】 【关键字】

前言

信息论的理论定义是由当代伟大的数学家美国贝尔实验室杰出的科学家香农在他1948 年的著名论文《通信的数学理论》所定义的，它为信息论奠定了理论基础。后来其他科学家，如哈特莱、维纳、朗格等人又对信息理论作出了更加深入的探讨。使得信息论到现在形成了一套比较完整的理论体系。

信息通过信道传输到信宿的过程即为通信，通信中的基本问题是如何快速、准确地传送信息。要做到既不失真又快速地通信，需要解决两个问题：一是不失真或允许一定的失真条件下，如何提高信息传输速度（如何用尽可能少的符号来传送信源信息）；二是在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大（如何尽可能地提高信息传输的可靠性）。

实际的信源虽然多种多样，但可归纳为图像、语音、文字、数据等。其中图像、语音常表现为时间连续的随机波形，可通过采样变换成随机的时间序列。无论那种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源输出符号序列的统计特性，寻找合适的方法把信源输出符号序列变换为最短的码字序列。

信源编码的基本途径有两个，一是编码后使序列中的各个符号之间尽可能地互相独立，即解除相关性；二是使编码后各个富豪出现的概率尽可能相等，即均匀化分布。

目前去除信源符号之间冗余度的有效方法包括预测编码和变化编码，去除信源符号概率分布冗余度的主要方法是统计码。上述方法已经相当成熟，在实际中得到了广泛应用，并被有关压缩编码的国际标准所采用。

1.1 信源编码的基本原理 1.1.1 信源研究内容

信息论对信源研究的内容包括3个方面： (1)信源的建模

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

(2)信源输出信号中携带信息的效率的计算

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

(3)信源输出信息的有效表示

一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地表示信源输出的信息是人们感兴趣的问题，这就是信源编码的问题。 1.1.2 信源编码器

为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，这样信息传输系统模型变为图1-1所示。 信 u

源 u12信源编码器 w2?wnw1a1 a2?ar信 道 信源译码器 信 宿 ?un图1-1

1.1.3 相关概念

设信源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}；码字中所用的码符号的个数称为码长。 1.1.4 码的类型

若码符号集中符号数等于2称为二元码，等于3称为三元码，…，等于r称为r元码。若一组码中所有码字的码长都相同，称为等长码,否则称为变长码。若码组中所有码字都不相同则称为非奇异码，否则称为奇异码。

符号 码1 码2 码3 码4 a b c d 00 01 10 11 0 10 00 01 0 11 00 11 1 01 001 0001 表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元码，其码长分别为l1, l2，…，ln，则即时码存在的充要条件：

n?lim ? ? 1 (1-1)

i?1式（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)用Sardinas和Patterson设计的判断方法：计算出码组中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码。

上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是否

是惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。该准则是萨得纳斯(A．A．Sardinas)和彼得森(G．W．Patterson)于1957年设计出来的.

1.2 无失真信源编码原理

1.2.1变长码的平均码长及编码效率

对n元基本离散信源，设编码后各码字的码长分别为l1 ,l2 ,…，ln,则定义码的平

均码长度为

p ( u )（码符合 (1-2) L ?l / 信源符号）

编码的效率η为

H (U ) (1-3)

m??

L 1.2.3 变长码的特点 1．使信道复杂化

2．容易产生溢出或取空错误 3．差错的扩散 1.2.4 变长信源编码定理

用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？下面的定理将回答这个问题。

定理1-3一个熵为H（U）的基本离散无记忆信源U，若用m元码对其进行变长编码，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足

n?i?1ii? ? ? L 1 (1-4)

lbmlbm

此编码定理给出了最佳变长码的平均码长的上限和下限。定理表明码字的平均长度不能小于极限H(U)/lbm，否则惟一可译码不存在。

实际上，信源U发出的消息，往往不是信源U的单个符号，而是由单个符号组成的序列来表示。倘若信源发出的消息由N个符号组成，则每一条消息都可看作信源U的N次扩展信源的某一个“符号” ，因此在构造即时码时，如不把信源U的单个符号作为编码对象，而直接把扩展信源的某一个输出 “符号” 作为编码对象，使码字与一一对应，能否使信源U每个符号所需要的平均码符号数，即平均码长有所下降?也就是说，能否用扩展信源的手段，达到数据压缩的目的?下面讨论这个问题。

定理1-4无失真变长信源编码定理（香农第一定理）离散无记忆信源U的N次

H(U)H(U)

扩展信源UN，其熵为H(UN)，用 m元码对信源UN进行编码，总可以找到一种编码方法，构成惟一可译码，使信源U中每个信源符号所需的平均码长满足：

H(U)LNH(U)1

??? (1-5)

lbmNlbmN

1.3 限失真信源编码原理 1.3.1失真函数及保真度准则

由于只涉及信源编码问题。所以可以将信道编码和译码看成是信道的一部分。这样接收者收到消息后所产生的失真（或误差）只是由信源编码带来的。从直观感觉可知，若允许失真越大，信息传输率可越小; 若允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真（或误差）是有关的。为了定量地描述信息传输率和失真的关系，可以略去广义的无扰信道，所谓广义无扰信道是指，把信道编码、信道、信道译码这三部分看成一个没有任何干扰的广义信道。这样通信系统可简化成如图1-2所示。 信 源

信 源 编码 U 广义 无扰 信道 V 信 译 编码 信 道 P(V|U)

图1-4 简化的通信系统

1.3.1.1．基本离散信源失真 设离散无记忆信源：

信源符号通过信道传输到接收端，则接收端接收量为：

?V??v1?????P(V)??p(v1)v2p(v2)????p(vm)?vm?U??u1?????P(U)??p(u1)u2p(u2)????p(un)?un

对应于一对(u,v)，定义一个非负函数：

d(ui,vj)?0 (1-6)

i=1,2, ... ,n; j=1,2, ...,m

称(1-6)函数为失真函数（或称单个符号失真度）。

失真函数d(ui,vj) 有n?m个，这 n?m个非负的函数可以排成矩阵形式，即：

) .... d(u,v1n)??d(u1,v1) d(u,v12??d(u2,v1) d(u,v) .... d(u,v)222n? Dij=? (1-7)

?..... ...... .....???d(u,v) d(u,v) .... d(u,v)n1n1nn??称(1-7)为失真矩阵。

失真函数应尽可能符合信宿的主观特性；也就是主观上的失真感觉应与失真函数的值相对应。设x为信源输出信息，y为信宿收到信息，则常用失真函数有： 均方失真：d(x,y)=(x-y)2 绝对失真：d(x,y)=|x-y| 相对失真：d(x,y)=|x-y|/|x|

?0 x=y汉明失真： d(x,y)=??1 x?y

因为信源U和信宿接收量V都是随机变量，因此单个符号失真度也是随机变量。那么，现在定义传输一个符号引起的平均失真，即信源平均失真：

nmijiij (1-8) D?p(u)p(vu)d(u,v) 式中:

ui —信源输出符号，i＝1，2，…，n；vi—信宿接收符号；j＝1,2,…，m； i?1j?1??p(vj|ui)—广义无扰信道传递概率。

单个符号的失真度描述了某个信源符号通过传输后失真的大小，对于不同的信源符号和不同的接收符号，其值是不同的。但平均失真度已对信源和信道进行了统计平均，所以此值是描述某一信源在某一广义无扰信道（或称为试验信道）传输下的失真大小，是从总体上描述整个系统的失真情况。 1.3.1.2. N次扩展信源失真

N次无记忆扩展信源失真度（失真函数）

Nd(S,Y)??d(sl,yl) (1-9)

N次扩展信源平均失真度：

l?1D(N)?E[d(S,Y)]?

?S,Yp(S,Y)d(S,Y)??S,Yp(S)?p(YS)?d(S,Y) (1-10) 若平均失真度不大于所允许的失真D，即：

（1-11）

称式（1-11）为保真度准则。

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

(1-12) D?DD(N)?ND

1.3.2信息率失真函数

在满足保真度准则下，寻找信源必须传输给信宿的信息率R的下限值。从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息I(U；V)来表示，这就变成了在满足保真度准则的条件下,寻找平均互信息I(U；V)的最小值。这个最小值就是在满足保真度准则条件下，信源必须传输的最小平均信息量。即： （1-13） _

p(vj|ui)?BDR(D)=min{I(U;V)}称（1-13）式 R(D)为信息率失真函数（或率失真函数），R(D)单位同互信息量单位相同。

N次扩展信源的信息率失真函数RN(D)：

p(Y|S)?BND_ （1-14）

RN(D)=min{I(S;Y)}

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

1．R(D)的定义域 (Dmin,Dmax) (1)Dmin和 R(Dmin)

一般，当给定信源[U,P]及失真矩阵，信源的最小平均失真度为平均失真最小值：

??p(ui)p(vjui)d(ui,vj)? Dmin?min? ?? （1-15）

n?m?

p(ui)min?p(vjui)d(ui,vj)? ?i?1?j?1?

选择这样的试验信道，当i=1，2，…，r时，它满足

??p(vjui)?1所有d（ui，vj）?最小值的vj?V?v （1-16） ?j ?（d（ui，vj）?最小值的vj?Vpvu）?0ji ?则可得信源的最小平均失真度为

n （1-17）

Dmin??p(u)mind(u,v)??p(ui)mind(ui,vj) VjUi?1

允许失真度D是否能达到零，这与单个符号的失真函数有关，只有当失真矩阵中每行至少有一个零元素时，信源的平均失真度才能达到零值。否则，信源的最小

????平均失真度不等于零值。在实际情况中，一般 Dmin=0。另外，假如 Dmin?0 时，可以适当改变单个符号的失真度，使Dmin=0 。而对信息率失真函数来说，它只是起了坐标平移作用。所以，可以假设 Dmin=0而不失其普遍性。 这时

R(0)?H(U)R(Dmax)Dmax和 (2)

根据信息率失真函数R（D）的定义，R(D)函数是在保真度准则下，平均交互信息量的最小值。因为平均交互信息量是非负的，其最小恒等于零。所以，把能使平均交互信息量为零的最小平均失真度定义为最大允许失真度。

当平均交互信息量为零时，信道的输入随机变量U和输出随机变量V之间一

p(vjui)?p(vj)(i?1,2,...,n;j?1,2,...,m)。由信源平均失定统计独立，即有 真度公式(1-8)式可知，这时平均失真度的最小值

?nm? Dmin?min???p(ui)p(vjui)d(ui,vj)?p(vu) ?i?1j?1? ?nm? ?min???p(ui)p(vj)d(ui,vj)? （1-18）

p(v)?i?1j?1?

n ?m? ?minp(v)p(u)d(u,v)??j?iij? p(v)i?1?j?1? n?p(ui)d(ui,vj)取最小值 时, 显然一定能使平均失真度(1-17)式 若 i?1

得到最小值，这样可以得到最大允许失真度

?n? (1-9)

?in?min??p(ui)d(ui,vj)?Dmax?Dmj ?i?1?

根据最大允许失真度 的定义和(1-19)式可知，在信源U给

jijj定，失真矩阵规定的前提下，若允许失真度选择为最大允许失真 度,则满足保真度准则的试验信道必须同时满足

p(vu)?p(v) i?1,2,...,n;j?1,2,...,mjij

n

p(vj)?1 p(ui)d(ui,vj) (j?1,2,...,m)取最小值

i?1 n p(vj)?0 p(ui)d(ui,vj) (j?1,2,...,m)不取最小值 i?1这时的信源U的信息率失真函数

?in)?0R(Dmax)?R(Dm

??应用

二元等概离散无记忆信源，信道矩阵为

?31??4 4?P=?? ?1 2???33??

失真测度为汉明失真测度，求:平均失真及2次扩展信源的单个符号平均失真? 解:由式（1-8）可计算得

nm 7D???p(ui)p(vjui)d(ui,vj)? 24i?1j?1

二维扩展信源概率分布

?u1u1u1u2u2u1u2u2? ?U2???? 1111??2?P(U)??? ?4444?二次扩展信道矩阵 v1v1v1v2v2v1v2v2

9331 u1u116161616

3612uu P?1212121212

3162 u2u1 12121212 1224uu 229999

由此得二次扩展信源失真矩阵，将其除2得单个符号失真矩阵为

v1v1v1v2v2v1v2v2 u1u100.50.51

D2(S,Y)?u1u20.5010.5

u2u10.5100.5

u2u210.50.50

由（1-8）式得二次扩展信源平均失真

7 D(2)??p(S)?p(YS)?d(S,Y)?24S,Y

删除信源U取值于 ?0,1?，V取值于 0,1,2，而失真矩阵为

??

1??0 1 ?2?Dij=??

?1 0 1 ????2?求：Dmin及其对应的信道。

解：由式1-17)可知最小允许失真度为

nn Dmin??p(ui)mind(ui,vj)??p(ui)?0?0ji?1i?1

由式（1-16）得满足最小允许失真度的试验信道是一个无噪无损的试验信道，信道矩阵为

?1 0 0?P=??

0 1 0??DD?Dmin?0，则 可以看出，若取允许失真度 集合中只有这个信道是惟一可

B取的实验信道、也就是无失真一一对应的编码。

设二元离散信源

12?U??P(U??0???)???1??1???Dmax及对应的信道。 其中 ??，规定失真函数为汉明失真度时，求

解： 由（1-18）式得最大允许失真度

Dmax?min???0?(1??)?1;??1?(1??)?0??

jmin?(1??);????,j?2j由此式得此时的试验信道的信道矩阵：

?0 1?P???0 1???inDmax?Dm?n??min??p(ui)d(ui,vj)?j?i?1?

本文来源：https://www.bwwdw.com/article/1u5p.html