信息论试验报告

1、信息论是现代通信与信息工程的理论基础。作为电子信息科学与技术专业本科生的学科基础课，本课程主要讲授：信息的定义和测度、信源和信息嫡、连续嫡和信息变差、信道和互信息、平均互信息和信道容量、数据处理和信息测量理论、无失真信源编码理论和编码方法等内容。本课程按单符号离散信息系统”、多符号离散信息系统”、连续信息系统”三个系统”层面，逐步深入展开，以严密的数学分析贯串始终。通过教学，使学生掌握信息理论的基本概念和信息分析方法，为今后进一步研究信息科学和信息技术打下坚实的理论基础。实验一：唯一可译码判断实验学时：3实验类型：(演示、验证、综合、，设计、研究)实验要求：(，必修、选修)一、实验目的通过本次

2、试验了解唯一可译码地判断原理；实现用C语言编写判断唯一可译码地程序二、实验内容编程实现唯一可译码的判决准则SardinasPatterson算法三、实验原理、方法和手段SardinasPatterson算法描述：设C为码字集合，按以下步骤构造此码的尾随后缀集合F:(1)考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中；(2)考查C和Fi两个集合，若WjCC是WiCFi的前缀或WiCFi是WjCC的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；(3)F=UFi即为码C的尾随后缀集合；(4)若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；

3、否则若F中没有出现新的元素，则返回真。在我们设计的算法中，需要注意的是我们需要的是先输出所有尾随后缀的集合，然后再判断该码是否是唯一可译码，即如F中出现了C中的元素，则C不是唯一可译码，否则若F中没有出现新的元素，则C为唯一可译码。而不是F中出现C中的元素就终止，这也是在本题的要求中需要注意的问题。1、概要设计：由于需要判断尾随后缀，所以我们需要反复的比较C和F中的码字。1)首先我们用一个b3030的数组来存放所有的尾随后缀的集合；用Q记录所有尾随后缀的个数；2)用数组a3030来存放输入的码字，L30来存放码字的长度；通过一个双重循环并调用houzhui(ai,aj,Li,Lj)函数来找到a

4、3030中的为随后缀，即：for(i=0;i<n-1;i+)for(j=0;j<n;j+)(if(i!=j&&Li<Lj)HuoZhui(ai,aj,Li,Lj);)3)通过判断Q是否大于0,如果不大于0,即b3030中没有码字，也就是不存在尾随后缀，那么可判断a3030是唯一可译码，否则进行如下操作；4)计算b3030中尾随后缀的长度，用k1表示；并调用HuoZhui(bi,aj,k1,Lj)其中k1<Lj来a3030中所存在的后缀，并加入到b3030中，通过一个循环，找到a3030中所有尾随后缀；即for(i=0;i<Q;i+)(k1=strl

5、en(bi);for(j=0;j<n;j+)(if(k1<Lj)HuoZhui(bi,aj,k1,Lj);)5)寻找b3030中的尾随后缀；用k2表示b3030中码字的长度，并调用HuoZhui(ai,bj,Li,k2)来实现，其中k2>Lj;通过循环调用即可找到b3030中的所有尾随后缀，最后再将他们分别存放在b3030中；即通过for(i=0;i<n;i+)(for(j=0;j<Q;j+)(k2=strlen(bj);if(k2>Li)(HuoZhui(ai,bj,Li,k2);)6)在反复调用HuoZhui(ai,aj,Li,Lj)函数中如果b3030

6、中有重复出现的，即尾随后缀相同的不用再次放入b3030中。7)在调用函数中所需要注意的问题就是一个比较的问题，也就是实现6)中所提到的。四，实验数据源1: 10,0.1002: 10,110,1110五、实验组织运行要求以学生自主训练为主的开放模式组织教学六、实验条件1. 计算机2. WindowsXP3. VC+6.0七、实验内容1.实验源程序#include<iostream.h>#include<stdlib.h>#include<string.h>structstringschar*string;structstrings*next;structst

7、ringsFstr,*Fh,*FP;输出当前集合voidoutputstr(strings*str)docout<<str->string<<endl;str=str->next;while(str);cout<<endl;inlineintMIN(inta,intb)returna>b?b:a;inlineintMAX(inta,intb)returna>b?a:b;#definelength_a(strlen(CP)#definelength_b(strlen(tempPtr)判断一个码是否在一个码集合中，在则返回0,不在返回1i

