信息论课程设计

程设计(论文) 武汉工程大学课

目录

目录 .......................................................................................................... I 摘要 ........................................................................................................ III 前言 ........................................................................................................ IV 1 1.1 1.2 1.3 1.4 2 2.1 2.2 3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 4 4.1 4.2

课题背景 ............................................................................................. 1 背景 .......................................................................................................... 1 需求分析 ................................................................................................... 1 意义 .......................................................................................................... 2 文献综述 ................................................................................................... 2 设计简介及设计方案论述 ..................................................................... 3 设计简介 ................................................................................................... 3 设计方案论述............................................................................................ 3 详细设计 ............................................................................................. 5 结构体定义 ............................................................................................... 5 统计字符 ................................................................................................... 5 霍夫曼编码 ............................................................................................... 6 费诺编码 ................................................................................................... 7 普通编码 ................................................................................................... 9 输出信息 ................................................................................................. 10 转码 ........................................................................................................ 10 解码 ........................................................................................................ 11 设计结果及分析 ................................................................................ 13 测试结果 ................................................................................................. 13 测试分析 ................................................................................................. 15

5总结 ..................................................................................................... 16

I

程设计(论文) 武汉工程大学课

致谢 ........................................................................................................ 18 参考文献 ................................................................................................. 19 附录 程序代码 ...................................................................................... 20

II

程设计(论文) 武汉工程大学课

摘要

本课题主要是运用VC6.0，开发基于控制台下的霍夫曼、费诺与普通编码程序。本文较详细地介绍了这一程序的设计思想，功能结构以及算法与数据结构的设计和某些功能函数的设计。本文还给出了对这一程序的测试情况以及对测试结果的分析。

关键词：霍夫曼吗，费诺码，普通码，算法与数据结构。

III

程设计(论文) 武汉工程大学课

前言

本文详细介绍了编码程序的设计与开发。全文共5章。

第1章介绍了编码程序的背景，以及它所要实现的基本功能。并根据这些进行了必要的需求分析，从而确定了该程序应实现了一些基本功能。本章中，还简要地介绍了该程序开发的意义以及在整个开发过程中，我们所查阅并借用的一些参考文献的主要内容。

第2章主要介绍了编码程序中各功能模块的总体框图，主要类的设计以及各类之间的相互关系，这是全文的核心部分。

第3章是编码程序的详细设计，由于文章篇幅的限制，我们仅给出了主要类的设计，关键函数设计，包括结点定义、编码定义、霍夫曼编码、费诺编码、普通编码以及转码和解码，并给出了其程序代码。

第4章是对编码程序的运行测试和分析。通过我们对输入字符串的测试，检验程序是否达到了预定的设计要求。

第5章是编码程序开发过程的总结。总结了本次课程设计的意义，以及测试中所发现的一些问题，有待进一步改进的地方。重点还谈到了我在本次课程设计中的收获与感想。

全文的最后是致谢、参考文献和程序的全部源代码。

胡哲 袁琪 张小柯

2014-06-16于武汉工程大学理学院

IV

程设计(论文) 武汉工程大学课

2 课题背景

2.1 背景

信源编码主要可分为无失真信源编码和限失真信源编码。无失真信源

编码主要适用于离散信源或数字信号，如文本、表格及工程图纸等信源，它们要求进行无失真地数据压缩，要求完全能够无失真地可逆恢复。限失真信源编码主要适用于波形信源或波形信号（及模拟信号），如语音、电视图像、彩色静止图像等信号，它们不要求完全可逆地恢复，而是允许在一定限度内可以有失真的压缩。无论是无失真还是限失真的信源编码，其目的都是为了用较少的码率来传送同样多的信息，增加单位时间内传送的信息量，从而提高通信系统的有效性。

