编码理论课件

第一章绪论信息论相关知识和概念编码理论信息论相关知识介绍信息的产生和传播信息的定义与分类信息的特性及性质狭义信息论：指香农信息理论，主要研究信息的测度，信道容量，信道信源编码等问题，也称经典信息论。是基础理论一般信息论：泛指通信理论，通信的数学理论，广泛研究信息传输和处理的问题。广义信息论：包含上述两种理解，还包括所有与信息有关的自然、社会领域。香农信息理论，是为设计有效可靠的通信系统提供理论依据。对信息论的理解

信息的产生和传播信息是人类生产实践中互通情报中产生的信息发展的五次变革，极大的推动了社会的进步信息科学技术知识成为最重要的战略资源，人们现在关注于信息科学技术知识的开发和利用，人类社会的发展与信息传播速度密切相关

信息科学、信息技术、信息产业信息的定义与分类1948年，维纳提出：信息就是信息，它既不是物质也不是能量一般普遍对信息的理解是，信息=消息=情报=知识=信号？信息不等同于情报信息不等同于知识信息与消息：消息是信息的载荷者，需要指出的是：一个消息可以含有不同的信息量，同一信息也可以用不同的消息来载荷。数据、图片可能发布的是同一信息

信息不等同于信号：信号是消息的一种表现形式，又是消息的载体，它是一种物理量。信号携带着信息，但不是信息本身，同一信息可以用不同信号表示，同一信号也可以表示不同信息。信息的定义与分类信息的定义与分类信息是构成客观世界的三大要素之一信息的定义：信息是事物运动状态或存在方式的不确定性的描述信息的分类：语法信息：事物的状态和状态改变方式本身。研究事物运动出现的各种可能状态和这些状态之间的联系。是抽象的。语义信息：研究信息的主体含义。语用信息：研究信息客观价值。人们对客观世界运动规律和存在状态的认识结果。信息传递信息处理—再生信息传递信息获取信息施用外部世界问题／环境信息运动过程语义信息语法信息语用信息信息的特性及性质信息的特性：信息是无形的（无形性）信息是可共享的（共享性）共享性的矛盾（竞争），加密信息阻碍信息的传播和发展。信息是扩充的，信息永远在产生、更新、演变（无限性）信息是可以度量的：必须满足信息的三个条件——结构的（离散结构）、统计的（用统计方式、发生概率来测量不确定性）、语义的（有具体含义）信息的特性及性质信息的性质：普遍性无限性性对性转移性变换性有序性动态性转化性编码理论编码理论的基本概念编码理论的发展编码理论研究的内容和目的编码理论的基本概念所谓编码，广义地说就是信号的变换，是信息处理的主要手段。编码的主要目的是提高系统对某一方面的要求以及优化系统某一方面的性能指标根据信息论的各种编码定理和通信系统的性能指标，编码可分为信源编码、信道编码和密码编码三类通信系统模型编码理论的基本概念信源加密密钥干扰信道信宿信源信源编码加密信道信道编码信道解码解密信源解码信宿解密密钥通信系统模型的组成部分和功能说明主要实体：信源和信宿信道及干扰源编码器译码部分——编码部分的逆过程编码理论的发展信源编码1、无失真信源编码：对信源进行编码，没有带来信息量的损失。（适用于离散信源或数字信号）

2、限失真信源编码：在一定准则下，对信号源进行编码。（适用于连续信源或模拟信号）信道编码

编码理论研究的内容和目的

编码理论是以信息作为主要研究对象，以信息的运动规律和利用信息的原理作为主要的研究内容，以信息科学方法论作为主要的研究方法，以扩大人的信息功能为主要研究目的的一门新兴科学。它的基本理论是信息论，控制论和系统论。第二章无失真信源编码信息量、熵和互信息信源编码定理霍夫曼码及其他编码方法算术编码游程编码改进的霍夫曼码通用编码第二章无失真信源编码无失真编码：保证信源产生的全部信息无失真地传递给信宿。（只有对离散信源可以实现无失真信源编码。）实质上是一种概率匹配编码。限失真信源编码：在确定标准和准则的条件下，信源所必须传递的最小信息量。也称信息率失真函数（限定波形失真——波形编码，限定特性参量失真——参量编码）。第二章无失真信源编码信源中的统计多余度主要取决于以下两个主要因素：一是消息概率分布的非均匀性，另一个是消息间的相关性。对无记忆信源主要取决于概率分布的非均匀性，但是，对于有记忆信源，两者都起作用，且相关性更加重要。第二章无失真信源编码统计匹配编码：是根据信源的不同概率分布而选用与之相匹配的编码，以达到的系统同中传信速率最小，且满足在信宿复制时无失真或低于某一允许的失真限度值。2．1信息量、熵和互信息量时间发生的概率越小，不确定性就越大，给人的信息量就越小；发生的概率越大，不确定性就越小，给人的信息量就越大。

条件概率联合概率必须掌握的概率论知识必须掌握的概率论知识全概率：设B1

,B2

,…

是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（样本空间）；p（Bi）＞0，i=1，2，…，则对任一事件A，有：必须掌握的概率论知识4)Bayes公式:

设B1

,B2

,…

是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（样本空间）；

p（Bi）＞0，i=1，2，…，则对任一事件A，有：一个离散无记忆信源是由n个符号消息组成的集合:X={x1，x2

·

·

·

xn

}，这n个符号消息的概率分布为了：称为符号xi

的先验概率,散信源数学模型表示为：

称为概率空间,其中从概率的角度看，可以将符号消息xi看一个随机事件。因此xi具有不确定性。

