信息论与编码第4章无失真信源编码

信源编码信源编码是以提高通信的有效性为目的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。同样多的信息用较少的码率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。1信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。2信源编码的基础是信息论中的两个编码定理：无失真信源编码定理限失真信源编码定理

无失真信源编码只适用于离散信源

对于连续信源，只能在失真受限制的情况下进行限失真编码下面介绍几种典型的离散信源编码方法。3第4章无失真信源编码4.1无失真信源编码的概念4.2等长编码4.3变长编码4.4常用的变长编码算法44.1无失真信源编码的概念信源符号(字母)集：S＝{s1,s2,…,sq}.码符号(字母、元)集：A＝{a1,a2,…,am}.编码函数f:将有限个信源符号变换成有限个码符号的函数

用AN表示全体长度为N的信源符号序列构成的集合码字：wi

=f(si)码字wi的长度(码长)：li=l(wi)码:C={wi

=f(si)|si

SN}.54.1无失真信源编码的概念N=1时f：无失真信源编码器6如何分离码字？如果0，01都是码字，译码时如何分离？？74.1无失真信源编码的概念例4-1几个二元码

信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001码的扩展码C1的扩展:s1s3

001084.1无失真信源编码的概念m元码:码符号集A＝{a1,a2,…,am}.

二元码:m=2,A＝{0,1}等长码（定长码）:所有码字的码长相等.

例:中文电报码是码长为4的等长的10元码中

0022;国

0948;

北

0554;京

0079.变长码（非定长码）:码字的码长不相等.非奇异码:

s1,s2

A,s1

s2

f(s1)

f(s2)

否则，称为奇异码94.1无失真信源编码的概念唯一可译码:

任意有限长的码元序列,只能被唯一地分割成一个一个的码字,则称为唯一可译码,或单义可译码.否则，就称为非唯一可译码,或非单义可译码.

例：码4是唯一可译码:1000100

1000,100

码3是非唯一可译码:1000100

10,00,10,0或10,0,01,00信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001备注等长码非唯一可译非

唯一可译唯一可译及时码104.1无失真信源编码的概念即时码:

如果收到一个码字后,就能及时译出，则称为即时码,也称为非延长码，或异前缀码.即没有任何完整的码字是其它码字的前缀。否则，就称为非即时码.

例：码5是即时码,码4是非即时码.信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001备注等长码非唯一可译非

唯一可译唯一可译及时码11关系即时码一定是唯一可译码唯一可译码一定是非奇异码定长的非奇异码一定是唯一可译码非定长的非奇异码不一定是唯一可译码4.1无失真信源编码的概念12第4章无失真信源编码4.1无失真信源编码的概念4.2等长编码4.3变长编码4.4常用的变长编码算法134.2等长编码离散信源X的熵：H(X)字母集:S＝{s1,s2,…,sq}.对信源输出的N个符号进行编码:共有qN个消息码元集A＝{a1,a2,…,am}.

长度为L的等长码：共有mL个可能码字能正确译码的必要条件：(非奇异码)144.2等长编码编码速率（编码信息率）:编码后每个信源符号所能承载的的最大信息量编码效率平均码长：平均每个信源符号所需要的码符号个数编码效率:154.2等长编码例4-2

设一个离散信源的输出字母表有q=10个符号，将其编为无失真二元码，即m=2

，求平均码长。164.2等长编码无失真编码假设信道无干扰译码错误概率:Pe=P{M

M’}无失真编码:译码错误概率Pe可以任意小.MWM’信源信源编码信道

信宿信源解码W174.2等长编码等长信源编码定理定理4-1(Shannon信源编码定理)

设离散无记忆信源X的熵为H(X),若对长为N的信源符号序列进行等长编码,码长为L

,码元符号个数为m.则对任意的

>0,

>0,只要时,则译码差错概率一定是有限值(不可能实现无失真编码),而当N足够大时,译码错误概率近似等于1。则当N足够大时，必可使译码错误概率小于

。反之，当184.2等长编码等长信源编码定理最佳等长编码:

编码效率:194.2等长编码等长信源编码定理设信源自信息方差为D(X)=D[I(pi)]，编码效率为

,当允许译码错误概率Pe

<

时，有容许译码错误概率越小信源序列长度越大编码效率越高20第4章无失真信源编码4.1无失真信源编码的概念4.2等长编码4.3变长编码4.4常用的变长编码算法214.3变长编码字母集:S＝{s1,s2,…,sq}.信源X的概率分布：p(si)(i=1,2,…,q

).离散信源X的熵：H(X)码元集A＝{a1,a2,…,am}.

信源符号si的码字:wi=f(si)

码字wi的长度为li

(i=1,2,…,q

)224.3变长编码编码速率:编码后每个信源符号所能承载的的最大信息量编码效率:不等长码的编码效率平均码长:码的多余度（剩余度）:234.3变长编码平均码长：平均每个信源符号所需的码元符号个数信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001备注2非唯一可译非唯一可译唯一可译及时码平均码长21.51.51.8751.875244.3变长编码码树编码方法三元树码：C={w1,w2,…,w11}w1=0,w2=11,w3=12,w4=20,w5=22,w6=100,w7=101,w8=102,w9=210,w10=211,w11=212.树码一定是即时码011201201210202w2w3w1w4w10w5w9w8w7w6w110级节点1级节点2级节点3级节点254.3变长编码码树编码方法（1）树根编码的起点；（2）每一个中间节点树枝的个数

编码的进制数；（3）树的节点

