第5章(无失真信源编码定理).ppt

2004-10-28 Elements of Information Theory 第5章 无失真信源编码 5.1 编码器 5.2 等长码 5.3 渐进等分割性和e典型序列* 5.4 等长信源编码定理 5.5 变长码 5.6 变长信源编码定理 5.1 编码器 对整个通信系统来说，要解决两个问题：信源编码和信道编码。 ?对信源来说有两个重要问题：一个是信源输出信息量的定量度量问题。这在前面信源及其信息熵章中已讨论。本章将要讨论第二个问题：如何有效地表示信源输出问题。即将重点讨论对信源进行无失真信源编码的要求、方法及理论极限，从而得出香农第一定理。 信源编码器的主要任务：完成输入消息集合与输出代码集合之间的映射。若要实现无失真编码，则这种映射必须是一一对应的、可逆的。 常用码型 1、二元码：若信道码符号集A={0，1 }，编码输出的码字都是二元码，称为二元码。 2、等长码：若一组码中所有码字的码长都相同，称为等长码。 3、变长码：若一组码中所有码字的码长Ki各不相同，即任意码字由不同长度的码符号序列组成，则称为变长码。 常用码型 4、非奇异码和奇异码：若一组分组码中的所有码字都不相同，即所有信源符号映射到不同的码字。称此分组码为非奇异码。否则为奇异码 5、同价码和非同价码：若每个码符号的传输时间都相同则称为同价码。否则为非同价码 5.5 变长码 变长码也必须是唯一可译码，才能实现无失真编码。 定义：在唯一可译变长码中，有一类码，它在译码时，无须参考后续的码符号就能立即作出判断，译成对应的信源符号，则这类码称为即时码 5.6变长信源编码定理 设信源 有n个离散符号，编码后的码字为 其码长分别为 对于唯一可译码来说，信源符号与码字一一对应，所以有 则这个码的平均长度为 码的平均长度是每个信源符号平均需用的码元数。平均每个码元携带的信息量即编码后信道的信息传输率为 若要信息传输效率高，需寻求使平均码长最短的码，即紧致码，或称最佳码。 平均码长可能达到的理论极限 定理：若一离散无记忆信源 X 具的熵为H(X)，并有 r 个码元的码符号，则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足 无失真变长信源编码定理 编码效率： 码的剩余度： 二元无噪无损信道中信息传输率 例：有一离散无记忆信源 其熵为H(X)=0.811比特/信源符号。 用二元码构造一个非续长码：x1?0，x2?1 这时平均码长 ，编码效率 信道信息传输率为 对该信源的二次扩展信源进行编码如下 这个码的平均长度 得信源中每一个单个符号的平均码长 编码效率 信道信息传输率为 同样可得 香农第一定理 信息论课件 通信与信息基础教学部 信息论课件 通信与信息基础教学部 编码器的描述 码元 码字 码 码长 l 码符号集 常用码型 6、码的N次扩展码：假使某分组码W，把信源X中的符号xi一一变换成码W中的码字Wi 字，则码W的N次扩展码是N个码字组成的码字序列的集合。 ? 例：设信源X的概率空间为 若把该信源通过一个二元信道进行传输，为适合信道传输，就必须把信源符号xi变换成0、1符号组成的码序列（二元序列）。可采用不同的二元序列使其与信源符号si一一对应，所以可有多种方法得到二元码。如表4.1所示 表5.1 信源X的两种不同编码码字 现求码S2的二次扩展码。 常用码型 7、唯一可译码：若码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此码为唯一可译码。否则，称为非唯一可译码。 唯一可译码的物理含义：不仅要求不同的码字表示不同的信源符号，而且还进一步要求对由信源符号构成的信息序列进行编码时，在接收端仍能正确译码，而不发生混淆。 本章主要研究的是同价唯一可译码。 5.2 定长码 一般来说，若要实现无失真的编码，所编的码必须是唯一可译码，否则，就会因译码带来的错误与失真。 非奇异定长码的N次扩展码一定也是非奇异定长码。 非奇异定长码一定是唯一可译码。 信源存在唯一可译定长码的条件： 对信源X 进行等长编码，必须满足 其中l 是等长码的码长,有 例：英文电报有32个符号，即n=32。若对它进行二元编码，则r=2，可得l=5。也就是说，每个英文电报符号至少要用5位二元符号编码才行。 实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，其信息熵约为1.4比特/符号，即平均每个英文符号所提供的信息量为1.4比特。 因此等长编码后5个二元符号只携带约1.4比特信