第三章-信息理论基础与熵编码.pptx
第三章信息理论基础与熵编码
3.1经典数据压缩理论
3.2Hufaman编码
3.3、香农一范诺编码
3.4、算术编码
3.5、行程编码
3.6词典编码
1
3.1经典数据压缩理论
信息论中的信源编码理论解决的主要问题:
(1)数据压缩的理论极限
(2)数据压缩的基本途径
2
信源X₁,X₂,X₃,X4......
A={a1,al,as,.am}
●信息被假设为由一系列随机变量代表,往往用随机出现的符号来表示。输出这些符号集的源为信源
●信源被抽象为一个随机变量序列(随机过程)。
●如果信源输出的随机变量取值于某一连续区间,就叫做连续信源。。
●如果信源输出的随机变量取值于某一离散符号集合,就叫做离散信源。
●如果信源输出的随机变量一部分取值于连续区间,一部分取值于离散符号集合,就叫做混合信源。
3.1.1离散无记忆信源
信源
3
离散信源
信源X={Xi,X₂,X₃,X4..…}
A={a1,a2,a3,..am}
●如果随机序列中各个变量具有相同的概率分布,则称为离散平稳信源。
●如果离散平稳信源的输出序列中各个变量是相互独立的,即前一个符号的出现不影响以后任何一个符号出现的概率,则称为离散无记忆平稳信源,否则称为离散有记忆平稳信源。
4
自信息量和一阶熵
●Shannon信息论把一个事件(字符aj)所携带的信息量定义为:
I(aj)=log(1/p)=-log.p(bit)
其中p为事件发生(字符出现)的概率
●I(a)称自信息函数,即随机变量X取值为a时所携带的信息量
●对数的底r可取不同的值,通常取r=2,当r=2时,I(a)的单位为比特。log.p简写为logp。
5
●在符号出现之前,熵表示符号集中的符号出现的平均不确定性;
●在符号出现之后,熵代表接收一个符号所获得的平均信息量。
●熵还可理解为是事件随机性的量度,因其仅仅对概率p取另一个坐标而已
●信源编码的数据输出速率(平均码长)与信源熵之间有某种对应关系。
●因为X的信息量也是一个随机变量,所以我们要
研究它的统计特性。其数学期望为:
●称H(X)为一阶信息熵或者简称为熵(Entropy),单位为bit/字符。
6
●最大离散熵定理:当与信源对应的字符集中的各个字符为等概率分布时,熵具有极大值logm。m为字符集中字符个数。
信源的概率分布与熵的关系
●熵的大小与信源的概率模型有着密切的关系。
*logp,≤logm
等概率时
,
7
●从物理意义上说,通常传输或存储的1个二元字符,其所含的信息量总低于1bit。只有1或0等概率时,每一信源符号才含有1bit信息量。
●因此最大离散熵与信源的实际熵之间的差值,就是信源X所含有的冗余度。
二进制信源的熵
●二进制信源输出一个二进制数码
所携带的平均信息量最大为1bit。
8
●离散无记忆信源的冗余度隐含在信源符号的非等概率分布之中。只要H(X)小于logm,就存在数据压缩的可能。
●最大离散熵与信源的实际熵之间的差值,就是信源X所含有的冗余度。
r=Hmax(X)-H(X)=logm-H(X)
最大离散熵定理的应用
9
平均码长与熵
●如果对字符aj的编码长度为L,则X的平均码长为:
在Lj=—logpj时,平均码长取得极小值H(X)
●在信息论中已经证明熵具有极值性,即:
10
●将压缩前每个信源符号(取样)的编码位数与压缩后平均每个符号的编码位数(1)之比,
定义为数据压缩比。
●编码效率用信源的熵与压缩后平均每个符号的编码位数之比来表示。
11
关于离散无记忆平稳信源的结论
●一阶熵即为离散无记忆平稳信源的压缩极限。(基本极限)
●只要信源不是等概率分布,就存在着数据压缩的可能性。
●对于离散无记忆平稳信源,数据压缩的基本途径:
●①准确得到字字符概率{p};
●②使各字符的编码长度尽量等于字符的信息量
12
●熵编码包括香农一范诺编码、霍夫曼编码和算术编码,其宗旨在于找到一种编码使得平均码长到达熵极限,基本思想就是对出现概率较大的符号取较短的码长,而对出现概率较小的符号取较大的码长。
熵编码
13
●内容:在变字长编码中,对于出现概率大的信息
符号编以短字长的码,对于概率小的符号编以长字长的码。如果码字长度严格按所对应符号出现概率大小逆序排列,则平均码字长度一定小于其他以任何符号顺序排列方式得到的平均码字长度。
3.2霍夫曼编