当前位置：文档之家› Huffman编码的应用-课程设计

Huffman编码的应用-课程设计

重庆科技学院

《数据结构》课程设计

报告

学院:_电气与信息工程学院_ 专业班级:计科2010-01

学生姓名: XXX 学号: 201044****

设计地点（单位）__ _ 计算机基础自主学习中心 __ _ _

设计题目:_______ Huffman编码的应用

完成日期：2012年 1 月 13 日

指导教师评语: ___________________ _________________ _____________________________________________________________________________ _______________________________________________

__________ _

成绩（五级记分制）:______ __________

指导教师（签字）:________ ________

课程设计任务书

设计题目：Huffman编码的应用

学生姓名吴冀师

课程名称数据结构课程设计专业班级计科2010-01

地点计算机基础自主学习中心起止时间2011.12.31-2012.1.13

设计内容及要求

利用赫夫曼编码的实现原理码对数据进行无损压缩，设计一个实现Huffman压缩的编码和解码的程序。具体要求如下：

1）读入待压缩的文本文件；

2）统计分析文本文件中各字符的出现频度，以频度作为构造Huffman树的权值。

3）根据各字符出现的不同频度构造Huffman树，然后规定每种字符的Huffman 编码。

4）再次读入待压缩的文本文件，然后根据各字符的Huffman编码逐一替代，将得到的编码流写入到新的文件中，并且计算压缩率。

5）解码过程：先读入上一步骤得到的新文件，将其看作比特流，根据Huffman 树，对比特流逐位译码，将解码结果又写入一个新的文件中。

设计参数

测试数据要求：

自行设计一个能说明压缩效果和过程的实例，待压缩的文本文件字符不能少于1000个。

进度要求2011.12.31 完成任务的讲解、并接受课程设计任务，选定课程设计的题目

2012.01.04 了解任务的算法、并画出算法的程序流程图，对任务的关键技术进行验证、并确定解决办法

2012.01.05-2012.01.06 编制程序

2012.01.09 对程序进行调试，设计测试用例进行测试

2012.01.10 整理课程设计的过程、并进行总结，完善程序功能

2012.01.11 编写课程设计报告初稿

2012.01.12 完善课程设计报告、并准备答辨

2012.01.13 提交课程设计报告和程序，进行答辨

参考资料1．严蔚敏吴伟民，数据结构，清华大学出版社，2007.3

2．李春葆，数据结构教程，清华大学出版社，2005.1

3．（美）Stephen Prata, C Primer Plus中文版（第五版），人民邮电出版社，2005.2

其它

说明1.本表应在每次实施前一周由负责教师填写二份，学院审批后交学院教务办备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。

系主任：雷亮指导教师：向毅/彭军/王双明/龙冯文/黄永文

2011年 12月 26日

摘要

随着多媒体技术的迅猛发展，压缩技术也快速发展起来。Huffman高效率压缩编码，其压缩程度很高，目前在很多领域已经开始广泛应用，具有良好的市场前景。这次课程设计运用的huffmam高效率编码，对编码译码，对文件进行逐位读，写。实现压缩文件，再对文件进行解压。实现了对数据的压缩及解压，并且可以运用在软件上面。效果高效很实用。

关键字：软件高效模块

摘要 ............................................................................................................................. III 目录 ................................................................................................................................. IV 1 设计内容与要求 .. (1)

1.1设计内容 (1)

1.2 设计要求 (1)

2 需求分析 (2)

2.1 系统实现的目标 (2)

2.2 系统实现方案 (2)

3 系统设计 (3)

3.1 总体功能的实现 (3)

3.2 总体流程图 (4)

4 系统实现 (5)

4.1构造哈夫曼树 (5)

4.2 哈夫曼编码 (6)

5 系统实现 (7)

5.1 主要代码实现 (7)

5.2 测试结果 (10)

6 总结 (13)

致谢 (13)

参考文献 (14)

1 设计内容与要求

1.1设计内容

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。

作为信息管理专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。

1.2 设计要求

读入待压缩的文本文件；统计分析文本文件中各字符的出现频度，以频度作为构造Huffman树的权值。根据各字符出现的不同频度构造Huffman树，然后规定每种字符的Huffman编码。再次读入待压缩的文本文件，然后根据各字符的Huffman编码逐一替代，将得到的编码流写入到新的文件中，并且计算压缩率。解码过程：先读入上一步骤得到的新文件，将其看作比特流，根据Huffman树，对比特流逐位译码，将解码结果又写入一个新的文件中。

2 需求分析

2.1 系统实现的目标

在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

2.2 系统实现方案

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。

3 系统设计

3.1 总体功能的实现

本程序设计包括两个模块:主程序模块和子程序模块。

在主页面可以清楚了解系统的功能实现，在控制台菜单页面，根据需要，可以根据提示进行选择，选择后可以进行相应的操作。compress()和decompress ()1通过菜单选择，调用子函数，从而实现对功能的要求，如图3.1总体功能图。

图3.1 主页面图

开始

输入一个数字

主菜单

选择功能

退出系统

输入文件名

结束

3.2 总体流程图

根据对huffman 功能分析，设计得到该系统的总体功能图如图3.2。

图3.3 总体功能图

结束

统计字符种类及频率

字符总数count

建立哈夫曼树

