河南理工大学课程设计报告书信息论与编码课程设计报告设计题目：判断唯一可译码、香农编码专业班级电信12-03学号311208000607学生姓名曹琳指导教师成凌飞教师评分2015年3月21日1河南理工大学课程设计报告书目录一、设计任务与要求....................................................................................................2二、设计思路................................................................................................................2三、设计流程图............................................................................................................3四、程序运行及结果....................................................................................................4五、心得体会................................................................................................................6参考文献........................................................................................................................7附录：源程序................................................................................................................82河南理工大学课程设计报告书一、设计任务与要求通过本次课程设计的练习，使学生进一步巩固信源熵、信源编码的基本原理，掌握具体的编码方法，熟悉编程软件的使用，培养学生自主设计、编程调试的开发能力，同时提高学生的实践创新能力。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中出现C中的元素就终止，这也是在本题的要求中需要注意的问题。2、香农编码3河南理工大学课程设计报告书香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。香农第一定理指出，选择每个码字的长度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、判断唯一可译码其框图如下：2、香农编码其框图如下：开始输入码字个数与码字进行尾随后缀编码判断是否为唯一可译码调用main（）函数结束4河南理工大学课程设计报告书四、程序运行及结果1、判断唯...
