河南理工大学课程设计报告书
信息论与编码课程设计报告
设计题目：判断唯一可译码、香农编码
专业班级 电信12-03 学 号 311208000607 学生姓名 曹 琳 指导教师 成凌飞 教师评分
2015年 3月21日
河南理工大学课程设计报告书
目 录
一、设计任务与要求.................................................................................................................2 二、设计思路.............................................................................................................................2 三、设计流程图.........................................................................................................................3 四、程序运行及结果.................................................................................................................4 五、心得体会.............................................................................................................................6 参考文献.....................................................................................................................................7 附录：源程序.............................................................................................................................8
1
河南理工大学课程设计报告书
一、设计任务与要求
通过本次课程设计的练习，使学生进一步巩固信源熵、信源编码的基本原
理，掌握具体的编码方法，熟悉编程软件的使用，培养学生自主设计、编程调试的开发能力，同时提高学生的实践创新能力。
1、判断唯一可译码
利用尾随后缀法判断任意输入的码是否为唯一可译码，即设计一个程序实现判断输入码组是否为唯一可译码这一功能。
2、香农编码
熟悉运用香农编码,并能通过C语言进行编程,对任意输入消息概率，利用香农编码方法进行编码，并计算信源熵和编码效率。
二、设计思路
1、判断唯一可译码
在我们学习使用了克劳夫特不等式之后，知道唯一可译码必须满足克劳夫特不等式。但是克劳夫特不等式仅仅是存在性的判定定理，即该定理不能作为判断一种码是否为唯一可译码的依据。也就是说当码字长度和码符号数满足克劳夫特不等式时，则必可以构造出唯一可译码，否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译码的方法，尾随后缀法。 尾随后缀法算法描述：
设C为码字集合，按以下步骤构造此码的尾随后缀集合F：
(1) 考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个 尾随后缀放入集合F0中；
(2) 考查C和Fi两个集合，若Wj∈C是Wi∈Fi的前缀或Wi∈Fi 是Wj∈C 的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1 (3)F包含于Fi即为码C
(4) 若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)； 否则若F中没有出现新的元素，则返回真。
在我们设计的算法中，需要注意的是我们需要的是先输出所有尾随后缀的集合，然后再判断该码是否是唯一可译码，即如F中出现了C中的元素，则C不是唯一可译码，否则若F中没有出现新的元素，则C为唯一可译码。而不是F中出
2
河南理工大学课程设计报告书
现C中的元素就终止，这也是在本题的要求中需要注意的问题。
2、香农编码
香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编 码使平均码长达到极限值，这是一个很重要的极限定理。香农第一定理指出，选择每个码字的长度Ki满足下式：
I(xi)≤K﹤I(xi)+1, 就可以得到这种码。这种编码方法就是香农编码。
香农编码法有重要的理论意义。编码步骤如下： （1）将信源消息符号按其出现的概率大小依次排列： p（x1）≥p（x2）≥···≥p（xn） （2）确定满足下列不等式整数码长Ki： -log2p(xi)≤Ki＜-log2p(xi)+1
（3）为了编成唯一可译码，计算第i个消息的累加概率； （4）将累加概率Pi变成二进制数；
（5）取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。
三、设计流程图
1、判断唯一可译码 开 始 其框图如下：
输入码字个数与码字 进行尾随后缀编码 判断是否为唯一可译码 调用main（）函数 结 束 3
河南理工大学课程设计报告书
2、香农编码
其框图如下：
开 始
输入符号概率
将概率从大到小排序
求前j个的累加和
求码长Ki
十进制转换为二进制
四、程序运行及结果
1、判断唯一可译码 其运行结果如下图所示：
结 束 4