哈夫曼编码

哈夫曼译码

压缩解压？

开始

否

是

4 系统实现

4.1构造哈夫曼树

图4.1

开始

结束

第i 个结点权值

i=count

创建哈夫曼树

输出字符统计情况

第i 个根结点

i=2*count-1

i=count

否

是否

是

否

是

4.2 哈夫曼编码

图4.2

结束

开始

Val[i].c=c

i<=count

Val[i]，i<127

Val[i]=0

Val[i]=1

否

是

5 系统实现

5.1 主要代码实现

5.11 主掉函数

int initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp);

char *create_filename(char *source_filename,char* obj_filename);

int compress(char *source_filename,char *obj_filename);

long frequency_data(FILE *in,long fre[]);

int search_set(htnp ht,int n,int *s1, int *s2);

int create_hftree(long w[],int n,htnode ht[]);

int encode_hftree(htnp htp,int n,hufcode hc[]);

unsigned char chars_to_bits(const unsigned char chars[8]);

int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc[],char* source_filename,long source_filesize);

int decompress(char *source_filename,char *obj_filename);

void get_mini_huffmantree(FILE* in,short mini_ht[][2]);

int write_decompress_file(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long obj_filesize);

int d_initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp);

5.12 压缩文件时的代码

int compress(char *source_filename,char *obj_filename)

{

FILE *in,*out;

char ch;

float compress_rate;

hufcode hc[256];

htnode ht[256*2-1];

long frequency[256],source_filesize,obj_filesize=0;

error_code=initial_files(source_filename,&in,obj_filename,&out);

if(error_code!=0)

{

puts("文件打开失败！请重新输入文件路径：");

return error_code;

}

source_filesize=frequency_data(in,frequency);

printf("文件大小%ld 字节\n",source_filesize);

error_code=create_hftree(frequency,256,ht);

if(error_code!=0)

{

puts("建立哈夫曼树失败！");

return error_code;

}

error_code=encode_hftree(ht,256,hc);

if(error_code!=0)

{

puts("建立哈夫曼编码失败！");

return error_code;

}

for(i=0;i<256;i++)

obj_filesize+=frequency[i]*hc[i].len;

obj_filesize=obj_filesize%8==0?obj_filesize/8:obj_filesize/8+1;

for(i=0;i<256-1;i++)

obj_filesize+=2*sizeof(short);

obj_filesize+=strlen(source_filename)+1;

obj_filesize+=sizeof(long);

obj_filesize+=sizeof(unsigned int);

compress_rate=(float)obj_filesize/source_filesize;

printf("压缩文件大小:%ld字节,压缩比例:%.2lf%%\n",obj_filesize,compress_rate*100); error_code=write_compress_file(in,out,ht,hc,source_filename,source_filesize);

if(error_code!=0)

{

puts("写入文件失败！");

return error_code;

}

puts("压缩完成!");

puts(" ");

puts("是否打印该文件中字符对应的huffman树及编码？");

do{

scanf("%s",&ch);

switch(ch)

{

case 'Y':

puts("以下是哈夫曼树：");

for(i=256;i<256*2-2;i++)

{

if(ht[i].w>0)

printf("%-10d%-10d%-10d%-10d%-10d\n",i,ht[i].w,ht[i].p,ht[i].l,ht[i].r);

}

puts("以下是哈夫曼编码：");

for(i=0;i<256;i++)

{

if(frequency[i]==0)

i++;

else

{

printf("%d\t",frequency[i]);

for(j=0;j

printf(" %d",hc[i].codestr[j]);

printf("\n");

}

break;

case 'N': break;

default :

printf("指令错误！请重新输入指令：\n");

}

}while(ch!='Y'&&ch!='N');

fclose(in);

fclose(out);

for(i=0;i<256;i++)

{

free(hc[i].codestr);

}

return 0;

}

5.13 解压文件时的代码

int decompress(char *source_filename,char *obj_filename)

{

int error_code;

FILE *in,*out;

short mini_ht[256*2-1][2];

long obj_filesize;

error_code=d_initial_files(source_filename,&in,obj_filename,&out);

if(error_code!=0)

{

puts("打开文件失败！请重新输入文件路径：");

return error_code;

}

fread(&obj_filesize,sizeof(long),1,in);

printf("解压文件大小:%ld字节\n",obj_filesize);

get_mini_huffmantree(in,mini_ht);

error_code=write_decompress_file(in,out,mini_ht,ftell(in),obj_filesize);

if(error_code!=0)

{

puts("解压缩失败！");

return error_code;

}

puts("解压缩完成!");

fclose(in);

fclose(out);

return 0;

} 5.2 测试结果

进入主页面，如图5.1。

图 5.1 查看哈弗曼码，如图5.2。

图 5.3 输入文件路劲及压缩效果显示，如图5.3。

图 5.4

6 总结

通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识更加明白哈

夫曼编码译码在信息技术中的重要性和地位。许多的错误让我明白了一个道理---细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。

通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是平时实践太少的缘故。在这个程序中，还有许多地方值得完善。比如，读出文本只能是大写的文档，空格和小写不能识别，更不用说是任意的ASCⅡ码字符了。由于时间问题，暂时不能实现了。我想在暑假里好好研究这个问题。

致谢

写出在本次课程设计及论文完成过程中，为你提供帮助的人，并表达谢意

。

签名

日期 2012/1/12

参考文献

1．严蔚敏吴伟民，数据结构，清华大学出版社，2007.3

2．李春葆，数据结构教程，清华大学出版社，2005.1

3．（美）Stephen Prata, C Primer Plus中文版（第五版），人民邮电出版社，2005.2

代码：

#include

typedef struct node

{

long w;

short p,l,r;

}htnode,*htnp;

typedef struct huffman_code {

unsigned char len;

}hufcode;

typedef char **huffmancode;

int initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp);

char *create_filename(char *source_filename,char* obj_filename);

int compress(char *source_filename,char *obj_filename);

long frequency_data(FILE *in,long fre[]);

int search_set(htnp ht,int n,int *s1, int *s2);

int create_hftree(long w[],int n,htnode ht[]);

int encode_hftree(htnp htp,int n,hufcode hc[]);

unsigned char chars_to_bits(const unsigned char chars[8]);

int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc[],char* source_filename,long source_filesize);