2．1信息量、熵和互信息量信息量定义：2．1信息量、熵和互信息量信息量定义：美国科学家L.V.R.Hartley于1928年给出了信息的度量方法。定义若信源发出一符号xi，由于信道存在干扰，收到的不是xi而是yi，从yi中获取有关xi的信息量用I(xi；yi)表示，称为互信息量。

定义上述情况，若信道无干扰，收到的就是xi本身，这样I(xi；yi)就可以用I(xi；xi)表示，或简单记作I(xi)，并称为自信息量。一、自信息量1)函数I(xi)的属性

1º

若有两个事件xi

，xj

，其先验概率为p(xi)＜p(xj)，则事件xi比事件xj有更大的不确定性，同时会带来更多的信息量；I(xi)>I(xj)2º

事件xi先验概率p(xi)=1（确定事件）,则不存在不确定性，同时不会带来信息量；I(xi)=0.3º

事件xi先验概率p(xi)=0（不可能事件）,则存在不确定性应为无穷大，同时会带来无穷的信息量；I(xi)→∞.4º

两个统计独立事件的联合自信息量应等于它们各自信息量之和;则I(xy)=

I(x)＋I(y)2)

定义一个符号消息xi的自信息量为其发生概率的对数的负数，并记为I(xi)：

I(xi)=－logp(xi)

当p(xi)=0，则I(xi)→∞；当p(xi)=1，则I(xi)=0.3)自信息量的单位自信息量的单位与所用对数的底有关：

1º

对数的底是2时，单位为比特—bit(binaryunit)2º

对数的底是e(自然对数)时，单位为奈特

—nat(natureunit)3º

对数的底是10(常用对数)时，单位为笛特或哈特

—det(decimalunit)orHart(Hartley)三种信息量单位之间的换算：

1det=log210≈3.322bit1bit=ln2≈0.6931nat

1bit=lg

2≈0.3010det1nat=log2e≈1.4427bit

在信息论中常用以2为底的对数，为了书写方便，以后将log2书写为log，因其单位为比特bit，不会产生混淆；注意有些文献将log2书写为lb4)自信息量的含义是随机量、根据单个符号消息的先验概率确定其信息量和不确定度。二、离散信源熵信源X发出某一个符号提供的信息量不适合描述信源X发出一个符号提供的信息量。定义信息源的平均不确定度为信源中各个符号不确定度的数学期望，记作H(X)

其中

H(X)又称为信源X的信源熵。

2)H(X)

的含义

1º

表示的是信源的平均不确定度。

2º

表示信源X发出一个符号提供的平均信息量。

3º

是统计量、数学期望（统计平均）、各个符号平均不确定度和平均信息量。

3)

信源熵单位：二进制:bit/信源符号，或bit/信源序列十进制:det/信源符号，或det/信源序列

e进制:nat/信源符号，或nat/信源序列

4)信源熵的三种特殊情况1º

当

p(xi)=0时（p(xi)→0），则p(xi)logp(xi)=02º

信源X={x1，x2

·

·

·

xn

}

，若其中xi

的概率p(xi)=1

则其余xj的p(xj)=0，因为则H(X)=0bit/信源符号3º

当信源中X所有n个符号均有相同的概率p(xi)=1/n，则H(X)=-(1/n)log(1/n)=lognbit/信源符号2º

联合熵（共熵）

联合熵是联合符号集合XY上的每个元素对xi

,

yj的自信息量的概率加权的统计平均值。3º

条件熵与联合熵的关系

I(xi

|yj)=－logp(xi

|

yj)

，I(xi

yj)=－logp(xi

yj)

因

全概率公式5)条件熵与联合熵

1º

条件熵在给定yj条件下，xi的条件自信息量为：

I(xi

|yj)=－logp(xi

|

yj)

集合X的条件熵为：

在给定Y（即各个yj）条件下，集合X的条件熵定义为：三、互信息（一）简单的通信模型

若信源发出符号xi，由于信道存在干扰，收到的不是xi而是yi，从yi中获取有关xi的信息量称为互信息量，用I(xi;yi)表示。信源X有干扰离散信道信宿Y干扰源所以H(XY)=H(X

)＋H(Y|X)同理H(XY)=H(Y)＋H(X|Y)含义：平均从Y获得的关于X的信息量。 （又称信道 的信息传输率R）（二）平均互信息※I(X;Y)与熵：※I(X;Y)与I(x;y)：

I(x;y)表示由随机事件y中获得的关于事件x的信息。互信息

:关系：I(X;Y)＝EXY[I(x;y)]注意：（二）平均互信息

※比较：I(x;y)可正可负，1．非负性I(X;Y)≥0（三）平均互信息的性质

※

当I(X;Y)=0全损信道：H(X)=H(X|Y)，说明：

通信的意义——通过消息的传递可获得信息信源加密密钥源信道解密信宿保密通信系统框图XY’Y非法用户全损信道（三）平均互信息的性质

※信息处理的一般规律：通过传输获得的信息量不大于提供的信息量。

※

I(X;Y)=H(X)无损信道：H(X|Y)=02．

极值性，P(x|y)=0or1（三）平均互信息的性质

I(X;Y)=I(Y;X)３．交互性（对称性)（三）平均互信息的性质I(X;Y)=H(X)－H(X|Y)=H(Y)－H(Y|X)

4.

I(X;Y)与各类熵的关系

文氏图H(X∣Y)H(Y∣X)信源熵信道疑义度（损失熵）噪声熵（散布度）I(X;Y)

=H(X)+H(Y)－H(XY)信宿熵H(XY)（三）平均互信息的性质特殊信道特殊信道总结

