《信息论与编码基础》课件 14-压缩编码基本理论

§5信源压缩编码基本理论§5.1信源编码的基本概念§5.2无失真可变长信源编码 定理信源编码的定义信源编码器分类§5.1信源编码的

基本概念一、信源编码的定义

例1:S:{a,b,…,z,空格符,…},q=32,q>rX:{0,1}编码一（电传码）：A－11100，B－10011，…编码二（ASCII码）：A－31H，B－32H，…编码器{英文字母/符号/命令}二进制代码码符号集{0，1}l=5l=7√一、信源编码的定义信源编码：

将信源输出的消息进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的剩余度尽量减少。两大任务对象§5.1信源编码的

基本概念编码器消息符号码字li

为码字Wi的码长，所有码字的集合为码集C基本源编码（单符号信源编码）一、信源编码的定义码元消息集合§5.1信源编码的

基本概念编码输入符号码字：N次扩展信源编码编码器一、信源编码的定义§5.1信源编码的

基本概念

②

①

③

惟一可译码:非惟一可译码:定义5-1：若某一种码的任意一串有限长的码序列只能被惟一地译成所对应的信源符号，则该码称为惟一可译码，反之为非惟一可译码。

④

二、信源编码器分类信源符号与编码码字之间的映射是一一映射§5.1信源编码的

基本概念

Morse电码：例2电报注册专利产品、1849年5月1日专利号塞缪尔FBMorse变长码§5.1信源编码的

基本概念二、信源编码器分类

Morse电码：Z:{·、－}，X:{0、1} 例2§5.1信源编码的

基本概念二、信源编码器分类

·：10－：1110字母间隔：000单词间隔：000000信源编码器I{A,B,…,Z}二进制符号码符号集{0，1}信源编码器II电码集{点/划/字母间隔/单词间隔}例2变长码§5.1信源编码的

基本概念二、信源编码器分类序号字母电码

序号字母电码

1A●—14N—●2B—●●●15O—

——3C—●—●16P●—

—●4D—●●17Q——●●5E●18R●—●6F●●—●19S●●●7G——●20T—8H●●●●21U●●—9I●●22V●●●—10J●—

——23W●—

—11K—●—24X—●●—12L●—●●25Y—●——13M——26Z——●●例3．

5种编码比较基本特点：等长码——若为非奇异码，则为惟一可译码；

变长码——码本身及任意次扩展码均非奇异。信源符号si符号概率P(si)码1码2码3码4码5s11／2001100s21／41110100101s31／8000010000110s41／811011000000111奇异码惟一可译码非奇异非惟一可译二、信源编码器分类§5.1信源编码的

基本概念§5信源压缩编码基本理论§5.1信源编码的基本概念§5.2无失真可变长信源编码 定理

Shannon信息论对压缩编码的指导意义

Shannon第一定理§5.2无失真可变长信源编码定理2.数据压缩的理论极限1.数据压缩的基本途径数据冗余客观冗余主观冗余一、Shannon理论对数据压缩的指导意义有记忆信源的冗余度寓于信源符号间的相关性中。去除它们之间的相关性，使之成为或几乎成为不相关的信源，其熵将增大。结论1：离散无记忆信源的冗余度寓于符号概率的非均匀分布中。改变原来信源的概率分布，使之成为或接近等概分布的信源，其熵将增大。结论2：一、Shannon理论对数据压缩的指导意义§5.2无失真可变长信源编码定理信源的冗余度主要来自以下方面：信源样点间的相关性信源符号概率分布不均匀时间相关性空间相关性预测编码变换编码统计编码信源总存在一定的冗余度，可以进行压缩。一、Shannon理论对数据压缩的指导意义§5.2无失真可变长信源编码定理二、编码指标1．平均码长code/sig§5.2无失真可变长信源编码定理扩展源编码：2．编码后信息传输率基本源编码:（bit/code）（bit/code）二、编码指标§5.2无失真可变长信源编码定理3．

编码效率※

对于二元编码，r=2，∴η=R

※二、编码指标§5.2无失真可变长信源编码定理例1：二元DMS进行无失真编码H(S)=H(3/4,1/4)=0.811(bit/sig)(code/sig)(bit/code)基本信源编码：三、Shannon第一定理§5.2无失真可变长信源编码定理二次扩展信源编码：平均码长：信息传输率：(bit/code)信源概率码字码长例1：二元DMS进行无失真编码§5.2无失真可变长信源编码定理三、Shannon第一定理平均码长效率信息传输率基本信源编码：二次扩展信源编码：三次扩展信源编码：四次扩展信源编码：扩展次数N增加时：减小增加提高若采用等长编码，且要求编码效率达96%，

N≥41291672例1：二元DMS进行无失真编码§5.2无失真可变长信源编码定理例2：设信源

则二次扩展信源为：

l=2(code/sig)L2=2(code/2_sigs),l=1

(code/sig)信源有记忆时，采用N长源编码，l减小随着N的增加，平均码长减小，有效性逐步提高；当N趋于无穷时，平均码长可以无限制地减小吗？§5.2无失真可变长信源编码定理

DMS的N次扩展信源SN＝｛

1，

2，

qN｝，其熵为H(SN)，并有码符号X＝｛x1，x2，

xr｝。对信源SN进行编码，总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：

定理5.1：香农第一定理（可变长无失真信源编码定理）

且当N

时，有：

其中， 为N长源编码的平均码长，

i是

i所对应的码字长度。

这个平均值不是直接对信源S中符号编码获得的，而是对扩展信源SN中符号进行编码获得的。§5.2无失真可变长信源编码定理①平均码长的下限即信源熵是无失真信源编码的最小平均码长！②存在性定理 方法：N长源，变长码③适用于平稳有记忆信源，H(S)=H∞熵是信源无失真压缩的一个临界值，达到熵的编码是最优的。§5.2无失真可变长信源编码定理二、Shannon第一定理说明：表述二

若R

>H(S)，就存在唯一可译变长编码；若R

<H(S)，唯一可译变长编码不存在，不能实现无失真编码。(其中，)例：§5.2无失真可变长信源编码定理说明：二、Shannon第一定理DM编码的过载失真表述三

（无噪信道编码定理） 若信道的信息传输率R不大于信道容量，总能对信源的输出进行适当编码，使得在无损无噪信道上能无差错地以最大信息传输率C传输信息；但要使信道信息传输率R大于C而无差错地传输则是不可能的。§5.2无失真可变长信源编码定理说明：二、Shannon第一定理习题：P100：T2，T5§5.2无失真可变长信源编码定理§5.2无失真可变长信源编码定理若有一信源，每秒信源发生2.66个信源符号，将其送入一个每秒只能传送2个二进制符号的无噪二元信道中传输，试问信源不经过编码能否与信道直接连接？通过适当编码能否与信道连接？采用何种编码，为什么？习题1：P100：T2§5.2无失真可变长信源编码定理

某信道输