信息论与编码(第四版)课件 第4章 离散信源编码理论_第1页
信息论与编码(第四版)课件 第4章 离散信源编码理论_第2页
信息论与编码(第四版)课件 第4章 离散信源编码理论_第3页
信息论与编码(第四版)课件 第4章 离散信源编码理论_第4页
信息论与编码(第四版)课件 第4章 离散信源编码理论_第5页
已阅读5页,还剩140页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第4章

离散信源

编码理论主要内容4.1信源编码概述4.2渐近等同分割性4.3无失真信源编码4.4信息率失真函数及性质4.5信息率失真函数的参量计算4.6信息率失真函数的迭代算法4.7香农第三定理离散信源编码理论

通信本质是信息的传输,即将信源输出的符号序列经过信道传送到信宿,在信宿精确或者近似重现信源发送的信息。需要解决以下两个问题:

信源的输出如何描述,即如何计算信源产生的信息量;

如何表示信源的输出,即信源编码问题。

上述两个问题都与新宿对通信质量的要求有关,如果要求精确地重现信源的输出,信源产生的信息全部无损传送到信宿,则要求对信源进行无失真编码;如果不要求在信宿精确重现信源的输出,允许信息传输过程中出现一定失真,这就是限失真编码问题。

通信系统的信道容量是有限的,根据第

3

章中信源与信道匹配理论,为了有效传输信息,信道的输入分布应当尽可能接近信道要求的最佳分布。

实际信道很多都是对称信道,最佳分布为等概率分布,这就要求对信源进行编码,去除信源输出符号序列之间的相关性,从而实现信道输入与信道的匹配。离散信源编码理论主要内容4.1

信源编码概述4.2渐近等同分割性4.3无失真信源编码4.4信息率失真函数及性质4.5信息率失真函数的参量计算4.6信息率失真函数的迭代算法4.7香农第三定理4.1

信源编码概述

信源编码的实质是对信源输出符号进行描述,将原始符号按照一定的规则进行变换,以满足信息传输的要求。图4.1信源编码器的一般模型

信源编码时首先将信源的消息符号划分成符号序列,用

xi表示,假设信源序列符号长度为

N,则

信源编码就是将信源输出序列

xi按照一定的变换规则映射为一个码字

yi,这样产生的码称为分组码或者块码。4.1

信源编码概述

码字

yi取值于一个码字集合,称为码集,记作

,r为信源符号数

。每个码字

Ci

是由若干个来自于同一个码符号集合的符号构成的,如果码符号集合为

,则称这样构成的码为

d

元码。码字

Ci

的符号数量称为码字长度,记作

li,i=1,2,……,r。例4.1

左表为信源编码所使用的码表,信源输出序列的长度为

N=1,信源共有4个符号,对应的概率空间为:

信源符号符号概率码表码1码2a1p(a1)000a2p(a2)0110a3p(a3)10110a4p(a4)111114.1

信源编码概述信源符号符号概率码表码1码2a1p(a1)000a2p(a2)0110a3p(a3)10110a4p(a4)11111对于码1:

信源编码器输出共有4个码字,分别为00、01、10和11,码字的长度都为2,即

li

=2,i=1,2,3,4。每个码字都是由取值于码符号集合{0,1}的两位二元码组成的,即码符号的数量为2,即

d=2,称这样的码为二元码。且该码字具有相同的长度,这样的码为等长码。

码2的码字同样是由二进制码符号组成,与码1不同的是,并非所有的码字都具有相同的码字长度,所以称这种码为变长码。4.1

信源编码概述唯一可译码

如果信源编码器输入的每个元素映射为不同的码字,即则称该码为非奇异码。奇异码

如果存在信源编码器的不同输入序列的元素映射为相同的码字,即则称该码为奇异码。4.1

信源编码概述非奇异码

如果任意有限长的码符号序列,只能被唯一地译码为所对应的信源符号序列,这样的码称为唯一可译码,即编码的码字只有一种可能信源序列与之相对应,这就要求码是非奇异的。

假设对例4.1给定的四个信源符号进行如下的不等长编码:则该码就是非唯一可译码。如给定码序列001,就存在两种解释,即0,01和001,相应的译码就有两种,即a1a2或者a3,因此这种编码就不是唯一可译码的。4.1

信源编码概述即时码

译码时如果不需要考虑后续的码符号,就可以直接根据当前的码符号序列正确地译出相应的码字,则称该码为即时码。

即时码的充要条件是没有一个码字是其它码字的前缀,所以即时码是唯一可译码;反之,唯一可译码不一定是即时码,有时可以通过搜遍整个码符号序列自后至前进行译码。4.1

信源编码概述

对某一信源进行了如下4种方式编码,判断产生的码字为奇异码、非奇异码、唯一可译码还是即时码?奇异码非奇异码非唯一可译码奇异码唯一可译码即时码奇异码唯一可译码非即时码4.1

信源编码概述码树

通常情况下可用码树来表示各个码字的构成,如果码序列符号为

d

进制的,可以使用

d

个符号的码树来构造码字。

每个码树有一个树根,树根有

d

个树枝,树枝的尽头称为节点,每个节点生出的树枝数量等于码符号数量

d

,形成

d

进制码树。当某个节点被安排为一个码字后,不再继续生出树枝,该节点称为终端节点。每个树枝分别标上码符号,终端节点对应的码字就是从根节点出发到终端节点经过的路径所对应的码符号按顺序排列而成。

