当前位置:首页 >> 理学 >>

信息论与编码第二版复习课件第四章


第4章 信息率失真函数

第 4 章 信息率失真函数
4.1 平均失真和信息率失真函数 4.2 离散信源和连续信源的R(D)计算

1

第4章 信息率失真函数

实际信息处理过程中允许一定的失真存在 不可能也不必要完全表示信源信息 允许压缩信源输出的信息率 研究内容:信息率 允许失真

本章主要讨论在信源允许一定失真情况下所 需的最少信息率,从分析失真函数、平均失真 出发,求出信息率失真函数R(D) 。
2

第4章 信息率失真函数

4.1 平均失真和信息率失真函数
在实际问题中,信号有一定的失真是可以 容忍的。但是当失真大于某一限度后,信息质 量将被严重损伤,甚至丧失其实用价值。要规 定失真限度,必须先有一个定量的失真测度。 失真函数

失真度
3

第4章 信息率失真函数

4.1.1 失真函数
信源X,输出样值为xi,xi∈{a1,…,an},经过有失真 的信源编码器,输出Y,样值为yj,yj ∈{b1,…bm}。 xi = yj xi ≠ yj 失真函数 d(xi , yj) 没有失真 产生失真

衡量用yj代替xi所引起的失真程度

xi = y j ?0 一般失真函数定义为: d ( xi ,y j ) = ?α α > 0 x ≠ y i j ?
4

第4章 信息率失真函数

失真矩阵 单个符号的失真度的全体构成的矩阵 [d ( xi ,y j )]
?d (a1, b1) d (a1, b2 ) L d (a1, bm ) ? ?d (a , b ) d (a , b ) L d (a , b )? 2 2 2 m ? d =? 2 1 ? M M M ? ? ? ?d (an , b1) d (an , b2 ) L d (an , bm )?

