第5章-信源编码课件

第5章

无失真信源编码为什么要进行编码？信源发出的消息符号可能不适合信道的传输。将信源发出的消息符号转换为适合信道传输的符号。信源消息确定后，提高通信的有效性—信源编码。提高通信的可靠性,编码具有发现错误或纠正错误的抗干扰能力—信道编码。提高通信的安全性—加密编码。信源编码：以提高通信有效性为目的的编码。通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信道编码：是以提高信息传输的可靠性为目的的编码。通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。加密编码：是以提高通信系统的安全性为目的的编码。通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。一、信源的符号集和符号序列信源符号集：信源发出的符号消息的集合，记为X；设X有n个符号：X={x1,x2,…,xn

}.信源符号序列：由信源符号集合X中的符号组成长度为L的符号序列，记为。

L为信源符号序列长,不同的符号序列共有nL。

若L=1，则信源符号序列为信源符号集合中的符号。信源编码器信道码表5.1信源编码的基本概念二、码元和码字

1°码元(符)集

信道可传输的基本符号的集合,记为Y；设Y有m个符号：

Y={y1,y2,…,ym

}，其中yi

称为码元或码符。

m元信道:可传输m个基本符号的信道。二元信道:可传输2个基本符号的信道。这是一种最常用的信道,其基本符号常用0,1表示。

2°码字:

由码元组成的序列称为码字，记为Yi

。

码字Yi的码元个数Ki称为Yi的码长。

所有码字Yi的码长Ki

均相等称为码长为K定长码。

码字Yi的码长Ki

不全相等称为变长码。三、编码与译码1°信源编码：将信源符号xi或符号序列XLi

按一种规则映像成码字Yi的过程。2°无失真编码：信源符号到码字的映射必须一一对应。3°译码：从码符号到信源符号的映射。4°码表：所有映射规则的集合。四、许用码和禁用码1°许用码字：信源符号xi或符号序列XLi与码字Yi定义对应关系的码字。2°禁用码字：信源符号xi或符号序列XLi与码字Yi未定义对应关系的码字。3°许用码字的全体称为码集五、分组码（块码）分类

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

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

3°按译码唯一性分类唯一可译码：对于多个码字组成的有限长码流，只能唯一地分割成一个个的码字。唯一可译码又称为单义码。非唯一可译码：对有限长码流，不能唯一地分割成一个个的码字。信源符号ai码1码2a100a21110a30000a41101奇异码与非奇异码

【例】

码流100111000…

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

x2

x1

x3

x2x1x1

码2x1→1x2→10x3→11则无法唯一分割。4°按译码的即时性分类

非即时码：接收端收到一个完整的码字后，不能立即译码，还需要等到下一个码字开始接收后才能判断是否可以译码。即时码：接收端收到一个完整的码字后，就能立即译码，即时码又称为非延长码或异前缀码。

【例】

非即时码码流01001100…

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

即时码码流01001100…

x1→0x2→10x3→11译码为x1x2x1x3x1x1信源符号ai码1码2a110a21001a3100001a410000001即时码与唯一可译码即时码

异前缀码(即时码)：码集中任何一个码不是其他码的前缀。

即时码必定是唯一可译码,唯一可译码不一定是即时码。5°有实用价值的分组码分组码：将信源符号集中的每个信源符号固定地映射成一个码字。是非奇异码、唯一可译码、即时码。六、码树图

1°码树图:用码树来描述给定码集中各码字的方法。

2°码树图的树根、树枝、节点中间节点（一级节点、二级节点…）用○表示,终端节点用●表示。

3°二元（进制）码树

【例1】

x1→1x2→01x3→00

A○01○●x1

【例2】

x1→1x2→10x3→1101○●x2A○11●x3●x101●x2●x34°用码树图构造码在树的生长过程中，中间节点生出树枝，各树枝标出相应的码元，为了清晰起见，相同码元的树枝方向相同，终端节点表示信源符号，从树根到终端节点所经过的树枝旁的码元按经过的顺序组成的序列构成码字。5°用码树图构造即时码的条件如果表示信源符号的终端节点不再延伸，这样构造的码满足即时码条件。七、唯一可译码存在的条件1°前提条件：非奇异码2°唯一可译码存在定理设n为信源符号或信源符号序列个数，m为码元个数，Ki