二进制码树4.1

信源编码概述定理4.1

采用

d

进制符号集进行信源编码,产生的码字

Ci

所对应的长度为

li

,则即时码存在的充分必要条件为

该不等式就是克劳夫特不等式(KraftInequality)。主要内容4.1信源编码概述4.2渐近等同分割性4.3无失真信源编码4.4信息率失真函数及性质4.5信息率失真函数的参量计算4.6信息率失真函数的迭代算法4.7香农第三定理4.2渐近等同分割性自信息量的算术平均逼近熵算术平均以概率逼近统计平均

典型序列是渐近等同分割性中的概念,是信源编码(等长编码)的理论基础。渐近等同分割性是由大数定律得到的。大数定律:对于独立同一分布(i.i.d,independentidenticallydistributed)的随机变量

X

和充分大的

N

,

逼近其数学期望EX。渐进等同分割性:当

X1,X2,…,XN服从独立同一分布的随机变量

X,且

,则

逼近熵

H(X),其中

表示观察序列的概率,所观察序列的概率逼近

。4.2渐近等同分割性

将所有序列分为两个集合:典型集合:样点值熵逼近真正熵;非典型集合:包含剩余序列。

主要关心典型序列,典型序列的任何特性都是以大概率成立的,而且决定了样点值的主要特性。4.2渐近等同分割性例4.2

随机变量X∈{0,1}的概率密度空间为

,如果随机变量序列

X1,X2,…,XN

都服从独立同一分布,那么序列

的概率为

,如序列(1,0,1,1,0,1)的概率为

。长度为

N的序列共有2N

种可能取值,显然,不可能所有2N

种序列对应的概率都是相同的。

在该例子中,

,当

N足够大时,序列中“0”的数量以大概率逼近于

Np

,而所有这列序列都大致有相同概率2-NH(p)。4.2渐近等同分割性定理4.2

如果

X1,X2,…,XN

服从独立同一分布

p(x),且

,那么

以概率逼近

H(X)。证明:由于独立随机变量的函数也是独立随机变量,且

X1,X2,…,Xi,i∈1,2,…,N服从独立同一分布

p(x),所以logp(xi)

也服从同一分布。根据弱大数定律可得:以概率4.2渐近等同分割性含义:对于给定的基本信源和参数

ε,对于一个具体排列(样本),满足上述关系,则属于典型序列的一个元素;所有这类元素构成典型集合。定义4.1

关于

p(x)的典型集合

是序列

的集合,具有下列性质:例如:一个二元信源,p(0)=0.75,p(1)=0.25,则H(x)=0.811bit/符号,取ε=0.111,N=100,则

100个元素都是0的序列,对应的联合概率为0.75100=3.21×10-13,那么该序列就不是典型序列;80个元素都是0的序列,对应的联合概率为0.7580×0.2520=9.2×10-23,那么该序列就是典型序列。4.2渐近等同分割性

所以典型序列的概率几乎为1,典型序列的所有元素几乎是等概率的,元素个数几乎是

2NH(X)。定理4.3

如果

,那么

。当

N充分大时,

。

,其中|A|表示集合A的元素个数。当

N充分大时,

。

4.2渐近等同分割性定理4.3证明:

性质(1)可以根据定义4.1两边直接取对数,得:性质(2)可以由定理4.2加以证明:当

,典型序列集合以概率逼近1,根据大数定理可得:令

,即证明了该性质。4.2渐近等同分割性性质(3)证明:性质(4)证明:对于充分大的

N,

,所以故4.2渐近等同分割性定理4.4

设离散无记忆信源

X输出一个长度为

N

的特定序列

,对于任意给定的

,存在一个整数

N0,当

N≥N0时,有典型序列的平均自信息量以概率逼近熵4.2渐近等同分割性

令

X1,

X2,

…,

XN

是服从独立同一分布的随机变量

,概率密度函数为

p(x),对于这样的随机变量序列

X,希望以更短长度加以描述,实现数据压缩。

首先将随机变量序列

X

分为两个集合,典型集合

及其补集。每个集合都按照某种顺序对数据进行排序,这样就可以使用序列排序的序号来描述每个序列。4.2渐近等同分割性

前缀码

根据典型序列的性质可知,

中所有序列的数量不大于2N(H(X)+ε),所以使用不多于

N(H(X)+ε)+1比特就可以对序列进行编号,对于典型序列在前面加上前缀0,这样就可以使用长度为

N(H(X)+ε)+2比特的序列描述所有的序列。

同理,可对非典型序列中的每个序列进行变换,序号长度不超过

Nlog|X|+1比特,其中|X|表示信源符号个数,并在非典型序列在前面加上前缀1。

这样,序列集合中所有的序列都有唯一的序号与之对应。4.2渐近等同分割性上述的前缀码编码方案具有下列性质:码与序列之间是一一对应的,第一位是前缀码,表示码的长度或者类型。非典型序列采用的是枚举法,尽管没有考虑非典型序列的长度一定小于信源符号的个数,但是这种描述方法也是十分有效的,因为非典型序列对应的概率较小,对平均长度的贡献较小。典型序列的最小描述长度约为

NH(X)。

4.2渐近等同分割性

非典型序列不参与编码

对所有的典型序列进行编码,非典型序列不参与编码直接丢弃,使得对应的序列编码码长会减小,序列的平均码长不大于

N(H(X)+ε)+1比特。但可能会导致译码错误,一旦非典型序列出现,译码错误就会出现。