编码或编码的一部分；（4）树的终止节点（端点、树叶）

码；（5）树的节数

码长；（6）码位于多级节点

变长码；（7）码位于同一级节点码

等长码；011201201210202w2w3w1w4w10w5w9w8w7w6w110级节点1级节点2级节点3级节点264.3变长编码克拉夫不等式(L.G.Kraft,1949)长度为l1,l2,…,lr的m元即时码存在的充分必要条件是：麦克米伦定理(麦克米伦:B.McMillan,1956).长度为l1,l2,…,lr的m元唯一可译码存在的充分必要条件是:274.3变长编码例信源符号概率分布码1:C1码2:C2码3:C3码4:C4码5:C5s10.5000011s20.250111101001s30.125100000100001s40.12511110110000001备注2非唯一可译非唯一可译唯一可译及时码平均码长21.51.51.8751.87528判断以下码字是否可分离（唯一可译）？习题294.3变长编码设离散信源X的熵为H(X),则其任意一个m元唯一可译码满足：同时存在m元唯一可译码，其平均长度满足：单个符号不等长信源编码定理304.3变长编码设离散信源X的熵为H(X),其N次扩张信源为XN，将信源XN编为m元码，总存在唯一可译码f，使得信源X的每个符号所需的平均码长满足：离散平稳无记忆序列变长编码定理香农第一编码定理31第4章无失真信源编码4.1无失真信源编码的概念4.2等长编码4.3变长编码4.4常用的变长编码算法324.4.1香农编码设有离散无记忆信源331234香农编码方法的步骤按信源符号的概率从大到小的顺序排队不妨设34例设有一单符号离散无记忆信源试对该信源编二进制香农码。35编码过程（1）3637§4.1.2费诺编码对概率按m进行分组，使每组概 率尽可能相等给每个分组分配一个码元对每个分组重复2、3步，直到不可分为止1234按信源符号的概率从大到小的顺序排队不妨设38设有一单符号离散无记忆信源试对该信源编二进制费诺码。例39编码过程40可以看出本例中费诺码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。41将信源符号按概率由大到小顺序排队给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队给缩减信源中概率最小的符号各分配一个码元重复步骤2、3直至概率和为121434.4.3赫夫曼编码42设有一单符号离散无记忆信源试对该信源编二进制哈夫曼码。例43编码过程444546说明：Huffman码的编码方法不是唯一的。首先，每次对缩减信源两个最小的符号分配“0”和“1”码元试任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长，平均码长都不变，所以没有本质区别。其次，若合并后的新符号的概率与其他符号的概率相等，从编码的方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不同。不同的编法得到的码字长度也不尽相同。47对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。如下面的例子48例

设有离散无记忆信源用两种不同的方法对其编二进制huffman码49方法一方法二50信源符号xi概率p(xi)码字Wi1码长Ki1码字Wi2码长K’i2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113两种不同的编码方法得到的码字和码长的对比51平均码长和编码效率52两种编码方法编出的码字的码长方差比较53可以看出第二种编码方法的码长方差要小许多。这意味着第二种编码方法的码长变化较小，比较接近平均码长。由此可以得到一个结论(怎样得到码方差较小的huffman编码)。54结论：进行赫夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。

554.4常用的变长编码算法最佳不等长编码(最佳码)

对于给定的信源和码元符号集，在其所有的唯一可译码中，平均长度最小的码称为最佳码，或紧致码。字母集:S＝{s1,s2,…,sq}.信源X的概率分布：p(si)(i=1,2,…,q

).码元集A＝{a1,a2,…,am}.

信源符号si的码字:wi=f(si)

码字wi的长度为li

(i=1,2,…,q

)564.4常用的变长编码算法习题

已知离散无记忆信源X为：求二进制香农码，二进制费诺码，二进制霍夫曼码，三进制霍夫曼码。

574.4常用的变长编码算法信源X的熵:H(X)=2.61符号序列概率分布第1次分组第2次分组第3次分组第4次分组码字码长a10.200(0.57)0(0.2)002a20.191(0.37)00103a30.1810113a40.171(0.43)0(0.17)102a50.151(0.26)01103a60.1010(0.10)11104a70.011(0.01)11114584.4常用的变长编码算法习题

求以下信源X的霍夫曼码解：赋予码元594.4常用的变长编码算法解：写出码字

604.4常用的变长编码算法习题

求以下信源X的三进制霍夫曼码614.4常用的变长编码算法符号序列概率分布123码字码长a0a0

9/169/169/160101a0a13/164/16017/16112a1a03/16013/161003a1a1

1/161013例4.10设二元离散无记忆信源X的符号集为{a0,a1},概率分布为：p0=0.75,p1=0.25,则

H(X)=0.75log0.750.25log0.25=0.811.

对两个信源符号X2进行编码,则有624.4常用的变长编码算法例4.10

对三个信源符号X3进行编码634.4常用的变长编码算法课堂练习已知离散无记忆信源X如下，求其三元霍夫曼码。并求其平均码长与编码效率。644.4常用的变长编码算法LZ码1977年，齐费(J.Ziv,以色列)与兰佩尔齐(A.Lempel,以色列)提出LZ码，1978年进行改进，称为LZ78.设信源符号集S＝{s1,s2,…,sq},输入信源符号序列为

u=u1u2…uL

(ui

S)编码规则分段：将符号序列u分成小段。分段原则:各小段尽可能短，且不相同.分成的小段称为短语.

短语总数记为:M(u)依次