香农编码实验报告

中南大学《信息论与编码》实验报告题目信源编码实验指导教师学院专业班级姓名学号日期目录一、香农编码……………………………………….....3实验目的.................................................................................3实验要求.................................................................................3编码算法.................................................................................3调试过程.................................................................................3参考代码.................................................................................4调试验证.................................................................................7实验总结.................................................................................7二、哈夫曼编码……………………………………….8实验目的.................................................................................8实验原理.................................................................................8数据记录.................................................................................9实验心得................................................................................10一、香农编码1、实验目的（1）进一步熟悉Shannon编码算法；（2）掌握C语言程序设计和调试过程中数值的进制转换、数值与字符串之间的转换等技术。2、实验要求（1）输入：信源符号个数q、信源的概率分布p；（2）输出：每个信源符号对应的Shannon编码的码字。3、Shannon编码算法1：procedureSHANNON(q,｛Pi｝)2:降序排列｛Pi｝3:fori=1qdo4:F(is)5：il2[]log1/()ips6：将累加概率F(is)（十进制小数）变换成二进制小数。7：取小数点后il个二进制数字作为第i个消息的码字。8：endfor9：endprocedure------------------------------------------------------------------------------------------------------------------4、调试过程1、fatalerrorC1083:Cannotopenincludefile:'unistd.h':NosuchfileordirectoryfatalerrorC1083:Cannotopenincludefile:'values.h':Nosuchfileordirectory原因：unistd.h和values.h是Unix操作系统下所使用的头文件纠错：删去即可2、errorC2144:syntaxerror:missing')'beforetype'int'errorC2064:termdoesnotevaluatetoafunction原因：l_i(int*)calloc(n,sizeof(int));l_i后缺少赋值符号使之不能通过编译纠错：添加上赋值符号11()ikkps3、errorC2018:unknowncharacter'0xa1'原因：有不能被识别的符号纠错：在错误处将不能识别的符号改为符合C语言规范的符号4、errorC2021:expectedexponentvalue,not''原因：if(fabs(sum-1.0)DELTA);这一行中DELTA宏定义不正确纠错：#defineDELTA0.0000015、errorC2143:syntaxerror:missing';'before'}'原因：少写了“;”号纠错：在对应位置添加上“;”号5、参考代码#includestdio.h#includemath.h#includestdlib.h#includestring.h#defineDELTA0.000001/*精度*/voidsort(float*,int);/*排序*/intmain(void){registerinti,j;intn;/*符号个数*/inttemp;/*中间变量*/float*p_i;/*符号的概率*/float*P_i;/*累加概率*/int*l_i;/*码长*/char**C;/*码集合*//*用sum来检验数据，用p来缓存了中间数据*/floatsum,p;/*输入符号数*/fscanf(stdin,%d,&n);/*分配内存地址*/p_i=(float*)calloc(n,sizeof(float));P_i=(float*)calloc(n,sizeof(float));l_i=(int*)calloc(n,sizeof(int));/*存储信道传输的概率*/for(i=0;in;i++)fscanf(stdin,%f,&p_i[i]);/*确认输入的数据*/sum=0.0;for(i=0;in;i++)sum+=p_i[i];if(fabs(sum-(1.0))DELTA)fprintf(stderr,Invalidinputdata\n);fprintf(stdout,Starting…\n\n);/*以降序排列概率*/sort(p_i,n);/*计算每个符号的码长*/for(i=0;in;i++){p=(float)(-(log(p_i[i])))/log(2.0);l_i[i]=(int)ceil(p);}/*为码字分配内存地址*/C=(char**)calloc(n,sizeof(char*));for(i=0;in;i++){C[i]=(char*)calloc(l_i[i]+1,sizeof(char));C[i][0]='\0';}/*计算概率累加和*/P_i[0]=0.0;for(i=1;in;i++)P_i[i]=P_i[i-1]+p_i[i-1];/*将概率和转变为二进制编码*/for(i=0;in;i++){for(j=0;jl_i[i];j++){/*乘2后的整数部分即为这一位的二进制码元*/P_i[i]=P_i[i]*2;temp=(int)(P_i[i]);P_i[i]=P_i[i]-temp;/*整数部分大于0为1，等于0为0*/if(temp==0)C[i]=strcat(C[i],0);elseC[i]=strcat(C[i],1);}}/*显示编码结果*/fprintf(stdout,Theoutputcodingis:\n);for(i=0;in;i++)fprintf(stdout,%s,C[i]);fprintf(stdout,\n\n);/*释放内存空间*/for(i=n-1;i=0;i--)free(C[i]);free(C);free(p_i);free(P_i);free(l_i);exit(0);}/*冒泡排序法*/voidsort(float*k,intm){inti=1;/*外层循环变量*/intj=1;/*内层循环变量*/intfinish=0;/*结束标志*/floattemp;/*中间变量*/while(im&&!finish){finish=1;for(j=0;jm-i;j++){/*将小的数后移*/if(k[j]k[j+1]){temp=k[j];k[j]=k[j+1];k[j+1]=k[j];finish=0;}i++;}}}6、调试验证：程序结果：7、实验总结1949年香农在《有噪声时的通信》一文中提出了信道容量的概念和信道编码定理，为信道编码奠定了理论基础。无噪信道编码定理（又称香农第一定理）指出，码字的平均长度只能大于或等于信源的熵。有噪信道编码定理（又称香农第二定理）则是编码存在定理。它指出只要信息传输速率小于信道容量，就存在一类编码，使信息传输的错误概率可以任意小。随着计算技术和数字通信的发展，纠错编码和密码学得到迅速的发展。香农编码定理虽然指出了理想编码器的存在性，但是并没有给出实用码的结构及构造方法，编码理论正是为了解决这一问题而发展起来的科学理论。编码的目的是为了优化通信系统。香农编码是码符号概率大的用短码表示，概率小的是用长码表示，程序中对概率排序，最后求得的码字就依次与排序后的符号概率对应。二、哈夫曼编码1、实验目的和任务1、理解信源编码的意义；2、熟悉MATLAB程序设计；3、掌握哈夫曼编码的方法及计算机实现；４、对给定信源进行香农编码，并计算编码效率；2、实验原理介绍1、把信源符号按概率大小顺序排列，并设法按逆次序分配码字的长度；12.......nppp2、在分配码字长度时，首先将出现概率最小的两个符号的概率相加合成一个概率；3、把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止；4、完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为零，概率小的赋为1；5、从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。3、实验内容和步骤对如下信源进行哈夫曼编码，并计算编码效率。12345670.200.190.180.170.150.100.01XaaaaaaaP（1）计算该信源的信源熵，并对信源概率进行排序（2）首先将出现概率最小的两个符号的概率相加合成一个概率，把这个合成概率与其他的概率进行组合，得到一个新的概率组合，重复上述做法，直到只剩下两个概率为止。之后再反过来逐步向前进行编码，每一次有两个分支各赋予一个二进制码。对大的概率赋“1”，小的概率赋“0”。（3）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。（4）计算码字的平均码长得出最后的编码效率。4、实验数据记录clearallp=[0.200.180.150.170.190.100.01];l=0;H=0;N=length(p);fori=1:NH=H+(-p(i)*log2(p(i)));endfprintf('信源信息熵：\n');disp(H);fori=1:N-1forj=i+1:Nifp(i)p(j)m=p(j);p(j)=p(i);p(i)=m;endendendfori=1:N-1c(i,:)=blanks(N*N);endc(N-1,N)='0';c(N-1,2*N)='1';fori=1:N-1%对字符数组c码字赋值过程，记下沿路径的“1”和0;c(N-i,1:N-1)=c(N-i+1,N*(find(m(N-i+1,:)==1))-(N-2):N*(find(m(N-i+1,:)==1)));c(N-i,N)='0';c(N-i,N+1;2*N-1)=c(N-i,1:N-1);c(N-i,2*N)='1';forj=