信息论第三章离散信源无失真编码教程.ppt

第3章????????? 离散信源无失真编码 ;第3章 离散信源无失真编码 ;3．1 绪论 ;（1）提高传输效率，用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。;信源编码包括两个功能：;{a1, a2, …, aK}为信源符号集，序列中每一个符号uml都取自信源符号集。 {b1 ，b2 ，…，bD}是适合信道传输的D个符号，用作信源编码器的编码符号。编码输出码字cm = cm1 cm2 … cmn， c mk∈{b1 ，b2 ，…，bD} k = 1, 2 , …, n ，n表示码字长度，简称码长; 信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。; 3.变长码 若码字集合C中的所有码字cm (m = 1,2, …,M)，其码长不都相同，称码C为变长码。; 4.奇异码 对奇异码来说，从信源消息到码字的影射不是一一对应的。奇异码不具备惟一可译性。 ; 5.非奇异码 从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码。;扩展信源 ;对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然，见表3-2。;对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然，见表3-2。; 8. 即时码 对于变长码，又有如下定义; 表3-2中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码, 称之为即时可译码，简称即时码。 而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。;即时码可用树图法来构造。;码;3.1.2 平均码长的计算 ; N次扩展码的平均码长 等于扩展码中码字长度的概率加权平均值。 对于2次扩展码，有： (3-2) 设nm, ns分别是原信源消息um, us所对应的码长, cm, cs是um, us所对应的码字， 则式(3-2)中的nm + ns是扩展后新的信源序列nmns所对应的码字cmcs的长度； q(um) q (us)是cmcs出现的概率。 ;3.1.3 信息传输速率 ;【例3.8】 给定信源 ，为 提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到 ，求编码后的信息传输率RD 。 ;3.2 等长码及等长编码定理;3.2 等长码及等长编码定理;定理3.1 等长编码定理 设离散无记忆信源S ={x1 ，x2 ，…，xk}的熵为H（X），S的L维扩展信源为 ，对信源输出的L长序列si ，i = 1, 2, …, KL 进行等长编码，码字是长度为n的D进制符号串，当满足条件 ，则L →∞时，可使译码差错率pe δ(ε、δ为无穷小量)，反之，当 时，则不可能实现无差错编码。;编码效率 定理3.1要求 ，即 ， 可看出比值 是一个小于1的无量纲纯数，定义它为等长编码的编码效率，记为 （3-7） ;3.3 变长码及变长编码定理 ;3.3.2 克拉夫特不等式 ;3.3.3 变长编码定理 ;3.3.3 变长编码定理 ;Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。; 对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。 一般情况下，霍夫曼编码法得到的平均码长 最短，即编码效率最高。 编码效率定义为：;3.4.1 香农编码法 ;