第5章[无失真信源编码定理].ppt

信息论基础Elements ofInformation Theory;第5章 无失真信源编码;5.1 编码器;编码器的描述;信源编码器的主要任务：完成输入消息集合与输出代码集合之间的映射。若要实现无失真编码，则这种映射必须是一一对应的、可逆的。 ;常用码型;常用码型;常用码型;例：设信源X的概率空间为;表5.1 信源X的两种不同编码码字 ;常用码型;5.2 定长码 ;信源存在唯一可译定长码的条件：;实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，其信息熵约为1.4比特/符号，即平均每个英文符号所提供的信息量为1.4比特。 因此等长编码后5个二元符号只携带约1.4比特信息量。 对于无噪无损二元信道，每5个二元符号最大能载荷5比特的信息量。 因此，如此等长编码的信息传输效率极低。;5.4等长信源编码定理;编码信息率;5.5 变长码; 一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。故即时码一定是唯一可译码，反之，唯一可译码不一定是即时码。 ;树码：通过树图法构成的码叫树码 对r进制树图，有树根、树枝和节点。树图最顶部的节点称为树根。树枝的尽头称为节点，每个节点生出的树枝树目等于码符号树r。 ;Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.;即时码可用树图法来进行编码和译码。 构造步骤： 1、最上端为树根，从根出发向下伸出树枝，树枝总数等于m（码符号数），树枝的尽头为节点。 2、从每个节点再伸出m枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的节点称为中间节点。一直继续进行，直到都不能伸枝为止。 3、每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。;树码一定是即时码，任一即时码都可用上述树图法来表示。即时码一定是唯一可译码。唯一可译码，不一定是即时码。;例：一信源X (x1, x2, x3, x4)经编码后得码字集合S (1, 01, 001, 0001)且一一对应。现接收码元序列为101110001001101011，试写出译码结果。 解：该编码规则为：x1→1, x2→01, x3→001, x4→001，每一码字均以1结???，见1即可译码。对所接收序列的译码结果为 x1, x2, x1, x1, x4, x3, … 这种编码，译码时不需要考察后续码元，故又称之为即时码。 ;编码的树图表示 ;单义可译定理（即时码存在的充要条件）;例：信源空间为 X： x1, x2, x3, x4 P(X)： 1/2， 1/4， 1/8， 1/8 对其进行信源编码，信道基本符号集合为： {m=0, 1}；若编码后对应的码长分别为k1 = 1, k2 = 2, k3 = 3, k4 = 3，问能否构造出一种即时码？ 解：将m = 2, n = 4 和ki的4个值带入Kraft不等式得 ;Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.;唯一可译码的判断法;唯一可译码的判断步骤： ;5.6变长信源编码定理;码的平均长度是每个信源符号平均需用的码元数。平均每个码元携带的信息量即编码后信道的信息传输率为 若要信息传输效率高，需寻求使平均码长最短的码，即紧致码，或称最佳码。;平均码长可能达到的理论极限;编码效率： 码的剩余度： 二元无噪无损信道中信息传输率 ;例：有一离散无记忆信源 其熵为H(X)=0.811比特/信源符号。 用二元码构造一个非续长码：x1?0，x2?1 这时平均码长 ，编码效率 信道信息传输率为;对该信源的二次扩展信源进行编码如下 这个码的平均长度 得信源中每一个单个符号的平均码长 编码效率 信道信息传输率为 同样可得 ;香农第一定理仅是一个存在性定理，指出了平均码长与信源熵之间的关系，但没有给出如何构造的信息。 用前述例子的编码方法虽然可以得到即时码，但通常不是最佳编码，故有必要寻求更高效率的编码方法。