信息论与编码课程设计

河南理工大学课程设计报告书

信息论与编码课程设计报告

设计题目：判断唯一可译码、香农编码

专业班级 电信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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库信息论与编码课程设计在线全文阅读。