信道名称信道特征信息传输情况全损信道P(xy)=P(x)P(y)H(X︱Y)=H(X)I(X；Y)=0无噪信道

P(y︱x)=0or1H(Y︱X)=0I(X；Y)=H(Y)无损信道

P(x︱y)=0or1H(X︱Y)=0I(X；Y)=H(X)（三）平均互信息的性质

5．

凸状性I(X;Y)=f[P(x)，P(y|x)]（三）平均互信息的性质Th3.2：对于固定信源分布，平均互信息I(X;Y)是信道传递概率p(y|x)的∪型凸函数。※不同信源通过不同信道传输得到的平均互信息不同；

5．

凸状性Th3.1：对于固定信道，平均互信息I(X;Y)是信源概率分布p(x)的∩型凸函数。平均互信息是信源符号概率分布的上凸函数平均互信息是信道转移概率的下凹函数（三）平均互信息的性质

例1．

分析二元信源通过BSC信道的I(X;Y)特性信源：，信道：1－p1－ppp0011则（三）平均互信息的性质其中，

（三）平均互信息的性质，得：（三）平均互信息的性质

I.

固定信道（p一定），∴H(p)一定I(X;Y)∝H(ω+p－2ωp)由熵上凸性的该I(X;Y)为ω的上凸函数I(X;Y)1－H(p)01/21ωω＝1/2时，I(X;Y)极大I(X;Y)＝H(1/2)－H(p)=1－H(p)

（三）平均互信息的性质Ⅱ.

固定信源（ω一定）则I(X;Y)～p，∴I(X;Y)=I(p)∴I(p)为下凹函数可求：p=1/2,I(X;Y)=0,极小p=0,I(X;Y)=H(ω)p=1,I(X;Y)=H(ω)I(X;Y)01/21p（三）平均互信息的性质2．2信源编码定理信源编码的无失真编码：接收端信宿要求无失真精确的复制信源输出的消息。只有对离散信源才可以实现无失真编码。实质上是一种统计匹配编码——根据信源的不同概率分布而选用与之相匹配的编码，以达到在系统中传送速率最小，且满足在信宿复制时无失真或低于某一允许的失真限度值。2．2．1信源编码的基本概念信源编码：将信源输出符号，经信源编码器变换成另外的压缩符号，然后将压缩有信息经信道传送到信宿。只考虑信源和信宿两个因素。通信系统模型简化为P15图2-1编码A器输入为：编码器输出的码字为：符号码1码2码3码4等长码变长码u100001u201101101u3100000001u311011100012．2．1信源编码的基本概念树图（码树）法：树根=码字的起点树的度=码元数分支结点=码的符号的一部分终端结点=待编码符号满树=等长码：树中各结点有相同树枝数，且每层结点树达到最大值。非满树=变长码2．2．1信源编码的基本概念编码方法：1）将待编码的字符作为终端结点，构造码树；2）按一定规则给每个树枝分配一个标记；3）将从根到终端结点的路径上的编号依次相连，作为该终端结点所表示的字符的编码。2．2．1信源编码的基本概念译码方法：1）从树根出发，根据接收到的第一个码字符号来选择应走的第一条路径。2）沿所选路径走到分支结点，在根据收到的第而个码字选择应走的第二条路径。直至走到终端结点为止。3）根据所走路径，可立即判断出接收到的码符号。4）重新返回到树根，再作下一个接收码符号的判断。2．2．1信源编码的基本概念

分组码（块码）分类

1°按码字的码长分类定长码：码集中所有码字的码长相等。变长码：码集中所有码字的码长不全相等。

2°按信源符号与码字对应关系分类非奇异码：信源符号与码字是一一对应的。奇异码：信源符号与码字不是一一对应的。

3°按译码唯一性分类

唯一可译码：对于多个码字组成的有限长码流，只能唯一地分割一个个的码字。唯一可译码又称为单义码.例码流100111000…

码1x1→0x2→10x3→11可分割10,0,11,10,0,0

码2x1→1x2→10x3→11则无法唯一分割

唯一可译码在传输过程中不需要同步码。

非唯一可译码：对有限长码流，不能唯一地分割一个个的码字。4°按译码的即时性分类

非即时码：接收端收到一个完整的码字后，不能立即译码；还需要等到下一个码字开始接收后才能判断是否可以译码。

即时码：接收端收到一个完整的码字后，就能立即译码；即时码又称为非延长码或异前缀码。例非即时码

码流01001100…

x1→0x2→01x3→11译码为x2,x1,x1,x3,x1,?

即时码码流01001100…x1→0x2→10x3→11译码为x1,x2,x1,x3,x1,x1

异前缀码(即时码)指的是码集任何一个码不能是其他码的前缀.

即时码必定是唯一可译码,唯一可译码不一定是即时码.5°有实用价值的分组码分组码是非奇异码、唯一可译码、即时码

2．2．2变长码若要实现无失真编码，不但要求信源符号与每个符号的码字一一对应，而且要求码符号序列与信源符号序列也一一对应。也就是要求所编的码为惟一可译码。我们首先分析等长编码，再分析变长编码，以做比较。一、等长码基本问题等长码特点：C2={000,001,100,101,111}，l2=3code/sig要求：

问题：

例1．

惟一可译码等长编码C1={00,01,10,11,10}，l1=2code/sig(2)高效奇异码一、等长码基本问题可能的码字数≥消息数

对基本信源编码：对N长源编码：要求：消息数码字数：rl∴rl≥q(l≥logrq)（对例1，q=5,∴要求：2l≥5，即l≥3）∴rl≥qN(l/N≥logrq)一、等长码基本问题则，q=53=125种<128=27

