中南大学信息论与编码编码部分实验报告

1信息论与编码编码部分实验报告课程名称：信息论与编码实验名称：关于香农码费诺码Huffman码的实验学院：信息科学与工程学院班级：电子信息工程1201姓名：viga学号：指导老师：张祖平日期：2014年1月3日2目录⊙实验目的及要求1.1实验目的………………………………………………41.2开发工具及环境………………………………………41.3需求分析与功能说明…………………………………4⊙实验设计过程2.1用matlab实现香农码、费诺码和Huffman编码2.1.1说明………………………………………………62.1.2源代码……………………………………………72.1.3运行结果（截图）………………………………192.2用C\C++实现香农码2.2.1说明………………………………………………222.2.2源代码……………………………………………232.2.3运行结果（截图）………………………………262.3用C\C++实现Huffman码2.3.1说明………………………………………………262.3.2源代码……………………………………………292.3.3运行结果（截图）………………………………362.4用C\C++实现费诺码2.4.1说明………………………………………………3732.4.2源代码……………………………………………372.4.3运行结果结果（截图）…………………………40⊙课程设计总结……………………………………………42⊙参考资料4.1课程设计指导书……………………………………434实验目的及要求1.1实验目的1.掌握香农码、费诺码和Huffman编码原理和过程。2.熟悉matlab软件的基本操作，练习使用matlab实现香农码、费诺码和Huffman编码。3.熟悉C/C++语言，练习使用C/C++实现香农码、费诺码和Huffman编码。4.应用Huffman编码实现文件的压缩和解压缩。1.2开发工具及环境MATLAB7.0、wps文字、红精灵抓图精灵2010Windows7系统环境1.3需求分析与功能说明1、使用matlab实现香农码、费诺码和Huffman编码，并自己设计测试案例。2、使用C\C++实现香农码、费诺码和Huffman编码，并自己设计测试案例。3、可以用任何开发工具和开发语言，尝试实现Huffman编码应用在数据文件的压缩和解压缩中，并自己设计测试案例。5具体要求：读入有关信源的文本文件（测试用例，里面为每个符号的概率，概率数值用,隔开），然后分别用matlab实现香农码、费诺码和Huffman编码，并计算各个码的平均码长，编码效率，并用matlab图示出来（可以是曲线图或直方图），再尝试对同样的信源用C\C++实现香农码、费诺码和Huffman编码。文本文件例如infosource.txt。文件里面的内容为0.4，0.2，0.1，0.1，0.15，0.05（，可能是全角或半角）。6实验设计过程2.1用matlab实现香农码、费诺码和Huffman编码2.1.1说明（1）使用matlab实现香农码、费诺码和Huffman编码，并自己设计测试案例。具体要求：读入有关信源的文本文件（测试用例，里面为每个符号的概率，概率数值用,隔开），然后分别用matlab实现香农码、费诺码和Huffman编码，并计算各个码的平均码长，编码效率，并用matlab图示出来（直方图）文本文件例如gailv.txt我测试的案例为0.40.20.10.10.150.05，存在gailv.txt这个文本文档中。用“loadgailv.txt”语句读入文本文档中的概率分布。（2）编码部分设计：香农编码：1、将概率序列按降序排序，为方便，还是记作p，在编程时调整一下就行。2、算累加概率B(i)=p(i-1)+B(i-1);,i=0..i-1，视B(0)=03、算码长C=-log2(p);N=ceil(C);[ceil函数为取不小于自变量的最小整数的函数]4、将pa(i)换成二进制表示，取小数前k(i)位为c(i)费诺编码：1、将概率序列排序，为方便，还是记作p，在编程时调整一下就行。72、按编码进制数将概率分组，尽量使每组的概率和接近。3、给每组分配一位码元（0，1，。。。）4、对每一组按同样地方法划分，直到每个符号有唯一码字。哈夫曼编码：可以用哈夫曼树的观点来看。1、选取概率最小的两个节点a，b2、将他们合并为c加入原概率序列3、从c指向a的边标为0，向b的边标为14、重复到仅有一棵树为止。5、每个符号的码字就是从根走到该符号的所有边上的码元连接起来。2.1.2源代码1、程序总程序（源文件见zong.m，文本文档见gailv.txt）%loadmydataA;%A是原始概率loadgailv.txt;A=gailv;[m,n]=size(A);%m为A的行数n为A的列数%香农码fori=1:nif(A(i)0)error('信源概率不能小于0');EndEndif((sum(A)-1)0.0001)error('信源概率之和必须为1');EndA=sort(A,2,'descend');%完成对A的降序排列8fori=1:nifi==1B(i)=0;elseB(i)=A(i-1)+B(i-1);%B是累加后概率endendC=-log2(A);%C是对A求log2N=ceil(C);%N是每一个码的长度m=max(max(N));INT=ones(n,m);fori=1:nforj=1:N(i)B(i)=2*B(i);ifB(i)1INT(i,j)=0;elseINT(i,j)=1;end9B(i)=rem(B(i),1);endend%求二进制并进行编码string='码字';ST=cell(1,n);fori=1:nforj=1:N(i)a=num2str(INT(i,j));ST(i)=strcat(ST(1,i),a);endendfprintf('\n信源概率为：\n');disp(A);fprintf('\n香农码为：\n');disp(ST);fprintf('\n香农平均码长为：\n');n_1=sum(N.*A);disp(n_1);10fprintf('\n香农编码效率为:\n');ha=sum(A.*(-log2(A)));t1=ha/n_1;disp(t1);%费诺码fori=1:nB(i,1)=A(i);%生成B的第1列enda=sum(B(:,1))/2;fork=1:n-1ifabs(sum(B(1:k,1))-a)=abs(sum(B(1:k+1,1))-a)break;endendfori=1:n%生成B第2列的元素ifi=kB(i,2)=0;else11B(i,2)=1;endend%生成第一次编码的结果FN=B(:,2);FN=sym(FN);%生成第3列及以后几列的各元素j=3;while(j~=0)p=1;while(p=n)x=B(p,j-1);forq=p:nifx==-1break;elseifB(q,j-1)==xy=1;continue;else12y=0;break;endendendify==1q=q+1;endifq==p|q-p==1B(p,j)=-1;elseifq-p==2B(p,j)=0;FN(p)=[char(FN(p)),'0'];B(q-1,j)=1;FN(q-1)=[char(FN(q-1)),'1'];elsea=sum(B(p:q-1,1))/2;fork=p:q-2ifabs(sum(B(p:k,1))-a)=abs(sum(B(p:k+1,1))-a);13break;endendfori=p:q-1ifi=kB(i,j)=0;FN(i)=[char(FN(i)),'0'];elseB(i,j)=1;FN(i)=[char(FN(i)),'1'];endendendendp=q;endC=B(:,j);D=find(C==-1);[e,f]=size(D);14ife==nj=0;elsej=j+1;endendfori=1:n[u,v]=size(char(FN(i)));lon(i)=v;endlonl=sum(A.*lon);fprintf('\n信源概率为：\n');disp(A);fprintf('\n费诺码为：\n');disp(FN);fprintf('\n费诺编码效率为:\n');15ha=sum(A.*(-log2(A)));t2=ha/l;disp(t2);fprintf('\n费诺码平均码长为：\n');n_2=sum(lon)/n;disp(n_2);%HuffmanQ=A;%建立索引矩阵IndexIndex=zeros(n-1,n);%初始化Indexfori=1:n-1[Q,L]=sort(Q);Index(i,:)=[L(1:n-i+1),zeros(1,i-1)];G(i,:)=Q;Q=[Q(1)+Q(2),Q(3:n),1];%将概率最小的两个元素相加end16fori=1:n-1%进行回溯Char(i,:)=blanks(n*n);end%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码Char(n-1,n)='0';%G中的N-1行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置Char(n-1,2*n)='1';%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置%以下从G的倒数第二行开始向前编码fori=2:n-1Char(n-i,1:n-1)=Char(n-i+1,n*(find(Index(n-i+1,:)==1))-(n-2):n*(find(Index(n-i+1,:)==1)));%将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置Char(n-i,n)='0';%然后在当前行的第一个编码位置末尾填入'0'Char(n-i,n+1:2*n-1)=Char(n-i,1:n-1);%将G后一行中索引为1的编码码字填入到当前行的第二个编码位置Char(n-i,2*n)='1';%然后在当前行的第二个编码位置末尾填入'1'forj=1:i-1%内循环作用：将Index后一行中索引不为1处的编码按照左右顺序填入当前行的第3个位置开始的地方,最后计算到Index的首行为止17Char(n-i,(j+1)*n+1:(j+2)*n)=Char(n-i+1,n*(find(Index(n-i+1,:)==j+1)-1)+1:n*find(Index(n-i+1,:)==j+1));endend%Char中第一行的编码结果就是所需的Huffman编码输出，通过Index中第一行索引将编码对应到相应概率的信源符号上。fori=1:nresult(i,1:n)=Char(1,n*(find(Index(1,:)==i)-1)+1:find(Index(1,:)==i)*n);lon(i)=length(find(abs(result(i,:))~=32));%求每个码的长度endl=sum(A.*lon);fprintf('\n信源概率为：\n');disp(A);fprintf('\n哈夫曼码为:\n');disp(result);fprintf('\n哈夫曼平均码长为：\n');n_3=sum(lon.*A);disp(n_3);18fprintf('\n哈夫曼编码效率为:\n');t3=ha/n_3;disp(t3);x=[1,2,3];y=[t1,t2,t3];z=[n_1,n_2,n_3];figure(1);subplot(1,2,1);bar(x,y,'m');xlabel('香农码费诺码哈夫曼码');title('编码效率');holdoff;gridsubplot(1,2,2);bar(x,z,'b');xlabel('香农码费诺码哈夫曼码');title('平均码长