为信源各符号或信源符号序列对应的码长。则唯一可译码存在的充分和必要条件是满足Kraft不等式

【注意】

Kraft不等式是一个存在定理，不是唯一可译码的判定定理;

如果n、m、Ki

满足Kraft不等式，则存在唯一可译码;

如果是唯一可译码,则n、m、Ki

必定满足Kraft不等式。一、平均码长和编码有效性

1平均码长

单符号信源空间，其中

信源符号xi

对应的码字为Yi

（i=1,2,…,n），码字Yi对应的码长为Ki（i=1,2,…,n

）。

所有的Ki相等为定长码，记为K,不相等时为变长码。

单符号对应变长码的平均码长为

码符/信源符号5.2离散信源编码符号序列信源空间XL

其中XL是X的L次扩展。

信源符号序列

对应的码字为Yi

（i=1,2,…,nL），码字Yi对应的码长为Ki（i=1,2,…,n

L）。

符号序列对应变长码的平均码长为

码符/信源符号序列码符/信源符号2编码效率（码率）定义：平均一个码符所携带的平均信息量称为编码效率，记作η。概率匹配原则：概率大的编短码，概率小的编长码。按照概率匹配原则编码可以提高编码效率。【例5.2.1】信源空间

H(X)=－(1/2log1/2＋1/4log1/4＋1/8log1/8＋1/8log1/8)=1.75bit/消息信源符号个数为n=4，二元码符{0,1}，码符个数为m=2，Ki为信源各符号对应的码字长,且满足Kraft不等式。

定长码:

K1=K2=K3=K4=22-2+2-2+2-2+2-2=1

码字:Y1=00,Y2=01,Y3=10,Y4=11

变长码:

K1=1,K2=2,K3=3,K4=32-1+2-2+2-3+2-3=1

码字:Y1=0,Y2=10,Y3=110,Y4=111定长码

x1→00x2→01x3→10x4→11

K=2η=1.75÷2=0.825变长码

方案1:

x1→0x2→10x3→110x4→111=1×1/2+2×1/4+3×1/8+3×1/8=1.75码符/信源符号

η=1.75÷1.75=1

方案2:

x1→111x2→110x3→10x4→0=3×1/2+3×1/4+2×1/8+1×1/8=2.625码符/信源符号

η=1.75÷2.625=0.667

比较方案1、2.二、定长编码定理

1定长编码定理

信源X有n个信源符号,其L次扩展信源为XL,信源熵为H(XL),信源

XL中的信源符号序列均用码长为

KL的码字对其进行编码，H(X)=H(XL)/L,对任意ε>0,δ>0,只要当L足够大时,必定可使译码码小于δ。若译码差错一定是有限值,当L足够大时,译码必定出错。

2切比雪夫不等式设随机变量ξ有数学期望Mξ及方差Dξ,则对任何正数ε，不等式成立。3定长编码L的计算计算随机变量I(xi)的数学期望M[I(xi)]，即H(X)；计算I(xi)的方差σ2(X)

。计算符号序列长度L

若已知编码效率η和译码错误概率δ三、变长编码定理

1平均码长的界限—变长编码定理符号信源空间

Y1

Y2…Yn

对应K1K2

…

Kn。m为码符个数，则存在唯一可译码，使其平均码长满足如下不等式证明：若xi

按如下不等式取所对应码字的码长为Ki若为整数,则上述不等式左边取等号。

故可得因为所以所有码字长度满足Kraft不等式。

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

（2）增加信道码元数m。2离散平稳无记忆序列变长编码定理信源X

的L次扩展信源XLXL的信源熵为：H(XL)bit/L个信源符号

XL所对应码字的码长为码符/L个信源符号因为，

所以，当L→∞时

【例5.2.2】

H(X)=0.811bit/符号

定长码

x1→0，x2→1K=1

编码效率η=H(X)/K=0.811序列：L=2，XL

x1x1

x1x2

x2x1

x2x2p(XL)9/163/163/161/16

H(XL)=1.622bit/2个符号