由于非典型序列对应概率很小,译码的错误也就很小,几乎可以无失真编码,译码错误概率等于非典型序列集合的概率。4.2渐近等同分割性

非典型序列使用典型序列代替

对所有的典型序列正常编码,一旦非典型序列出现,则找到一个合适的典型序列替代非典型序列并进行编码。但这种编码方法同样出现译码错误,如果替代序列选择较好的话,相较于“非典型序列不参与编码”的译码错误概率会降低,但不可能做到无失真编码,也是只能做到几乎无失真编码。主要内容4.1信源编码概述4.2渐近等同分割性4.3无失真信源编码4.4信息率失真函数及性质4.5信息率失真函数的参量计算4.6信息率失真函数的迭代算法4.7香农第三定理4.3无失真信源编码

根据信源编码输出码长的特点,可以将信源编码分为等长编码和变长编码。如果对于信源不同的输出符号,码字的长度总是相同的,这样的编码称为等长编码,即:反之,如果编码产生的码长不完全相同,称这样的码为变长码。

无失真信源编码就是要求信源符号与编码输出的码字之间形成一一映射关系,且编码输出的码字序列对应的反变换是唯一的,即是唯一可译码的,否则会造成译码错误或者失真。定理4.5

设离散无记忆信源

X

的符号数量为

r,信源熵为

H(X),对应

N

次扩展信源

为

。现在使用码符号个数为

d的

码符号集合,对

N

次扩展信源进行等长编码,码长为

l,对于任意

ε>0,只要满足

,则当

N

足够大时,错误译码的概率为任意小,即可实现几乎无失真编码。反之,如果

,则当

N

充分大时,译码错误的概率趋向1,不可能实现无失真编码。4.3无失真信源编码——等长码证明:根据渐近等分割定理可知,在离散无记忆信源输出中,典型序列对应的概率应当满足条件设典型序列集合

G中序列数量为

NG,于是有4.3无失真信源编码——等长码

当

N

足够大时,典型序列的数量所占比例很小,这样就可以只对典型序列进行一一对应的等长编码,那么码字的总数应当不小于

NG,即

4.3无失真信源编码——等长码

当选取等长码的长度满足上述要求时,典型序列集合中所有的序列都有不同的码字与之相对应,而非典型序列没有相应的码字。4.3无失真信源编码——等长码

尽管非典型序列出现的概率很小,但是仍然有可能出现,一旦非典型序列出现,就会造成译码错误,相应的错误概率就是非典型序列集合

GC的概率,即所以如果等长码的码长满足当

N

趋向无穷大时,译码错误的概率

PE趋向于0。

4.3无失真信源编码——等长码将序列的概率上限和

代入,可得:

由于典型序列中只有

dl

个序列存在一一对应的码字,译码时不会产生错误,而其他没有对应码字的序列在译码时一定会出现错误,所以正确译码的概率为:当

时,错误译码的概率

。4.3无失真信源编码——等长码反之,如果等长码的码长满足即此时典型序列的数量小于下界

,典型序列集合中将有一些序列没有一一对应的码字。将典型序列中存在一一对应的码字的序列的概率之后记作

Pt,应当满足4.3无失真信源编码——等长码

定理4.5可以扩展到平稳离散有记忆信源,但是要求有记忆信源的极限熵存在,并将上述定理中的替换为极限熵。定理4.5的意义在于:对于给定的离散无记忆信源

X

和码符号集合

D,如果对

X

的

N

次扩展信源进行无失真等长编码,那么当扩展信源编码的码长

l

满足下列条件

时,一定存在某种编码方案,使得正确译码的错误概率趋向0,即能够实现无失真编码;反之,如果上述不等式不成立,不可能存在一种编码方案,能使得正确译码的概率趋向0,也就是说,不可能进行无失真编码。4.3无失真信源编码——等长码对于给定的离散无记忆信源

X,信源的熵

H(X)是一定的,当码符号数量

d

选定时,可以增加信源序列的长度

N,使得无失真编码产生的每个符号平均长度

尽可能小,但是无论怎样增加序列长度

N,信源每个符号的平均码长

不可能小于

,即平均码长的极限为

。当序列长度

N

一定,译码错误概率

PE

为

其中,

为自信息量的方差。4.3无失真信源编码——等长码定义4.2

设离散无记忆信源

X

的熵为

H(X),对其

N

次扩展信源的符号序列

XN进行等长无失真编码,码长为

l,定义为编码信息率。每个符号的平均码长

结合定理4.5可知,如果编码信息率

,则总是存在某种编码方法,能够实现无失真编码;反之,则不能够实现无失真编码。4.3无失真信源编码——等长码定义4.3

定义信源熵与编码信息率之比为编码效率

η,即

已知自信息量方差和编码效率情况下,信源序列长度

N与最佳编码效率

η

和允许错误概率

δ

之间的关系为:允许错误概率越小,编码效率越高,信源序列的长度就越大。4.3无失真信源编码——等长码例4.3

设某离散无记忆信源的熵为

H(X)=0.6bit/符号,采用二元码编码,分别使用长度为10和100的序列进行等长无失真编码,分别计算最短平均码长和编码效率。

解:当

N=10时,考虑到码长必须为整数,所以最短码长为,此时最短平均码长为:编码效率为:4.3无失真信源编码——等长码当

N=100时,考虑到码长必须为整数,所以最短码长为,此时最短平均码长为:编码效率为:结论:随着序列长度