香农信息理论——香农第一定理和香农第三定理是信源编码的理论基础，它们分别从理论上给出了进行无失真信源压缩和限失真信源压缩的理论极值，而且还论证与指出了理想最佳信源编码是存在的。但是并没有给出信源编码的实际构造方法和实用码的结构。为此，随着科学技术的发展和需求，人们广泛地致力于对各种文本、图片、图形、语言、声音、活动图像和影视信号等实际信源进行了实用压缩方法和技术的研究，使信源的数据压缩技术得以蓬勃发展和逐渐走向成熟。

2.2 需求分析

根据上节所描述，用户需要设计一个关于对信息能够进行编码压缩以及解码的程序，使需要对文件进行压缩的用户，可以通过输入文本，便可对文件进行编码以及解码。

另外，该程序还要实现以下功能：

(1) 能够用霍夫曼编码方式进行编码、解码； (2) 能够用费诺编码方式进行编码、解码； (3) 能够用普通方式进行编码、解码； (4) 能够直观地看出三种编码方式的差别。

1

程设计(论文) 武汉工程大学课

2.3 意义

通过编码的实例可以看出，我们编写的二元霍夫曼码具有以下三个特点： 第一，霍夫曼码的编码方式保证了概率大的符号对应短码，概率小的符号对应长码，即pj?pk，有lj?lk，而且短码得到充分利用。

第二，每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同（二元编码情况）。

第三，每次缩减信源的最长两个码字有相同的码长。 这三个特点保证了所得的霍夫曼码一定是最佳码。

费诺编码方法属于概率匹配编码，这种编码方法稍不同于前述的霍夫曼编码，它不是最佳的编码方法，但有时也可得到最加码的性能。费诺码的编码方法实际上是构造码树的一种方法，所以费诺码是即时码。费诺码也考虑了信源的统计特性，使经常出现的信源符号能对应码长短的码字。显然，费诺码仍是一种相当好的编码方法。但是这种编码方法不一定能使短码得到充分利用。尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会出现后面小组的“概率和”相差较远，因而使平均码长增加。

普通编码方式放在此例中仅用于对比作用。

2.4 文献综述

文献[1]较详细地介绍了数据结构的一些基本知识，它对于我们了解和运用用数据结构知识有非常直接的帮助。

文献[2]信息编码的专业知识，帮助我们了解编码的相关原理，流程，以及及算法，是保证我们进行编程的理论基础。

2

程设计(论文) 武汉工程大学课

3 设计简介及设计方案论述

3.1 设计简介

根据需求分析，我们将设计两个结构体：Node（树结点结构体）和CodeNode（即编码结构体）。其主要功能模块有：输入字符串、筛选概率、霍夫曼编码、费诺编码、普通编码，以及转码和解码，并计算平均码长和编码效率。其类结构见图2-1。

输入字符串 统计每个字符概率 霍夫曼编码 费诺编码 普通编码 平均码长、编码效率 转码、解码 图2-1 程序的功能结构

3.2 设计方案论述

该程序大致包含以下功能：

输入字符串，设置一个结束符，例如‘#’，只有输入结束符或字符长度超过定义的字符容量时，才会结束。接着会把字符串中的每个字符统计起来，并几率这些字符各自相应的概率。

霍夫曼编码：保证出现概率最小的字符码长最大。

3

程设计(论文) 武汉工程大学课

费诺编码：保证概率平均分配。

普通编码：按字符出现的先后顺序按二进制编码。 转码：将字符串中的每个字符转化成相应的编码。 解码：将转码的编码翻译成字符。

4

程设计(论文) 武汉工程大学课

4 详细设计

4.1 结构体定义

1.定义结点结构体： struct Node { };