8、ntcomparing(strings*st_string,char*code)(while(st_string->next)(st_string=st_string->next;if(!strcmp(st_string->string,code)return0;return1;判断两个码字是否一个是另一个的前缀，如果是则生成后缀码voidhouzhui(char*CP,char*tempPtr)(if(!strcmp(CP,tempPtr)(cout<<"集合C和集合F中有相同码字："<<endl<<CP<<

9、;endl<<"不是唯一可译码码组!"<<endl;exit(1);if(!strncmp(CP,tempPtr,MIN(length_a,length_b)(structstrings*cp_temp;cp_temp=new(structstrings);cp_temp->next=NULL;cp_temp->string=newcharabs(length_a-length_b)+1;char*longstr;longstrlongstr=(length_a>length_b?CP:tempPtr);/将长度长的码赋给取出后缀f

10、or(intk=MIN(length_a,length_b);k<MAX(length_a,length_b);k+)cp_temp->stringk-MIN(length_a,length_b)=longstrk;cp_temp->stringabs(length_a-length_b)=NULL;F集合判断新生成的后缀码是否已在集合F里，不在则加入if(comparing(Fh,cp_temp->string)FP->next=cp_temp;FP=FP->next;voidmain()功能提示和程序初始化准备cout<<"tt唯一

11、可译码的判断！n"<<endl;structstringsCstr,*Ch,*CP,*tempPtr;Ch=&Cstr;CP=Ch;Fh=&Fstr;FP=Fh;charc="C:"Ch->string=newcharstrlen(c);strcpy(Ch->string,c);Ch->next=NULL;charf="F:"Fh->string=newcharstrlen(f);strcpy(Fh->string,f);Fh->next=NULL;输入待检测码的个数intCnum

12、;cout<<"输入待检测码的个数："；cin>>Cnum;cout<<"输入待检测码"<<endl;for(inti=0;i<Cnum;i+)cout<<i+1<<":"chartempstr10;cin>>tempstr;CP->next=new(structstrings);CP=CP->next;CP->string=newcharstrlen(tempstr);strcpy(CP->string,tempstr)

13、;CP->next=NULL;outputstr(Ch);CP=Ch;while(CP->next->next)CP=CP->next;tempPtr=CP;dotempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);while(tempPtr->next);outputstr(Fh);structstrings*Fbegin,*Fend;Fend=Fh;while(1)if(Fend=FP)cout<<"是唯一可译码码组!"<<endl;ex

14、it(1);Fbegin=Fend;Fend=FP;CP=Ch;while(CP->next)CP=CP->next;tempPtr=Fbegin;for(;)tempPtr=tempPtr->next;houzhui(CP->string,tempPtr->string);if(tempPtr=Fend)break;outputstr(Fh);/输出F集合中全部元素3.数据测试(1)输入10,0,100"C:XFKOGKA1C-FKEE,5te>pWiititledl-eae揄入性检恻加的个数：3输入桂桂侧铝1 ;102 ：6，：100e=L0a

15、teep；o集合C和集合F中有相同码字：3不是唯一可译码码组，Pi&c号卷anykeytotictntinu电.(2)输入10,110,1110-<.C:FRgKA“lC-FKEEL5te«pUntitledl.叮e甄入食检测阴的个数门输入荐检帆帼2 ：1103 1110C:101101110P：是唯一可译明曲组！Pressanytocontinue.八，实验心得1 .更深入理解了唯一可译码地判断原则2 .学会了用SardinasPatterson算法实现编码判断3 .掌握用C编程实现唯一可译码判断实验二：Huffman编码的实现实验学时：3实验类型：（演示、验证、综合

16、、，设计、研究）实验要求：（，必修、选修）1、 实验目的理解和掌握huffman编码的基本原理和方法，实现对信源符号的huffman编码2、 实验内容1 .理解和掌握huffman编码的基本原理和方法2 .通过MATLAB编程实现对单信源符号的huffma编码3 .计算信源的信息嫡、平均码长以及编码效率3、 实验原理1 .Huffman编码按信源符号出现的概率而编码，其平均码长最短，所以是最优码。2 .无失真信源编码定理：对于嫡为H（X）的离散无记忆的平稳信源，必存在一种无失真编码，使每符号的平均码长满足不等式：旦®L且ilogrlogr3 .二元Huffman编码：若将编码设计为长

17、度不等的二进制编码，即让待传字符串中出现概率大的字符采用尽可能短的码字，而把长的码字分配给概率小的信源符号。构造方法如下：(a)将信源概率分布按大小以递减次序排列；合并两概率最小者，得到新信源；并分配0/1符号。(b)新信源若包含两个以上符号返回(a),否则到(c)。(c)从最后一级向前按顺序写出每信源符号所对应的码字。4 .Huffman编码算法ProcedureHUFFMAN(si,pi)ifq=2thenreturns0-0,s1-1else降序排序pi缩减信源:创建一个符号s'以取代sq-2,sq-1，其概率为p'=pq-2+pq-1递归调用Huffman算法以得到s0

18、，,sq-3,s'的编码:W0，,Wq-3,w',相应的概率分布为p0，,pq-3,p'Returns0-W0,，sq-3-Wq-3,sq-2-w'0,sq-1-W1endifendprocedure4、 实验数据源_622s3s4s51. XP:45X:0,10.40.20.20.10.1_s132s32435s62. XP:3X:0,10.240.200.180.160.140.08五、实验组织运行要求以学生自主训练为主的开放模式组织教学六、实验条件4 .计算机5 .WindowsXP6 .VC+6.0七、实验内容1 .实验源程序#include<st

19、dio.h>#defineMAXBIT100#defineMAXVALUE10000#defineMAXLEAF30#defineMAXNODEMAXLEAF*2-1typedefstructintbitMAXBIT;intstart;HCodeType;/*编码结构体*/typedefstructintweight;intparent;intlchild;intrchild;HNodeType;/*结点结构体*/*构造一颗哈夫曼树*/voidHuffmanTree(HNodeTypeHuffNodeMAXNODE,intn)/*i、j:循环变量，m1、m2：构造哈夫曼树不同过程中两个最

20、小权值结点的权值,x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/inti,j,m1,m2,x1,x2;/*初始化存放哈夫曼树数组HuffNode口中的结点*/for(i=0;i<2*n-1;i+)*/0;1;1;1;HuffNodei.weight=HuffNodei.parent=-HuffNodei.lchild=-HuffNodei.lchild=-/*endfor*/*输入n个叶子结点的权值for(i=0;i<n;i+)printf("Pleaseinputweightofleafnode%d:n",i);scanf("

21、%d",&HuffNodei.weight);/*endfor*/*循环构造Huffman树*/for(i=0;i<n-1;i+)/*m1、m2中存放两个无父结点且结点权值最小的两个结m1=m2=MAXVALUE;点*/x1=x2=0;/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/for(j=0;j<n+i;j+)if(HuffNodej.weight<m1&&HuffNodej.parent=-1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;elseif(HuffNodej.weigh

22、t<m2&&HuffNodej.parent=-1)m2=HuffNodej.weight;x2=j;/*endfor*/*设置找到的两个子结点x1、x2的父结点信息*/HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;%d:%d,%dn",i+1,/*用于测试*/*定义一个结点结构体数组*/*定义一个编码结构体数组，同HuffNoden+i.rchild=x2;print

23、f("x1.weightandx2.weightinroundHuffNodex1.weight,HuffNodex2.weight);printf("n");/*endfor*/*endHuffmanTree*/intmain(void)HNodeTypeHuffNodeMAXNODE;HCodeTypeHuffCodeMAXLEAF,cd;时定义一个临时变量来存放求解编码时的信息*/inti,j,c,p,n;printf("Pleaseinputn:n");scanf("%d",&n);HuffmanTree(H

24、uffNode,n);for(i=0;i<n;i+)cd.start=n-1;c=i;p=HuffNodec.parent;while(p!=-1)/*父结点存在*/if(HuffNodep.lchild=c)0;1;/*求编码的低一位*/*设置下一循环条件*/cd.bitcd.start=elsecd.bitcd.start=cd.start-;c=p;p=HuffNodec.parent;/*endwhile*/*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/for(j=cd.start+1;j<n;j+)HuffCodei.bitj=cd.bitj;HuffCodei.s

25、tart=cd.start;/*endfor*/*输出已保存好的所有存在编码的哈夫曼编码*/for(i=0;i<n;i+)printf("%d'sHuffmancodeis:",i);for(j=HuffCodei.start+1;j<n;j+)printf("%d",HuffCodei.bitj);printf("n");return0;2 .流程框图3 .数据测试(1)XP:62223s40.40.20.20.1S50.1X:0,1.<“匚=XPEOGRAIC-FKEH*1.5respYUn-ritlf?

26、d2.evePLoqinputsn3THPleaseinputweightdFleafnoden=4BP'Xcascxnput;wc=:Jit：of±ca£node1sPLea&einpucIjjhrofleafmode2s：2。工仁也型特inputw。工vhtuTleafflU>Ue3工P工。也©。inpu%w®ightofleafnodo4£10i_uelHltandlx2._Ll吟igliit:In产始undft二10,1.0.wcand.?c2wc工gJi七£n1'ou.nd2:叽2BMl.ij。±<yhitand.x2,ij刍Iglitini*ound3s20.40xi.3的五0htrllltl注2.iql.七intqmiiml41API.GHB*HHiFfmLFicodei卡111,sHluF&