N

的增加,平均码长减小,编码效率增加。但序列长度的增加,意味着编码复杂度相应增加,编码付出的代价也会增大,因此通过无限制增加码长提高编码效率并不总是一种有效方法。4.3无失真信源编码——等长码例4.4

设某离散无记忆信源为

,如果要求编码效率为92%,允许错误概率为

,求编码序列的长度

N。

解:信源的熵为

自信息量方差为

如果采用二进制码,则序列长度

N应满足:从指标来看,编码效率和允许错误概率的要求并不高,但是序列的长度却很大。这是因为等长码的编码没有充分利用信源统计特性的结果。4.3无失真信源编码——等长码总结:

等长编码的平均码长受到熵的约束;增加序列长度有利于提高编码效率,但序列长度增加会提高编码复杂度。

等长编码使用概率方式:根据概率大小,将序列划分为典型序列和非典型序列;所有典型序列的码长相等,没有充分利用每个序列的概率指导编码,所以编码效率难以提高。4.3无失真信源编码——变长码

变长码的基本思想是:对于给定的信源,当信源符号对应的先验概率不是等概率分布时,为了提高编码效率,给概率大的符号分配较短码字,概率小的符号分配长码字,从而使得平均码长尽可能短。

定理4.6

设信源符号数为

r,对信源进行无失真编码,码符号的个数为

d,码字的长度分别为

,则唯一可译码存在的充分必要条件是该不等式就是麦克米伦不等式(McmilanInequality),与格拉夫特不等式具有相同的形式,。4.3无失真信源编码——变长码定义4.4

设信源的概率空间为

,码符号个数为

d,编码产生的码字对应的长度分别为

l1,l2,…,lr,则平均长度为定义4.5

给定信源

X

的熵为

H(X),编码得到的每个信源符号平均长度为

,那么定义平均每个码符号携带的信息量为编码后的信息传输率,即4.3无失真信源编码——变长码定义4.6

对于给定的信源和码符号集合,如果存在一个唯一可译码,其平均码长

小于其他所有唯一可译码的平均码长,则称该码为紧致码或者最佳码。无失真编码的目的就是寻找最佳码,最佳码的平均码长

就是编码可能达到的理论极限。定理4.7

设离散无记忆信源

X

的熵为

H(X),编码使用的符号个数为

d,一定存在某种无失真编码方法,构成唯一可译码,使得平均码长

满足香农第一定理的基本形式4.3无失真信源编码——变长码证明:

首先证明下界,根据熵和平均码长的定义可得:先求函数,后求数学期望先求数学期望,后求函数令

,根据詹森不等式可得:4.3无失真信源编码——变长码唯一可译码存在的条件就是满足即克拉夫特不等式,即:4.3无失真信源编码——变长码然后证明上界。对于给定的概率分布

p(ai),一定存在一个正整数

mi,使得下列不等式成立。选择该信源符号对应码字的长度

li=mi,两边取对数,可得:4.3无失真信源编码——变长码两边同乘以

p(ai),并且对

i

求和,可得:根据熵、平均码长的定义4.3无失真信源编码——变长码定理4.7的意义在于:无失真不等长编码的平均码长不能小于极限

Hd(X),否则唯一可译码不存在;同时给出上界1+Hd(X),说明小于上界的唯一可译码是存在的;最佳码的平均码长应当满足上述不等式

;平均码长超出上界的唯一可译码是存在的。4.3无失真信源编码——变长码定理4.8(香农第一定理)

设离散无记忆信源的概率空间为:信源的熵为

H(X),其

N次扩展信源为:扩展信源的熵为H(X)。使用

d

元码对其

N次扩展信源进行编码,可以找到某种编码方法,构成唯一可译码,使得

N次扩展信源

X编码得到的每个信源符号的平均码长

满足

。4.3无失真信源编码——变长码注意:

和

都表示离散无记忆信源

X

的平均码长,但两者含义不同

:

表示对信源

X

的

N次扩展信源

X进行编码得到的每个信源符号的平均码长;

表示直接对信源

X

进行编码得到的每个信源符号的平均码长;

令

,则可得:4.3无失真信源编码——变长码证明:

由于信源

X

为无记忆信源,其次扩展信源

X=XN也是无记忆的,且直接应用定理

4.7的结论,即

将该结论加以推广,对于平稳、遍历的有记忆信源,可得:4.3无失真信源编码——变长码香农第一定理的意义:使用

d

元码对信源进行无失真编码,每个符号平均码长的极限就是信源熵;如果编码产生的平均码长大于信源熵,唯一可译码是存在的;反之,唯一可译码是不存在的,即在译码时一定会引入失真或者差错;如果要取得好的编码效果,序列的长度应当更长,但这会增加系统编码复杂度,因此,在实际编码时,往往是通过变换方法进行编码,降低编码系统复杂度。

4.3无失真信源编码——变长码定义4.8

定义变长码的码剩余度为定义4.7

设对信源

X

进行变长编码得到的平均码长为

,定义编码效率为:编码效率是衡量各种编码方法的优劣指标之一。4.3无失真信源编码——变长码无噪无损信道例4.5

设离散无记忆信源的概率空间为

,信源熵为(1)如果采用二元码对其进行等长编码,映射关系为

平均码长为

