中南大学《信息论与编码》实验报告目录一、香农编码 (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：procedure SHANNON(q,｛Pi ｝)2: 降序排列｛Pi ｝ 3: for i=1 q do 4: F(i s ) 5：i l 2[]log 1/()i p s 6：将累加概率F(i s )（十进制小数）变换成二进制小数。

7：取小数点后i l 个二进制数字作为第i 个消息的码字。

8：end for9：end procedure------------------------------------------------------------------------------------------------------------------4、调试过程1、fatal error C1083: Cannot open include file: 'unistd.h': No such file or directoryfatal error C1083: Cannot open include file: 'values.h': No such file or directory原因：unistd.h 和values.h 是Unix 操作系统下所使用的头文件纠错：删去即可2、error C2144: syntax error : missing ')' before type 'int'error C2064: term does not evaluate to a function原因：l_i(int *)calloc(n,sizeof(int)); l_i 后缺少赋值符号使之不能通过编译纠错：添加上赋值符号11()i k k p s -=∑3、error C2018: unknown character '0xa1'原因：有不能被识别的符号纠错：在错误处将不能识别的符号改为符合C语言规范的符号4、error C2021: expected exponent value, not ' '原因：if(fabs(sum-1.0)>DELTA); 这一行中DELTA宏定义不正确纠错：# define DELTA 0.0000015、error C2143: syntax error : missing ';' before '}'原因：少写了“;”号纠错：在对应位置添加上“;”号5、参考代码# include<stdio.h># include<math.h># include<stdlib.h># include<string.h># define DELTA 0.000001/*精度*/void sort(float*,int);/*排序*/int main(void){register int i,j;int n; /*符号个数*/int temp;/*中间变量*/float *p_i; /*符号的概率*/float *P_i; /*累加概率*/int *l_i; /*码长*/char * *C; /*码集合*//*用sum来检验数据，用p来缓存了中间数据*/float sum,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;i<n;i++)fscanf(stdin,"%f",&p_i[i]);/*确认输入的数据*/sum=0.0;for(i=0;i<n;i++)sum+=p_i[i];if(fabs(sum-(1.0))>DELTA)fprintf(stderr,"Invalid input data \n");fprintf(stdout,"Starting…\n\n");/*以降序排列概率*/sort (p_i,n);/*计算每个符号的码长*/for(i=0;i<n;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;i<n;i++){C[i]=(char *)calloc(l_i[i]+1,sizeof(char));C[i][0]='\0';}/*计算概率累加和*/P_i[0]=0.0;for(i=1;i<n;i++)P_i[i]=P_i[i-1]+p_i[i-1];/*将概率和转变为二进制编码*/for(i=0;i<n;i++){for(j=0;j<l_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,"The output coding is :\n"); for(i=0;i<n;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);}/*冒泡排序法*/void sort(float *k,int m){int i=1;/*外层循环变量*/int j=1;/*内层循环变量*/int finish=0;/*结束标志*/float temp;/*中间变量*/while(i<m&&!finish){finish=1;for(j=0;j<m-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.......n p p p ≥≥≥2、在分配码字长度时，首先将出现概率 最小的两个符号的概率相加合成一个概率；3、把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止；4、完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为零，概率小的赋为1；5、从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。

3、实验内容和步骤对如下信源进行哈夫曼编码，并计算编码效率。

12345670.200.190.180.170.150.100.01X a a a a a a a P ⎡⎤⎡⎤=⎢⎥⎢⎥⎣⎦⎣⎦（1）计算该信源的信源熵，并对信源概率进行排序（2）首先将出现概率最小的两个符号的概率相加合成一个概率，把这个合成概率与其他的概率进行组合，得到一个新的概率组合，重复上述做法，直到只剩下两个概率为止。

之后再反过来逐步向前进行编码，每一次有两个分支各赋予一个二进制码。

对大的概率赋“1”，小的概率赋“0”。

（3）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。

（4）计算码字的平均码长得出最后的编码效率。

4、实验数据记录>> clear all>> p=[0.20 0.18 0.15 0.17 0.19 0.10 0.01];l=0;H=0;N=length(p);for i=1:NH=H+(-p(i)*log2(p(i)));endfprintf('信源信息熵：\n');disp(H);for i=1:N-1for j=i+1:Nif p(i)<p(j)m=p(j);p(j)=p(i);p(i)=m;endendendfor i=1:N-1c(i,:)=blanks(N*N);endc(N-1,N)='0';c(N-1,2*N)='1';for i=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';for j=1:i-1c(N-i,(j+1)*N+1:(j+2)*N)=c(N-i+1,N*(find(m(N-i+1,:)==j+1)-1)+1:N*find (m(N-i+1,:)==j+1));endendfor i=1:Nh(i,1:N)=c(1,N*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*N);%码字赋值 ll(i)=length(find(abs(h(i,:))~=32));%各码字码长endl=sum(p.*ll);%计算平均码长n=H/l;%计算编码效率fprintf('编码的码字：\n');disp(h)%按照输入顺序从大到小排列后的码字fprintf('平均码长：\n');disp(l)%输出平均码长fprintf('编码效率：\n');disp(n)%输出编码效率5、实验心得由于我们的知识浅薄，经验不足及阅历颇浅，因此，在该程序的设计方面还有很多的不足，会在以后的学习过程中，根据所学的知识不断的修改、完善，争取慢慢趋于完美。