∴l=7code/3_sigs平均码长：l/N=7/3=2.33code/sig<l2

例1（续）S的三次扩展：

※

等长码码长要求l/N

logrq（保证唯一可译码，无失真）

※

logrq为下限

※

扩展信源编码的平均码长<基本源编码的平均码长结论：一、等长码基本问题

例2．英文源S：{26个字母+空格符号}，q=27

由q=27≤2l，得l≥5code/sig∴编码后信息传输率：R=H(S)/l=1.4/5=0.28bit/code

二元信源[0,1]：H(X)max=1bit/code考察效率：H∞(S)=1.4bit/sig该编码冗余度大平均码长太长例3：设信源

则二次扩展信源为：

l=2code/sigL2=2code/2_sigsl=1code/sig信源有记忆时，采用N长源编码，l减小一、等长码基本问题二、等长信源编码定理

定理2-1（等长信源编码定理） 一个熵为H(U)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从m个字母的码符号集中选取L个码元组成。对于任意

>0，只要满足：

则当N足够大时，可实现几乎无失真编码，即译码错误概率可为任意小。

则不可能实现无失真编码，且当N足够大时译码错误概率近似等于1。反之，若：※

适用于DMS及平稳有记忆信源※平均码长下限：

※

基本方法：N长源、变长编码

※对等长编码,若要实现几乎无失真编码,则信源长度必满足:定理2-1说明：二、等长信源编码定理当δ≤10-5（即PE<10-5）

解：H(S)=0.811bit/sig

例4．DMS进行等长编码

则有：η=0.5得N≥71687

η=0.8得N≥1146990

η=0.9得N≥5806641

η=0.96得N≥41291672等长码的缺点：平均码长太长使信道复杂化容易产生溢出或取空差错的扩散变长码特点：每个码字长度可不同要求：唯一可译定理2-2：（Kraft不等式）设信源符号S=｛s1,…,sN｝,码符号X＝{x1,…,xm}，又设码字W1，W2，…Wn的码长分别为l1，l2，…，ln，则存在惟一可译码的充要条件是：三、惟一可译码的判断※码长结构～惟一可译码1、Kraft不等式编码码元数目1、Kraft不等式

——惟一可译码存在的必要条件例1．考察：①l1=1，l2=2，l3=l4=3的二元码如：C1={1,01,001,000}

C2={0,10,110,111}②l1=1，l2=l3=l4=2的二元码∴必存在惟一可译码

∴必不存在惟一可译码惟一可译码C3={0,00,000,000}非惟一可译符号码1码2码3码4等长码变长码u100001u201101101u3100000001u31101110001惟一可译码非惟一可译码非惟一可译码惟一可译码2、根据定义判断基本准则：等长码——若为非奇异码，则为唯一可译码；变长码——码本身及任意次扩展码均非奇异。主要方法：

树图法（即时码必为惟一可译码）

尾随后缀法（尾随后缀集合F中不含任一码字）010110010010111010011001110101111例2.C1={0,10,1100,1110,1011,1101}F:{11,00,10,01,0,11,1,100,110,011,101}100非惟一可译码eg:1011001110...例2.C2={1,10,100,1000}1101000000

F={0,00}惟一可译码C3={1,01,001,0001}

F=一般离散无记忆信源输出的各消息（符号）的概率是不相等的。对出现频率大的信源符号采用较短的码字；而对出现概率小的信源符号采用较长的码字。从整个信源来看，编成的信源码字的平均码长最短，也实现了与信源统计特性相匹配。定义码字的平均码长度：平均码长是每个信源符号平均需用的码元数。它和编码后的压缩效果密切相关。平均码长大，则压缩效果差，系统有效性差。因此，我们一般选用平均码长最短的编码。编码后每个码元携带的信息量就是信道的信息传输率：例3．对DMS进行无失真编码。编码一：基本源编码——L=1code/sig编码二：N长源编码aiP(ai)码CliS1S19/1601S1S23/16102S2S13/161103S2S21/161113四、变长信源编码定理

若一个离散无记忆信源U具有熵为H(U)，并有m个码元的码符号X＝｛x1，x2，

xm｝。则总可以找到一种无失真编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：

紧致码：若有一个唯一可译码，其平均码长小于所 有其他唯一可译码的平均码长，称此码为紧 致码或最佳码。定理2-3：变长编码定理四、变长信源编码定理

证明若xi

按如下不等式取所对应码字的码长为L

,

若为整数,则上述不等式左边取等号.

故可得

四、变长信源编码定理

因为所以

所有码字长度满足Kraft不等式

如何降低平均码长：（1）减少信源熵H(X)

（2）增加信道码元数m四、变长信源编码定理

注意到li∈Z,∴取其整数部分例3．Shannon编码的核心四、变长信源编码定理

DMS的N次扩展信源UN＝｛

1，

2，

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

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

定理2-4：香农第一定理（无失真变长信源编码定理）

四、变长信源编码定理

且当N

时，有：

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

i是

i所对应的码字长度。

信源X

的N次扩展信源XNXN

的信源熵为H(XN)bit/N个信源符号

XN

所对应码字的码长码符/N个信源符号①平均码长的下限即信源熵是无失真信源编码的最小平均码长！②存在性定理 方法：N长源，变长码③适用于平稳有记忆信源，H(U)=H∞定理2-4说明四、变长信源编码定理

表述三：（无噪信道编码定理） 若信道的信息传输率R不大于信道容量，总能对信源的输出进行适当编码，使得在无损无噪信道上能无差错地以最大信息传输率C传输信息；但要使信道信息传输率R大于C而无差错地传输则是不可能的。表述二：若R

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

