信息论与编码重点笔记.docxVIP

实习一：设计程序判别唯独可译码

一、题目分析

设计一个程序实现判别输入码组是否为可译码组这一功效。

在我们学习使用了克拉夫特不等式之后，知道唯独允许码务必满足克拉夫特不等式。但是克拉夫特不等式仅仅是存在性的判定定理，即该定理不能作为判别一种码是否为唯独可译码的依据。也就是说当码字长度和码符号数满足克拉夫特不等式时，则必允许构造出唯独可译码，否则不能构造出唯独可译码。所以我们务必找到一种能够判别一种码是否为唯独可译码的形式---Sardinas—Patterson算法。

二、算法分析

Sardinas—Patterson算法描述：

设C为码字集合，按以下步骤构造此码的尾随后缀集合