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

《信息论第4章无失真信源编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章无失真信源编码重庆交通大学信息科学与工程学院通信工程系李益才2012年8月第4章无失真信源编码4.1信源编码的相关概念4.2定长码及定长编码定理4.3变长码及变长编码定理4.4变长码的编码方法4.5实用的无失真信源码方法4.1信源编码的相关概念4.1.1编码器信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为码序列，对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码，完成编码功能的器件，称为编码器。接收端有一个译码器完成相反的功能。信源编码器的输入是信源符号集，共有q个信源符号。同时存在另一个符号集，称为码符号集，

2、共有r个码符号，码符号集中的元素称为码元或码符号，编码器的作用就是将信源符号集S中的符号变换成由个码符号组成的一一对应的码符号序列。编码器输出的码符号序列称为码字，并用来表示，它与信源符号之间是一一对应的关系，如图4.1所示。4.1.1编码器码字的集合C称为码，即。信源符号对应的码字包含个码符号，称为码字长度，简称码长。所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总是希望把信源所有的信息毫无保留地传递到接收端，即实现无失真传递，所以首先要对信源实现无失真

3、编码。图4.1信源编码器4.1.1编码器信源编码有以下3种主要方法：匹配编码根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。这类编码主要有香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。变换编码先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。包括DCT、DFT、DWT。识别编码识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如文字和语音的识别。后两种信源编码均为有失真的信源编码。无失真信源编码

4、针对离散信源，连续信源在量化编码的过程中必然会有量化失真，连续信源只能近似地再现信源的消息。4.1.2码的分类分组码和非分组码定义4.1将信源符号集中的每个信源符号固定地映射成一个码字，这样的码称为分组码。用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非分组码，又称为树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。奇异码与非奇异码定义4.2若一种分组码中的所有码字都不相同，则称此分组码为非奇异码，否则称为奇异码。4.1.2码的分类唯一可译码与非唯一可译码定义4.3任

5、意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码。唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。即时码与非即时码定义4.4无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。4.1.2码的分类下面讨论唯一可译码成为即时码的条件。定义4.5设为一码字，对于任意的，称码符号序列的前j个元素为码字的前缀。按照上述的前缀的定义，有下述结论：定理4

6、.1一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。即时码可以用树图来构造．图5.2是一个二元即时码的树图．图5.2二元即时码的树图4.1.2码的分类树是没有回路的图，所以它也是由节点和弧构成的．树中最顶部的节点称为根节点，没有子节点的节点称为叶子节点。所有根节点的子节点称为一阶节点，所有一阶节点的子节点称为二阶节点，依此类推。阶节点最多有个。节点的阶次又称为节点的深度。综上所述，可将信源编码作如下分类：码非分组码（树码）分组码（块码）奇异码非奇异码非唯一可译码唯一可译码即时码非即时码4.2定长码及定长编码定理若对一

7、个有q个信源符号的信源S进行定长编码，那么信源S存在唯一可译定长码的条件是(4.1)其中，r是码符号集中的码元数，l是定长码的码长。如果对信源S的N次扩展信源进行定长编码，若要编得的定长码是唯一可译码，则必须满足(4.2)其中，q是信源S的符号个数，是信源S的N次扩展信源的符号个数，r是码符号集X的码符号数。4.2定长码及定长编码定理定长编码的信息传输效率是很低的。提高信息传输效率的方法有：方法1考虑符号之间的依赖关系，对信源S的扩展信源进行编码。方法2对于概率等于0或非常小的符号序列不予编码。定理4.2离散无记忆信源的熵为H(S)

8、，若对信源长为N的序列进行定长编码，码符号集X中有r个码符号，码长为l，则对于任意，只要满足则当N足够大时，可实现几乎无失真编码，即译码错误概率δ任小；反之，如果则