2018年6月25日星期一

对独立可译码的判断

假定有两个二进制码字a和b,其中a的长度为k比特,b的长度为n比特,且k<n。如果b的前k比特与a相同,则将a称为b的前缀。b的后n-k比特称为悬挂后缀(dangling
suffix)。例如,如果a=010,b=01011,则称a为b的前缀,悬挂后缀为11。
1. 构造一个包含全部码字的集合。
2. 查看所有码字是否有任意码字是另一个码字的前缀,如果发现这样一对码字,则将悬挂后缀补充道清单中,如果在之前的迭代过程中已经添加了该后缀,则不再添加。
3. 利用这个更大的集合重复上述步骤,知道发现两种情况之一:
(1)发现一个悬挂后缀是码字。
(2)没有更多悬挂后缀了。

如果是第一种情况,该代码就不是独特可译码。如果是第二种情况,就是独特可译码。


例1:码字{0,01,11}

码字0是码字01的前缀,悬挂后缀为1。在其他码字对中不存在一个元素是另一个元素前缀的情况。向码字列表中添加该悬挂后缀:
{0,01,11,1}
对比这个列表的元素,发现0是01的后缀,悬挂后缀为1。但元素1已经在列表中了。另外,1是11的一个前缀,悬挂后缀为1,也已经在列表中了。没有其他码字对会生成悬挂后缀,所以不能再向列表中添加内容。因此,{0,01,11}是独特可译码。

例2:码字{0,01,10}
码字0是码字01的前缀,悬挂后缀为1。在其他码字对中,不存在一个元素是另一个元素前缀的情况。向码字列表中添加悬挂后缀1,得到{0,01,10,1}
在这个列表中,1是10的前缀。这一对码字的悬挂后缀为0,它是已有的码字。因此,{0,01,10}不是独特可译码。

较新的博文 较早的博文 主页