《信息论实验报告.doc》由会员分享，可在线阅读，更多相关《信息论实验报告.doc（16页珍藏版）》请在三一办公上搜索。
1、前 言信息论是现代通信与信息工程的理论基础。作为电子信息科学与技术专业本科生的学科基础课，本课程主要讲授：信息的定义和测度、信源和信息熵、连续熵和信息变差、信道和互信息、平均互信息和信道容量、数据处理和信息测量理论、无失真信源编码理论和编码方法等内容。本课程按“单符号离散信息系统”、“多符号离散信息系统”、“连续信息系统”三个“系统”层面，逐步深入展开，以严密的数学分析贯串始终。通过教学，使学生掌握信息理论的基本概念和信息分析方法，为今后进一步研究信息科学和信息技术打下坚实的理论基础。实验一：唯一可译码判断实验学时：3实验类型：（演示、验证、综合、设计、研究）实验要求：（必修、选修）一、实验目
2、的通过本次试验了解唯一可译码地判断原理；实现用C语言编写判断唯一可译码地程序二、实验内容编程实现唯一可译码的判决准则SardinasPatterson算法三、实验原理、方法和手段SardinasPatterson算法描述： 设C为码字集合，按以下步骤构造此码的尾随后缀集合F： (1) 考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中； (2) 考查C和Fi两个集合，若WjC是WiFi的前缀或WiFi 是WjC的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中； (3)F=Fi即为码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,
4、Li,Lj）函数来找到a3030中的为随后缀，即：for(i=0;in-1;i+) for(j=0;jn;j+) if(i!=j&LiLj) HuoZhui(ai,aj,Li,Lj); 3） 通过判断Q是否大于0，如果不大于0，即b3030中没有码字，也就是不存在尾随后缀，那么可判断a3030是唯一可译码，否则进行如下操作；4） 计算b3030中尾随后缀的长度，用k1表示；并调用HuoZhui(bi,aj,k1,Lj)其中k1Lj来a3030中所存在的后缀，并加入到b3030中，通过一个循环，找到a3030中所有尾随后缀；即 for(i=0;iQ;i+) k1=strlen(bi); for(
5、j=0;jn;j+) if(k1Lj;通过循环调用即可找到b3030中的所有尾随后缀，最后再将他们分别存放在b3030中；即通过 for(i=0;in;i+) for(j=0;jLi) HuoZhui(ai,bj,Li,k2); 6） 在反复调用HuoZhui(ai,aj,Li,Lj)函数中如果b3030中有重复出现的，即尾随后缀相同的不用再次放入b3030中。7） 在调用函数中所需要注意的问题就是一个比较的问题，也就是实现6）中所提到的。四，实验数据源1： 10,0.1002: 10,110，1110五、实验组织运行要求以学生自主训练为主的开放模式组织教学六、实验条件1. 计算机2. Win
6、dows XP3. VC+ 6.0七、实验内容实验源程序#include #include #include struct strings char *string; struct strings *next;struct strings Fstr, *Fh, *FP;/输出当前集合void outputstr(strings *str)docoutstringnext;while(str);coutb?b:a; inline int MAX(int a, int b) return ab?a:b; #define length_a (strlen(CP)#define length_b (s
7、trlen(tempPtr)/判断一个码是否在一个码集合中，在则返回0，不在返回1int comparing(strings *st_string,char *code)while(st_string-next)st_string=st_string-next;if(!strcmp(st_string-string,code)return 0;return 1;/判断两个码字是否一个是另一个的前缀，如果是则生成后缀码void houzhui(char *CP,char *tempPtr)if (!strcmp(CP,tempPtr)cout集合C和集合F中有相同码字:endlCPendl不是唯
8、一可译码码组!next=NULL;cp_temp-string=new charabs(length_a-length_b)+1; char *longstr;longstr=(length_alength_b ? CP : tempPtr);/将长度长的码赋给longstr/取出后缀for (int k=MIN(length_a,length_b); kstringk - MIN(length_a,length_b)=longstrk;cp_temp-stringabs(length_a-length_b)=NULL;/判断新生成的后缀码是否已在集合F里，不在则加入F集合if(compari
9、ng(Fh,cp_temp-string)FP-next=cp_temp;FP=FP-next;void main()/功能提示和程序初始化准备couttt唯一可译码的判断!nstring=new charstrlen(c); strcpy(Ch-string, c); Ch-next=NULL; char f=F :; Fh-string=new charstrlen(f); strcpy(Fh-string, f); Fh-next=NULL;/输入待检测码的个数int Cnum;coutCnum;cout输入待检测码endl;for(int i=0; iCnum; i+) couti+1
10、tempstr; CP-next=new (struct strings);CP=CP-next;CP-string=new charstrlen(tempstr) ;strcpy(CP-string, tempstr);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);struct strings *F
11、begin,*Fend; Fend=Fh; while(1) if(Fend = FP)cout是唯一可译码码组!next) CP=CP-next;tempPtr=Fbegin;for(;)tempPtr=tempPtr-next;houzhui(CP-string,tempPtr-string);if(tempPtr = Fend)break;outputstr(Fh);/输出F集合中全部元素 流程框图数据测试（）输入10,0,100(2)输入10,110，1110八，实验心得1.更深入理解了唯一可译码地判断原则2.学会了用SardinasPatterson算法实现编码判断3.掌握用C编程实
12、现唯一可译码判断实验二： Huffman编码的实现实验学时：3实验类型：（演示、验证、综合、设计、研究）实验要求：（必修、选修）一、 实验目的理解和掌握huffman编码的基本原理和方法，实现对信源符号的huffman编码。二、 实验内容1. 理解和掌握huffman编码的基本原理和方法2. 通过MATLAB编程实现对单信源符号的huffma编码3. 计算信源的信息熵、平均码长以及编码效率三、 实验原理1 Huffman编码按信源符号出现的概率而编码，其平均码长最短，所以是最优码。2 无失真信源编码定理：对于熵为H(X)的离散无记忆的平稳信源，必存在一种无失真编码，使每符号的平均码长满足不等式
13、：3 二元Huffman编码：若将编码设计为长度不等的二进制编码，即让待传字符串中出现概率大的字符采用尽可能短的码字，而把长的码字分配给概率小的信源符号。构造方法如下：（a） 将信源概率分布按大小以递减次序排列；合并两概率最小者，得到新信源；并分配0/1符号。（b） 新信源若包含两个以上符号返回（a），否则到（c）。（c） 从最后一级向前按顺序写出每信源符号所对应的码字。4Huffman编码算法Procedure HUFFMAN(si ,pi ) if q=2then return s0 0, s1 1else 降序排序pi缩减信源:创建一个符号s以取代sq-2 ,sq -1 ,其概率为p=p
14、q-2+ pq-1 递归调用Huffman算法以得到s0 ,sq-3 ,s的编码:w0 ,wq-3 ,w,相应的概率分布为p0 ,pq -3 ,p Returns 0 w0,sq-3 wq-3 ,sq-2 w0,sq-1 w1 end ifend procedure四、 实验数据源1 2 五、实验组织运行要求以学生自主训练为主的开放模式组织教学六、实验条件4. 计算机5. Windows 6. VC+ 6.0七、实验内容实验源程序#include #define MAXBIT 100#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE
15、MAXLEAF*2 -1typedef struct int bitMAXBIT; int start; HCodeType; /* 编码结构体 */typedef struct int weight; int parent; int lchild; int rchild; HNodeType; /* 结点结构体 */* 构造一颗哈夫曼树 */void HuffmanTree (HNodeType HuffNodeMAXNODE, int n) /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值， x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号
16、。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼树数组 HuffNode 中的结点 */ for (i=0; i2*n-1; i+) HuffNodei.weight = 0; HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.lchild =-1; /* end for */ /* 输入 n 个叶子结点的权值 */ for (i=0; in; i+) printf (Please input weight of leaf node %d: n, i); scanf (%d, &HuffNodei.we
17、ight); /* end for */ /* 循环构造 Huffman 树 */ for (i=0; in-1; i+) m1=m2=MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */ x1=x2=0; /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */ for (j=0; jn+i; j+) if (HuffNodej.weight m1 & HuffNodej.parent=-1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight m2 & Hu
18、ffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /* end for */ /* 设置找到的两个子结点 x1、x2 的父结点信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.lchild = x1; HuffNoden+i.rchild = x2; printf (x1.weight and x2.weight in round %d: %d, %
19、dn, i+1, HuffNodex1.weight, HuffNodex2.weight); /* 用于测试 */ printf (n); /* end for */ /* end HuffmanTree */int main(void) HNodeType HuffNodeMAXNODE; /* 定义一个结点结构体数组 */ HCodeType HuffCodeMAXLEAF, cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */ int i, j, c, p, n; printf (Please input n:n); scanf (%d, &n);
20、HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父结点存在 */ if (HuffNodep.lchild = c) cd.bitcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求编码的低一位 */ c=p; p=HuffNodec.parent; /* 设置下一循环条件 */ /* end while */ /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
21、 for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; /* end for */ /* 输出已保存好的所有存在编码的哈夫曼编码 */ for (i=0; in; i+) printf (%d s Huffman code is: , i); for (j=HuffCodei.start+1; j n; j+) printf (%d, HuffCodei.bitj); printf (n); return 0;2.流程框图3.数据测试（1） （2） 八实验心得1.更深入了解了哈夫曼编码的构造原理 2.同本次试验学会了利用构造哈弗曼树实现哈夫曼编码3.掌握用C编程实现哈夫曼编码