2.定义编码结构体 struct CodeNode {

char str; int suffix;

float weight; //权值 char str;

int left,right,parent; //分别指向该节点的左孩子，右孩子，和双亲节点

double weight;//权值 };

int length;//编码长度 char code[L];//编码字符

4.2 统计字符

void SearchStr(char s[],Node a[])

{//查找字符串中字符的个数和每个字符出现的次数

int i,j,k=0;

5

程设计(论文) 武汉工程大学课

}

for(i=0;i

a[i].weight=0;

i=0; do {

for(j=0;j

if(a[j].str==s[i]){

a[j].weight++; break;

}

if(j==k)

{ //在str[]中无该字符，将其存入最后一个单元

a[k].str=s[i];

a[k++].weight++; } i++;

}while(s[i]!='\\0');

a[k].str='\\0'; //将字符串结尾置\ Len=k; //不同字符数 SumL=i; //总字符数

4.3 霍夫曼编码

void HuffCode(Node a[],CodeNode cd[],int n) //霍夫曼编码 { int i,k,f,strlen;

6

程设计(论文) 武汉工程大学课

char temp[N]; for(i=0;i

for(k=i,f=a[i].parent;f!=-1;k=f,f=a[f].parent)

if(a[f].left==k)

{ temp[strlen]='0';//左分枝取0 strlen++; } else

{ temp[strlen]='1';//右分枝取1 }

strlen++;

cd[i].str=a[i].str;//第i个叶结点字符 cd[i].weight=a[i].weight;//第i个叶结点权值

cd[i].length=strlen;//第i个叶结点的编码长 }

}

//将存放在temp中的码值，依逆序方式导入cd[i].code cd[i].code[strlen]='\\0';//字符数组的最后一位设置为空值 strlen--; k=0;

while(strlen>=0)

cd[i].code[k++]=temp[strlen--];

4.4 费诺编码

int Group(CodeNode FC[],int low,int high)

7

程设计(论文) 武汉工程大学课

{ /*一次分组(一分为二)并编码*/

float MinSum=FC[low].weight,MaxSum=FC[high].weight;

FC[low].code[FC[low].length++]='0'; FC[high].code[FC[high].length++]='1';

while(low+1

} else { }

MinSum+=FC[++low].weight;

FC[low].code[FC[low].length++]='0'; //编码加0

{

if(MinSum>MaxSum) {

MaxSum+=FC[--high].weight;

FC[high].code[FC[high].length++]='1'; //编码加1

return low; }

void FanoEncoding(CodeNode FC[],int s,int t){/*递归进行费诺编码*/

if(s

int pivotloc=Group(FC,s,t); if(s

FanoEncoding(FC,s,pivotloc); FanoEncoding(FC,pivotloc+1,t);

8

//返回分组的第一部分的上界

程设计(论文) 武汉工程大学课

}

}

}

4.5 普通编码

void CommCoding(Node a[],CodeNode cd[]) {//对普通码的每个字符进行编码 int i,j,ibak; for(i=0;i

ibak=i;

cd[i].weight=a[i].weight; cd[i].str=a[i].str; cd[i].length=L; for(j=0;j

if(ibak%2==0)

cd[i].code[L-1-j]='0';

else

cd[i].code[L-1-j]='1';

ibak=ibak/2; }

} }

9

程设计(论文) 武汉工程大学课

4.6 输出信息

void DisCode(CodeNode cd[],int n)

{cout<<\字符\\t\概率\\t\码长\\t\编码\\t\ for(int i=0;i

{cout<

cout<

cout<

}

double K=0,H=0,R; for(i=0;i

{K=K+(cd[i].weight/SumL)*cd[i].length;

H+=-(cd[i].weight/SumL)*log((cd[i].weight/SumL)); } R=H/K;

cout<<\平均码长为:\ cout<<\编码效率为:\}

4.7 转码

void Coding(char s[],CodeNode cd[],char code[]) {//利用哈夫曼编码表对整个字符串进行编码 int i,j,k,m=0;

code[0]='\\0';//编码数组初始化 for(i=0;s[i];i++)

10

程设计(论文) 武汉工程大学课

{//将每个字符在赫夫曼编码表中对应的编码存入存放总编码的数组中 for(j=0;j<=Len;j++) if(s[i]==cd[j].str)

{for(k=0;k

break;

code[m++]=' '; }

for(i=0;i

cout<

cout<

4.8 解码

void DeCode(char ss[],CodeNode HC[],char code[])//解码 {int i,j,k,m,n=0,flag; int a[M];

a[0]='\\0';ss[0]='\\0'; k=0;

for(i=0;code[i];i++)

if(code[i]!=' ') a[k++]=code[i]; else { a[k]='\\0';

for(j=0;j

{ flag=1; //表示a[k]=HC[j].code

11

程设计(论文) 武汉工程大学课

for(m=0;m

a[0]='\\0'; k=0;

break;

}

} }

for(i=0;i

cout<

cout<

12

程设计(论文) 武汉工程大学课

5 设计结果及分析

5.1 测试结果

(1) 任意输入字符串

图4-1 输入字符串

(2) 霍夫曼编码

图4-2 霍夫曼码相关信息

13

程设计(论文) 武汉工程大学课

(3) 费诺编码

图4-3 费诺码相关信息

(4) 普通编码

14

程设计(论文) 武汉工程大学课

图4-4 普通码相关信息

5.2 测试分析

表4-5 比较不同编码的平均码长和编码效率

平均码长 编码效率 霍夫曼码 4.311 0.689 费诺码 4.338 0.685 普通码 8 0.371 根据上表可知霍夫曼码的平均码长最小，编码效率最高；普通码的平均码平均码长最大，编码效率最低。

15

程设计(论文) 武汉工程大学课

5总结

大二第二学期，我学习了《信息论与编码理论》，初步了解了编码理论的相关知识。对于其中的理论证明，我总是感到似曾相识，里面的一些内容在《算法与数据结构》中有所介绍，只是讲解的比较基础，而偏向于程序。

这学期对这门课的学习真的云里雾里。由于以前的数学课程没有学好，听起这门课就像听天书；看起书上一个个推理公式，头就晕了，畏难情绪油然而生。在这门课程里，我时常能感受到郭老师热情激昂的讲解与一丝不苟的推理其中的奥秘。对于数学知识海洋的高深莫测，我总是束手无策，除此之外，就是退缩与妥协。然而，课程设计就在我毫无准备的情况下不期而至，留给我的就像一道天然的屏障，无法逾越，给我的挑战是不言而喻的。

好在我以前学的《算法与数据结构》的知识还是相当不错，自己数学底子还有一点，能够看懂霍夫曼码，费诺码，普通码的原理，能够了解其中的算法推理。在自己大脑中萦绕着其中的思绪，不禁信心大增，我难以阻挡突如其来的自信来面对课程设计。这些理论我理解起来还是比较轻松的，更大的挑战莫过于编程了，就是用计算机实现其中的原理，再对霍夫曼码、费诺码、普通码的平均码长和编码效率进行比较。

我开始了从所未有的艰难抉择，尽管理论不难，可在计算机上实现时每一步都以为着可能出现多处错误，不同错误相互影响，不同错误共同构造程序编码的神圣地位，而我注定要与之进行持久战。每当我敲下一行代码，都意味着这句代码实现的相关作用及其如何承上启下，充当机器此轮中的一个零件。每当运行时，总会有些莫名其妙的错误，总会有不如人意的地方。每当修改一个错误，就不知道会有多少错误同事出现，这就意味着我必须要有统筹全局的大局观和精益求精地把握每一个细节，不能忽视每一个细节。然而，这还不是最令人痛苦的，而是语法结构没错，而程序运行结果会出现莫名其妙的错误，而其中的错误原因可能是数以万计的代码中其中的一个字母或是一个符号，这就必须要从头再来，对不同函数进行测试，找出有问题的函数；再查询该函数的

16

本文来源：https://www.bwwdw.com/article/45qh.html