<H(S)，唯一可译变长编码不存在，不能实现无失真编码。四、变长信源编码定理

编码后每个信源符号能载荷的最大信息量为：表述四：设信源熵为H（比特/符号），无噪无损信道的信道容量为Ct（比特/秒），则总可以找到一种编码方法对信源的输出进行无失真编码，使得在信道上传输的平均码速率为（Ct/H-ε）（符号/秒），其中ε为任意小的正数，但要使传输的平均码速率大于Ct/H（符号/秒）是不可能的。四、变长信源编码定理

四、变长信源编码定理

若对信源U进行编码所得到的平均码长，因为平均码长一定大于或等于Hm(U)，所以定义编码的效率为：对同一信源来说，码的平均码长越短，越接近极限值Hm(U)，信道的信息传输率就越高，越接近无噪无损信道容量。码剩余度定义：对于二元无噪无损信道m=2，Hm(U)=H(U)αiP(αi)

码Cλis1s19/1601s1s23/16102s2s13/161103s2s21/161113例3．比较

N长源编码的效率。解：H(S)=0.811bit/sig

四、变长信源编码定理

五、统计匹配编码离散无失真编码实质上是一种统计匹配编码，是根据信源符号的不同概率分布分配与之相对应码字，对出现概率大的符号分配短的码字，对出现概率小的符号分配长的码字，这样可以使信源符号的平均码长最短。编码器输入：编码器输出的码字为：要实现无失真信源编码，必须同时满足无失真和有效性两个条件，只能从信源统计特性上去考虑。2.3霍夫曼码及其他编码方法一、霍夫曼码二、费诺编码三、香农-费诺-埃利斯码1．二元Huffman编码一、Huffman编码

④

分配码元。缩减信源步骤：①

递减排序；S=[s1，s2，…，sq]②

合并概率最小的两个符号;③

重复①②，直至缩减信源中只有两个符号为止；合二为一一分为二例1:已知离散无记忆信源如下所示，对应的霍夫曼编码为：消息符号ui符号概率P(ui)u10.5u20.25u30.125u40.1250.250.51.0010101111111码长码字1021031103111信息熵：平均码长：编码效率：编码不唯一（0、1分配不同，排序不同）1．二元Huffman编码消息符号si消息概率P(si)s10.20s20.19s30.18s40.17s50.15s60.10s70.0101010001010101码长码字21021130003001301040110401111100000101011011例2．平均码长唯一0.110.260.350.39一、Huffman编码

码长方差：码21．二元Huffman编码（例2）源符Si概率P(Si)S10.4S20.2S30.2S40.1S50.1010001000001001000110100101101001101

一、Huffman编码

二元Huffman码的特点：※※每次缩减信源的最后两个码字总是最后一位不同（前面各位相同）1．二元Huffman编码——惟一可译一、Huffman编码

n=(m－1)Q+m

（对于二元编码，n=Q+m）※

为使短码充分利用，，要求最后信源有m个符号“合m为一，一分为m”填充法消息数目缩减次数一、Huffman编码

2．m元Huffman编码一、Huffman编码

2．m元Huffman编码步骤：验证n是否满足n=(m-1)Q+m，若不满足，可以人为地增加一些概率为零的符号，使最后一步有m个信源符号；取概率最小的m个符号合并成一个新结点，并分别用0，1，…，（m+1）给各分支赋值，把这些符号的概率相加作为该新结点的概率；将新结点和剩下结点重新排队，重复步骤2；取树根到叶子（信源符号对应结点）的各树枝上的赋值，得到各符号码字。

解：n=5,若取m=32．m元Huffman编码∴需加入两个填充符号有5=2Q+3n=(m－1)Q+m

一、Huffman编码

例3．三元Huffman编码若取m=4有5=3Q+4取5+2=3Q+42．m元Huffman编码过程一、Huffman编码

消息符号ui符号概率P(ui)u10.4u20.3u30.2u40.05u50.050120120.30码字1202122码长112222．m元Huffman编码过程一、Huffman编码

消息符号ui符号概率P(ui)u10.4u20.3u30.2u40.05u50.05u60u70012301230.1码字01230313233码长1112222填充符号一、Huffman编码

H(U)=1.95bit编码效率：2．r元Huffman编码过程

一般情况下，信源符号集的数目应远大于码元数。定理在变长编码中，如果码字长度严格按照所对应符号的出现概率逆序排列，则其平均码长为最小。3．Huffman码的最佳性

码字长度与出现概率逆序排列；每次缩减信源的最后r个码字末位不同。一、Huffman编码

费诺（Fano）编码（即时码）二、费诺（Fano）编码

