信息论与编码[第五章无失真信源编码定理与编码]山东大学期末考试知识点复习.pdfVIP

山东大学期末考试知识点复习

第五章无失真信源编码定理与编码

5．1．1信源编码和码的类型

1．信源编码

2．码的类型

若码符号集中符号数r=2称为二元码，r=3称为三元码，……，r元码。

若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。

若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。

若每个码符号x∈X的传输时间都相同则称为同价码，否则称为非同价码。

i

若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号

序列则称为唯一可译码，否则称为非唯一可译码。

若分组码中,没有任何完整的码字是其他码字的前缀，则称为即时码（又称

非延长码或前缀条件码），否则称为延长码。

本章主要研究的是同价唯一可译码.

5．1．2即时码及其树图构造法

即时码（非延长码或前缀条件码)是唯一可译码的一类子码。

即时码可用树图法来构造。构造的要点是:

（1）最上端为树根A，从根出发向下伸出树枝，树枝总数等于r，树枝的尽

山东大学期末考试知识点复习

头为节点。

（2）从每个节点再伸出r枝树枝，当某节点被安排为码字后,就不再伸枝，

这节点为终端节点。一直继续进行，直至都不能伸枝为止。

(3）每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应

的码符号序列则为终端节点的码字。

即时码可用树图法来进行编码和译码。

从树图可知，即时码可以即时进行译码。

当码字长度给定，即时码不是唯一的。

可以认为等长唯一可译码是即时码的一类子码。

5．1．3唯一可译码存在的充要条件

（1)对含有q个信源符号的信源用含r个符号的码符号集进行编码,各码字的

码长为l，l,…,l的唯一可译码存在的充要条件是,满足Kraft不等式

12q

5．1．4唯一可译码的判断法

唯一可译码的判断步骤:

首先，观察是否是非奇异码.若是奇异码则一定不是唯一可译码。

其次，计算是否满足Kraft不等式。若不满足一定不是唯一可译码。

再次，将码画成一棵树图，观察是否满足即时码的树图的构造,若满足则是

唯一可译码。

或用Sardinas和Patterson设计的判断方法：计算出分组码中所有可能的尾

山东大学期末考试知识点复习

随后缀集合F，观察F中有没有包含任一码字，若无则为唯一可译码;若有则一

定不是唯一可译码.

上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是

否是唯一可译码的方法,所以可以跳过前三个步骤直接采用该判断法。

5．1．5渐近等分割性和ε典型序列

则称此N长序列αi为非ε典型序列。

（2)ε典型序列集

山东大学期末考试知识点复习

5．1．6无失真等长信源编码定理

离散信源S，其信息熵为H∞，用含r个字母的码符号集对N长信源符号序

列进行等长编码，若满足l/N≥H∞/logr+ε(ε0的任意小数)，则当N足够大时,

可实现几乎无失真编码。

其中，当S为离散无记忆信源时,H∞=H（S）;

当S为离散平稳信源，H∞为信源的极限熵；

当S为马尔可夫信源，H∞为马尔可夫信源的极限熵。

5．1．7无失真变长信源编码定理(香农第一定理）

用含r个字母的码符号集对N长信源符号序列进行变长编码,总能找到一种

无失真的唯一可译码，使信源符号所需平均码长满足:

山东大学期末考试知识点复习

5．1．8无失真信源编码定理和数据压缩

1．无失真数据压缩的极限值

无失真信源编码定理（无论等长码