第四章限失真信源与信息率失真函数R(D)§4-1 引言
(一)引入限失真的必要性:
1)失真在传输中是不可避免的;
2)接收者(信宿)无论是人还是机器设备,都有一定的分辨能力与灵敏度,超过分辨能力与灵敏度的信息传送过程是毫无意义的;
3)即使信宿能分辨、能判别,但对通信质量的影响不大,也可以称它为允许范围内的失真;
4)我们的目的就是研究不同的类型的客观信源与信宿,在给定的Qos要求下的最大允许(容忍)失真D,及其相应的信源最小信息率R(D).
5)对限失真信源,应该传送的最小信息率是R(D),而不是无失真情况下的信源熵H(U).
显然H(U)≥R(D).
当且仅当D=0时,等号成立;
6)为了定量度量D,必须建立信源的客观失真度量,并与D建立定量关系;
7)R(D)函数是限失真信源信息处理的理论基础;
(二) R(D)函数的定义
1) 信源与信宿联合空间上失真测度的定义:
)(j i v u d : ),0[∞→?+R V U
其中: U u i ∈ (单消息信源空间) V v j ∈ (单消息信宿空间) 则有
∑∑
=
i
j
u j i v
j i v u d v u p d )
()(
称d 为统计平均失真,它在信号空间中可以看作一类“距离”,它有性质
1〉0)(=j i v u d , 当 j i v u =
2〉0)(min ,=∈∈j i V
v U u v u d j
i
3〉∞<≤)(0j i v u d
对离散信源:i=j=1,2……..n,,)(ij j i d v u d = 则有:
?
?
?≠==)j(i 0,)
j(i ,0有失真当〉无失真当ij
d 若取 ij d 为汉明距离,则有:
?
?
?≠==)j(i ,1)
j(i ,0有失真当无失真当ij
d
对连续信源,失真可用二元函数d (u,v )表示。
则有:
v u v u v u d -=-=2
)
(),(
推而广之,d (u,v )可表示任何用v 表达u 时所引进的失真,误差,损失,风险,甚至是主观感觉上的差异等等。 进一步定义允许失真D 为平均失真的上界:
∑∑
∑∑
=
=
≥i
j
i
j
ij
ji i j i j i d P p v u d v u p d D ),(),(--对离散
在讨论信息率失真函数时,考虑到信源与信宿之间有一个无失真信道,称它为试验信道,对离散信源可记为
ji
P ,对限失真信源这一试验信道集合可定义为:
?
?
?
?
??
=
≥=∑∑
i
j
ij ji i ji D d P p d D P P : 根据前面在互信息中已讨论过的性质: );();(ji i P p I V U I =
且互信息是i p 的上凸函数,其极限值存在且为信道容
量:);(max ji i p
P p I C i
= 这里,我们给出其对偶定义:
);(m i n );(m i n )(ji i P
P P P P p I V U I D R D
ji
D
ji
∈∈== 即互信息是ji P 的下凸函数。其极限值存在且为信息率失真函数。
它还存在下列等效定义:
{}??
??
?≤==≥=∑∑∈)();(:min )(给定速率R V U I P P d P p d D R D ji R i j
ij ji i P P R
ji
称D(R)为失真信息率函数,是R(D)的逆函数,它是求在允许最大速率情况下的最大失真D 。
至此,我们已给定R(D)函数一个初步描述。
)(U H D
由定义,R(D)函数是在限定失真为最大允许失真为
D 时信源最小信息速率,它是通过改变试验信道ji p 特性(实际上是信源编码)来达到的。所以R(D)是表示不同D 值时对应的理论上最小信息速率值。
然而对于不同的实际信源,存在着不同类型的信源编码,即不同的试验信道特性'ji p 并可以求解出不同的信息率失真R ’(D)函数,它与理论上最佳的R(D)之间存在着差异,它反映了不同方式信源编码性能的优劣,这也正是R(D)函数的理论价值所在。特别对于连续信源,无失真是毫无意义的,这时R (D )函数具有更大的价值。
例:若有一个离散、等概率单消息(或无记忆)二元信源:21
)()(10==u p u p ,且采用汉明距离作为失真
度量标准:即?????≠==j
i j i ij
u u u u d
当当,
1,
0 若有一具体信源编码方案
为:N 个码元中允许错一个码元,实现时N 个码元仅送N-1个,剩下一个不送,在接收端用随机方式决定(为掷硬币方式)。此时,速率R ’及平均失真D 相应为:
D
N
N
D R N N D b N N N R 21212111)(',21211/111'-=?
-=-
=∴
=
?=-=-=符号
若已知这一类信源理论上的)
()2
1
()(D H H D R -=(后面将进一步给出计算),则有
D
阴影范围表示实际信源编码方案与理论值间的差
距,我们完全可以找到更好,即更靠近理论值,缩小阴影范围的信源编码,这就是工程界寻找好的信源编码的方向和任务。
§4-2 R(D)函数的性质
讨论R(D)性质以前先简要介绍R(D)的定义域。 对离散:[]max ,0D
对应R(D)值:)()(max )0(p H D R R ==
值
时即当D R D R D R 0),(min )(max →=。
对连续:[]max min ,D D
值
时即当D R D R D R p H D R c 0),
(min )()()(max min →=∞==
R(D)函数性质可用下列定理总结:
定理4-2-1:对离散、单个消息限定失真信源,其R(D)函数满足下列性质:
(1)R(D)是D 的下凸(?)函数; (2)R(D)是D 的单调非增函数; (3)R(D)是D 的连续函数; (4))()0(p H D R ==;
证明:(1)证明思路:根据R(D)函数定义,与下凸函数定义,只需证明:
)"()1()'(]")1('[D R D R D D D
R θθθθθ
-+≤-+=
首先证θ
θ
D ji P P ∈,再利用互信息对ji P 的下凸性。
即:若用ji
P '与ji P ''表示达到)'(D R 与)"(D R 时的条件分布,且"
')1(ji ji ji P P P θθθ-+= 则有:
ij ji ji
i
j
i ij ji i
j
i ji d P P p d P p P d ])1([)(''-+'=
=
∑∑
∑∑
θθθ
θ
θ
θθθθθθD D D P d P d d P p d P p ji ji
ij ji
i
j
i ij ji
i
j
i =-+≤''-+'=''-+'=∑∑
∑∑
")1(')()1()()1(
这里')(D P d ji
≤',")(D P d ji ≤'' 由})(:{θ
θθθD P d P P ji ji D ≤= 可得 θθ
D ji P P ∈
再利用互信息对ji P 的下凸性,有
)
"()1()'();()1();()
;();(min )(D R D R P p I P p I P p I P p I D R ji i ji
i ji i ji i P
P D
ji θθθθθ
θ
θθ
θ
-+=''-+'≤≤=∈ (2)设12D D ≥ 则12
D D P P ?
)
()()
;(m i n );(m i n 121
2
D R D R P p I P p I ji i P P ji i P P D
ji D
ji ≤∴
≤∴
∈∈
即R(D)是D 的单调非增函数。 (3)设D D D D →→+='0
'δδ
当。
由D P 定义,有D D P P →'。
同时,由于);(ji i P p I 是ji P 连续函数。 即当,0→ji P δ 有);();(ji i ji ji i P p I P P p I →+δ
)
;(min )();(min )'('
ji i P P ji ji i P P P p I D R P P p I D R D
ji D ji ∈∈=→+=∴δ 即)()'(D R D R →,R (D )是D 的连续函数。 (4)当0=D ,即无失真时,j i v u ?,一一对应
???≠===时,
,
时,
j i j i P ij
ji 0,1δ )
(1log
log
);()
;()0(p H p p p p p I P p I R j
i i
i i
ij
ij i
j
i ij i ji i ==
===∴∑
∑∑
=δδδ
§4-3 离散信源R (D )函数计算:
);(m i n )(ji i P
P p p I D R D
ji
∈= 可见,求解R(D)实质上是求解互信息的条件极值,可采用拉氏乘子法求解。但是,在一般情况下只能求得用参量(R(D)的斜率S )来描述的参量表达式,并借助计算机进行迭代运算。 由信道容量C 与R(D)数
)
;(min )()
;(max V U I D R Y X I C D
ji i
P P p ∈==
其迭代运算与求信道容量迭代运算相仿的。在正式讨论R(D)迭代运算前,这里,我们先介绍特殊情况下的R(D)计算。
具有等概率、对称失真信源的R(D)计算:
例1:有一个二元等概率平稳无记忆信源U ,且失真函数为:
1
2
1
??
??
?
??∞∞=011
)(ij d
试求其R(D)=? 解:由:ij
ji i
j
i d P p d D ∑∑
=
≥
为了运算方便,取ij
ji i
j
i d P p D ∑∑
=
上式中,已知:21
=i p ,D (允许失真)给定。
则ij ji d P ?一一对应。
这时,由概率归一性,可进一步假设:
???
? ?
?--=A A
A A P ji 10
01 可见:???
???∞-??0
110A
A
代入上述公式,有
)
1()1(2
1)1(2
1]
1)1(00[2
1]1)1(00[21A A A A A A A d P p D ij
ji i
j
i -=-+
-=
?-+?+∞?+?-+∞?+?==
∑∑
再将它代入转移概率公式中:
??? ?
?--=D D
D D P ji 10
1
由:∑
=
i
ji i j P p q ,得:)2
1,
,2
1(
)(D D D q j --=
则:)
2
1,
,2
1()()(D D D
H q H V H j --==
),1()()/(D D H P H U V H ji -==
2
log )1()1log()1()1log()1(2log )1(log )1log()1(log 2
1log
212)
,1(21,
,21(
)]/()([)
;()(D D D D D D D
D D D D D D
D
D D H D D D H U V H V H V U I D R D D -=--+----=+--+--?
=----=-==∴--)参量
参量
0=D 1
=D
例2:若有一个n 元等概率、平稳无记忆信源U ,且规定失真函数为:
1
12
2
n
n
????????
?
??------=01
11
11101
1
11110)(
n n n n n n d ij
试求R (D )=? 解:
?
????
??
?
??----=?????????
??--=
A n A
A
n A A P n n d ji ij 1
111)(01
10
11
0)(
由n p i 1
=,求得
A
n
A n n n A n n d P p D i
j
ij ji i -=??
+?--?
-==
∑∑
101)
1(1)1(n
n A n n n
P p q i
ji i j 1]1
1)1(1[1=
--?
-+?=
=
∑
∴参量
参量
D ji j D P H q H V U I D R )]()([)
;()(-==
)1
1,1()1
1
(----=n D
n D
D H n n H
1
log
1
)
1()1log()1(log ---+--+=n D n D n D D n )1l o g ()1,(l o g
----=n D D D H n 取2=n ,4,8,有
D
由上图可见 无失真0
=D 时
bit p H R n 3)()0(8===, , bit p H R n 2)()0(4===, ,
bit
p H R n 1)()0(2===, ,
有失真,比如2
.0=D
时
OF
OE K n OD OC K n OB OA K n =
=====248248,压缩比:
,压缩比:,压缩比:
显然 ① 842K K K >>,进制n 越小,压缩比K 越大;
② ↑↑K D ,,但相对关系不变, 允许失真D 越大,压缩比亦越大。
R (D )的参量表达式:
要讨论R(D)的计算,由R(D)函数定义,需要求下列约束条件下的互信息极值。 ①
};
:{D d d P p P P i
j
ij ji i ji D ≤==∑
∑
② 211;,,,对n i i P j
ji =?=∑
③ ;,,,,对m j n i j i P ji 110==?≥
求解这类极值有好几种方法:
变分法、拉氏乘子法、凸规划方法等等。这里引用最简单的拉氏乘子法。但是它不能处理不等式约束关系,因此需对上述条件进行必要的修改,这时上述问题可归纳为在下列)1(+n
组约束条件下:
)组约束(,,,对12111
+????
???=?===∑∑∑=n n i i P d P p d D m
j ji i j
ij ji i
求互信息j
ji i
j
ji i ji j q P P p P q I ∑∑
=
log
)
;(的极小值。
引用拉氏乘子法,并设S 与),n i i 21(=μ分别表
示)1(+n 个约束条件的待定参数,则有:
)log 1()log 1(0
]);([=--+++-=-
-??∑∑i ij i i ji i j j
ji
i
i ji i ji
d Sp p P p q P
SD P p I P μμ
求得 ij
Sd
i j ji e
q P λ= —— ①
由归一化条件有
∑
∑
=
=
j
Sd i j i
ji ij
e
q P λ1
求得
∑
=
j
Sd j i ij
e
q 1
λ —— ②
再将①式两边同乘i p 并对i 求和,且设q j >0,则有
∑
∑
=
=
i
Sd i j i i
ji i j ij
e
q p P p q λ
∴ 1=∑
i
Sd i i ij
e
p λ
—— ③
代②入③,得: 1
1
=∑∑
ij
ij
Sd j
Sd j
i
i
e
e
q
p —— ④
当信源给定0
i
i p p =,选定S 与ij d 以后,它是一个求解m
个j q 的方程组,则可按下列顺序求解:
)()(),1()2,1(S R S D P n i m j q ji i j →→?→?=?→?= λ
最后求得参量方程如下:
???
?
??
???==∑∑∑∑i j j Sd i j Sd i
j i i j ij Sd i j i q e q e q p S R d e q p S D ij ij ij λλλlog )( )(— ⑤— ∑+=i
i i p S SD λlog () —— ⑥
这就是用参量s [)(D R 的斜率]表达的)(D R 函数形式,又称为参量方程。
定理4-3-1:S
D R =)(',即R(D)斜率为参量S 。证明从
略。
例:引用上述参量方程求解一个二进不等概率离散信源:p p p p -==
121,,且?
??≠==,,当,,当j i j i d ij
10其中21,,=j i ,试求?)(=D R
解:首先求参量1
λ与2
λ
由公式③,有:
???=+=+1)exp()exp(1
)exp()exp(2222121
121221111Sd p Sd p Sd p Sd p λλλλ 求得
]
1)[1(1
]
1[121S
S
e p e p +-=
+=λλ 将它带入式②,有
???
???
?
=+=+2
2222111
1221111
)exp()exp(1
)exp()exp(λλSd q Sd q Sd q Sd q
求得
S
S S
S
e
pe
p q e e
p p q ---=
---=
1)1(1)1(21
再将2121q q ,λλ带入⑤式)(S D 中:
)exp()exp()(12122111111111Sd d q p Sd d q p S D λλ+=
)exp()exp(22222222121122Sd d q p Sd d q p λλ++ S S
e e
+=1? D D
S -=1log 再将它带入)(S R ,有:
D
D S D
D S p p S SD S R D R -=-=-++==1log
2
11log
log )1(log )()()(λλ ]1,[]1,[)]
1log()1(log [)]1log()1(log [D D H p p H D D D D p p p p ---=--++--+-=
取
8
14121,
,=p ,的曲线:
0.6
D
由图可见:
无失真:bit R D 1002
1==)(,
bit R 8.004
1=)(
bit R 6.008
1=)( 限失真,比如1.0=D 时
17
.06.045
.08.067
.00.18
14
12
1=
<=
<≈
K K K
结论:1) 信源概率分布越不均匀,压缩比越大;
2) D
越大,压缩比也越大。
R (D )函数的迭代算法
首先让我们从信道容量C 与)(D R 函数定义与数学上的对偶性来分析:
)
;(max )()
;(max )();(max Y X I F C V U I D R Y X I C i
i i D
ji i
F
f p P P p ∑===≤∈,
显然,我们可以利用求解信道容量的计算迭代公式的方法与思路求解)(D R 函数。其关键步骤为:
1)寻求两个决定互信息的互为因果关系的自变量对,这里选0
),;(i
i ji j p p P q I = ,且通过ji P 求极值;
2)对互信息求条件极值(极小值),引用拉氏乘子法;
具体求解步骤如下:
1) 两个自变量中首先固定ji P 值,则在满足1
=∑j
j q 和∑∑=i
j
ij ji i d P p D 的约束条件下求);(ji j P q I 的极小值。
引用拉氏乘子法,有:0
]);([=+-??
∑j
j ji j j
q SD P q I q λ 即 0=+-∑λi
j
ji
i
q P p , 求得:
∑=
i
ji
i j P p q λ
1
,再由归一化条件
λλ
1
11=
=
=
∑∑∑i
j
ji i j
j
P p q
? 1=λ, 再代入原式得: ∑=
i
ji
i
j P
p q *
—— ①
2) 再固定j q 值,在满足1=∑j
ji P (对所有i 值)和
∑∑=
i
j
ij
ji
i
d P
p D 的约束条件下求);(ji j P q I 极值:
]);([=+-??
∑∑i j ji i ji j ji
P SD P q I P λ 0
]log
1[=+-+i ij i j
ji i d Sp q P p λ
?)]
1(
exp[+-=i
i
ij j ji p Sd q P λ
由归一化条件,有
∑∑+-?=
=
j
p Sd
j
j ji
i
i
ij
e
e
q
P
][1]
1[
λ
求出:
∑
=
+-j
Sd
j p ij
i
i
e
q e 1
]
1[
λ
再将它带入ji
P 表达式,求得
∑=
j
Sd j
Sd
j ji ij
ij
e
q
e
q P *
——②
① 式与②式是两个基本迭代公式 若假设一个S 值,比如1S S =,通过①②逐次迭代,
求得)(),(1*
1*
S P S q ji j ,代入互信息公式中,求得
)](),([)(1*
1*
1S P S q I S R ji j =
再继续假设2S S =、3
S 、4S 、5
S 等。求得相应的)(2S R 、)(3S R 、)(4S R 、)(5S R 。最后再将其值连成一个曲线,即为)
(D R 函
数曲线。
下面,为了迭代方便,可将①②改写为:
迭代公式
— ④—— ③—?
??
????==∑∑+j Sd n j Sd
n j n ji i n
ji i n j ij
ij e q e q P P p q 1
假设1S S =,则可按下列顺序迭代:(当信源给定0
i
i
p p =,
选一初始分布m
P ji 11
=
)
4.1 一个四元对称信源? ?????=??????4/14/1324/14/110)(X P X ,接收符号Y = {0, 1, 2, 3},其失真矩阵为????? ???????0111 101111011110,求D max 和D min 及信源的R(D)函数,并画出其曲线(取4至5个点)。 解: 0041041041041),(min )(43041141141141),()(min min min max =?+?+?+?===?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 因为n 元等概信源率失真函数: ?? ? ??-??? ??-+-+=a D a D n a D a D n D R 1ln 11ln ln )( 其中a = 1, n = 4, 所以率失真函数为: ()()D D D D D R --++=1ln 13 ln 4ln )( 函数曲线: D 其中: symbol nat D R D symbol nat D R D symbol nat D R D symbol nat R D /0)(,4 3/12ln 2 14ln )(,21/3 16ln 214ln )(,41/4ln )0(,0==-==-==== 4.2 若某无记忆信源??????-=??????3/113/13/101)(X P X ,接收符号??????-=21,21Y ,其失真矩阵???? ??????=112211D 求信源的最大失真度和最小失真度,并求选择何种信道可达到该D max 和D min 的失真度。
4.1 一个四元对称信源? ?????=??????4/14/1324/14/110)(X P X ,接收符号Y = {0, 1, 2, 3},其失真矩阵为????? ???????0111 101111011110,求D max 和D min 及信源的R(D)函数,并画出其曲线(取4至5个点)。 解: 0041041041041),(min )(43041141141141),()(min min min max =?+?+?+?===?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 因为n 元等概信源率失真函数: ?? ? ??-??? ??-+-+=a D a D n a D a D n D R 1ln 11ln ln )( 其中a = 1, n = 4, 所以率失真函数为: ()()D D D D D R --++=1ln 13 ln 4ln )( 函数曲线: D 其中: sym bol nat D R D sym bol nat D R D sym bol nat D R D sym bol nat R D /0)(,4 3/12ln 2 14ln )(,21/3 16ln 214ln )(,41/4ln )0(,0==-==-==== 4.2 若某无记忆信源??????-=??????3/113/13/101)(X P X ,接收符号??????-=21,21Y ,其失真矩阵???? ??????=112211D 求信源的最大失真度和最小失真度,并求选择何种信道可达到该D max 和D min 的失真度。 4.3 某二元信源??????=??????2/12/110)(X P X 其失真矩阵为?? ????=a a D 00求这信源的D max 和D min 和R(D)
第八章 限失真信源编码 8.1设信源X 的概率分布P(X):{p(α1), p(α2), …,p(αr ) },失真度为d (αi , βj )≥0,其中 (i=1,2,…,r;j=1,2,…,s).试证明: ∑==r i j i j i b a d a p D 1 min )},(min ){( 并写出取得min D 的试验信道的传输概率选取的原则,其中 ))}/(,),/(),/({min ),(min 21i S i i j j i j a b p a b p a b p b a d = (证明详见:p468-p470) 8.2设信源X 的概率分布P(X):{p(α1), p(α2), …,p(αr ) },失真度为d(αi , βj )≥0,其中 (i=1,2,…,r;j=1,2,…,s).试证明: }),()({min 1 max ∑==r i j i i j b a d a p D 并写出取得max D 的试验信道传递概率的选取原则. (证明详见:p477-p478) 8.5设二元信源X 的信源空间为: -1 )( 1 0X :][X ????ωωX P P 令ω≤1/2,设信道输出符号集Y:{0,1},并选定汉明失真度.试求: (1) D min ,R(D min ); (2) D max ,R(D max ); (3) 信源X 在汉明失真度下的信息率失真函数R(D),并画出R(D)的曲线; (4) 计算R(1/8). 解: {}{}{}{}0 )()(0);()1()}0();1({min )1,1()1()1,0()0(;)0,1()1()0,0()0(min ),()(min )2() ()()/()(min );(min )0()(0 )/(),2,1(1)/(0)/(100110][1 0 00 0)1(0)0(),(min )()1(max 21min max min min 2 1 min ==∴====++=? ?? ???=' ===-===∴====?? ?? ??===?+?==∑∑==ωω ωR D R Y X I p p p d p d p d p d p b a d a p D D H X H Y X H X H Y X I R D R Y X H i a b p a b p P D D p p b a d a p D j j i j i i j i j i j i j i j i 此时故此时或的信道矩阵 则满足保真度=最小允许失真度:
第四章信息率失真函数(第九讲) (2课时) 主要内容:(1)平均失真和信息率失真函数(2)离散信源和连续信源的R(D)计算重点:失真函数、平均失真、信息率失真函数R(D)、信息率失真函数的计算。 难点:信息率失真函数R(D)、信息率失真函数的计算。 作业:4、lo 说明:本堂课推导内容较多,枯燥平淡,不易激发学生兴趣,要注意多讨论用途。另外,注意,解题方法。多加一些内容丰富知识和理解。 §4-1引言 (一)引入限失真的必要性: 失真在传输中是不可避免的; 接收者(信宿)无论是人还是机器设备,都有一定的分辨能力与灵敏度,超过分辨能力与灵敏度的信息传送过程是毫无意义的; 即使信宿能分辨、能判别,但对通信质量的影响不大,也可以称它为允许范围内的失真; 我们的目的就是研究不同的类型的客观信源与信宿,在给定的Qos要求下的最大允许(容忍)失真D,及其相应的信源最小信息率R(D). 对限失真信源,应该传送的最小信息率是R(D),而不是无失真情况下的信源爛H(U). 显然H(U)2R(D). 当且仅当D=0时,等号成立; 为了定量度量D,必须建立信源的客观失真度量,并与D建立定量关系; R(D)函数是限失真信源信息处理的理论基础; (二)R(D)函数的定义 信源与信宿联合空间上失真测度的定义:d (见叩:t/xV^/r[0,oo) 其屮:u*U(单消息信源空I'可) v y eV (单消息信宿空间) 则有 万=Y工〃(吧 称7为统计平均失真,它在信号空I'可屮可以看作一类“距离”,它有性质 1〉= 0,当比=Vj 2〉min 〃(吧)=°
3〉05〃(比/匕)<00 对离散信源:i=j=l,2............. n , d(upj) = djj, 则有: d 」0,当;可(无失真) 厂]〉0,当iHj (有失真) 若取冷为汉明距离,则有: Jo,当i = j (无失真) 厂[1,当iHj (有失真) 对连续信源,失真可用二元函数d(u,v)表示。 推而广之,d(u,v)可表示任何用V 表达U 时所引进的失真,误差,损失,风险,甚至是 主观感觉 上的差异等等。 进一步定义允许失真D 为平均失真的上界: D>d =工=工工〃£皿???对离散 ? ? ? ? 在讨论信息率失真函数时,考虑到信源与信宿之I'可有一个无失真信道,称它为试验信 道,对离散信源可记为p 〃,对限失真信源这一试验信道集合可定义为: P D =\P ji -D>d = YLP :P J^ 根据前面在互信息中已讨论过的性质: 1(U\ I,p ;j\ 且互信息是门的上凸函数,其极限值存在且为信道容量:C = max/(卫: p< ? 这里,我们给出其对偶定义: R(D)= mi 1Y U # ) m"pQp2,_ D P j f P D 陆 j i P D 即互信息是◎的下凸函数。其极限值存在且为信息率失真函数。 它还存在下列等效定义: D(R) = minD>d =工工门叽 < P 泸 P R i J P R = {? : /(t/;V) < R (给定速率)} 称D(R)为失真信息率函数,是R(D)的逆函数,它是求在允许最大速率情况下的最大 失真Do 至此,我们已给定R(D)函数一个初步描述。 则有: d(u. v)= (w-仍 H = \u-v
7.1 设输入符号集为}1 ,0{=X ,输出符号集为}1 ,0{=Y 。定义失真函数为 1 )0,1()1,0(0)1,1()0,0(====d d d d 试求失真矩阵D 。 解: 041 041041041),(min )(43 0411********),()(min min min max =?+?+?+?=== ?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 7.2 设输入符号集与输出符号集为}3 ,2 ,1 ,0{==Y X ,且输入信源的分布为 )3 ,2 ,1 ,0( 4 1 )(===i i X p 设失真矩阵为 []????? ???? ???=01 11 101111011110d 求D max 和D min 及R(D)。 解: 041 041041041),(min )(43 0411********),()(min min min max =?+?+?+?=== ?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 因为n 元等概信源率失真函数: ?? ? ??-??? ??-+-+=a D a D n a D a D n D R 1ln 11ln ln )( 其中a = 1, n = 4, 所以率失真函数为: ()()D D D D D R --++=1ln 13 ln 4ln )( 7.3 利用R(D)的性质,画出一般R(D)的曲线并说明其物理含义?试问为什么R(D)是非负且非增的? 解: 函数曲线:
第五章无失真信源编码定理与编码 5.1.1 信源编码和码的类型 1.信源编码 2.码的类型 若码符号集中符号数r=2称为二元码,r=3称为三元码,……,r元码。 若分组码中所有码字的码长都相同则称为等长码,否则称为变长码。 若分组码中所有码字都不相同则称为非奇异码,否则称为奇异码。 若每个码符号x i∈X的传输时间都相同则称为同价码,否则称为非同价码。 若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号序列则称为唯一可译码,否则称为非唯一可译码。 若分组码中,没有任何完整的码字是其他码字的前缀,则称为即时码(又称非延长码或前缀条件码),否则称为延长码。 本章主要研究的是同价唯一可译码。 5.1.2 即时码及其树图构造法 即时码(非延长码或前缀条件码)是唯一可译码的一类子码。 即时码可用树图法来构造。构造的要点是: (1)最上端为树根A,从根出发向下伸出树枝,树枝总数等于r,树枝的尽头
为节点。 (2)从每个节点再伸出r枝树枝,当某节点被安排为码字后,就不再伸枝,这节点为终端节点。一直继续进行,直至都不能伸枝为止。 (3)每个节点所伸出的树枝标上码符号,从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。 即时码可用树图法来进行编码和译码。 从树图可知,即时码可以即时进行译码。 当码字长度给定,即时码不是唯一的。 可以认为等长唯一可译码是即时码的一类子码。 5.1.3 唯一可译码存在的充要条件 (1)对含有q个信源符号的信源用含r个符号的码符号集进行编码,各码字的码长为l1,l2,…,l q的唯一可译码存在的充要条件是,满足Kraft不等式 5.1.4 唯一可译码的判断法 唯一可译码的判断步骤: 首先,观察是否是非奇异码。若是奇异码则一定不是唯一可译码。 其次,计算是否满足Kraft不等式。若不满足一定不是唯一可译码。 再次,将码画成一棵树图,观察是否满足即时码的树图的构造,若满足则是唯一可译码。 或用Sardinas和Patterson设计的判断方法:计算出分组码中所有可能的尾
4.1 一个四元对称信源,接收符号Y = {0, 1, 2, 3},其失??????=??????4/14/1324/14/110)(X P X 真矩阵为,求D max 和D min 及信源的R(D)函数,并画出其曲线(取4至5个点)。????????????0111101111011110解: 0041041041041),(min )(43041141141141),()(min min min max =?+?+?+?===?+?+?+?===∑∑i j i j i i j i i j j y x d x p D y x d x p D D 因为n 元等概信源率失真函数:??? ??-??? ??-+-+=a D a D n a D a D n D R 1ln 11ln ln )(其中a = 1, n = 4, 所以率失真函数为: ()()D D D D D R --++=1ln 13ln 4ln )(函数曲线: D 其中:symbol nat D R D symbol nat D R D symbol nat D R D symbol nat R D /0)(,43/12ln 214ln )(,21/316ln 214ln )(,41/4ln )0(,0==-==-====4.2 若某无记忆信源,接收符号,其失真矩阵求信??????-=??????3/113/13/101)(X P X ??????-=21,21Y ??????????=112211D 源的最大失真度和最小失真度,并求选择何种信道可达到该D max 和D min 的失真度。
4.3 某二元信源其失真矩阵为求这信源的D max 和D min 和R(D)??????=??????2/12/110)(X P X ?? ????=a a D 00函数。解:0021021),(min )(202121),()(min min min max =?+?===?+?===∑∑i j i j i i j i i j j y x d x p D a a y x d x p D D 因为二元等概信源率失真函数:??? ??-=a D H n D R ln )(其中n = 2, 所以率失真函数为: ????????? ??-??? ??-+-=a D a D a D a D D R 1ln 1ln 2ln )(4.4 已知信源X = {0, 1},信宿Y = {0, 1, 2}。设信源输入符号为等概率分布,而且失真函数,求信源的率失真函数R(D)。??????∞∞=1100D 4.5 设信源X = {0, 1, 2, 3},信宿Y = {0, 1, 2, 3, 4, 5, 6}。且信源为无记忆、等概率分布。失真函数定义为 证明率失真函数R(D)如图所示。???????∞ ======且且且且53,21 41,010),(j i j i j i y x d j i log22log2D 4.6 设信源X = {0, 1, 2},相应的概率分布p (0) = p (1) = 0.4,p (2) = 0.2。且失真函数为)2,1,0,(10),(=???≠==j i j i j i y x d j i (1) 求此信源的R(D); (2) 若此信源用容量为C 的信道传递,请画出信道容量C 和其最小误码率P k 之间的曲线关系。 4.7 设0 < α, β < 1, α + β = 1。试证明:αR(D’) +βR(D”) ≥ R(αD’ +βD”) 4.8 试证明对于离散无记忆N 次扩展信源,有R N (D) = NR(D)。其中N 为任意正整数,D ≥ D min 。 4.9 设某地区的“晴天”概率p (晴) = 5/6,“雨天”概率p (雨) = 1/6,把“晴天”预报为“雨天”,把“雨天”预报为“晴天”造成的损失为a 元。又设该地区的天气预报系统把“晴天”预报为“晴天”,“雨天”预报为“雨天”的概率均为0.9;把把“晴天”预报为“雨天”,把“雨天”预报为“晴天”的概率均为
第6章 限失真信源编码 一、例题: 【例6.1】 二元对称信源,信源{0,1}U =,接收变量{0,1}V =,在汉明失真定义下,失真函数为: (0,0)(1,1)0d d ==,(0,1)(1,0)1d d == 其失真矩阵为 011 0??=? ??? D 容易看出:对于离散对称信源,其汉明失真矩阵D 为一个方阵,且对角线上的元素为零,即: 011110111 1011 1 1 0?? ??????=???????? D 【例6.2】 信源U ={0,1,2},接收变量V ={0,1,2},失真函数为2 (,)()i j i j d u v u v =-,求失真矩阵。由失真定义得: d (0,0)=d (1,1)=d (2,2)=0 d (0,1)=d (1,0)=d (1,2)=d (2,1)=1 d (0,2)=d (2,0)=4 所以失真矩阵D 为 141 014 1 4?? ??=?????? D 【例 6.3】 离散无记忆信源输出二维随机序列12()U U =U ,其中(1,2)i U i =取自符号集 {0,1},通过信道传输到信宿,接收N 维随机序列12()V V =V ,其中(1,2)i V i =取自符号集
{0,1},定义失真函数 (0,0)(1,1)0(0,1)(1,0)1 d d d d ==== 求符号序列的失真矩阵。 解: 由N 维信源序列的失真函数的定义得 1 1(,)(,)(,) ,k k N N N i j i j k d d d u v N αβ=== ∈∈∑u v u U v V 所以 [][]1(00,00)(0,0)(0,0)0211(00,01)(0,0)(0,1)2 2 N N d d d d d d =+== += 类似计算其他元素值,得到信源序列的失真矩阵为 11012211012211102211102 2 N ??????????=? ?????????? ? D 【例6.4】 设信源符号有8种,而且等概率,即1()8 i P u = 。失真函数定义为 0(,)1i j i j d u v i j =?=?≠? 假如允许失真度12 D =,即只要求收到的符号平均有一半是正确的。我们可以设想这 样的方案: 方案一:对于1234,,,u u u u 这四个信源符号照原样发送,而对于5678,,,u u u u 都以4u 发送。如图6.1(a )所示。 方案二:对于1234,,,u u u u 这四个符号照原样发送,而对于5678,,,u u u u 分别以 1234,,,u u u u 发送。如图6.1(b )所示。
第四章 信息率失真函数 无失真信源编码和有噪信道编码告诉我们:只要信道的信息传输速率 R 小于信道容量 C ,总能找到一种编码方法,使得在该信道上的信息传输的差错概率 P e 任意小;反之,若信道的信息传输速率大于信道容量,则不可能使信息传输差错概率任意小。但是,无失真的编码并非总是必要的。无失真的编码并非总是可能的。在实际信息传输系统中,失真是不可避免的,有时甚至是必须的。 香农首先定义了信息率失真函数R(D),并论述了关于这个函数的基本定理。定理指出:在允许一定失真度D 的情况下,信源输出的信息传输率可压缩到R(D)值,这就从理论上给出了信息传输率与允许失真之间的关系,奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。 本章主要介绍信息率失真理论的基本内容,侧重讨论离散无记忆信源。首先给出信源的失真度和信息率失真函数的定义与性质;然后讨论离散信源和连续信源的信息率失真函数计算;在这基础上论述保真度准则下的信源编码定理。 1 失真测度 1.1 失真度 从直观感觉可知,若允许失真越大,信息传输率可 越小;若允许失真越小,信息传输率需越大。所以信息传输率与信源编码所引起的失真(或误差)是有关的。 离散无记忆信源U ,信源变量U ={u1,u2,…ur},概率分布为P(u)=[P(u1),P(u2),…P(ur)] 。 信源符号通过信道传输到某接收端,接收端的接收变量V = {v1,v2,…vs} 。 对应于每一对(u,v),我们指定一个非负的函数: 称为单个符号的失真度(或失真函数)。 通常较小的d 值代表较小的失真,而d(ui,vj)=0表示没有失真。 若信源变量U 有r 个符号,接收变量V 有s 个符号,则d(ui,vj)就有r ×s 个,它可以排列成矩阵形式,即: 它为失真矩阵D ,是 r ×s 阶矩阵。 须强调: 这里假设U 是信源,V 是信宿,那么U 和V 之间必有信道。实际这里U 指的是原始的未失真信源,而V 是指失真以后的信源。因此,从U 到V 之间实际上是失真算法,所以这里的转移概率p(vj/ui)是指一种失真算法,有时又把p(vj/ui) 称为试验信道的转移概率,如图所示: j i j i v u d j i ≠=???>=)0(0),(α????????????=),(...),(),(:...::),(...),(),(),(...),(),(212221212111s r r r s s v u d v u d v u d v u d v u d v u d v u d v u d v u d D
第四章 信息率失真函数(第九讲) (2课时) 主要内容:(1)平均失真和信息率失真函数(2)离散信源和连续信源的R(D)计算 重点:失真函数、平均失真、信息率失真函数R(D)、信息率失真函数的计算。 难点:信息率失真函数R(D)、信息率失真函数的计算。 作业:4、1。 说明:本堂课推导内容较多,枯燥平淡,不易激发学生兴趣,要注意多讨论用途。另外,注意,解题方法。多加一些内容丰富知识和理解。 §4-1 引言 (一) 引入限失真的必要性: 失真在传输中是不可避免的; 接收者(信宿)无论是人还是机器设备,都有一定的分辨能力与灵敏度,超过分辨能力与灵敏度的信息传送过程是毫无意义的; 即使信宿能分辨、能判别,但对通信质量的影响不大,也可以称它为允许范围内的失真; 我们的目的就是研究不同的类型的客观信源与信宿,在给定的Qos 要求下的最大允许(容忍)失真D ,及其相应的信源最小信息率R(D). 对限失真信源,应该传送的最小信息率是R(D),而不是无失真情况下的信源熵H(U). 显然 H(U)≥R(D). 当且仅当 D=0时,等号成立; 为了定量度量D ,必须建立信源的客观失真度量,并与D 建立定量关系; R(D)函数是限失真信源信息处理的理论基础; (二) R(D)函数的定义 信源与信宿联合空间上失真测度的定义:()i j d u v : [0,)U V R + ?→∞ 其中: i u U ∈ (单消息信源空间) j v V ∈ (单消息信宿空间) 则有 ()()i j i j i j u v d p u v d u v =∑∑ 称d 为统计平均失真,它在信号空间中可以看作一类“距离”,它有性质 1〉()0i j d u v =, 当i j u v = 2〉 ,()0min i j i j u U v V d u v ∈∈=