第10讲 信源编码的性能指标Word文档下载推荐.docx
《第10讲 信源编码的性能指标Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《第10讲 信源编码的性能指标Word文档下载推荐.docx(5页珍藏版)》请在冰点文库上搜索。
定义设f是一个N-分组码,各码字的码长分别记为li,1?
i?
q,对应的N长分组的概率为pi,则f的平均码长定义为 1qL?
pili(码元/信源) Ni?
1 注:
在有的教材中,当平均码长的单位转化为“比特/信源”时,称为编码速率。
本课程用不到这个概念。
讨论:
用平均码长估计编码后的数据长度 设S是一个离散无记忆信源,f:
S?
C是信源S的一个编码,其平均码长为L。
令假设用f对该数据进行编码,试估计编码后码元序列的长度。
s?
s1s2?
sn是一个信源序列。
对于信源数据s?
sn,我们令Li表示信源符号si所对应的码字f(si)的长度,则编码后的数据长度为L1+L2+我们把Li视为随机变量,则对于任何i,我们有E[Li]?
L。
+Ln。
1/6 因为S是离散无记忆的,所以{Li}是独立同分布随机序列。
根据辛钦大数定理,我们有 1设S是具有AEP性质的信源,f是S的一个平均码长为L的无失真N-分组码。
假设在编码f下,某数据在编码前的长度为n信源,在编码后的长度为m码元,则 mP?
L(n?
)n意义:
信源序列长度n越大,编码后所得的码元序列的长度越有可能近似于nL(码元)。
3.码率和编码效率 定义码率:
编码后的信息传输率H∞(X),记为R,单位是“比特/码元”。
下列定理给出了无失真编码的码率计算公式。
定理设S是具有AEP性质的信源,f是信源S的无失真编码。
若S的熵率为H∞,f的平均码长为L,则f的码率为 R?
H?
L证明:
记编码后的信源为X。
根据定义,X的熵率为码率R。
用Sk,Xk分别表示信源S和X所产生的信源序列中的第k个符号。
根据渐近等分性定理, 1I(S1S2nPSn)?
(1) 于S具有渐近等分割性,易知X也具有渐近等分割性。
于是我们有 1I(X1X2m其中X1X2PXm)?
R
(2) Xm为S1S2Sn经编码后的码元序列,故有 Sn)?
I(X1X2Xm). I(S1S2根据依概率收敛的性质,和
(2)得 mPH?
.?
nR码2/6 再前面的编码后数据长度定理, mP?
L.n于是我们得L?
HH?
,即R码?
。
证毕R码L 定义编码效率:
对于编码f来说,编码后信源X的信息传输效率称为f的编码效率,记为?
f。
因此, ?
f?
X?
H0?
码率和编码效率是信源编码的两个重要性能指标,其值越大,则编码的数据压缩能力越强。
注意,对于无失真信源编码来说,提高编码效率与数据压缩是一回事。
而对于限失真信源编码来说,除了通过提高编码效率来实现数据压缩之外,还通过量化方法缩小信源熵率,为后面的无失真压缩提高更大的压缩空间。
提问:
码率与编码效率的的最大值分别是多少?
试确定码率与编码效率的之间的数量关系。
答:
码率最大值=码元最大熵H0(X),从而最大编码效率=H0(X)/H0(X)=1。
编码效率=码率/码元最大熵。
定义编码冗余度:
度量信源编码与理想编码之间的差距,定义为 编码冗余度=最大码率-码率 编码相对冗余度=编码冗余度/最大码率=1-编码效率 4.压缩率 根据第8讲的渐近等分割性定理,对于足够长的的数据,我们有如下近似关系:
数据长度?
数据信息量 信源熵率数据越长,该近似关系越准确和可信。
根据该近似关系,读者可以看出,在信息量不变的前提下,熵率越大,数据越短。
因此,提高熵率所带来的结果就是数据压缩。
压缩效果用压缩率来度量,定义为 压缩率=编码后的数据长度 编码前的数据长度3/6 数据压缩率:
对于一个数据x,其以比特为单位的长度称为x的比特数,记为l(x)。
x 经过编码后的比特数记为L(x)。
x的在此编码下的压缩率定义为 ?
(x)?
L(x)l(x)无失真信源编码压缩率:
教材上都没有定义。
能否给出一个合理的定义?
设f是信源S的无失真编码,s是S的一个信源序列,x是 在编码f下所得的码元序列。
令s的长度是n,即nH0(S)比特。
令x的长度是m,即mH0(X)比特。
则s在f下的压缩率为 mH0?
nH0?
根据渐近等分割性,我们有 I(s)PI(x)P?
(S)和?
(X)nm于编码是无失真的,故I(s)=I(x)。
因此, mPH?
(S)?
nH?
(X)mH0(X)PH?
(S)H0(X)?
nH0(S)H?
(X)H0(S)即 mH0(X)P?
nH0(S)?
X其中?
S是信源S的信息传输效率,?
X是编码后信源X的信息传输效率,即编码效率。
这个收敛关系表明,当信源序列足够长时,其数据压缩率很有可能近似于信源效率比上编码效 率。
因此,这个常数可以度量编码f的压缩效果。
因此,我们定义无失真信源编码的压缩效率如下:
无失真信源的压缩效率=信源效率/编码效率 因此,编码效率越大,则压缩能力越强。
信源的极限压缩率:
数据是不可能被无限压缩下去的,总存在各自的极限。
我们讨论信源数据的压缩极限。
假设信源S的熵率H∞在某编码下被提高到了最大值H0,则该编码的压缩性能达到理论允许的极限。
此时压缩率为 编码后的数据长度数据的信息量I?
编码前的数据长度编码后的信息速率H0H数据的信息量I?
编码前的信息速率H?
H0因此,信源的相通信效率H?
H0是信源数据的压缩率期望的极限。
我们把这个极限称为信源极限压缩率。
4/6 无失真信源编码关系图信源序列s信息量:
I(s)数据长度:
n信源信息速率:
r-元编码器f码元序列xI(x)m码元Rf无失真:
I(s)?
I(x)I(s)PI(x)P?
且?
RfnmmP辛钦大数定理:
?
L nH结论:
Rf=?
LH?
?
f=LlogrAEP:
5.信源的最优无失真编码 根据上面的计算公式,编码效率与平均码长是反比例关系。
这表明,缩短平均码长与提 高编码效率是同一回事。
因此,对于无失真编码来说,数据压缩与提高编码效率是同一回事。
编码效率越接近于1,编码的压缩能力越强。
因此,在某信源的所有无失真编码中,我们把其中编码效率达到1的编码称为该信源的最优无失真编码。
这为无失真编码的设计工作指明了努力的目标。
一般来说,于编码的离散性,这个目标是永远达不到的,但是可以无限地接近。
因此,一般来说,信源编码没有最好,但有更好。
如果把上述最优编码称为绝对最优编码的话,还有一种相对最优编码,其定义如下。
定义在信源S的所有r-元N-分组无失真编码中,平均码长最小的称为S的最优r-元N-分组无失真编码。
注:
一个信源的r-元N-分组码是有限多的,所以其中一定存在最优码。
比较两个不同元数的编码的平均码长时,其单位要化为相同的单位后才可以比较。
无失真信源编码理论的核心问题就是寻找最优无失真编码。
根据编码效率与平均码长的反比关系,要提高编码效率只需缩短平均码长即可,这是实现无失真编码的数据压缩功能的唯一途径。
下一讲我们将重点讨论这个问题。
这里我们先了解最优编码的两个简单性质。
命题最优编码是概率匹配编码,即信源符号的概率越小,对应的码字长越大。
5/6 证明设f是信源U的最优的1-分组编码。
令U的n个符号的分别为ai,对应的概率为pi,在某编码下,对应码字长为li。
假设存在两个符号ai,aj,有pi>
pj且li>
lj,则pili+pjlj>
pilj+pjli。
因此,对调ai与aj的码字后,可以得到平均码长更小的编码。
这与f的最优性矛盾。
证毕 命题最优编码充分用短字符串作为码字。
设f是某信源的最优编码,最大码字长为L,则任何长度小于L的串一定是f的某个码字的前缀。
证明留给读者。
证毕6.本讲要点小结 1)平均码长的定义和物理意义。
2)平均码长的应用:
估计无失真编码的码元序列长度≈信源序列长度×
平均码长 这表明,无失真编码的平均码长越小,压缩能力越强。
计算无失真编码的码率=信源熵/平均码长 计算无失真编码的效率=码率/码元最大熵=信源熵/这表明,编码效率与平均码长是反比关系,从而无失真编码的数据压缩功能与提高信息传输率的功能是一致的。
3)无失真编码的绝对最优性和相对最优性:
绝对最优性:
编码效率=1的无失真编码是该信源的绝对最优无失真编码。
一般 不存在,是可以逼近的理想目标。
相对最优性:
在所有元数固定且分组长度也固定的无失真编码中,编码效率最 大或者平均码长最小的码是相对最优无失真编码。
一定存在,是可以实现的目标。
4)实现无失真信源编码的数据压缩功能的唯一途径是,尽可能地缩小平均码长。
6/6
证明设f是信源U的最优的1-分组编码。