编码效率为:该编码方案可以使用信道形式表示,对应信道矩阵为4.3无失真信源编码——变长码(2)现在对信源进行二次扩展,并且采用下列编码方法进行变长编码:显然,得到的码字为即时码。扩展信源的概率分布为:序列的平均码长为:每个符号的平均码长为:4.3无失真信源编码——变长码编码效率为:编码方案对应信道矩阵为:无噪无损信道4.3无失真信源编码——变长码(3)如果采用序列等长编码,要求编码效率为

η=96%,而允许译码错误概率为

。

根据信源统计特性,可以计算自信息方差为:

编码序列的长度应当满足:

要取得与变长编码相当的编码效率,在允许译码错误概率并不是很小的情况下,定长编码所需要的序列长度很长,这就意味着需要产生巨大的码表;而采用变长编码,只采用二次扩展信源编码就可以得到相同的编码效率,随着序列的长度增加,变长编码的效率越接近1。4.3无失真信源编码——变长码变长编码之所以能够取得好的编码效率,是因为变长编码更好地利用了信源的统计特性。概率越大码长越短,概率越小码长越长,从统计角度来看,平均码长就可以变小。变长编码采用一一映射构造即时码,不仅编码效率高,也不会存在译码错误。而等长编码是将符号序列分为两大类:典型序列和非典型序列。典型序列分配相同长度的码字,而非典型序列被丢弃或者通过附加前缀的方法与典型序列的码字区分开。而典型序列的概率分布并不完全相同,分配相同长度的码字显然没有利用统计特性,所以等长码的编码效率难以提高。另一方面,在香农的等长编码理论中,非典型序列是不编码的,一旦非典型序列出现,则不可能再现或者重建该序列,所以会存在译码错误。

主要内容4.1信源编码概述4.2渐近等同分割性4.3无失真信源编码4.4信息率失真函数及性质4.5信息率失真函数的参量计算4.6信息率失真函数的迭代算法4.7香农第三定理4.4.1失真测度4.4.2信息率失真函数的定义4.4.3信息率失真函数的性质4.4信息率失真函数及性质

对于信源无失真编码,无论是等长编码还是变长编码,都可以通过增加序列的长度提高编码效率。但信源无失真编码平均码长受信源熵的限制,无论采用何种编码方案,平均码长不可能小于信源熵。

由于编码产生的信息率受到熵的限制,当其大于信道容量时,不能够在信道中有效传输信息。而在实际中,为了传输信息,允许出现一定的失真,从而降低信息传输率。

那么在允许一定失真条件下,信源编码输出的信息率是否存在极限?或者说,当信息率一定时,是否会存在最小失真,使得在有效传输信源信息的同时,尽可能减小编码引入的失真。4.4.1失真测度

由于只是讨论信源编码问题,将信道编译码器看作信道的一部分,即不考虑信道编码是否会引入失真,这是就可以引入广义信道简化信道模型,,得到如下图所示的信源编码模型,这种信道称为试验信道。

从直观上来看,如果允许失真越大,信息传输率应当越小;反过来,如果允许失真越小,信息传输率越大,所以信息传输速率与信源编码引入的失真是相关的,在允许失真一定的情况下,应当存在一种信源编码方法使得信息传输率最小。4.4.1失真测度定义4.9

设离散无记忆信源的概率空间为

,经过限失真编码后,译码再现的符号集合为

Y={b1,b2,…,bs}。对于每一对(ai,bj),指定一个非负函数

d(ai,bj),其中,i=1,2,…,r,j=1,2,…,s,称该函数为单符号的失真函数。失真实际是距离的一种,其定义应当满足一定的条件,对于任意

i,j

满足:非负性:即

,当且仅当

ai=bj时,d(ai,bj)=0;可交换性:即

;三角不等式:即

,其中

c

是任意给定符号。4.4.1失真测度称

D为失真矩阵。

失真函数

d(ai,bj)表示在信源输出符号,而接收端再现为符号

所引入的失真或者误差。将所有的

d(ai,bj)排列起来,用一个

r×s矩阵表示为:4.4.1失真测度

当

ai=bj时,d(ai,bj)=0。如果

r=s且

ai=bj(即编码器输入符号与译码再现符号相同),则失真矩阵为:常用的失真函数有以下三种:平方误差失真:4.4.1失真测度

当

ai=bj时,d(ai,bj)=0。如果

r=s且

ai=bj(即编码器输入符号与译码再现符号相同),则失真矩阵为:绝对失真:4.4.1失真测度

当

ai=bj时,d(ai,bj)=0。如果

r=s且

ai=bj(即编码器输入符号与译码再现符号相同),则失真矩阵为:汉明失真:4.4.1失真测度例4.6

对于离散对称信源(

r=s),信源发送符号变量为X={a1,a2,…,ar},再现符号变量为

Y={b1,b2,…,bs},定义单个符号失真为它表示:当再现符号与信源发送符号相同时,就不存在失真和错误,所以失真度

d(ai,bj)=0,当再现符号与信源发送符号不同时,就有失真存在,且认为发送符号为

ai,再现符号为

bj(i≠j)所引起的失真都相同,所以失真度

d(ai,bj)(ai≠bj

)为常数,该常数取值为1,这种失真称为汉明失真。4.4.1失真测度汉明失真矩阵

D

是一方阵,且对角线上的元素为0,即4.4.1失真测度例4.7

对于删除信源,假设信源发送符号变量为X={a1,a2,…,ar},再现符号变量为

Y={b1,b2,…,bs},且

s=r+1。定义单个符号失真为其中,再现符号