1.递减排列;2.等概分组P(A)≈P(B);3.每个子集以符号“0”或“1”标识。方法：等概分割步骤：费诺编码属于统计匹配编码，但它不是最佳的编码方法例4：DMS如下，用费诺编码方法编码消息符号ui符号概率P(ui)u10.5u20.25u30.125u40.125第一次分组01第二次分组01第三次分组01码字010110111码长1233H(U)=1.75bit消息符号si消息概率P(si)s10.20s20.19s30.18s40.17s50.15s60.10s70.01第一次分组01第二次分组0101第三次分组0101第四次分组01码字码长0020103011310211031110411114例5香农-费诺-埃利斯码三、香农-费诺-埃利斯码方法：根据信源符号累积概率分配码字不是分组码，也不是最佳码，但效率高步骤：1.确定信源符号修正的累积概率函数；2.将修正的累积概率函数转换成二进制小数，取小数点后l(uk)位为码字。设信源为：信源符号积累概率为：信源符号修正的积累概率为：码长：平均码长：例6：DMS如下，用香农-费诺-埃利斯编码方法编码消息符号ui符号概率P(ui)u10.25u20.5u30.125u40.125F(uk)0.150.750.8751F(uk)0.1250.50.81250.9375二进制F(uk)0.0010.1000.11010.1111码长l(uk)3244码字0011011011111H(U)=1.75bitHuffman码在实际应用中的问题误差扩散概率匹配速率匹配2.4算术编码Huffman编码更适合于大消息集信源，对于小消息集信源使用算术编码和游程编码压缩效果更好。主要内容：积累概率的递推公式算术编码原理算术编码的码长递推公式的应用不做乘法的算术编码2.4.1积累概率的递推公式信源符号积累概率设信源信源符号积累概率：2.4.1积累概率的递推公式信源序列积累概率传递公式设独立信源序列信源序列S添加一个新的信源符号ur后所得新序列Sur的积累概率。信源序列S的概率。信源符号ur的积累概率。信源序列S添加一个新的信源符号ur后所得新序列Sur的概率。信源符号ur的概率。信源序列的积累概率F(S)与信源符号的积累概率一样，可用[0,1)区间内的个点来表示，因此积累概率F(S)将区间[0,1)分成许多不同的小区间，他们互不重叠，序列S的概率p(S)就是两点间小区间的长度。小区间内的一个点可用来表示序列的概率。2.4.2算术编码原理基本思路：把信源序列的积累概率映射到[0,1)区间上，使每个序列对应该区间内的一点，这些点把区间[0,1)分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的概率相匹配。算术编码的主要任务是计算信源序列对应的小区间。2.4.2算术编码原理小区间划分的递推计算公式小区间左端点递推公式：小区间右端点递推公式：新序列Sur对应区间的左端点值。信源序列S对应区间的左端点值。信源序列S对应区间的宽度值。信源符号ur对应区间的左端点值。新序列Sur对应区间的右端点值。信源序列S对应区间的左端点值。信源序列S对应区间的宽度值。信源符号ur对应区间的右端点值。2.4.2算术编码原理计算小区间端点值的步骤（1）给出信源符号对应的区间；（2）初始时，设S=Ø（Ø代表空集），low(Ø)=0，high(Ø)=1，range(Ø)=1（3）输入ur，根据公式计算序列Sur的左右端点值，依次下去，直到全部信源序列对应的区间被确定为止。2.4.2算术编码原理[例2-10]设信源

求信源序列S=abda对应的小区间信源符号对应区间端点值符号概率区间a0.5[0,0.5)b0.25[0.5,0.75)c0.125[0.75,0.875)d0.125[0.875,1)信源序列对应区间端点值信源序列lowhigha00.5ab0.250.375abd0.3593750.375abda0.3593750.36718752.4.2算术编码原理信源序列对应区间的划分0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.375不同的信源序列分别对应不同的互不重叠的小区间，取小区间内的一个点作为对应序列的编码。--------即时码S=abda的编码2.4.2算术编码原理译码步骤：（1）判断码字落在哪个符号区间，翻译出1个符号；（2）将码字减去刚翻译出的符号的左端点值；（3）用刚翻译出的符合对应的区间的长度去除步骤2的结果，判断此值落在哪个符号区间，翻译出一个新符号；（4）反复步骤（2）（3）直至全部信源序列被翻译完为止。2.4.2算术编码原理0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.3752.4.3算术编码的码长码字长度应与序列的概率匹配取信源序列码字的前L位，若后面有尾数，就进位到第L位。根据信源编码定理可知信源序列S的平均码长满足：平均每个信源符号的码长：对于DMS有2.4.4递推公式的应用用序列积累概率的递推公式进行序列的算术编码的计算步骤：（1）根据信源符号积累概率公式计算信源符号的积累概率；（2）初始时，设S=Ø，F(Ø)=0，p(Ø)=1；（3）根据序列的积累概率递推公式，计算序列的积累概率F(ur)和序列的概率p(ur)；（4）计算码长；（5）将F(s)写成二进制数形式，取其前L位作为序列S的码字，若后面有尾数就进位到第L位。2.4.4递推公式的应用例[2-12]设二元独立信源求信源序列S=1010的算术编码。解：信源符号的积累概率F(0)=0；F(1)=0.25信源序列1010算术编码序列F(S)p(S)L序列码字Ø01010.010.1111100.010.00112011010.0100110.001001301110100.0100110.00001001501010S=Ø，F(Ø)=0，p(Ø)=12.4.4递推公式的应用算术编码具有渐近最佳性：当序列无限增长时，平均码长渐近地等于序列的熵值。实际存在问题：递推运算中都有乘法——运算量大解决办法：1）编码对象是二元序列，符号概率较小的一个为2-k的形式，则乘以2-k等于移位，乘以1-2-k等于移位相减。

2）不做乘法的算术编码。2.4.5不做乘法的算术编码二元信源序列积累概率的递推公式为：

F(S0)=F(S)+p(S)F(0)=F(S)F(S1)=F(S)+p(S)F(1)p(S1)=p(S)p(1)p(S0)=p(S)p(0)p(S)=p(S0)+p(S1)，F(1)=p(0)如果令p(S1)≈2-qp(S)，则不做乘法的二进制算术编码的递推公式为

