中南大学信息论及编码实验2实验报告.doc

中 南 大 学 -信息论与编码题 目 关于编码的实验 学生姓名 指导教师 学 院 信息科学与工程学院 学 号 专业班级 2015年12月目 录一、 实验目的3二、实验原理3三、实验内容5四、实验要求5五、代码调试结果6六、实验代码8一、实验目的1. 掌握香农码和 Huffman 编码原理和过程。2. 熟悉 matlab 软件的基本操作，练习使用matlab 实现香农码和Huffman编码。3. 熟悉 C/C+语言，练习使用C/C+实现香农码和Huffman 编码。4. 应用 Huffman 编码实现文件的压缩和解压缩。二、 实验原理 香农编码：香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度Ki满足下式 I(xi)KI(xi)+1, 就可以得到这种码。这种编码方法就是香农编码。香农第一定理：设离散无记忆信源为S P=s1 s2 .sq p(s1) p(s2) .p(sq) 熵为H(S)，其N 次扩展信源为熵为H(SN)。码符号集X=（x1,x2,xr）。先对信源S N 进行编码，总可以找到一种编码方法，构成惟一可以码，使S 中每个信源符号所需的平均码长满足：当N时L 是平均码长 是ai 对应的码字长度哈夫曼编码：要完成哈夫曼的编码和解码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码和解码。首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2*N-1就为最终根节点）为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。对于哈夫曼编码树来说，由于哈夫曼编码是前缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。建立哈夫曼编码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码0，如果当前节点为右子则对其编码1。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。对于码值的逆向存储可以使用栈结构，先将一个码的每一步编码存入栈，再在一个码结束后出栈至空。当然也可以定义一个字符型数组，将值从后向前存入数组，再将数组有值部分粘贴到新的数组中进行存储。本次采用了后者，因为个人认为为此一步操作建立栈结构不划算，而且前一个设计也已经熟练掌握了栈的方法，此处进行新的尝试会更好。对文件进行编码。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件打开，将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。对文件进行解码。先打开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是0的时候，则索引走向左子节点；当是1的时候，则走向右子节点。以此类推，一直走到叶子节点为止，则当前叶子节点所代表的字符即为前一段密文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕，并将解码结果存入到新的解码文件当中。在解码之前，还应该先确认之前是否建立了哈夫曼树并且是否构建了编码表。不过由于本次将a到z都进行了编码，所以此步省略了，因为编码表是唯一的。需要的时候可以在Encoder 函数中先进行判定。将编码和解码写在了一起，可以在运行时进行选择调用。三、实验内容1.使用matlab 实现香农码和Huffman 编码，并自己设计测试案例。2.使用CC+实现香农码和Huffman 编码，并自己设计测试案例。3.可以用任何开发工具和开发语言，尝试实现Huffman 编码应用在数据文件的压缩和解压缩中，并自己设计测试案例。四、实验要求1. 提前预习实验，认真阅读实验原理以及相应的参考书。2. 认真高效的完成实验，实验中服从实验室管理人员以及实验指导老师的管理。3. 认真撰写实验报告，内容可以自己编排，可以考虑包括以下一些方面：原理概述、程序设计与算法描述、源程序及注释（程序太长可以只选取重要部分）、运行输出结果实例、调试和运行程序过程中产生的问题及采取的措施、对实验的讨论分析、总结。五、代码调试结果香农编码:哈夫曼编码：C语言之香农编码：C语言之哈夫曼编码：六、实验代码Matlab实现香农编码：clear;A=input('please input a number:') %提示输入界面A=fliplr(sort(A);%降序排列m,n=size(A);for i=1:n B(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(B(:,1)/2;for k=1:n-1 if abs(sum(B(1:k,1)-a)<=abs(sum(B(1:k+1,1)-a) break; endendfor i=1:n%生成B第2列的元素 if i<=k B(i,2)=0; else B(i,2)=1; endend%生成第一次编码的结果END=B(:,2)'END=sym(END);%生成第3列及以后几列的各元素j=3;while (j=0) p=1; while(p<=n) x=B(p,j-1); for q=p:n if x=-1 break; else if B(q,j-1)=x y=1; continue; else y=0; break; end end end if y=1 q=q+1; end if q=p|q-p=1 B(p,j)=-1; else if q-p=2 B(p,j)=0; END(p)=char(END(p),'0' B(q-1,j)=1; END(q-1)=char(END(q-1),'1' else a=sum(B(p:q-1,1)/2; for k=p:q-2 if abs(sum(B(p:k,1)-a)<=abs(sum(B(p:k+1,1)-a); break; end end for i=p:q-1 if i<=k B(i,j)=0; END(i)=char(END(i),'0' else B(i,j)=1; END(i)=char(END(i),'1' end end end end p=q; end C=B(:,j); D=find(C=-1); e,f=size(D); if e=n j=0; else j=j+1; endendBAENDfor i=1:n u,v=size(char(END(i); L(i)=v;endavlen=sum(L.*A)哈夫曼编码：p=input('please input a number:') %提示输入界面 n=length(p); for i=1:n if p(i)<0 fprintf('n The probabilities in huffman can not less than 0!n'); p=input('please input a number:') %如果输入的概率数组中有小于0 的值，则重新输入概率数组 endendif abs(sum(p)-1)>0 fprintf('n The sum of the probabilities in huffman can more than 1!n'); p=input('please input a number:') %如果输入的概率数组总和大于1，则重新输入概率数组 endq=p; a=zeros(n-1,n); %生成一个n-1 行n 列的数组 for i=1:n-1 q,l=sort(q); %对概率数组q 进行从小至大的排序，并且用l 数组返回一个数组，该数组表示概率数组q 排序前的顺序编号 a(i,:)=l(1:n-i+1),zeros(1,i-1); %由数组l 构建一个矩阵，该矩阵表明概率合并时的顺序，用于后面的编码 q=q(1)+q(2),q(3:n),1; %将排序后的概率数组q 的前两项，即概率最小的两个数加和，得到新的一组概率序列 endfor i=1:n-1 c(i,1:n*n)=blanks(n*n); %生成一个n-1 行n 列，并且每个元素的的长度为n 的空白数组，c 矩阵用于进行huffman 编码，并且在编码中与a 矩阵有一定的对应关系 endc(n-1,n)='0' %由于a 矩阵的第n-1 行的前两个元素为进行huffman 编码加和运算时所得的最 c(n-1,2*n)='1' %后两个概率，因此其值为0 或1，在编码时设第n-1 行的第一个空白字符为0，第二个空白字符1。 for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)=1)-(n-2):n*(find(a(n-i+1,:)=1); %矩阵c 的第n-i 的第一个元素的n-1 的字符赋值为对应于a 矩阵中第n-i+1 行中值为1 的位置在c 矩阵中的编码值 c(n-i,n)='0' %根据之前的规则，在分支的第一个元素最后补0 c(n-i,n+1:2*n-1)=c(n-i,1:n-1); %矩阵c 的第n-i 的第二个元素的n-1 的字符与第n-i 行的第一个元素的前n-1 个符号相同，因为其根节点相同 c(n-i,2*n)='1' %根据之前的规则，在分支的第一个元素最后补1 for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)=j+1)-1)+1:n*find(a(n-i+1,:)=j+1); %矩阵c 中第n-i 行第j+1 列的值等于对应于a 矩阵中第n-i+1 行中值为j+1 的前面一个元素的位置在c 矩阵中的编码值 endend %完成huffman 码字的分配 for i=1:n h(i,1:n)=c(1,n*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n); %用h 表示最后的huffman 编码，矩阵h的第i 行的元素对应于矩阵c 的第一行的第i 个元素 ll(i)=length(find(abs(h(i,:)=32); %计算每一个huffman 编码的长度 enddisp('二元Huffman编码平均码长') l=sum(p.*ll); %计算平均码长 disp(l)%fprintf('n huffman code:n'); h disp('信源熵') hh=-sum(p.*log2(p) %计算信源熵 %fprintf('n the huffman effciency:n'); disp('编码效率') t=hh/l %计算编码效率C语言实现香农编码：#include<iostream.h>#include<math.h>#include<iomanip.h>#include<stdlib.h>class Tpublic: T() T(); void Create(); void Coutpxj(); void Coutk(); void Coutz(); void Print();protected: int n; double *p; double *pxj; int *k; double *mz;void T:Create() cout<<"输入信源符号个数:" cin>>n; p=new doublen; cout<<"请输入这几个"<<n<<"概率:n" int i; for(i=0;i<n;i+) cin>>pi; pxj=new doublen; k=new intn; mz=new doublen; double sum=0.0; for(i=0;i<n;i+) sum+=pi; if(sum!=1.0) throw 1; else for(i=0;i<n;i+) int k=i; for(int j=i+1;j<n;j+) if(pk<pj) k=j; double m=pi; pi=pk; pk=m;T:T() delete p; delete pxj; delete k; delete mz;void T:Coutpxj() pxj0=0; for(int i=1;i<n;i+) pxji=0; for(int j=0;j<i;j+) pxji+=pj;void T:Coutk() for(int i=0;i<n;i+) double d=(-1)*(log(pi)/log(2); if(d-(int)d>0) ki=(int)d+1; else ki=(int)d;void T:Print() cout<<"Xi"<<setw(8)<<"P(xi)" <<setw(8)<<"Pa(xj)" <<setw(8)<<"Ki" <<setw(8)<<"码字" <<endl; int i; for(i=0;i<n;i+) cout<<"X"<<i+1 <<setw(8)<<setprecision(2)<<pi <<setw(8)<<setprecision(2)<<pxji <<setw(8)<<ki<<" " mzi=pxji; for(int j=0;j<ki;j+) if(2*mzi-1>=0) cout<<1; mzi=2*mzi-1; else cout<<0; mzi=2*mzi; cout<<endl; double K=0.0,H=0.0,Y; for(i=0;i<n;i+) K+=(double)pi*ki; H+=(-1)*pi*(log10(pi)/log10(2.0); Y=H/K; cout<<"平均码长:"<<K<<endl; cout<<"信源熵:"<<H<<endl; cout<<"编码效率:"<<Y<<endl;void main() T t;int e; try t.Create(); t.Coutpxj(); t.Coutk(); t.Print(); catch(int e) if(e=1) cout<<"输入错误，请重新运行"哈夫曼编码：#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXLEN 100typedef struct int weight; int lchild; int rchild; int parent; char key;htnode;typedef htnode hfmtMAXLEN;int n;void inithfmt(hfmt t)/对结构体进行初始化 int i; printf("n"); printf("-n"); printf("*输入区*n"); printf("n请输入n="); scanf("%d",&n); getchar(); for(i=0;i<2*n-1;i+)/对结构体进行初始化 ti.weight=0; ti.lchild=-1; ti.rchild=-1; ti.parent=-1; printf("n");void inputweight(hfmt t)/输入函数 int w;/w表示权值 int i; char k;/k表示获取的字符 for(i=0;i<n;i+) printf("请输入第%d个字符:",i+1); scanf("%c",&k); getchar(); ti.key=k; printf("请输入第%d个字符的权值:",i+1); scanf("%d",&w); getchar(); ti.weight=w; printf("n");void selectmin(hfmt t,int i,int *p1,int *p2)/选中两个权值最小的函数 long min1=999999; long min2=999999; int j; for(j=0;j<=i;j+)/选择最小权值字符的下标返回 if(tj.parent=-1) if(min1>tj.weight) min1=tj.weight; *p1=j; for(j=0;j<=i;j+)/选择次小权值字符的下标还回 if(tj.parent=-1) if(min2>tj.weight && j!=(*p1)/注意 j!=(*p1) min2=tj.weight; *p2=j;void creathfmt(hfmt t)/创建哈夫曼树的函数 int i,p1,p2; inithfmt(t); inputweight(t); for(i=n;i<2*n-1;i+) selectmin(t,i-1,&p1,&p2); tp1.parent=i; tp2.parent=i; ti.lchild=p1; ti.rchild=p2; ti.weight=tp1.weight+tp2.weight; void printhfmt(hfmt t)/打印哈夫曼树 int i; printf("-n"); printf("*哈夫曼编数结构:*n"); printf("tt权重t父母t左孩子t右孩子t字符t"); for(i=0;i<2*n-1;i+) printf("n"); printf("tt%dt%dt%dt%dt%c",ti.weight,ti.parent,ti.lchild,ti.rchild,ti.key); printf("n-n"); printf("nn"); void hfmtpath(hfmt t,int i,int j)/编码的重要哈夫曼树路径递归算法 int a,b; a=i; b=j=ti.parent; if(tj.parent!=-1) i=j; hfmtpath(t,i,j); if(tb.lchild=a) printf("0"); else printf("1");void phfmnode(hfmt t)/对字符进行初始编码 int i,j,a; printf("n-n"); printf("*哈夫曼编码*"); for(i=0;i<n;i+) j=0; printf("n"); printf("tt%ct",ti.key,ti.weight); hfmtpath(t,i,j); printf("n-n"); void encoding(hfmt t)/对用户输入的电文进行编码 char r1000;/用来存储输入的字符串 int i,j; printf("nn请输入需要编码的字符:"); gets(r); printf("编码结果为:"); for(j=0;rj!='0'j+) for(i=0;i<n;i+) if(rj=ti.key) hfmtpath(t,i,j); printf("n"); void decoding(hfmt t)/对用户输入的密文进行译码 char r100; int i,j,len; j=2*n-2;/j初始从树的根节点开始 printf("nn请输入需要译码的字符串:"); gets(r); len=strlen(r); printf("译码的结果是:"); for(i=0;i<len;i+) if(ri='0') j=tj.lchild; if(tj.lchild=-1) printf("%c",tj.key); j=2*n-2; else if(ri='1') j=tj.rchild; if(tj.rchild=-1) printf("%c",tj.key); j=2*n-2; printf("nn"); int main() int i,j; hfmt ht; char flag; printf(" |-|n"); printf(" |-电子信息1002-|n"); printf(" |*|n"); printf(" | 哈夫曼编码 |n"); printf(" |*|n"); printf(" |-|n"); creathfmt(ht); printhfmt(ht); phfmnode(ht); printf("n-n"); printf("*编码&&译码&&退出*"); printf("n【1】编码t【2】t译码t【0】退出"); printf("n您的选择："); flag=getchar(); getchar(); while(flag!='0') if(flag='1') encoding(ht); else if(flag='2') decoding(ht); else printf("您的输入有误，请重新输入。n"); printf("n*编码&&译码&&退出*"); printf("n【1】编码t【2】t译码t【0】退出"); printf("n您的选择："); flag=getchar(); getchar(); printf("nn-n"); printf("*欢迎使用哈夫曼编码系统*n"); printf("-n"); system("pause");