bs作为一个删除符号。如果信源符号再现为删除符号

bs,则其失真程度要比再现为其他接收符号的失真程度少一半。4.4.1失真测度定义4.10

设信源符号序列为

X=(X1X2…XN),其中每个随机变量都取值于相同的符号集合{a1,a2,…,ar},从而有

rN

种不同序列

αi,αi=(ai1ai2…aiN)。设再现符号序列为

Y={Y1Y2…YN},其中每个随机变量都取值于相同的符号集合{b1,b2,…,bs},从而有

sN

种不同序列

βi,βi=(bj1bj2…bjN)。定义信源序列的失真度为即信源序列的失真度等于构成该序列的各个单符号失真度之和,失真矩阵共有

rN×sN

个元素。根据单个符号的失真,可以得到

N

次扩展信源符号序列的失真度。4.4.1失真测度

无论是单个符号的失真还是序列的失真,实际都是反映了具体符号或者具体符号序列的失真,为了衡量每传输一个符号引入的失真大小,需要引入平均失真。

定义4.11

设离散无记忆信源的概率空间为

,再现符号集合为{b1,b2,…,bs}。单个符号的失真度为

d(ai,bj),定义

d(ai,bj)的数学期望为平均失真,即4.4.1失真测度

平均失真是信源分布和信道转移概率的函数,描述了信源在某试验信道下,平均失真的大小,描述了整体失真情况。如果已知试验信道的转移概率

,

平均失真可表示为:

如果将信源序列中的每个序列看作是扩展信源的一个符号,类似地可以定义符号序列的平均失真。4.4.1失真测度平均每个信源符号的失真为:

定义4.12

定义信源

X

的

N

维符号序列的平均失真度为:

4.4.1失真测度如果信源还是平稳的,就可以得出:

如果信源与试验信道都是无记忆的,利用序列概率与构成序列的各符号概率之间的关系,可得:

对于离散无记忆平稳信源,如果试验信道也是无记忆的,那么信源序列的平均失真度等于单个符号的平均失真度的

N

倍。4.4.2信息率失真函数的定义

信源编码的目的是为了减小信息传输率

R,而

R与编码引入的失真存在一定的关系。对于给定的信源和选择的失真测度,在编码输出的平均码长,即信息传输率

R一定的条件下,总是希望编码引入的平均失真越小越好;或者说,对于给定的平均失真,希望编码产生的平均码长越小越好。

信源编码可以看作是存在一个试验信道,信道的输入就是信源

X,而信道的输出就是译码后再现符号

Y。对于给定的信源

X

和选择的失真测度

d(ai,bj),信源编码就是寻找一种试验信道

p(bj|ai),在平均失真一定条件下,输出码率

R最小。

所以,编码输出码率

R是平均失真的函数,称为信息率失真函数。4.4.2信息率失真函数的定义定义4.13

对于给定信源

X

和失真测度

d(ai,bj),信息率失真函数

R(D)定义为:其中,Y为试验信道的输出,

p(bj|ai)为试验信道的转移概率,

为编码引入平均失真,D是给定平均失真,或者是允许失真。已知条件信源先验分布p(x),给定失真D变化参数平均互信息量极大值极值问题试验信道条件转移概率

p(bj|ai)试验信道是不存在的,是为了分析限失真编码理论而引入的,便于分析信息率失真函数。4.4.2信息率失真函数的定义

根据熵的性质可知:在已知

H(X)条件下,平均互信息

I(X;Y)是信道转移概率的U型凸函数,所以最小值是存在的。

对于离散无记忆信源,

在信源编码允许失真一定的前提下,X与

Y之间没有一一映射关系,通过去掉一些非主要成分,或者进行符号合并,增加条件信息熵

H(X|Y),减少平均互信息量

I(X;Y),从而实现数据压缩,降低信息传输率。4.4.2信息率失真函数的定义

信息率失真函数不仅与信源符号取值、信源概率分布、失真的测度有关,而且与接收端再现符号也是密切相关的。

例4.8

设信源概率空间为

,选择试验信道的输出为{b1=0,b2=2},失真测度为

,编码方案如下:无噪有损信道,H(Y|X)=04.4.2信息率失真函数的定义又

经过信源编码后,信源所需要传输的信息量由原来的2比特/符号压缩为1比特/符号。4.4.2信息率失真函数的定义

根据失真测试,可得失真矩阵为:平均失真4.4.2信息率失真函数的定义

如果改变再现或者重建符号取值为{b1=0.5,b2=2.5},编码方案为:

相对第一种情况,试验信道的条件转移概率矩阵并未变化,只是重建符号发生了变化,此时失真矩阵为:4.4.2信息率失真函数的定义平均失真

即使采用相同的信源编码方案,但信源译码时采用不同的重建符号取值,则得到的平均失真也不同。

对于这种给定的简单试验信道,平均失真可以根据失真测度计算出来;当改变试验信道的转移矩阵,平均失真会发生变化,所以平均失真是信道转移概率的函数;同样平均互信息量也是试验信道转移概率的函数。4.4.2信息率失真函数的定义

信息率失真函数就是在信源和再现符号取值一定情况下,对于给定平均失真测度,改变试验信道的转移概率,使得平均互信息量最小。

在信源编码中,平均互信息量就是信源进行限失真压缩后的输出码率,所以信息率失真函数就是在给定信源的情况下,在允许的失真内再现或者重建信源消息的最小平均信息量,即信源压缩后的最小输出码率。4.4.3信息率失真函数的性质R(D)的定义域——Dmin