例: 设信源符号X∈{0,1} ,编码器输出符号Y∈{0,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.5? d =? 1 0 0.5? ? ?
5

第4章 信息率失真函数

常用的失真函数 失真函数形式可以根据需要任意选取 均方失真 绝对失真 相对失真 误码失真
d ( xi , y j ) = ( xi ? y j ) 2
d ( xi , y j ) = xi ? y j

适于连 续信源

d ( xi , y j ) = xi ? y j

xi
xi = y j 其它

? 0, d ( xi , y j ) = δ ( xi , y j ) = ? , ?1

适于离散 信源

6

第4章 信息率失真函数

汉明失真 失真矩阵

?0 ?1 d = ? ?M ? ?1

1 0 1

L L L

1? 1? ? M? ? 0?

如二元对称信源,X={0,1},Y={0,1}

?0 d =? ?1

1? 0? ?

例: 信源X={0,1,2},接收变量Y={0,1,2},失真度定 义为 d ( x i , y j ) = ( x i ? y j ) 2 “均方失真”

失真矩阵

?0 d = ?1 ? ?4 ?

1 0 1

4? 1? ? 0? ?
7

第4章 信息率失真函数

失真函数的定义可以推广到序列编码情况 离散信源输出符号序列 X = ( X 1 , X 2 , L , X L ) ,其 中L长符号序列样值 xi = ( xi1 , xi 2 , L , xiL ) ,经信源编 码后,输出符号序列 Y = (Y1 , Y2 ,L, YL ) ,其中L长符 号序列样值 y j = ( y j1 , y j 2 , L , y jL ) ,则
1 L d 失真函数定义为: L ( xi , y j ) = ∑d ( xil , y jl ) L l =1

其中d(xil , yjl)是信源输出 xi 中的第l个符号xil时,编码 输出 y j 中的第l个符号yjl的失真函数。
8

第4章 信息率失真函数

4.1.2 平均失真
将失真函数的数学期望称为平均失真
D=
n m n m

∑ ∑ p (a , b
i =1 j =1 i

j

) d ( ai , b j ) =

∑ ∑ p ( a ) p (b
i =1 j =1 i

j

| ai )d (ai , b j )

xi

p(y

j

xi )

信源编码器

yj

平均失真是对给定信源分布p(ai)经过某一种转移 概率分布为p(bj | ai)的有失真信源编码器后产生失 真的总体量度。
9

第4章 信息率失真函数

失真函数与平均失真 单个符号的失真度d(xi,yj)描述了某个信源符号通 过传输后失真的大小。对于不同的信源符号和不 同的接收符号,其值是不同的。 平均失真 D 已对信源和信道进行了统计平均,该 值是描述某个信源在某一试验信道传输下的失真 大小,是从总体上描述整个系统的失真情况。
10

第4章 信息率失真函数

对于连续随机变量同样可以定义平均失真:
D=∫
∞ ?∞ ?∞





p xy ( x , y ) d ( x , y ) dxdy
连续随机变量 的失真函数 第l个符号的 平均失真
l

连续随机变量的 联合概率密度

对于L长序列编码情况,平均失真为:
1 DL = L


l =1

L

1 E [ d ( x il , y jl )] = L

∑D
l =1

L

保真度准则

D≤D

允许失真
11

第4章 信息率失真函数

4.1.3 信息率失真函数R(D)
X

x ∈ {a1 , a2 , L an }

信源编码器

Y

y ∈ {b1 , b2 ,L bm }

假想信道

将编码器 看作信道

信源编码 在一定失真限制下,对信源输出的信号进行变 换,包括连续信号的离散化(即将模拟信号通过采样 和量化变成数字信号),以及对数据进行压缩,提高 数字信号传输的有效性而进行的编码。
12

第4章 信息率失真函数

无论是无噪信道还是有噪信道: 信息传输率R<信道容量C 总能找到一种编码,使在信道上能以任意小的 错误概率,以任意接近C的传输率来传送信息。 信息传输率R>信道容量C 就必须对信源压缩,使其压缩后信息传输率小 于信道容量C,但同时要保证压缩所引入的失真不 超过预先规定的限度。
13

第4章 信息率失真函数

信源编码器目的:使编码后所需的信息传输率R尽量小 R越小 条件:
D≤D

引起的平均失真就越大 选择一种编码方法使信息率R尽可能小

信息率R就是所需输出的有关信源X的信息量
对应到信道

接收端Y需要获得的有关X的信息量, 即互信息I(X;Y)。

选择信源编码方法的问题就变成了选择假想信道的 问题,符号转移概率p(yj | xi)就对应信道转移概率。
14

第4章 信息率失真函数

D=

∑ ∑ p( x ) p( y
i = 1 j =1 i

n

m

j

| xi ) d ( xi , y j )

当信源p(xi)给定,单个符号失真度d(xi,yj) 给定 时,选择不同的信道p(yj|xi),相当于不同的编码方 法,其所得的平均失真度不同。 1 D允许试验信道

若p(xi)和d(xi,yj)已定,则可给出满足 D ≤ D 条件的 所有转移概率分布pij,它们构成了一个信道集合PD
PD = p (b j | ai ) : D ≤ D

{

i = 1, L , n; j = 1, L , m

}

称为D允许试验信道。
15

第4章 信息率失真函数

2

信息率失真函数R(D) 在限定失真为D的条件下信源输出的最小信息率

若从接收端来着,就是在满足保真度准则下,再现 信源消息所必须获得的最低平均信息量(即平均互信 息I(X;Y)的最小值)。 复习 当p(xi)一定时,I(X;Y)是关于p(yj|xi)的下凸函数 PD是所有满足保真度准则的试验信道集合,因而可在 其中寻找某一种信道pij,使给定的信源p(xi)经过此信 道传输后,互信息I(X;Y)达到最小。该最小的互信息 就称为信息率失真函数 R(D) = minI ( X ;Y )
PD

16

第4章 信息率失真函数

离散无记忆信源
R(D) = min∑∑ p(ai ) p(bj | ai ) log
P ∈PD ij i=1 j =1 n m

p(bj | ai ) p(bj )

例: 已知编码器输入的概率分布为p(x)={0.5,0.5}
? 0.9 0.1 ? ? 0.6 0.4 ? 信道矩阵:1 pij = ? 0.2 0.8 ? 2 pij = ? 0.2 0.8 ? 求互信息 ? ? ? ? ? 0.3 0.2 ? p(y)={0.4, 0.6} 1 p ( xi , y j ) = p ( xi ) p ( y j | xi ) [ p(xi , y j )] = ? 0.1 0.4 ? ? ? 1 2 3 1 p ( x1 | y1 ) = , p ( x1 | y2 ) = , p ( x2 | y1 ) = , p ( x2 | y2 ) = 4 3 4 3
I ( X ;Y ) = ∑∑ p( xi , y j ) log
i j

p(xi | y j ) p(xi )

= 0.125bit / 符号

2 I ( X ;Y ) = 0.397bit / 符号

17

第4章 信息率失真函数

说明

当p(x)一定时,I(X;Y)随p(yj|xi)而变。

因为p(x)分布一定时,信道受干扰不同,所能 传递的信息量是不同的。 当p(x)一定时,I (X;Y)是关于p(yj|xi)的下凸函数。 因此当改变p(yj|xi)时,I (X;Y)有一极小值。 平均互信息、信道容量、信息率失真函数
? 平均互信息I(X;Y): – 信源概率分布p(xi)的上凸函数。 – 信道转移概率p(yj|xi)的下凸函数。 ? 信道容量: C = max I ( X ; Y ) p(x )
i

? 信息率失真函数:
R ( D ) = min I ( X ; Y )
PD

18

第4章 信息率失真函数

C I(X;Y)的上凸函数 I(X;Y)的极大值 {p(bj|ai)} 的函数 仅与信道特性有关 解决可靠性问题 信息传输的基础

R(D) I(X;Y)的下凸函数 I(X;Y)的条件极小值 {p(ai)}的函数 仅与信源特性有关 解决有效性问题 信源压缩的基础
19

第4章 信息率失真函数

信道容量 假定信道固定的前提下,选择一种试验信源使信 息传输率最大。 它所反映的是信道传输信息的能力,是信道可靠 传送的最大信息传输率。 一旦找到了信道容量,它就与信源不再有关,而 是信道特性的参量,随信道特性的变化而变化。 不同的信道其信道容量不同。

20

第4章 信息率失真函数

信息率失真函数 假定信源给定的情况下,选择一种试验信道,在 用户可以容忍的失真度内再现信源消息所必须获得的 最小平均信息量。 它所反映的信源可以压缩的程度,是在满足一定 失真度要求下信源可压缩的最低值。 率失真函数一旦找到,就与求极值过程中选择的 试验信道不再有关,而只是信源特性的参量。 不同的信源其R(D)不同。
21

第4章 信息率失真函数

研究信道容量:充分利用已给信道,使传输 研究信道容量 的信息量最大,而发生错误的概率任意小。 研究信息率失真函数:解决在已知信源和允许 失真度D的条件下,使信源必须传送给信宿的信息 率最小。即用尽可能少的码符号尽快地传送尽可 能多的信源消息,以提高通信的有效性。

22

第4章 信息率失真函数

例: 设信源符号表示为A={al,a2,…,a2n},概率分布 为p(ai)=1/2n,i=1,2,…,2n,失真函数规定为
?1 i ≠ j d ( ai , a j ) = ? ?0 i = j

符号不发生差错时失真为 0;一旦出错,失真为1。

试研究在一定编码条件下信息压缩的程度。 信源熵
1 1 1 H ( , L ) = log 2 n 2n 2n 2n

如果对信源进行不失真编码,平均每个符号至少 需要log2n个二进制码元。 现在假定允许有一定失真,失真限度为D=1/2。
23

第4章 信息率失真函数

设想采用下面的编码方案: a1→a1, a2→a2, …,an→an an+1→an,an+2→an,…,a2n→an 平均失真
1 D = ∑∑ p(ai ) p(a j | ai )d (ai , a j ) ≤ D = 2 i j

a1

a1



an


压缩

a2

a2 an

a2n

确定信道

pij=1(或0),H(Y|X)=0

I (X;Y) = H(Y) ? H(Y | X ) = H(Y)

输出概率分布:p1= p2=…= pn-1=1/2n 输出熵

pn= (1+n)/2n

n +1 1 1 1+ n H(Y ) = H ( ,L, , ) = log2n ? log(n +1) 2n 2n 2n 2n



an+1

24

第4章 信息率失真函数

说明

H ( X ) = log 2 n n +1 I ( X ;Y ) = H (Y ) = log2n ? log(n +1) 2n

信息率压缩了[(n+1)/2n]log(n+1),这是采用了 所设压缩编码方法的结果,所付出的代价是容忍了 1/2的平均失真。如果选取对压缩更为有利的编码方 案,则压缩的效果可能更好。但一旦达到最小互信 息这一极限值(即R(D)的数值),或超过此极限 值,那么失真就要超过限度。因此若需要压缩的信 息率更大,则可容忍的平均失真就要更大。
25

第4章 信息率失真函数

4.1.4 信息率失真函数的性质
1 R(D)函数的定义域 在信源和失真函数已知的情况下,讨论允许平均 失真度D的最小和最大取值问题。
1

Dmin和R(Dmin) Dmin=0 无失真
无噪声信道

信道传输的信息量等于信源熵
R(Dmin) = R(0) = H( X )
26

第4章 信息率失真函数

Dmin = min[∑∑ p( xi ) p( y j | xi )d ( xi , y j )]
i =1 j =1

n

m

= ∑ p ( xi ) min[∑ p( y j | xi )d ( xi , y j )]
i =1 j =1

n

m

若选择试验信道p(yj|xi)使对每一个xi,求和号后最 小,则总和值最小。
? ?∑ p ( y j | xi ) = 1 ? yj ? p( y | x ) = 0 j i ?
n

所有d ( xi , y j ) = 最小值的y j ∈ Y d ( xi , y j ) ≠ 最小值的y j ∈ Y

Dmin = ∑ p( xi ) min d ( xi , y j )
i =1 j

27

第4章 信息率失真函数

允许平均失真度能否达到其下限值0,与单个符 号的失真函数有关。 只有当失真矩阵中每行至少有一个0元素时, 信源的平均失真度才能达到下限值0。 当Dmin= 0,即信源不允许任何失真时,信息率至 少应等于信源输出的平均信息量—信息熵。 只有当失真矩阵中每行至少有一个0,并且每 一列最多只有一个0时,R(0)=H(X) 才成立。
28

第4章 信息率失真函数

对于连续信源
R ( Dmin ) = R (0) = H c ( x ) = ∞

? 因为实际信道总是有干扰的,其容量有限, 要无失真地传送连续信息是不可能的。 ? 当允许有一定失真时,R(D)将为有限值,传 送才是可能的。

29

第4章 信息率失真函数

2

Dmax和R(Dmax) R(D)是在约束条件下的I(X;Y)的最小值 R(D)≥0

选择所有满足R(D)=0中D的最小值,定义为R(D) 定义域的上限Dmax,即 Dmax = Rmin0 D ( D )= R(D)的定义域:D ∈ [0 , D max R(D) = 0即I(X;Y) = 0
n m p( y j ) i =1 j =1

]
p( y j | xi ) = p( y j )

X与Y统计独立

Dmax = min ∑∑ p( xi ) p( y j )d ( xi , y j )

求出满足条件 ∑

m

j =1

p( y j ) = 1

的D中的最小值
30

第4章 信息率失真函数

Dmax = min ∑ p ( y j )∑ p( xi )d ( xi , y j )
p( y j ) j =1 i =1

m

n

在j=1,…,m中,可找到 ∑1 p ( x i ) d ( x i , y j ) 值最小的j,当 i= 该j对应的p(yj)=1,而其余p(yj)为0时,上式右边达到 n n 最小。
Dmax = min
j =1, 2Lm

n

∑ p(x )d (x , y )
i =1 i i j

= min

j =1, 2Lm

∑pd
i =1

i ij

R(D)的定义域为[Dmin,Dmax ] 通常Dmin=0, R(Dmin) = H(X) D R
31

当 D≥Dmax时,R(D) = 0

第4章 信息率失真函数

例: 设输入输出符号表示为X=Y∈{0, 1},输入概率分 布p(x)={1/3, 2/3},失真矩阵为:
? 0 1? d =? 1 0? ? ?

失真矩阵的每一行至少有一个0元素

Dmin= 0

R(Dmin)=H(X)=H(1/3,2/3)=0.91比特/符号 信源编码器无失真 a1 → b1, a2 → b2 编码器的转移概率为
?1 P=? ?0 0? ? 1?

32

第4章 信息率失真函数

? 0 1? 输入概率分布p(x)={1/3, 2/3},失真矩阵 d = ? 1 0? ? ?

当R(Dmax)=0时
Dmax = min ∑ pi d ij = min {p1d11 + p2 d 21 , p1d12 + p2 d 22 }
j =1, 2 i =1 j =1, 2 2

2 1 2 ? ?1 ?2 1? 1 = min ? × 0 + × 1, × 1 + × 0? = min ? , ? = j =1, 2 3 3 3 ? j =1, 2 ? 3 3 ? 3 3 ?

j=2

输出符号概率p(b1)=0,p(b2)=1

a1 → b2 , a2 → b2

? 0 1? 编码器的转移概率为 P = ? 0 1? ? ?
33

第4章 信息率失真函数

例: 设输入输出符号表示为X=Y∈{0, 1},输入概率分 布p(x)={1/3, 2/3},失真矩阵为: ?1/ 2 1?
5 1 1 2 Dmin = ∑ p(xi ) p( y j | xi )d ( xi , y j ) = × + ×1 = 3 2 3 6 i, j
2

d =? ?2

1? ?

Dmax

1 1 2 1 2 3 = min ∑ pi dij = min( × + × 2, ×1 + ×1) = min( ,1) = 1 j =1,2 j =1,2 3 2 j =1,2 2 3 3 3 i =1

2

R(D)函数的下凸性和连续性 R(D)在定义域内是失真度D的下凸函数

3

R(D)函数的单调递减性
34

容许的失真度越大,所要求的信息率越小,反之亦然

第4章 信息率失真函数

结论 R(D)是非负的实数,即R(D)≥0。其定义域为0~Dmax, 其值为0~H(X)。当D>Dmax时,R(D) ≡ 0。 R(D)是关于D的下凸函数,也是关于D的连续函数。 R(D)是关于D的严格递减函数。
离 散 系 统
R(D) 0 D Dmax D 0 Dmax D R(D) H(X) R(D)

连 续 系 统

35

第4章 信息率失真函数

4.2 离散信源和连续信源的R(D)计算
某些特殊情况下R(D)的表示式
1
d(x, y) =(x? y)2
x2 ? 2 2σ

1 p(x) = e σ 2π

R ( D ) = log

σ
D

2

d(x, y) =| x ? y |

p( x) =

λ
2

e

?λ x

R ( D ) = log

1 λD

3

d(x, y) =δ(x, y)

p ( x = 0) = p, p ( x = 1) = 1 ? p

R( D) = H ( p) ? H ( D)
36

第4章 信息率失真函数
R ( D ) = log

1

σ
D

2

R ( D ) = log

1 λD

3

R( D) = H ( p) ? H ( D)

R(D)
Dmax1 = σ 2

(2) H(p) (1)

Dmax 2 = 1 λ ?p Dmax 3 = ? ?1 ? p p < 1/ 2 p > 1/ 2

(3) 0 Dmax D

信息率失真函数R(D)
37

第4章 信息率失真函数

1

Dmax = min D j = min ∑ p(ai )d (ai , b j )
j j i =1

n

R(D) 计算 步骤

2 3 4 5 6 7


i =1

n

λi p ( a i ) e
=

sd ( a i ,b j )

=1

λi
p (b j )
p (b j | ai )

1

λi



m

j =1

p (b j )e

sd ( a i , b j )

p (b j | ai ) = p (b j )λi e
n m

sd ( ai ,b j )

D( s ) = ∑∑ p (ai ) p (b j | ai )d (ai , b j )
i =1 j =1

s(D)

R ( D ) = sD ( s ) + ∑ p ( ai ) log λi
i =1

n

验证 p(b j ai ) 是否大于等于零
38

第4章 信息率失真函数

例: 设输入输出符号表示为X=Y∈{0,1},输入概率 分布p(x)=(p,1-p),0<p≤1/2,失真矩阵为
? d (a1 , b1 ) d (a1 , b2 ) ? ?0 1? d =? ? = ?1 0? ? ?d (a2 , b1 ) d (a2 , b2 )? ?

求信息率失真函数R(D)

解: 1

Dmax = min D j = min ∑ p(ai )d (ai , b j )
j j i =1

n

D1 = (1? p)
2

D2 = p
sd ( a i ,b j )

Dmax = D2 = p


i =1

n

λi p ( a i ) e

=1
1 λ1 = p (1 + e s ) 1 λ2 = (1 ? p )(1 + e s )
39

λ1 p + λ2 (1 ? p)es = 1

λ1 pes + λ2 (1? p) = 1

第4章 信息率失真函数

3

1

λi

=



m

j =1

p (b j )e

sd ( a i , b j )

p(b1 ) + p(b2 )es = p(1 + es ) p(b1 )e s + p(b2 ) = (1 ? p)(1 + e s )

p ? (1 ? p)es p(b1 ) = 1 ? es (1 ? p ) ? pe s p (b2 ) = 1 ? es

4

p (b j | ai ) = p (b j )λi e

sd ( ai ,b j )

p ? (1 ? p)es p(b1 | a1 ) = p(1 ? e2s )
(1 ? p) ? pes p(b1 | a2 ) = p(1 ? e2s )
n m

p ? (1 ? p)es p(b2 | a1 ) = (1 ? p)(1 ? e2s )
(1 ? p) ? pes p(b2 | a2 ) = (1 ? p)(1 ? e2s )

5

D( s ) = ∑∑ p (ai ) p (b j | ai )d (ai , b j )
i =1 j =1

es D( s) = 1 + es

D s = log 1? D

40

第4章 信息率失真函数

6

R ( D ) = sD ( s ) + ∑ p ( ai ) log λi
i =1

n

R(D) = D log D + (1? D) log( ? D) ? p log p ? (1? p) log( ? p) 1 1
= H ( p) ? H (D)

容忍失真允许 压缩的信息率
R(D)/bit

1 ? ?H ( p) ? H ( D), 0 ≤ D ≤ p ≤ R( D) = ? 2 ?0, D≥ p ?
1.0 0.8 0.6 0.4 0.2 0.0 0.1 0.2 D 0.3 0.4 0.5
41

p=0.5 p=0.3 p=0.2 p=0.1


相关文章:
信息论与编码复习课
信息论与编码复习课_教育学_高等教育_教育专区。...第二章 离散信源及离散熵 2 n ? 单符号离散信...但放在前面可以使短码得到充分利用 第四章 离散信道...
信息论与编码复习
信息论与编码复习_教育学_高等教育_教育专区。信息...第四章无计算题,其余各章一题计 算题 三、考试...第二章信息的度量 考核内容: 1.自信息量、熵、互...
《信息论与编码》习题解答-第四章
信息论与编码》习题解答-第二章《信息论与编码》习题解答-第二章隐藏>> 《信息论与编码》习题解答 信息论与编码》信息率失真函数第四章 信息率失真函数-习题...
信息论与编码第4章
陈运 信息论与编码 第三章... 88页 免费 信息论与编码(第二版)陈运... 437页 10财富值 陈运 信息论与编码 第四章... 68页 免费 matlab第七讲教案 11...
信息论与编码-曹雪虹-第四章-课后习题答案
搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...信息论与编码-第二版-曹雪... 36页 免费 信息论...信息论与编码-曹雪虹-第四章-课后习题答案 信息论与...
信息论与编码复习题目(2016)
广工信息论编码论考试大纲 信息论复习提纲 第一章 绪论 1. 通信系统模型; 2....(二进制,三进制,四进制) ; 6. 本章所有讲过的例题; 第四章 离散信道容量...
信息论与编码 第四章 (1)
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...信息论与编码 第四章 (1)_工学_高等教育_教育...0.7 ] =0 4.18 N 个同样的二进制对称信道 ...
信息论与编码复习-新【学生】
信息论与编码复习-新【学生】_工学_高等教育_教育...信源编码定理) 第二章 信源与信息熵 知识点: 1...3-12 第四章 信息率失真函数 知识点: 1、 失真...
信息论与编码复习
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...信息论与编码复习_工学_高等教育_教育专区。信息论...k-1 个零组成,第二行为第一行向右平 移 1 位。...
信息论与编码复习总结
信源的描述:通过概率空间描述 平稳包含齐次,而齐次不包含平稳 (重要,第二章...信息论与编码课件复习总... 26页 免费 2012《信息论与编码》复... 6页 ...
更多相关标签: