信息论 无失真信源编码

《信息论 无失真信源编码》由会员分享，可在线阅读，更多相关《信息论 无失真信源编码（42页珍藏版）》请在金锄头文库上搜索。

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称为码，即 。信源符号 对应 的码字 包含 个码符号， 称为码字长度，简称码长。 所以，信源编码就是把信源符号序列变换到码符号序列的一 种映射。 若要实现无失真编码，那么这种映射必须是一一 对应的、可逆的。 一般来说，人们总是希望把信源所有的 信息毫无保留地传递到接收端，即实现无失真传递，所以首 先要对信源实现无失真编码。图4

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

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

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

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

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

8、码符号集X中有r个码符号，码长为l，则 对于任意 ，只要满足则当N足够大时，可实现几乎无失真编码，即译码错误概率 任小；反之，如果则不可能实现几乎无失真编码，即当N足够大时，译码错误 概率为1。4.2 定长码及定长编码定理 定理5.2可以在离散平稳无记忆信源的条件下得到证明的，但它 同样适合于平稳有记忆信源，只要将式中H(S)改为极限熵 即可，条件是有记忆信源的极限熵 和方差 存在。 定长信源编码定理给出了定长编码时每个信源符号最少所需的 码符号的理论极限，该极限值由H(S)决定。 p定义4.6 设熵为H(S)的离散无记忆信源，若对信源的长为N 的符号序列进行定长编码，码符号集中码符号个数为r

9、，设码字长为l，定义 比特/信源符号为编码速率，它表示平均每个信源符号编码后能载荷的最大信息量。 这时，定理4.2的条件可表述为RH(S)+，即编码速率大于信 源的熵才能实现几乎无失真编码。为了衡量编码效果，引进编 码效率。4.2 定长码及定长编码定理 定义4.7 定义 为编码效率。 由定理4.2可得最佳编码效率为 ，所以在已知 方差和信源熵的条件下，信源符号序列长度N与最佳编码效 率和允许错误概率 的关系为： 当允许错误概率越小，编码效率又要高，那么信源符号序列 长度N必须越长在实际情况下，要实现几乎无失真的定长 编码，N需要的长度将会大到难以实现。4.3 变长码及变长编码定理4.3.1 K

10、raft不等式和McMillan不等式 定理4.3 设信源符号集为 ，码符号集为 ，对信源进行编码，得到的码为 ，码长分别 为 。即时码存在的充要条件是 这称为Kraft不等式。 由Kraft不等式可知，给定r和q，只要允许码字长度可以足够 长，则码长总可以满足Kraft不等式而得到即时码，Kraft不 等式指出了即时码的码长必须满足的条件 对于唯一可译码，该不等式又称为McMillan不等式。(4.11)4.3.1 Kraft不等式和McMillan不等式 定理4.4 唯一可译码存在的充要条件是 r为码符号个数，li为码字长度，q为信源符号个数。 定理4.4指出了唯一可译码中r、q、 之间的

11、关系，如果满足 这个不等式的条件，则一定能够构成至少一种唯一可译码 ，否则，无法构成唯一可译码它给出了唯一可译变长码 的存在性。 另外，从定理4.3和定理4.4可以得到一个重要的结论，即任 何一个唯一可译码均可用一个相同码长的即时码来代替， 因为即时码很容易用树图法构造，因此要构造唯一可译码 ，只要构造即时码就可以了。(4.12)4.3.2 唯一可译码的判别准则 A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判 断码C的唯一可译性此算法的原理如下所示： 其中 都是码字。可知，当且仅当某个有限长的码符号 序列能译成两种不同的码字序列时，此码不是唯一可译码， 此时

12、 一定是 的前缀，而 的尾随后缀一定是另一码字 的前缀；而 的尾随后缀又是其他码字的前缀最后，码符 号序列的尾部一定是一个码字。4.3.2 唯一可译码的判别准则 设C为码字集合，按以下步骤构造此码的尾随后缀集合F： p考查C中所有的码字，若 是 的前缀，则将相应的后缀 作为一个尾随后缀码放入集合 中； p考查C和 两个集合，若 是 的前缀或 是 的前缀，则将相应的后缀作为尾随后缀码放入集合 中 ； p 即为码C的尾随后缀集合； p若F中出现了C中的元素，则算法终止，返回假(C不是唯 一可译码)；否则若F中没有出现新的元素，则返回真。 定理4.5 一个码是唯一可译码的充要条件是的 并集中 没有C

13、中的码字。4.3.3 无失真变长编码定理 定义4.8 设有信源编码后的码字分别为 ，各码字相应的码长分别为li 因为是唯一可译码，信源符号 和码字 一一对应，则定义 此码的平均码长为 其中， 表示每个信源符号平均需用的码元数。 当信源给定时，信源熵H(S)就确定了，而编码后每个信源符 号平均用 个码元来变换，故平均每个码元载荷的信息量即 编码后信源的信息传输率。码符号/信源符号(4.20)4.3.3 无失真变长编码定理 定义4.9 编码后信源的信息传输率为 如果传输一个码符号平均需要t秒时间，则编码后信源每秒 钟提供的信息量为 可以看出， 越小，则 越大，信息传输率就越高，因此我 们感兴趣的码

14、是使平均码长 最短的码。 定义4.10 对于给定的信源和码符号集，若有一个唯一可 译码，其平均码长 小于所有其他唯一可译码，则称这种码 为紧致码或最佳码。 无失真信源编码的核心问题就是寻找紧致码比特/码符号(4.21)(4.22)4.3.3 无失真变长编码定理下面的定理给出了紧致码的平均码长可能达到的理论极限 定理4.6 若一个离散无记忆信源S，熵为H(S)，用拥有r个码 符号的码符号集 对S进行无失真编码，则总可以 找到一种唯一可译码，其平均码长满足若熵以r进制为单位，则式(4.23)可写成 另外还可以看到平均码长的极限值与无失真定长信源编码定 理中的极限值是一致的。(4.23)(4.33)4.3.4 香农第一编码定理 定理4.7 设离散无记