p(S0)=p(S)-p(S1)F(S0)=F(S)F(S1)=F(S)+p(S)F(1)=F(S)+p(S)p(0)=F(S)+p(S0)即：p(S1)≈2-qp(S)p(S0)=p(S)-p(S1)F(S0)=F(S)F(S1)=F(S)+p(S0)不做乘法的算术编码步骤：（1）初始时，设S=Ø，p(Ø)=0.111….1，F(Ø)=0.000…0;（2）输入一个信源符号，用递推公式计算p(S1)，p(S0)，F(S0)，F(S0)；（3）重复步骤（2），直至信源序列结束。2.4.5不做乘法的算术编码实际应用时，由p(S1)≈2-qp(S)，一般2-q近似等于二元序列中小概率符号的概率值。通常取p(0)≈2-q。2.5游程编码（RLC）游程编码属于无损压缩编码1)二元信源序列将“白”、“黑”二元信源用｛0，1｝表示。2)游程和游程序列

1°游程：规定以“0”开始的二元序列，例000101110010001…2°游程长度：序列中连续“0”段称“0”游程或“白”游程，其0的个数称“0”游程长度，记lW；序列中连续“1”段称“1”游程或“黑”游程，其1的个数称“1”游程长度，记lB。

3°游程序列:将二元序列中的lW、lB按其在二元序列中的顺序排列的序列称游程序列。上例3113213…3)游程编码将游程变换成游程序列后,二元序列就变换成多元序列.下面分别对“白”游程L(0)和黑”游程L(1)的编码进行讨论

1°白游程的熵

lW

:白游程的长度p(lW):白游程长度的概率

L白游程的最大长度

2°黑游程的熵

lB:黑游程的长度p(lB):白游程长度的概率

L白游程的最大长度

2.5游程编码（RLC）2.5游程编码（RLC）

3°白、黑游程编码的平均码长

4°白、黑游程的平均长度

5°白、黑像素的熵hWhB与平均码长

6°像素的熵h01与平均码长

pW:黑像素的概率pB:白像素的概率

2.5游程编码（RLC）2.6改进的Huffman码（MH）传真机信源编码应用于文件传真：如文件、手写稿、表格、报纸、图纸等“白”、“黑”像素点的信息。

CCITT(国际电话电报咨询委员会)为了保证传真文件的清晰度,对于A4幅面的文件（210mm×297mm）规定

1°行扫描线共有：

297mm×4线/mm=1188线或297mm×8线/mm=2376线

2°每条扫描线：

1728像素点/线，8像素点/mm3°对于A4幅面的文件像素点

1728像素点/线×1188线=2052864像素点

1728像素点/线×2376线=4105728像素点

直接编码,以码率2400bit/s或4800bit/s传输时间至少需5min以上.2.6改进的Huffman码（MH）2.6改进的Huffman码（MH）

方法介绍：Huffman编码＋游程编码MH编码：l=K+R，查表对游程编码之前,先要测得白、黑游程的概率分布,作为编码的依据.CCITT(国际电话电报咨询委员会)推荐8种样张我国原邮电部推荐7种样张为了减少码表数,采用截断Huffman编码(MH)

一类为结尾码,白、黑游程的长度为0--63

另一类为基干码,游程长度为64的整倍数2.6改进的Huffman码（MH）

例．一行中一段解：①lW＝131=2×64+3:K=10010R=1000∴100101000（l1=9）②lB=0×64+4:R=011（l2=3）③lW=0×64+6:R=1110（l3=4）④lB=1×64+6:K=0000001111R=0010（l4=14）比较：MH：码元表：9+3+4+14=30bit

直接编码：131+4+6+70=211bit

压缩比211/30=7.03lW＝131lB=4lW=6lB=70A．比较：码元表：MH：2×(64+1728/64)＝182个直接Huffman：2×1729=3458个性能：P（lW<61）＝80%P（lB<6）＝80%∴工程上性能不差

B．极限压缩比②

性能分析2.6改进的Huffman码（MH）2.7通用编码一、分段编码（LZ码）二、匹配编码三、LZW算法一、分段编码（LZ码）分段规则：

使连着的信源符号尽可能少，但不能出现重复段。

yj=yiur(j>i)

两个数可用一个数Nj（第j段段的码字）来表示

Nj=mi+r

特点：编码与符号概率无关。编码效率比较高。一、分段编码（LZ码）第j段码长公式：编码步骤：1.将信源序列分段2.计算Nj及第j段码长lj3.将Nj编成二进制码，取lj位为段的码字。[例1]设信源符号集U={a0,a1,a2,a3}，求信源序列S=a0a0a2a3a1a1a0a0a0a3a2的LZ编码。分7段：a0,a0a2,a3,a1,a1a0,a0a0,a3a2j段序号irNjlj码字1a00002002a0a212631103a3033400114a1011400015a1a040165100006a0a01045001007a3a23214501110信源序列码字：0011000110001100000010001110二、段匹配码（LZ78算法）编码步骤：1.分段2.将段号和信源符号分别进行编码，若组成二元码，段号所需码长每个信源符号所需码长：[例2]设信源符号集U={a0,a1,a2,a3}，求信源序列S=a0a0a2a3a1a1a0a0a0a3a2的匹配编码。分7段：a0,a0a2,a3,a1,a1a0,a0a0,a3a2

段号码字000001010011100101110段号1234567符号a0a0a2a3a1a1a0a0a0a3a2码字a000a101a210a311C=7段号所需码长：m=4信源符号所需码长：0000101101010000001110信源序列编码序列：000000010

010010110110

110001

001010

000110111

0二、段匹配码平均码长：当n很长时：LZ78码是一种简单的通用编码，编码方法不需要知道信源的统计概率分布，而且编码方法简单，编译码速度快，又能达到最佳压缩编码效率三、LZW算法LZW编码算法步骤：1.串表初始化：将所有单个字符存入串表中，并给每个符号赋一个码字值；2.将第一个输入字符作为“前缀串”P；3.每个新输入的字符作为扩展字符S。

