统计信源熵与哈夫曼编码毕业论文.doc

信息论与编码课程设计信息论与编码课程设计报告设计题目：统计信源熵与哈夫曼编码 专业班级 学 号 学生姓名 指导教师 教师评分 2015年 3 月 25 日目 录一、设计任务与要求3二、设计思路3三、设计流程图5四、程序运行及结果6五、心得体会8参考文献9附录：源程序10一、 设计任务与要求1.1设计目的信息论与编码是信息、通信、电子工程专业的基础，对理论研究和工程应用均有重要的作用。通过对本次课程设计，我们将学到的理论知识用于实践，用软件编写程序实现具体的计算和逻辑问题，使我们对所学知识有更深层次的认知，加深对课本知识的理解。1.2设计要求（1）统计信源熵要求：统计任意文本文件中各字符（不区分大小写）数量，计算字符概率，并计算信源熵。（2）哈夫曼编码要求：任意输入消息概率，利用哈夫曼编码方法进行编码，并计算信源熵和编码效率。二、 设计思路2.1编码效率计算公式： 其中H（X）为信源熵，K表示平均码长。2.3变长码的编码方法 能获得最佳码的编码方法主要有： 香农（Shannon） 费诺（Fano） 霍夫曼（Huffman）本设计以霍夫曼编码为例；（1）将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2) p(xn)（2）取两个概率最小的符号分别配以0和1，并将这两个概率相加作为一个新符号的概率，与未分配码元的符号重新排队。 （3）对重排后的两个概率最小符号重复步骤2的过程。 （4）继续上述过程，直到最后两个符号配以0和1为止。 （5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。2.3 具体设计思路（1）统计信源熵在VC+环境中进行编程 （1）运行程序，在对话框里输入一段英文，将26个英文字母及空格作为信源。 （2）计算每个字母出现的次数（不区分大小写），再通过计算信源总大小来计算在本篇文章中每个字母出现的概率。 （3）通过信源熵计算公式来计算信源熵。（2） 哈夫曼编码在VC+环境中进行编程（1） 输入概率矩阵，并检验是否正确，即各概率不能小于零，总概率之和等于一。（2） 建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯,从而得出对应的编码（3） 输出所需的哈弗曼编码。（4） 计算信源熵，并计算平均码长，算出编码效率。（5） 输出结果。三、 设计流程图3.1统计信源熵的设计思路 3.2哈夫曼编码设计思路 四、 程序运行及结果4.1统计信源熵程序运行结果运行程序并输入: The most distant way in the worldis not the way from birth to the end.it is when i sit near youthat you dont understand i love u.The most distant way in the worldis not that youre not sure i love u.It is when my love is bewildering the soulbut i cant speak it out. T测试目的：检验程序是否正确。检验方法：用验证法来检验；看中概率是否为一，并检测信源熵是否正确。检验结果：程序运行结果正确。如下为运行结果截屏4.2哈夫曼编码程序运行结果测试输入：0.20 0.19 0.18 0.17 0.15 0.10 0.01测试目的：测试经常出现的信源符号是否对应较短的码长，检测程序运行结果是否正确。正确输出：10 11 000 001 010 0110 0111 信源熵为-2.60868 bit/符号 平均码长为2.72 码元/符号 传送速率为0.959075 bit/码元实际输出：与争取而输出一样检测结果：程序无错误以下为运行结果截屏五、 心得体会刚开始课程设计的时候，自己是毫无头绪的，不知道从哪里下手，最重要的原因是对C 语言没有达到熟练的程度，自己不是很自信。但是万事开头难，什么困难只要踏出第一步，接下来就会一步步化解。 为了更加熟练地用C语言程序进行编写，我与同组成员仔细地复习以前学过的书籍，经过一段时间后对语法的掌握更加地熟练。 但是实际上在编写的时候，手打难免会碰到各类的问题，例如忘记在语句后面打“；”等一系列的小问题，所以自能耐心。对求概率，信源熵，哈夫曼编码的等公式有深入了解后，再构造一个程序的大体框架，再对各个语句的功能进行编写，一步步地完成。运行错误的话要慢慢检查，特别是一些小细节，直到程序完美运行。 尽管在完成设计过程中遇到了很多困难，但是通过自己和同组同学的努力最后还是完成了，不仅对信息论这门课的内容有了更加深入的了解，更增长了自己动手编程的能力。其中我最大的感悟是，学习一门课，要把它学好不仅仅是学懂书上的知识点，书本之外的知识也要掌握，这不是在课堂上就能学会的，要靠自己在课后慢慢地积累。身为大学生的我们把太多时间花在宿舍看电影和玩游戏上面，以至于荒废了太多的时间。对于身处大三的我们来说，剩下的时间尤为重要，若不考研，明年就该找工作了，那时自己身上没一点技能怎能在社会立足。所以我认为现在能做的最近本的就是把本专业的主要内容精髓学好，然后在这个基础上学习一些其他必备的技能。 人的一生就是在不断学习中度过，停止学习就等于与社会隔离，作为大学生就是应该与时俱进奋发图强。以上就是我对这次课程设计真正的感悟。 参考文献1曹雪虹、张宗橙编著信息论与编码.清华大学出版社，2009年第2版2 贾宗璞、许合利编著C语言程序设计.人民邮电出版社，2010年第1版3 严蔚敏、吴伟民编著数据结构（C语言版）.清华大学出版社，1997年第1版附页，源程序；一统计信源熵#include #include void main() double result=0; int k = 0,a=0,num26 = 0;double p26 = 0;int j;char ch;while(ch=getchar()!=n)if(ch = a & ch = A & ch = Z)if(ch 97)j = ch - 65;elsej = ch - 97;numj+;k+;printf(各字母出现的次数：n);for(int i = 0; i 26; i+)printf(%c:%dt, A + i, numi);printf(n字母个数：%dn, k);printf(各字母出现的概率：n);for(i = 0; i 26; i+)printf(%c:%ft, A + i, (double)numi/k); pa=(double)numi/k; a+;printf(n);/*求信源熵*/for(a = 0; a 26; a+)if(pa!=0) result=result+pa*log(pa)/log(2); result=-result; printf(信源熵为:%f,result); printf(n);二、哈夫曼编码程序/* file: hoffman coder.c date: 2015.03.24 describe: 霍夫曼编解码 (仅有霍夫曼码元的生成部分)*/#include #include #include #include #define MAX_MESSAGE 1024#define MAX_MESSAGE_BITS 64#define DEFAULT_FILE probability.txtstruct message_info int a_i; /* 消息符号, a1, a2, a3 . , 值为唯一的*/ double probability; /* 消息符号对应的概率 */ int father; /* 父节点, 用 a_i 表示 */ int left; /* 左子节点, 用 a_i 表示 */ int right; /* 子右节点, 用 a_i 表示 */ char codeMAX_MESSAGE_BITS; /* 编码后的 hoffman 码值存放在此处*/;/* 从文件中读取消息符号概率并存储于 struct message_info *message_info 中 */int hoffman_read_from_file(FILE *fp, struct message_info *message_info);/* 简单的冒泡排序, 适用于 消息种数较少 的情况, (n 10000) */int bubble_sort(struct message_info *p_message_info, int num);/* 合并最低的两个符号, 并使总符号数减少 1, 以被合并的符号将不再参与合并 */int hoffman_combine(struct message_info *p_message_info, int message_info_num, int *message_info_pos);/* 生成 hoffman 码 */int hoffman_create_code(struct message_info *message_info, int message_info_num);int main() int i, j; FILE *fp; struct message_info message_infoMAX_MESSAGE; struct message_info *p_message_infoMAX_MESSAGE; struct message_info *find; int message_info_num, message_info_pos; double entropy, encoded_efficiency, average_code_length; /* 信源熵, 编码效率 和 平均编码长度 */ if(fp = fopen(DEFAULT_FILE, r) = NULL) return -1; else message_info_num = hoffman_read_from_file(fp, message_info); average_code_length = encoded_efficiency = entropy = 0.0; for(j = 0; j message_info_num; j +) entropy += message_infoj.probability * log10(message_infoj.probability) / log10(2); for(j = 0; j MAX_MESSAGE; j +) p_message_infoj = &message_infoj; message_info_pos = message_info_num; for(j = 0; j message_info_num - 1; j +) hoffman_combine(p_message_info, message_info_num, &message_info_pos); bubble_sort(p_message_info, message_info_num + j + 1); for(i= 0; i probability); printf(-n); hoffman_create_code(message_info, message_info_num); printf(nninformation :n); for(j = 0; j 2 * message_info_num - 1; j +) printf(a_i = %2d, p = %4.3g, left = %2d, right = %2d, father = %2d, hoffman_code: %sn, message_infoj.a_i, message_infoj.probability, message_infoj.left, message_infoj.right, message_infoj.father, message_infoj.code); for(j = 0; j 0) message_infomessage_info_pos.a_i = message_info_pos; /* a_i 从 0 开始 */ message_info_pos +; return message_info_pos;/* 简单的冒泡排序, 适用于 消息种数较少 的情况, (n 10000) */int bubble_sort(struct message_info *p_message_info, int num) int i, j; struct message_info *temp; for(i = 0; i num - 1; i +) for(j = i + 1; j probability probability) temp = p_message_infoi; p_message_infoi = p_message_infoj; p_message_infoj = temp; return 0;/* 合并最低的两个符号, 并使总符号数减少 1 */int hoffman_combine(struct message_info *p_message_info, int message_info_num, int *message_info_pos) /* 从大到小排序 */ bubble_sort(p_message_info, message_info_num * 2 - *message_info_pos); p_message_infomessage_info_num * 2 - *message_info_pos - a_i = - (message_info_num - *message_info_pos + 1); p_message_infomessage_info_num * 2 - *message_info_pos - code0 = 0; p_message_infomessage_info_num * 2 - *message_info_pos - probability = p_message_info*message_info_pos - 1 - probability + p_message_info*message_info_pos - 2 - probability; p_message_infomessage_info_num * 2 - *message_info_pos - left = p_message_info*message_info_pos - 1 - a_i; p_message_infomessage_info_num * 2 - *message_info_pos - right = p_message_info*message_info_pos - 2 - a_i; p_message_info*message_info_pos - 1 - father = p_message_infomessage_info_num * 2 - *message_info_pos - a_i; p_message_info*message_info_pos - 2 - father = p_message_infomessage_info_num * 2 - *message_info_pos - a_i; (*message_info_pos) -; return 0;/* 生成 hoffman 码 */int hoffman_create_code(struct message_info *message_info, int message_info_num) int i, j, code_num; char codeMAX_MESSAGE_BITS; struct message_info *find, *find_father, *find_now; for(i = 0; i probability - 1.0) father father + message_info_num - 1 : find_now - father; if(find_father - left = find_now - a_i) codecode_num + = 1; else codecode_num + = 0; find_now = find_father; codecode_num = 0; strrev(code); /* 反转 code */ message_infoi.code0 = 0; strcat(message_infoi.code, code); return 0; 17