信息论与编码实验报告.doc

中南大学信息论与编码实验报告2实验名称： 关于编码的实验 班 级： 电子信息xxxx班 学 号： xxxxxxxx 姓 名： xxxx 指导老师： xxxx 实验一 关于编码的实验 一、 实验目的 1. 掌握香农码和 Huffman 编码原理和过程。2. 熟悉matlab软件的基本操作，练习使用matlab实现香农码和 Huffman 编码。3. 熟悉 C/C+语言，练习使用 C/C+实现香农码和 Huffman 编码。4. 应用 Huffman 编码实现文件的压缩和解压缩。二、实验原理 香农码：（1）将信源发出的N个消息符号按其概率的递减次序排列（2）按下式计算第个消息的二进制代码组的码长,并取整 （3）计算第个消息的累加概率(为小数)（4）将累加概率变换成二进制数（5）去掉小数点,并根据取小数点后的前几位为对应的代码组。霍夫曼（Huffman）编码：属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。三、 实验内容 1、 使用matlab实现香农码和Huffman编码，并自己设计测试案例。2、 使用CC+实现香农码和Huffman编码，并自己设计测试案例。3、 可以用任何开发工具和开发语言，尝试实现Huffman编码应用在数据文件的压缩和解压过程中，并自己设计测试方案。四、 程序设计与算法描述（1）香农码matlab程序：clear all;N=input(N=); %输入信源符号的个数s=0;l=0;H=0;for i=1:N p(i)=input(p=);%输入信源符号概率分布矢量,p(i)0, error(不符合概率分布)end for i=1:N-1 for j=i+1:N if p(i)p(j) m=p(j); p(j)=p(i); p(i)=m; end endend %按概率分布大小对信源排序for i=1:N a=-log2(p(i); if mod(a,1)=0 w=a; else w=fix(a+1); end%计算各信源符号的码长 l=l+p(i)*w; %计算平均码长end l=l;n=H/l; %计算编码效率P(1)=0for i=2:N P(i)=0; for j=1:i-1 P(i)=P(i)+p(j); endend %计算累加概率for i=1:N for j=1:w W(i,j)=fix(P(i)*2); P(i)=P(i)*2-fix(P(i)*2); endend %将累加概率转化为L(i)位二进制码字disp(W) %显示码字disp(l)% 显示平均码长disp(n) %显示编码效率运行结果：（2）Huffman编码matlab程序：clear all;I=input(please input a string:); %提示输入界面len=length(I);t=2;biaozhi=0;b(1)=I(1);for i=2:len for j=1:i-1 if I(j)=I(i) biaozhi=1; break; end end if biaozhi=0 b(t)=I(i); t=t+1; end biaozhi=0;endfprintf(信源总长度:n);disp(len); %信源总长度fprintf(字符:n);disp(b );L=length(b);for i=1:L a=0; for j=1:len if b(i)=I(j) a=a+1; count(i)=a; end endendcount=count/len;%各字符概率fprintf(各字符概率:n);disp(count);p=count;%s=0;l=0;H=0;N=length(p);for i=1:N H=H+(- p(i)*log2(p(i);%计算信源信息熵endfprintf(信源信息熵:n);disp(H);tic;for i=1:N-1 %按概率分布大小对信源排序 for j=i+1:N if p(i)p(j) m=p(j); p(j)=p(i); p(i)=m; end endendQ=p;m=zeros(N-1,N);for i=1:N-1 %循环缩减对概率值排序，画出由每个信源符号概率到1.0 处的路径， Q,l=sort(Q); m(i,:)=l(1:N-i+1),zeros(1,i-1); Q=Q(1)+Q(2),Q(3:N),1;endfor i=1:N-1 c(i,:)=blanks(N*N); end c(N-1,N)=0; c(N-1,2*N)=1;for i=2: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-1 c(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:N h(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) %输出编码效率fprintf(计算耗时time= %fn,toc);实验结果：（3）香农码C语言程序：#include #include #include #define max_CL 10 /*maxsize of length of code*/#define max_PN 6 /*输入序列的个数*/typedef float datatype;typedef struct SHNODE datatype pb; /*第i个消息符号出现的概率*/ datatype p_sum; /*第i个消息符号累加概率*/ int kl; /*第i个消息符号对应的码长*/ int codemax_CL; /*第i个消息符号的码字*/ struct SHNODE *next; shnolist;datatype sym_arrymax_PN; /*序列的概率*/void pb_scan(); /*得到序列概率*/void pb_sort(); /*序列概率排序*/void valuelist(shnolist *L); /*计算累加概率，码长，码字*/void codedisp(shnolist *L); void pb_scan() int i; datatype sum=0; printf(input %d possible!n,max_PN); for(i=0;i); scanf(%f,&sym_arryi); sum=sum+sym_arryi; /*判断序列的概率之和是否等于1，在实现这块模块时，scanf()对float数的缺陷，故只要满足0.99sum1.0001|sum0.99) printf(sum=%f,sum must (0.999sum1.0001),sum); pb_scan(); /*选择法排序*/void pb_sort() int i,j,pos; datatype max; for(i=0;imax_PN-1;i+) max=sym_arryi; pos=i; for(j=i+1;jmax) max=sym_arryj; pos=j; sym_arrypos=sym_arryi; sym_arryi=max; void codedisp(shnolist *L) int i,j; shnolist *p; datatype hx=0,KL=0; /*hx存放序列的熵的结果，KL存放序列编码后的平均码字的结果*/ p=L-next; printf(numtgailvtsumt-lb(p(ai)tlenthtcoden); printf(n); for(i=0;ipb,p-p_sum,-3.332*log10(p-pb),p-kl); j=0; for(j=0;jkl;j+) printf(%d,p-codej); printf(n); hx=hx-p-pb*3.332*log10(p-pb); /*计算消息序列的熵*/ KL=KL+p-kl*p-pb; /*计算平均码字*/ p=p-next; printf(H(x)=%ftKL=%fnR=%fbit/code,hx,KL,hx/KL); /*计算编码效率*/shnolist *setnull() shnolist *head; head=(shnolist *)malloc(sizeof(shnolist); head-next=NULL; return(head);shnolist *my_creat(datatype a,int n) shnolist *head,*p,*r; int i; head=setnull(); r=head; for(i=0;ipb=ai; p-next=NULL; r-next=p; r=p; return(head);void valuelist(shnolist *L) shnolist *head,*p; int j=0; int i; datatype temp,s; head=L; p=head-next; temp=0; while(jp_sum=temp; temp=temp+p-pb; p-kl=-3.322*log10(p-pb)+1;/*编码，*/ s=p-p_sum; for(i=0;ikl;i+) p-codei=0; for(i=0;ikl;i+) p-codei=2*s; if(2*s=1) s=2*s-1; else if(2*s=0) break; else s=2*s; j+; p=p-next; int main(void) shnolist *head; pb_scan(); pb_sort(); head=my_creat(sym_arry,max_PN); valuelist(head); codedisp(head);运行结果：（4）Huffman编码C语言程序：#include#include#include#include#include#define MAXVALUE 10000 /*权值最大值*/#define MAXLEAF 30 /*叶子最多个数*/#define MAXNODE MAXLEAF*2-1 /* 结点数的个数*/#define MAXBIT 50 /*编码的最大位数*/typedef struct node /*结点类型定义*/ char letter; int weight; int parent; int lchild; int rchild;HNodeType;typedef struct /*编码类型定义*/ char letter; int bitMAXBIT; int start;HCodeType;typedef struct /*输入符号的类型*/ char s; int num;lable;void HuffmanTree(HNodeType HuffNode,int n,lable a) int i,j,m1,m2,x1,x2,temp1; char temp2; for (i=0;i2*n-1;i+) /*结点初始化*/ HuffNodei.letter=0; HuffNodei.weight=0; HuffNodei.parent=-1; HuffNodei.lchild=-1; HuffNodei.rchild=-1; for (i=0;in-1;i+) for (j=i+1;jai.num) temp1=ai.num; ai.num=aj.num; aj.num=temp1; temp2=ai.s; ai.s=aj.s; aj.s=temp2; for (i=0;in;i+) HuffNodei.weight=ai.num; HuffNodei.letter=ai.s; for (i=0;in-1;i+) /*构造huffman树*/ m1=m2=MAXVALUE; x1=x2=0; for (j=0;jn+i;j+)/*寻找权值最小与次小的结点*/ if (HuffNodej.parent=-1&HuffNodej.weightm1) m2=m1; x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.parent=-1&HuffNodej.weightm2) m2=HuffNodej.weight; x2=j; HuffNodex1.parent=n+i; HuffNodex2.parent=n+i; /*权值最小与次小的结点进行组合*/ HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight; HuffNoden+i.lchild=x1; HuffNoden+i.rchild=x2; void HuffmanCode(int n,lable a) HNodeType HuffNodeMAXNODE; HCodeType HuffCodeMAXLEAF,cd; int i,j,c,p; HuffmanTree(HuffNode,n,a); for (i=0;in;i+) /*按结点位置进行编码*/ cd.start=n-1; c=i; p=HuffNodec.parent; while (p!=-1) if (HuffNodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=HuffNodec.parent; for (j=cd.start+1;jn;j+) /*储存编码*/ HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start; for (i=0;in;i+) HuffCodei.letter=HuffNodei.letter; printf( %c ,HuffCodei.letter); for (j=HuffCodei.start+1;jn;j+) printf(%d,HuffCodei.bitj); printf(n); int main() lable data30; char s100,*p; i