若PS字符串不在串表中，输出P对应的码字，将PS存入串表并分配一个码字值；S→P；若PS已在串表中，PS→P；4.重复步骤3，知道完成编码。[例3]由三元字符X、Y、Z组成的信源序列为：

S=XYXYZYXYXYXXXXXXX求LZW编码。X1Y2Z3XY4YX5XYZ6ZY7YXY8YXYX9XX10字符串码字XXX11XXXX12输入信源序列XYXYZYXYXYXXXXXX输出LZW码字12435811011编码表（串表）LZW算法是LZ78算法的使用修正形式，保留了LZ码的自适应性能，压缩效率大致相同，成为计算机文件压缩的标准算法。且算法硬件实现容易。本章重点内容信息量、信息熵、互信息的概念及定义式。克拉夫特不等式无失真变长信源编码定理（香农第一定理）主要的编码方法：Huffman码、费诺码、香农-费诺码、算术码、MH码、LZ码。各种编码方法的平均码长和编码效率的计算。本章难点克拉夫特不等式:

表述了信源符号数与码字长度应满足什么条件才能构成即时码。唯一可译码有相同不等式存在----麦克米伦不等式这两个不等式都只是描述了可构造性，不能作为判定的论据。唯一可译码的判定准则：树图法：（即时码必为惟一可译码）尾随后缀法：（尾随后缀集合F中不含任一码字）本章难点010110010010111010011001110101111例.C1={0,10,1100,1110,1011,1101}F:{11,00,10,01,0,11,1,100,110,011,101}100非惟一可译码eg:1011001110...例.C2={1,10,100,1000}1101000000

F={0,00}惟一可译码C3={1,01,001,0001}

F=第三章相关信源编码一、预测编码二、变换编码一、预测编码(PredictiveCoding)预测编码的基本原理预测方法预测编码的基本类型DPCM编译码原理(略)预测编码的基本原理预测编码是数据压缩三大经典技术之一是将信源输出信号通过预测变换后再对信源输出与被测值的差进行编码。预测编码原理图：预测器编码器信源输出编码输出预测编码的基本原理实现预测编码的关键问题：1.预测误差准则的选取；（决定了预测质量）

1）最小均方误差准则（MMSE）--最常用，最基本的

2）功率包络匹配准则（PSEM）

3）预测系数不变性准则（PCIV）--用于多种混合信号预测

4）最大误差准则（ME）--遥测数据压缩2.预测函数的选取；3.预测器输入数据的选取。预测方法线性预测—样值和预测值之间呈线性关系

1）前值预测

2）一维预测

3）二维预测（非线性预测）最佳预测—是按某种准则，选择线性预测系数使得预测误差为最小。（常用MSE）自适应预测—预测器的预测系数不固定，随信源统计特性重新调整预测系数预测编码的基本类型脉冲编码调制—PCM(pulscodemodulation)差分脉冲编码调制—DPCM(differentialpulscodemodulation)噪声反馈编码—NFC(noisefeedbackcoding)预测误差门限型变换编码正交变换编码是图像数据压缩技术中的基本方法。主要变化方法：

1°K-L变换:协方差矩阵

2°离散付里叶变换DFT快速算法FFT3°离散余弦变换DCT快速算法FCT4°Walsh-Hadamard变换DWH5°小波变换K-L变换若信源矢量的相关矩阵为：则解

可得其特征值和特征矢量

0>1>….>N-1>0i=(ai0,ai1…ai,N-1),i=0,1,2..N-1

各

i必相互正交。(r-s)s’r=s[]’r-r[]’s=0,r≠s。各yr必相互线性无关Eyrys=E(rx’)(sx’)=E(rx’)(x’s)=r[]’s=srs=rss.

DFT变换离散余弦变换实数运算简单些.Hardmard-Walsh变换Haar变换非连续函数，N必须是2n.连续信源的熵和互信息信息率失真理论标量量化编码矢量量化编码语音压缩编码图象压缩编码第四章

限失真信源编码第四章

限失真信源编码

限失真编码：信源编码经过译码后能保留应用要求的信息，允许信源有一定的失真。为什么要限失真编码

1°连续信源的绝对熵为无限大，由于信道的带宽有限，受信道容量的限制。不可能实现完全无失真的信源信息的传输。(可能性)2°信道资源和技术经济因素的限制。(可实现性)3°实际应用不必要无失真地恢复信源消息,不必要完全无失真的信源信息的传输.(必要性)

4°数字系统的应用,模拟量的采样,量化也会引入失真.语音信号传输语音（音频）信号的带宽：20～20000HZ

实际应用音频范围:电话质量:300～3.4KHZ电话公用网调幅广播质量:50～7KHZ有现场感的语音传输高保真音频信号:20～20KHZ高保真音响图像信号传输一路6MHz的普通电视信号数字化后，其数码率将高达167Mbps，对储存器容量要求很大，占有的带宽将达80MHz左右表4－1各种图像信号应用的码率应用种类象素数

/行行数/帧码率bps压缩前压缩后HDTV192010801.18G20~25M普通电视720480167M4~8M会议电视35228836.5M1.5~2M电视电话1281125.2M56k一、连续消息的统计特性时间连续、取值连续2.描述:随机过程1.波形信源：例如：

在一个具体的时间点ti

，{x(ti)}

为一个取值连续的随机变量，可用有限维概率密度函数族描述：4.1连续信源的熵和互信息平稳随机过程：统计特性不随时间平移而变化的随机过程。★

{x(t)}在时刻t=ti的集平均:{x(t)}在某一时刻ti变量x(ti)的统计平均一、波形信源的特性2.描述:

★

{x(ti)}的时间平均：{x