和

R(Dmin)

由于失真

D

是非负函数

d(ai,bj)的数学期望,所以

D

一定是非负的实数,即

D≥0。当

D=0时,

一般情况下,当给定信源和失真矩阵时,信源的最小平均失真不一定为0,此时应根据给定的条件求解。无失真4.4.3信息率失真函数的性质

由于

d(ai,bj)是已知的,现在任务就是选择试验信道的转移概率

p(bj|ai),对每个信源符号

ai,使得下列表示式最小先验概率p(ai)一定

该最小值问题,就是对给定

ai找到一个最小的失真

d(ai,bj)使得对应的条件转移概率为

p(bj|ai)=1,而对于其它失真

d(ai,bj),

p(bj|ai)=0,从而使得平均失真最小。4.4.3信息率失真函数的性质

对于给定的

ai,

最小失真

d(ai,bj)

可能不是唯一的,所以试验信道的选择也可能不是唯一的,只要满足下列条件即可。

从失真矩阵来看,平均失真最小值就是矩阵每行元素的最小值乘以对应符号概率,然后求累加和。允许失真最小值是否为0取决于失真函数,如果失真矩阵中每行都有一个0元素,则最小失真为0;否则,只要有一行没有0元素,则最小失真不为0。4.4.3信息率失真函数的性质解:由于失真矩阵中每行都存在0元素,所以例4.9

信源

X

的概率空间为

,而

Y的取值为{b1,b2,b3},失真矩阵为

,求

Dmin。取得最小允许失真所对应试验信道的信道矩阵为:4.4.3信息率失真函数的性质

从信道矩阵可以看出,允许失真取得最小值的条件是:信源符号与再现符号之间满足一一对应的关系,显然这是一个无噪有损信道,满足4.4.3信息率失真函数的性质解:最小失真为:

取得最小允许失真所对应试验信道的信道矩阵为:例4.10

信源

X

的概率空间为

,信宿

Y的取值为{b1,b2},失真矩阵为

,求

Dmin,并且给出取得最小失真的条件。找每行元素最小值

有噪有损信道,信源符号a2被合并,H(X|Y)≠0。4.4.3信息率失真函数的性质R(D)的定义域——Dmax和

R(Dmax)

根据信息率失真函数的定义,R(D)是在给定平均失真

情况下,平均互信息量的最小值。由于

I(X;Y)是非负的,其下限为0。当

R(D)=0时,对应的平均失真取得最大值

Dmax。I(X;Y)=0的条件是什么?4.4.3信息率失真函数的性质

此时取

的最小值得到

由于概率

p(ai)

和

d(ai,bj)是已知的,上述的极值问题就是找到一种概率分布

p(bj)

,使得表示式取得最小值即可,同时应当考虑到

p(bj)

的非负性和约束条件

。4.4.3信息率失真函数的性质例4.11

求例4.10给定条件的最大失真。解:根据最大失真计算公式:

首先计算

,可得:4.4.3信息率失真函数的性质R(D)的定义域为(0,Dmax),而值域为(0,H(X)),且满足4.4.3信息率失真函数的性质R(D)是

D的下凸函数下凸函数:假设有一个函数f(x),在定义域内任意两点

x1<x2,可以连成一条直线,该直线的函数表达式为直线上的任一点

x,满足

x1<x<x2,可以表示为4.4.3信息率失真函数的性质如果满足

,即则该函数是下凸函数。4.4.3信息率失真函数的性质

要证明

R(D)是

D的下凸函数,只需证明对任意

和任意

有:证明:设有两个试验信道

p1(bj|ai),p2(bj|ai),对应的信息率失真函数分别为

,有试验信道的平均失真度4.4.3信息率失真函数的性质再定义一个新的试验信道,设其信道转移概率为:对应的平均失真度为:在平均失真度

的信道集合中,这个信道并不一定是使

I(X;Y)

最小。4.4.3信息率失真函数的性质根据信息率失真函数的定义,可得:由于平均互信息

I(X;Y)

是信道转移概率的下凸函数4.4.3信息率失真函数的性质R(D)在区间

(0,Dmax)上是严格递减的连续函数

由于

R(D)具有凸状性,这就意味着它在定义域内是连续的。由于允许的失真越大,所要求的信息率就越小,所以

R(D)是非增函数。

实际上,R(D)在区间

(Dmin,Dmax)是上严格递减的连续函数,该性质可以利用

R(D)的下凸性进行证明。4.4.3信息率失真函数的性质R(D)H(X)D

D1

0R(D1)R(D)H(X)D

D1

0R(D1)Dmin

主要内容4.1信源编码概述4.2渐近等同分割性4.3无失真信源编码4.4信息率失真函数及性质4.5信息率失真函数的参量计算4.6信息率失真函数的迭代算法4.7香农第三定理4.5信息率失真函数的参量算法约束条件

设信源的概率空间为

,失真函数为

d(ai,bj)。由于4.5信息率失真函数的参量算法

信息率失真函数

R(D)

就是寻找一种试验信道

p(bj|ai)使得

I(X;Y)最小化,但需要满足下列约束条件:4.5信息率失真函数的参量算法极值求解

利用拉格朗日乘法对条件极值问题进行求解。构建如下的函数:对函数

J

求偏导数,并令其为0,即4.5信息率失真函数的参量算法以及