序列的定长码Y00011011K

2222编码效率η=H(XL)/KL=H(X)/K=0.811序列的变长码

Y010110111

Ki

1233=1×9/16+2×3/16+3×3/16+3×1/16=27/16=1.6875码符/2个信源符号编码效率

η=H(X)/K=0.811×32/27=0.961

当L=3η=0.985

L=4η=0.991采用扩展信源提高编码效率带来的问题：

(1)码表迅速扩大

(2)需求内存大

(3)译码延时三、信息传输效率

1平均信息率R

平均每个码元所含有的信息量。单位:bit/码元

2码元传输率码元速率(RB)：每秒钟传输码元的数目.单位:波特(B)

码元时间长度(TB):TB=1/RB，单位:秒(s)3平均信息传输率Rt

平均每秒钟传输的信息量Rt

=R/TB

单位:bit/s四、最佳编码

最佳码：能载荷一定信息量，码字的平均码长最短,可分离的码字集合。

编码思路：对概率大的信息符号编以短码，对概率小的信息符号编以长码

。

这种编码方法称为统计编码，熵编码，概率匹配编码。1Shannon编码方法若xi按如下不等式取所对应码字的码长为Ki

当m等于2时,logm=1，则Shannon编码过程:将信源符号消息按其出现概率的大小依次排序

p(x1)≥p(x2)…≥p(xn)按如下不等式取所对应码字的码长为Ki计算第i个消息的累加概率,以便获得唯一可译码将累加概率变换为二进制数；

取二进制数的小数点后Ki

位作为符号消息的二进制码。【例5.2.3】

xix1

x2

x3

x4

x5

x6

x7

p(xi)0.200.190.180.170.150.100.01解：信源熵H(X)=2.61bit/符号平均码长编码效率xip(xi)I(xi)KiPiPi二进制码字x10.202.32300.0000000x20.192.4030.200.0011001x30.182.4730.390.0110011x40.172.5630.570.1001100x50.152.7430.740.1011101x60.103.3240.890.111001110x70.016.6470.990.111111011111110Shannon编码过程【例5.2.3】

xix1

x2

x3

x4

x5

x6

x7

p(xi)0.200.190.180.170.150.100.01

2费诺（Fano

）编码方法将信源符号消息按其出现概率的大小依次排列

p(x1)≥p(x2)…≥p(xn)将依次排列的信源符号按其概率分为两大组,使两个组的概率之和近似相等,并对各组赋予一个码元0和1。按前一步将每一大组再分为两组,各组再赋予一个码元0和1。如此重复,直至每个组只剩一个信源符号为止。信源符号所对应的码字即为Fano

码。【例5.2.4】Fano

编码过程xip(xi)第1次第2次第3次第4次码字码长x0.2000002x20.190100103x30.180110113x40.1710102x50.151101103x60.10111011104x70.01111111114平均码长编码效率3Huffman编码方法将信源符号消息按其出现概率的大小依次排序

p(x1)≥p(x2)…≥p(xn)取两个概率最小的符号分别配以0和1,并将这两个概率相加作为新符号的概率,与未分配的符号重新排序。对重新排序后的两个概率最小的符号重复(2)的过程。不断重复上述过程，至最后两个符号配以0和1为止。从最后一级开始,向前返回到各个信源符号所对应的码元序列，即为相应的Huffman码。【例5.2.5】

x

p(xi)编码过程码字x10.200.200.260.350.390.610

10x20.190.190.200.260.3500.391

11x30.180.180.190.2000.261

000x40.170.170.1800.191

001x50.150.15

00.171010x60.1000.111

0110x70.011

0111平均码长编码效率Huffman编码方法并不唯一，因为：每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别。缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编码方法得到的码字长度ki也不尽相同。x

p(xi)编码过程码字

○x10.40.4

0.40.60

1

0

1x20.20.20.400.41

01○●x1x30.20.2

00.21

000

0

1

x40.100.2

1

0010○●x2X50.11

0011

0

1

x3●○x10.40.40.40.60

00

01x20.20.20.400.41

10

x4●●x5x30.20.200.21

11x40.100.21

100

x50.11

101

【例5.2.6】