香农编码--信息论大作业

信息论与编码课程大作业题目：香农编码学生姓名：******学号：&**********专业班级：*******************2013年5月10日香农编码1.香农编码的原理/步骤香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度Ki将满足式I(xi)≤Ki＜Ip(xi)+1就可以得到这种码。这种编码方法就是香农编码。香农编码步骤如下:(1)将信源消息符按从大到小的顺序排列。(2)计算p[i]累加概率；(3)确定满足自身要求的整数码长；(4)将累加概率变为二进制数；(5)取P[i]二进制数的小数点后Ki位即为该消息符号的二进制码字。2.用C语言实现#includestdio.h#includemath.h#includestdlib.h#definemax_CL10/*maxsizeoflengthofcode*/#definemax_PN6/*输入序列的个数*/typedeffloatdatatype;typedefstructSHNODE{datatypepb;/*第i个消息符号出现的概率*/datatypep_sum;/*第i个消息符号累加概率*/intkl;/*第i个消息符号对应的码长*/intcode[max_CL];/*第i个消息符号的码字*/structSHNODE*next;}shnolist;datatypesym_arry[max_PN];/*序列的概率*/voidpb_scan();/*得到序列概率*/voidpb_sort();/*序列概率排序*/voidvaluelist(shnolist*L);/*计算累加概率，码长，码字*/voidcodedisp(shnolist*L);voidpb_scan(){inti;datatypesum=0;printf(input%dpossible!\n,max_PN);for(i=0;imax_PN;i++){printf();scanf(%f,&sym_arry[i]);sum=sum+sym_arry[i];}/*判断序列的概率之和是否等于1，在实现这块模块时，scanf()对float数的缺陷，故只要满足0.99sum1.0001出现的误差是允许的*/if(sum1.0001||sum0.99){printf(sum=%f,summust(0.999sum1.0001),sum);pb_scan();}}/*选择法排序*/voidpb_sort(){inti,j,pos;datatypemax;for(i=0;imax_PN-1;i++){max=sym_arry[i];pos=i;for(j=i+1;jmax_PN;j++)if(sym_arry[j]max){max=sym_arry[j];pos=j;}sym_arry[pos]=sym_arry[i];sym_arry[i]=max;}}voidcodedisp(shnolist*L){inti,j;shnolist*p;datatypehx=0,KL=0;/*hx存放序列的熵的结果，KL存放序列编码后的平均码字的结果*/p=L-next;printf(num\tgailv\tsum\t-lb(p(ai))\tlenth\tcode\n);printf(\n);for(i=0;imax_PN;i++){printf(a%d\t%1.3f\t%1.3f\t%f\t%d\t,i,p-pb,p-p_sum,-3.332*log10(p-pb),p-kl);j=0;for(j=0;jp-kl;j++)printf(%d,p-code[j]);printf(\n);hx=hx-p-pb*3.332*log10(p-pb);/*计算消息序列的熵*/KL=KL+p-kl*p-pb;/*计算平均码字*/p=p-next;}printf(H(x)=%f\tKL=%f\nR=%fbit/code,hx,KL,hx/KL);/*计算编码效率*/}shnolist*setnull(){shnolist*head;head=(shnolist*)malloc(sizeof(shnolist));head-next=NULL;return(head);}shnolist*my_creat(datatypea[],intn){shnolist*head,*p,*r;inti;head=setnull();r=head;for(i=0;in;i++){p=(shnolist*)malloc(sizeof(shnolist));p-pb=a[i];p-next=NULL;r-next=p;r=p;}return(head);}voidvaluelist(shnolist*L){shnolist*head,*p;intj=0;inti;datatypetemp,s;head=L;p=head-next;temp=0;while(jmax_PN){p-p_sum=temp;temp=temp+p-pb;p-kl=-3.322*log10(p-pb)+1;/*编码，*/{s=p-p_sum;for(i=0;ip-kl;i++)p-code[i]=0;for(i=0;ip-kl;i++){p-code[i]=2*s;if(2*s=1)s=2*s-1;elseif(2*s==0)break;elses=2*s;}}j++;p=p-next;}}intmain(void){shnolist*head;pb_scan();pb_sort();head=my_creat(sym_arry,max_PN);valuelist(head);codedisp(head);}3.运行结果及分析（本程序先定义了码字长度的最大值和信源概率的个数，然后有设定了概率的和的范围。除此之外，程序采用多个函数求出每个概率的自信息量，采用结构化编程的思想将问题细分成多个模块，再利用数学方法求得累加概率对应的码字长度，在此基础上，利用循环函数求得对应的码字长度。这样就得到了所需的结果。再利用循环依次表达出来即可。4.心得体会通过这次大作业，我觉得自己对C该好好学习了，还有一些基本知识，导致编写程序出现困难。编码的原理虽然知道，但是操作出现困难。对信息论的认识也得到加强和巩固。