信息论惟可译码判别方法专题培训课件

信息论惟可译码判别方法3.唯一可译码与非唯一可译码

定义5.3

任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码。唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。4.即时码与非即时码

定义5.4

无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。下面讨论唯一可译码成为即时码的条件。

定义5.5

设为一码字，对于任意的，称码符号序列的前j个元素为码字的前缀。按照上述的前缀的定义，有下述结论：

定理5.1

一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。即时码可以用树图来构造．图5.2是一个二元即时码的树图．图5.2二元即时码的树图树是没有回路的图，所以它也是由节点和弧构成的．树中最顶部的节点称为根节点，没有子节点的节点称为叶子节点。所有根节点的子节点称为一阶节点，所有一阶节点的子节点称为二阶节点，依此类推。阶节点最多有个。节点的阶次又称为节点的深度。综上所述，可将信源编码作如下分类：码非分组码（树码）分组码（块码）奇异码非奇异码非唯一可译码唯一可译码即时码非即时码唯一可译码的判别准则A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判断码C的唯一可译性．此算法的原理如下所示：

其中都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时一定是的前缀，而的尾随后缀一定是另一码字的前缀；而的尾随后缀又是其他码字的前缀．最后，码符号序列的尾部一定是一个码字。设C为码字集合，按以下步骤构造此码的尾随后缀集合F：(1)考查C中所有的码字，若是的前缀，则将相应的后缀作为一个尾随后缀码放入集合中；(2)考查C和两个集合，若是的前缀或是的前缀，则将相应的后缀作为尾随后缀码放入集合中；(3)即为码C的尾随后缀集合；(4)若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)

否则若F中没有出现新的元素，则返回真。定理5.5

一个码是唯一可译码的充要条件是的并集中没有C中的码字。2023/5/247惟一可译码判别准则——例题命题5.4.1一种码是唯一可译码的充要条件是S1,S2,…中没有一个含有S0中的码字。S0S1S2S3S4S50000010111011100011000111101111001111101110111101惟一可译码判别准则——例题S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde方法一:根据异前缀码是唯一可译码来进行判断。其步骤如下:首先,观察是否为非奇异码。若是奇异码,肯定不是唯一可译码;其次,计算是否满足Kraft不等式。若不满足一定不是唯一可译码;最后,将码画成一棵码树图,观察是否满足异前缀码的码树图的构造,若满足则是唯一可译码。这种方法的理论基础是异前缀码一定是唯一可译码,通过经典的Kraft不等式及码树图进行判别。但它的缺点也是显而易见的,若不是异前缀码时,则此方法无法判断是否是唯一可译码惟一可译码判别方法方法二:使用A.A.Sardinas和G.W.Patterson设计的判断