int decompress(char *source_filename,char *obj_filename);

void get_mini_huffmantree(FILE* in,short mini_ht[][2]);

int write_decompress_file(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long obj_filesize);

int d_initial_files(char *source_filename,FILE **inp,char *obj_filename,FILE **outp);

int main()

{

int s;

char filename[10];

system("color 3F");

printf("

***************************************\n");

printf(" * 菜单：*\n");

printf(" * 1.——————压缩——————

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

目录一：实验原理----------------------------1 二：程序源代码--------------------------1 三：实验分析-----------------------------6 四：实验结论---------------------------7

赫夫曼编码一：实验原理哈夫曼编码的具体步骤归纳如下： ① 概率统计（如对一幅图像，或m幅同种类型图像作灰度信号统计），得到n个不同概率的信息符号。 ② 将n个信源信息符号的n个概率，按概率大小排序。 ③ 将n个概率中，最后两个小概率相加，这时概率个数减为n-1个。 ④ 将n-1个概率，按大小重新排序。 ⑤ 重复③，将新排序后的最后两个小概率再相加，相加和与其余概率再排序。 ⑥ 如此反复重复n-2次，得到只剩两个概率序列。 ⑦ 以二进制码元赋值，构成哈夫曼码字。编码结束。哈夫曼码字长度和信息符号出现概率大小次序正好相反，即大概信息符号分配码字长度短，小概率信息符号分配码字长度长。 C、哈夫曼编码的特点 (1)哈夫曼编码的构造顺序明确，但码不是唯一的(因以大赋1还是小的赋1而异；

(2)哈夫曼编码的字长参差不齐，硬件实现不方便； (3)只有在概率分布很不均匀时，哈夫曼编码才有显著的效果，而在信源分布均匀时，一般不使用哈夫曼编码。二：程序源代码： #define MAXVALUE 10000 #define MAXLEAF 30 #define MAXNODE 59 #define MAXBIT 10 #define LENTH 30 #include "" #include typedef struct{ float gailv; int flag; int parent; int lchild; int rchild; char ch; int t; }HNodeType; typedef struct{ int bit[MAXBIT]; int start; }HCodeType; typedef struct{ float gailv; char letter; }mytype; /*it's the type of data save in file*/ typedef struct filehuff{ int count; mytype mydata[MAXLEAF]; filehuff(){count=0; }; }; filehuff filedata; char code[MAXVALUE]; HNodeType HuffNode[MAXNODE]; void savetofile() { FILE *fp;

信息论与编码课程设计..

吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：哈夫曼编码的分析与实现专业班级：电子信息工程101 学生姓名：学号：指导教师：吕卅王超设计时间：2013.11.18－2013.11.29

一、设计的作用、目的《信息论与编码》是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法二、设计任务及要求通过课程设计各环节的实践，应使学生达到如下要求： 1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点； 3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程； 4. 能够使用MATLAB 或其他语言进行编程，编写的函数要有通用性。三、设计内容一个有8个符号的信源X ，各个符号出现的概率为：编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最小的字母分别配以0和1两个码元（先0后1或者先1后0，以后赋值固定），再将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。并不断重复这一过程，直到最后两个符号配以0和1为止。最后从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即为对应的码字。哈夫曼编码方式得到的码并非唯一的。在对信源缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减中的排序将会导致不同码字，但不同的排序将会影响码字的长度，一般讲合并的概率放在上面， 12345678,,,,, ()0.40.180.10.10.070.060.050.04X x x x x x x x x P X ????=????????

课程设计报告

课程设计报告题目基于数据挖掘的航电系统故障诊断专业名称电子信息工程学生姓名王腾飞指导教师陈杰完成时间 2014年3月18日

摘要航电系统是飞机的重要组成部分，由于其综合应用了电子、机械、计算机及自动检测等许多学科的先进技术，结构层次很多，所以对其实施故障诊断具有涉及专业领域多、诊断难度大、要求时间短等特点。这对快速处理故障数据提出了很大的挑战。从独立的联合式航电机箱的按键通电测试，到集中式飞机管理系统数据收集，飞机维修系统经过漫长的发展已演变成故障诊断工具。现代飞机均采用了中央维修系统，用以收集所有子系统的故障报告、判断故障根源并推荐修理方法。飞机的故障信息和历史数据存放在数据库中。如果用传统的数据分析方法对这些海量的数据进行分析时会显得力不从心，不仅浪费时间而且对于隐含的知识难以有效的进行挖掘。数据挖掘技术十分符合现实的需要，它可以客观地挖掘出历史数据库中潜在的故障规则，这些规则能更好地指导故障的定位与检修，并对潜在的故障做出预测。随着数据的不断增长，如何能自动获取知识已经成为故障诊断技术发展的主要制约条件，而数据挖掘技术为解决这个“瓶颈”问题提供了一条有效的途径。本文详细介绍了故障诊断技术与数据挖掘技术，并总结了航电系统的故障诊断的特点。拟采用聚类分析的技术对故障数据快速处理，实现对故障的快速定位。关键词：故障诊断数据挖掘聚类分析航电系统

故障诊断技术故障诊断技术简介故障诊断就是指当设备系统不能完成正常的功能时，利用一定的方法找出使该功能丧失的原因及发生故障的部位，实现对故障发展趋势的预测的过程。故障诊断涉及到多方面的技术背景，主要以系统论、信息论、控制论、非线性科学等最新技术理论为基础，它是一门综合性的学科，具有重要的实用价值。设备系统故障及故障诊断随着现代化工业的发展，设备系统能够以最佳状态可靠地运行，对于保证产品质量、提高企业的产能、保障生命财产安全都具有极其重要的意义。设备系统的故障是指设备系统在规定时间内、规定条件下丧失规定功能的状况。故障诊断的作用则是发现并确定发生故障的部位及性质，找出故障的起因，预测故障的发展趋势并提出应对措施。故障诊断技术的使用范围不应只局限于设备系统使用和维修过程中，在设备系统的设计制造过程中也可以使用故障诊断技术，为以后的故障监测和设备系统维护创造条件。因此，故障诊断技术应该贯穿于设备系统的设计、制造、运行和维护的全过程当中。机载设备的故障诊断流程框图:

哈夫曼编码信息论课程设计

信息论课程设计实验报告专业班级：信计0802 姓名：刘建勋学号：07 目录：

1.课题描述-----------------------------------------------------------------------------------------3 2.信源编码的相关介绍---------------------------------------------------------------------3 3.哈夫曼编码-------------------------------------------------------------------------------------3 哈夫曼编码算法-----------------------------------------------------------------------3 哈弗曼编码的特点--------------------------------------------------------------------4 哈夫曼实验原理----------------------------------------------------------------------- 4 4.哈夫曼编码的C++实现-----------------------------------------------------------------5 程序设计-----------------------------------------------------------------------------------5 运行结果-----------------------------------------------------------------------------------8 总结-----------------------------------------------------------------------------------------------------8 参考文献-------------------------------------------------------------------------------------------------8

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

信息论与编码课程设计报告设计题目：判断唯一可译码、香农编码专业班级电信12-03 学号7 学生琳指导教师成凌飞教师评分 2015年3月21日

目录一、设计任务与要求 (2) 二、设计思路 (2) 三、设计流程图 (3) 四、程序运行及结果 (4) 五、心得体会 (6) 参考文献 (7) 附录：源程序 (8)

一、设计任务与要求通过本次课程设计的练习，使学生进一步巩固信源熵、信源编码的基本原理，掌握具体的编码方法，熟悉编程软件的使用，培养学生自主设计、编程调试的开发能力，同时提高学生的实践创新能力。 1、判断唯一可译码利用尾随后缀法判断任意输入的码是否为唯一可译码，即设计一个程序实现判断输入码组是否为唯一可译码这一功能。 2、香农编码熟悉运用香农编码,并能通过C语言进行编程,对任意输入消息概率，利用香农编码方法进行编码，并计算信源熵和编码效率。二、设计思路 1、判断唯一可译码在我们学习使用了克劳夫特不等式之后，知道唯一可译码必须满足克劳夫特不等式。但是克劳夫特不等式仅仅是存在性的判定定理，即该定理不能作为判断一种码是否为唯一可译码的依据。也就是说当码字长度和码符号数满足克劳夫特不等式时，则必可以构造出唯一可译码，否则不能构造出唯一可译码。因此我们必须找到一种能够判断一种码是否为唯一可译码的方法，尾随后缀法。尾随后缀法算法描述：设C为码字集合，按以下步骤构造此码的尾随后缀集合F： (1) 考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中； (2) 考查C和Fi两个集合，若Wj∈C是Wi∈Fi的前缀或Wi∈Fi 是Wj

哈夫曼编译码器课程设计报告完整版

XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/译码器学生姓名：XXX 系别：XXX 专业：XXX 班级：XXX 学号：XXX 指导教师：XXX XXX 6 月 21日

xxx学院课程设计任务书题目一、赫夫曼编译码器专业、班级 xxx 学号 xxx 姓名 xxx 主要内容、基本要求、主要参考资料等： 1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端经过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（既能够双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。 2. 基本要求系统应具有以下功能：（1）C：编码（Coding）。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码（Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。（3）P：打印代码文件（Print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入

文件codeprint中。（4）T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。 3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限： 6月21 日指导教师签名：课程负责人签名： 6月 21 日一、设计题目（任选其一）实验一、哈夫曼编/译码器二、实验目的 1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力； 2 深化对算法课程中基本概念、理论和方法的理解； 3 巩固构造赫夫曼树的算法； 4 设计试验用程序实验赫夫曼树的构造。三、运行环境（软、硬件环境） Windows xp sp3，Visual C++ 6.0英文版

信息论课程设计报告

成绩： 2016-2017学年第1学期《信息论》课程设计学院名称：班级学号：学生姓名：教师姓名： 2016年12月一、判定唯一可译码 1. 任务说明

输入：任意的一个码(即已知码字个数及每个具体的码字) 输出：判决结果（是/不是）输入文件:in1.txt ，含至少2组码，每组的结尾为”$”符输出文件:out1.txt ，对每组码的判断结果说明：为了简化设计，可以假定码字为0，1串 2. 实现原理判断方法：将码C 中所有码字可能的尾随后缀组成一个集合F ，当且仅当集合F 中没有包含任一码字，则可判断此码C 为唯一可译变长码。构成集合F ：首先观察码C 中最短的码字是否是其他码字的前缀。若是，将其所有可能的尾随后缀排列出。就是将其他码字序列中截去与其最短码字相同的前缀部分，将余下的序列为尾随后缀。而这些尾随后缀又可能是某些码字的前缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。然后再观察这些新的尾随后缀是否是某些码字的前缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随后缀产生为止。这样，首先获得的是由最短码字能引起的所有尾随后缀。接着，按照上述步骤将次短的码字、......所有码字可能产生的尾随后缀前部列出。由此得到由码C 的所有可能的尾随后缀组成的集合F 。参考算法伪代码： For all ,i j W W C ∈ do if i W 是j W 的前缀 then 将相应的后缀作为一个尾随后缀放入集合0F 中 End if End for Loop For all i W C ∈ do For all j n W F ∈ do if i W 是j W 的前缀 then 将相应的后缀作为一个尾随后缀放入集合1n F +中 Else if j W 是i W 的前缀 then 将相应的后缀作为一个尾随后缀放入集合1n F +中 End if End for End for i i F F ← If ,i i W F W C ?∈∈ then Return false Else if F 中未出现新的元素 then Return true End if //能走到这里，说明F 中有新的元素出现，需继续 End loop

数据结构课程设计哈夫曼编码

题目：哈夫曼编码器班级：031021班姓名：李鑫学号：03102067 完成日期：2011/12 1. 问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 2.基本要求一个完整的系统应具有以下功能： (1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 (2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。以下为选做： (4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T：印赫夫曼树（Tree printing）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。 3.测试 (1)利用教科书例6-2中的数据调试程序。 (2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FA VORITE”。字符 A B C D E F G H I J K L M 频度186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z 频度57 63 15 1 48 51 80 23 8 18 1 16 1 4.实现提示 (1) 编码结果以文本方式存储在文件Codefile中。 (2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 (3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

信息论与编码课程设计报告,统计信源熵与香农编码

信息论与编码课程设计报告设计题目：统计信源熵与香农编码专业班级电信 12-06 学号学生姓名指导教师教师评分 2015年 3 月 30日

目录一、设计任务与要求 (2) 二、设计思路 (2) 三、设计流程图 (3) 四、程序运行及结果 (4) 五、心得体会 (6) 参考文献 (7) 附录：源程序 (8)

一、设计任务与要求 1.统计信源熵要求：统计任意文本文件中各字符（不区分大小写）数量，计算字符概率，并计算信源熵。 2.香农编码要求：任意输入消息概率，利用香农编码方法进行编码，并计算信源熵和编码效率。二、设计思路本次课程设计中主要运用C 语言编程以实现任务要求，分析所需要的统计量以及相关变量，依据具体公式和计算步骤编写语句，组成完整C 程序。 1、信源熵定义：信源各个离散消息的自信息量的数学期望为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或香农熵，有时称为无条件熵或熵函数，简称熵，记为H （）。计算公式： ) (log )(-)x (i i i x p x p H ∑= 2、香农编码过程：（1）将信源消息符号按其出现的概率大小依次排列为 n p p ≥???≥≥21p （2）确定满足下列不等式的整数码长i K 为 1)()(+-<≤-i i i p lb K p lb （3）为了编成唯一可译码，计算第i 个消息的累加概率 ∑-==11) (i k k i a p P （4）将累计概率 i P 变换成二进制数。（5）取i P 二进制数的小数点后i K 位即为该消息符号的二进制码字。

三、设计流程图 1、统计信源熵开始读取给定文件判断文件是否打开否并且不为空是统计文本字符，直关闭文件至文本字符读完。统计同一字符(不分大小写)出现的次数计算字符概率计算信源熵输出结束

哈夫曼编译码器课程设计报告(完整版)

XXX学院本科数据结构课程设计总结报告设计题目：实验一、哈夫曼编/ 译码器学生：系XXX 别：XXX 专业： XXX 班级： XXX 学号：XXX 指导教师：XXX XXX 2012 年 6 月21 日

xxx 学院课程设计任务书题目一、赫夫曼编译码器专业、班级xxx 学号xxx xxx 主要容、基本要求、主要参考资料等： 1. 主要容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/ 译码系统。试为这样的信息收发站写一个哈夫曼的编/ 译码系统。 2. 基本要求系统应具有以下功能：（1）C：编码（Coding）。对文件tobetrans 中的正文进行编码，然后将结果存入文件codefile 中，将以此建好的哈夫曼树存入文件HuffmanTree 中（2）D：解码（Decoding ）。利用已建好的哈夫曼树将文件codefile 中的代码进行译码，结果存入textfile 中。（3）P：打印代码文件（Print ）。将文件codefile 以紧凑格式显示在终端上，每行50 个代码。同时将此字符形式的编码文件写入文件codeprint 中。（4）T：打印哈夫曼树（Tree Printing ）。将已在存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint 中。3. 参考资料：数据结构（C 语言版）严蔚敏、吴伟民编著；数据结构标准教程胡超、闫宝玉编著完成期限：2012 年6 月21 日指导教师签名：课程负责人签名：、设计题目（任选其一）实验一、哈夫曼编/ 译码器二、实验目的 1 巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力； 2 深化对算法课程中基本概念、理论和方法的理解； 3 巩固构造赫夫曼树的算法； 2012 年 6 月21 日

信息论与编码课程大作业二进制哈夫曼编码

信息论与编码课程大作业题目：二进制哈夫曼编码学生姓名：学号：2010020200 专业班级： 2010级电子信息班 2013年5月18日

二进制哈夫曼编码 1、二进制哈夫曼编码的原理及步骤 1、1信源编码的计算设有N 个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n 、信源的概率分布P={p(s i )},i=1,…..,n 。且各符号xi 的以li 个码元编码，在变长字编码时每个符号的平均码长为∑==n i li xi p L 1)( ；信源熵为：)(log )()(1 xi p xi p X H n i ∑=-= ；唯一可译码的充要条件：11 ≤∑=-n i Ki m ；其中m 为码符号个数，n 为信源符号个数，Ki 为各码字长度。构造哈夫曼数示例如下图所示。 1、2 二元霍夫曼编码规则（1）将信源符号依出现概率递减顺序排序。（2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结 0.60 0.15 0.09 0.30 1.00 0.60 0.03 0.30 0.15 0.40 0.05 0.04 0.03

果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用s1 表示。（3）将缩减信源 s1 的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含（n-2）个符号的缩减信源s2。（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为 1，然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。 1、3 二元哈夫曼编码流程图如下图所示。是是开始等待数据输入判断输入的概率是否小于零判断概率和是否大于1 生成一个n - 1行n 列的数组按照哈弗曼的编码规则进行编码计算码长计算编码效率计算信源熵显示结果结束

哈夫曼树课程设计论文

课程论文题目：哈夫曼树及其应用课程设计报告学号： 201230210115 姓名：黄文宣班级： 1232101 专业：信息安全课程名称：数据结构课程老师：王晓燕二零一肆年一月

目录 1、课程设计的题目及简介 (3) 2、实验目的 (3) 3、设计说明 (4) 4、总体流图 (4) 5、详细设计 (5) 6、实现部分 (6) 7、测试程序 (9) 8、心得与体会 (10)

一、课程设计题目哈夫曼树及其应用数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。二、实验目的 1 熟悉树的各种存储结构及其特点。 2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。

三、设计说明建立哈夫曼树，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。给定的权值从键盘输入，输出所建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。四、总体流图哈夫曼树编码系统初始化编码重新建立哈夫曼树译码打印编码

信息论无失真信源编码

信息，例如霍夫曼编码。它相对简单，是本章的重点。信息有一定的差别，例如JPEG 、MPEG ■无失真信源编码：解码之后可以得到原始 jlll ■有失真信源编码：解码之后的信息与原始 jlll

■其中X 称为码符号集，X 中的元素“称为码元或者码符号。输岀符号叱?称为码字，植字的集合C 称为代码组或者码。码字比?的长度厶称为码字长度, 简称码长。 ■要实现无失真编码，编码器的映射必须是一一对应、可逆的。码的分类 5.1编码器编码器 C=(W1,W2,…,W 几 ■信源编码器表示为: X=(QK2,…对 ■例如: S=(ACD) r A B C D C=(OOJOJl)r 00,01,10,11 r X=(o ，l) S=(A ，CQ) AB C D C=(0,001,lip * 0,01,001,111 X=(0J)

■根据码长 □固定长度码（定长码）：所有码字的长度相同。 □可变长度码（变长码）：码字长短不一。 ■码字是否相同 □非奇异码：所有码字都不相同。 □奇异码：存在相同的码字。

5.2分组码 ■象稱蛊轟凋11映射 ■通常在接收端收到的码字之间并没有明显的间隔, 表现为皿叫…巴的形式，把这种形式称为g阶扩展码。例如前面的两个例子，ACD编码成另 001011/0001111的形式，均为3阶扩展码。 ■码字之间缺少间隔，给译码造成了一定的困难□定长码：不存在困难，001011必定译码成为ACD □变长码：存在困难，0001111可以译码成为ACD(0 001 111),也可以译码成为AABD(0 0 01 lll)o

信息论与编码课程设计(哈夫曼编码的分析与实现)

建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：哈夫曼编码的分析与实现专业班级：电子信息工程 101 学生：学号：指导教师：吕卅王超设计时间： 2013.11.18－2013.11.29

一、设计的作用、目的《信息论与编码》是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法二、设计任务及要求通过课程设计各环节的实践，应使学生达到如下要求： 1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点； 3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程； 4. 能够使用MATLAB 或其他语言进行编程，编写的函数要有通用性。三、设计容一个有8个符号的信源X ，各个符号出现的概率为：编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最小的字母分别配以0和1两个码元（先0后1或者先1后0，以后赋值固定），再将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。并不断重复这一过程，直到最后两个符号配以0和1为止。最后从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即为对应的码字。哈夫曼编码方式得到的码并非唯一的。在对信源缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减中的排序将会导12345678,,,,,()0.40.180.10.10.070.060.050.04X x x x x x x x x P X ????=????????

哈夫曼树课程设计报告(DOC)

课程设计题目：哈夫曼编码器院系：专业班级：学号：学生姓名：指导教师： 2014年1月2日

课程设计需求分析报告一、分析问题和确定解决方案 1.分析问题利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将

信息论与编码课程设计(精.选)

信息论与编码课程设计报告设计题目：统计信源熵、香农编码与费诺编码专业班级：XXXXXXXXXXXX 姓名：XXXXXXXXXXXX 学号：XXXXXXXXXXXX 指导老师：XXXXXXXXXXXX 成绩：时间：2015年3月31日

目录一、设计任务与要求 (2) 二、设计思路 (2) 三、设计流程图 (5) 四、程序及结果 (7) 五、心得体会 (11) 六、参考文献 (12) 附录 (13)

一、设计任务与要求 1. 统计信源熵要求：统计任意文本文件中各字符（不区分大小写）数量，计算字符概率，并计算信源熵。 2. 香农编码要求：任意输入消息概率，利用香农编码方法进行编码，并计算信源熵和编码效率。 3. 费诺编码要求：任意输入消息概率，利用费诺编码方法进行编码，并计算信源熵和编码效率。二、设计思路 1、统计信源熵：统计信源熵就是对一篇英文文章中的i 种字符（包括标点符号及空格，英文字母不区分大小写）统计其出现的次数count i （），然后计算其出现的概率()p i ，最后由信源熵计算公式： 1()()log ()n i i n H x p x p x ==-∑ 算出信源熵()H x 。所以整体步骤就是先统计出文章中总的字符数，然后统计每种字符的数目，直到算出所有种类的字符的个数，进而算出每种字符的概率，再由信源熵计算公式计算出信源熵。在这里我选择用Matlab 来计算信源熵，因为Matlab 中系统自带了许多文件操作和字符串操作函数，其计算功能强大，所以计算

信源熵很是简单。 2、香农编码信源编码模型：信源编码就是从信源符号到码符号的一种映射f ，它把信源输出的符号i a 变换成码元序列i x 。 1,2,...,,i i N f a i q x =→： 1:{,...,}q S s a a ∈ 信源 1 2 {,...,}li i i i i X x x x = 码元 1{,...,} 1,2,...,i q S a a i N ∈= 1,2,...,N i q = 1:{,...,} r X x x x ∈ 码符号 N 次扩展信源无失真编码器凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可以称为最佳码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳码的编码方法主要有：香农（Shannon ）、费诺（Fano ）、哈夫曼（Huffman ）编码等。香农第一定理：离散无记忆信源为 1 21 2......()()()...... q q s s s S p s p s p s P ????=???????? 熵()H S ,其N 次扩展为

哈夫曼树课程设计

数据结构课程设计哈弗曼编码程序说明书一、使用手册：

1、在字符里面输入字符（单个字符）以空格隔开，输入最大字符数量100； 2、输入完成后点击哈弗曼编码按钮，然后再右边的列表控件中显示出字符、权值以及相应的哈弗曼代码。 3、运行完一次后点击清空按钮。清空右边列表控件的内容，然后再测试下一组值。可以用delete键删除二．可行性分析通过对输入编辑框中的字符进行分型，通过最这个字符进行遍历，获得每个字母的重复次数。以此作为该字符的权值存入数组weight[]中，并与字符数组相对应，并将权值作为参数传入Status CHafumanDlg::HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)中，利用对应的处理函数获得哈弗曼编码，最后输出在列表控件中。二、概要设计在vc++6.0中生成的改程序 1、建立基于对话框的程序，在类CHafumanDlg中添加构造哈弗曼树的代码； 2、向对话框中添加静态文本控件（caption改为字符）；接着添加编辑框并关联String类型的关联变量m_zifu，还有两个按钮（caption 分别改为清空和哈弗曼代码）以及一个列表控件，并关联一个CLisrCtrl类型的变量m_list；然后分别为清空和哈弗曼编码按钮添加相应的响应函数

三、源代码 1构造哈弗曼树的代码（1）// hafumanDlg.h : header file//头文件 // #if !defined(AFX_HAFUMANDLG_H__ACA655FF_81FF_452A_855C_32381C74 3BB5__INCLUDED_) #define AFX_HAFUMANDLG_H__ACA655FF_81FF_452A_855C_32381C743BB5__INC LUDED_ #if _MSC_VER > 1000 #pragma once #endif // _MSC_VER > 1000 ///////////////////////////////////////////////////////////////////////////// // CHafumanDlg dialog #define ok 1 #define error 0 typedef int Status; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode, *HuffmanTree;//动态分配数组存储赫夫曼树 typedef char * *HuffmanCode;//动态分配数组存储赫夫曼编码表 class CHafumanDlg : public CDialog { // Construction public: Status HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n); Status Select(HuffmanTree HT,int n,int &n1,int &n2); CHafumanDlg(CWnd* pParent = NULL); // standard constructor }; （2）// hafumanDlg.cpp : implementation file // #include "stdafx.h"

信息论基础与编码(第五章)

5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码12345C C C C C 、、、、和6C 。（1）求这些码中哪些是唯一可译码；（2）求哪些是非延长码（即时码）；（3）对所有唯一可译码求出其平均码长。解：（1(2)1,3,6是即时码。 5-2证明若存在一个码长为12,,,q l l l ???的唯一可译码，则一定存在具有相同码长的即时码。证明：由定理可知若存在一个码长为的唯一可译码，则必定满足kraft 不等式 1。由定理4可知若码长满足kraft 不等式，则一定存在这样码长的即时码。所以若存在码长的唯一可译码，则一定存在具有相同码长P （y=0）的即时码。 5-3设信源1 2 61 26()s s s S p p p P s ??? ????=???? ??? ????，6 1 1i i p ==∑。将此信源编码成为r 元唯一可译变长码（即码符号集12{,,,}r X x x x =???），其对应的码长为（126,,,l l l ???）=（1，1，2，3，2，3），求r 值的最小下限。解：要将此信源编码成为 r 元唯一可译变长码，其码字对应的码长（l 1 ,l 2 ,l 3, l 4,l 5, l 6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即 13232116 1 ≤+++++=------=-∑r r r r r r r i li Lq L L ,,2,1 ∑=-q i l i r 1 ≤4?Lq L L ,,2,1

所以要满足 12 223 2≤++r r r ，其中 r 是大于或等于1的正整数。可见，当r=1时，不能满足Kraft 不等式。当r=2, 18 2 4222>++，不能满足Kraft 。当r=3, 127 26 2729232<=++，满足Kraft 。所以，求得r 的最大值下限值等于3。 5-4设某城市有805门公务电话和60000门居民电话。作为系统工程师，你需要为这些用户分配电话号码。所有号码均是十进制数，且不考虑电话系统中0、1不可用在号码首位的限制。（提示：用异前缀码概念）（1）如果要求所有公务电话号码为3位长，所有居民电话号码等长，求居民号码长度1L 的最小值；（2）设城市分为A 、B 两个区，其中A 区有9000门电话，B 区有51000门电话。现进一步要求A 区的电话号码比B 区的短1位，试求A 区号码长度2L 的最小值。解：(a) 805门电话要占用1000个3位数中的805个，即要占用首位为0～ 7的所有数字及以8为首的5个数字。因为要求居民电话号码等长，以9为首的数字5位长可定义10 000个号码，6位长可定义100 000 个号码。所以min L 16=。或由Craft 不等式，有 805106000010131?+?≤--L 解得 L 1103 180******** 5488≥--?=-log .，即 min L 16= (b) 在(a)的基础上，将80为首的数字用于最后5个公务电话，81～86 为首的6位数用于B 区51 000个号码，以9为首的5位数用于A 区9 000 个号码。所以，min L 25=。或由 Draft 不等式，有 80510 900010510001013 122?+?+?≤---+L L () 或 80510 900051000101013 12?++??≤---()L 解得L 210 3 18051090005100 4859≥--?+=-log . 即min L 25= 5-5求概率分布为)152,152,51,51,31(的信源的二元霍夫曼码。讨论此码对于概率分布为 )5 1 ,51,51,51,51(的信源也是最佳二元码。

信息论课程设计

电子科技大学电子工程学院信息论课程设计报告课程名称：信息编码与加密

课程设计报告学生姓名：农瀚学号：2014020908021 指导教师：李万春一、课程设计名称：编程实现霍夫曼、费诺、香农编码二、课设原理： 1）霍夫曼编码：霍夫曼编码的平均码长最短，是最佳编码。编码步骤如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两幅号分别赋予码元0和1；（3）将概率之和当做一个新符号的概率。与剩下的概率一起，形成一个缩减信源，再重复上述步骤，直到概率和为1为止；（4）按上述步骤实际上构成了一个码树，从根到端点经过的树枝即为码字。 2）费诺编码：编码步骤如下：（1）将信源概率从大到小排序；（2）将信源符号分成两组，使两组信源符号的概率之和近似相等，并给两组信源符号分别赋0和1；（3）再把各个小组的信源符号细分为两组并赋码元，方法与第一次分组相同；（4）如此一直下去，直到每一个小组只含一个信源符号为止；（5）由此可构造成一个码树，所有终端节点上的码字组成费诺码。

3）香农编码：编码方法如下： ⑴将信源消息符号按其出现的概率大小依次排列 p(u1)≥p(u2)≥…≥p(un) ⑵确定码长Ki (整数) ： Ki= []——取整 ⑶为了编成唯一可译码，计算第i个消息的累加概率 ⑷将累加概率Pi变换成二进制数。 ⑸取pi二进制数的小数点后Ki位即为该消息符号的二进制数。三、课设目的：通过编程实现三种方式的编码，掌握三种编码方式的步骤。四、课设内容：三种编码方式的编程思路： 1、霍夫曼编码：（1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）（2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之