考虑到r×s个方程4.5信息率失真函数的参量算法

共有(r×

s+r+1)个方程。而未知数有

r个

ui,一个

S和(r×

s)个

p(bj|ai),共有(r×

s+r+1)未知参数。理论上,方程的解是可以求出来的。如果能够解出方程的解,代入互信息量公式即可求出极小值,从而得到信息率失真函数。

加上

r个约束条件

和1个约束条件为了讨论问题方便起见,令4.5信息率失真函数的参量算法中间参数的表示

根据关系式

,可得:4.5信息率失真函数的参量算法将

两边同乘

p(ai),并对

i

累加,可得:

如果

p(bj)≠0,则有将

λi的表示式代入,得到由参量

S表示的

p(bj)为4.5信息率失真函数的参量算法将

两边同乘

p(ai),并对

i

累加,可得:

如果

p(bj)≠0,则有将

λi的表示式代入,得到由参量

S表示的

p(bj)为

根据上式可以求出由参量

S表示的

p(bj)。如果

p(bj)≠0,则vi=1;否则,如果p(bj)=0,则

vi≤1。4.5信息率失真函数的参量算法将

p(bj)代入

λi的表示式,可以求出

λi,再将

λi代入即可求出4.5信息率失真函数的参量算法信息率失真函数的参数表示

将参数

S表示的

p(bj|ai),p(bj)代入

I(X;Y)和平均失真

D中,即可得到以参数

S为变量的信息率失真

R(S)和平均失真

D(S)。显然这不是显式表达式,参数

S对应的限制条件为:即根据参数

S计算出的

p(bj|ai)必须满足上述条件的约束,从这种意义上讲,

p(bj|ai)以参数

S为变量,实际上就是以参数

D为变量。将

p(bj|ai)表示式代入上述约束条件得到平均失真

D(S)为:4.5信息率失真函数的参量算法4.5信息率失真函数的参量算法信息率失真函数的计算如下:首先,根据给定参数

S

取值,计算出

p(bj)、λi;然后,将其代入平均失真公式

D(S);最后,求出

R(S),从而得到信息率失真函数

R(D)。4.5信息率失真函数的参量算法参量

S

的物理意义

由于概率

p(bj)在[0,1]之间取值,当

p(bj)≠0时,

p(bj)与参量

S

之间的关系为:所以参量

S

的取值范围应当有一定的限制。

由于

,且

λi也是

S

的函数,所以可以将

S

看做

D

的函数,而

λi也就成为

D

的函数。4.5信息率失真函数的参量算法为了弄清参量

S

的物理意义,求解下列导数:为了得到,对方程

两边同时对

S求导,可得:

4.5信息率失真函数的参量算法将等式两边同时乘以

p(bj),并且对

i求和,可得D(S)即将

代入上式,可得:4.5信息率失真函数的参量算法又

该式表明:参量

S就是信息率失真函数

R(D)的斜率。由于

R(D)在(0,Dmax)之间是严格单调递减的下凸函数,所以斜率

S是非正的,并且是

D的单调递增函数。根据

R(D)的性质可知,

D=0时,R(D)的斜率可能为负无穷;而当

D>Dmax时,斜率为0,所以

S的取值范围为负实数,而且信息率失真函数

R(D)是参数

S的连续函数。4.5信息率失真函数的参量算法

解:首先,解下列方程式例4.12

信源

X

的概率空间为

,信宿

Y的取值为{b1,b2},失真矩阵为

,求

信息率失真函数R(D)。4.5信息率失真函数的参量算法其次,解下列方程得到

p(bj)。4.5信息率失真函数的参量算法然后,将上述参数代入求解信道转移概率。4.5信息率失真函数的参量算法最后,用参量

S

表示平均失真

D(S)。4.5信息率失真函数的参量算法将

S,λi

等参数代入下式。由于

D

的取值范围为[0,p],上式可表示为:4.5信息率失真函数的参量算法4.5信息率失真函数的参量算法对于某些特殊分布,信息率失真函数如下:如果连续信源服从均值为0的高斯分布,即

失真测度为

,则有:如果

,则有:主要内容4.1信源编码概述4.2渐近等同分割性4.3无失真信源编码4.4信息率失真函数及性质4.5信息率失真函数的参量计算4.6信息率失真函数的迭代算法4.7香农第三定理4.6信息率失真函数的迭代算法试验信道的条件转移概率可以表示为:其中,参数

S表示信息率失真函数的斜率,取值为非正。试验信道输出符号的概率为:

由4.5小节可知,信息率失真函数的参量计算十分复杂和繁琐。当信符号数量较多时,人工计算信息率失真是相当困难的,此时需要利用信息率失真函数的迭代算法进行计算,具体计算过程如下。

4.6信息率失真函数的迭代算法计算出一个新值

p*(bj|ai),这样就构成了一种迭代算法。

从上述两个公式来看,条件概率

p*(bj|ai)与再现符号概率

p*(bj)之间可以相互表示。在

S一定的条件下,可以假设试验信道的转移概率取值

p*(bj|ai),根据概率知识计算出概率

p*(bj),然后将得到的代入公式

4.6信息率失真函数的迭代算法迭代算法具体如下:(1)

首先假设绝对值足够大的负数作为斜率

S的取值,并且选择试验信道的转移概率p1(bj|ak)为等分布的,且令

n=1。(2)

根据公式

计算出

pn(bj)。(3)

将

pn(bj)代入公

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论