香农编码

香农编码基于C语言上的实现摘要编码是指为了达到某种目的而对信号进行的一种变换。根据编码的目的不同，编码理论有三个分支：①信源编码。对信源输出的信号进行变换，包括连续信号的离散化，即将模拟信号通过采样和量化变成数字信号,以及对数据进行压缩,提高数字信号传输的有效性而进行的编码。②信道编码。对信源编码器输出的信号进行再变换，包括区分通路、适应信道条件和提高通信可靠性而进行的编码。③保密编码。对信道编码器输出的信号进行再变换，即为了使信息在传输过程中不易被人窃取而进行的编码。编码理论在数字化遥测遥控系统、电气通信、数字通信、图像通信、卫星通信、深空通信、计算技术、数据处理、图像处理、自动控制、人工智能和模式识别等方面都有广泛的应用。其中信源编码又分为三种，包括香农编码、哈夫曼编码和算术编码。本文主要介绍香农编码。关键词：累加概率、排序、熵、码长、编码效率第1章前言1948年，美国科学家香农（Shannon）发表了一篇题为“通信的数学理论”的学术论文，这篇划时代论文的问世，宣告了信息论的诞生。信息论的研究领域从自然科学扩展到经济、管理科学甚至人文社会科学，从狭义信息论发展到如今的广义信息论，成为涉及面极广的信息科学。1951年美国电信工程师D.A.霍夫曼提出更有效的霍夫曼编码。此后又出现了传真编码、图像编码和话音编码，对数据压缩进行了深入的研究，解决了数字通信中提出的许多实际问题。在信源编码方面，1951年香农证明，当信源输出有冗余的消息时可通过编码改变信源的输出，使信息传输速率接近信道容量。1948年香农就提出能使信源与信道匹配的香农编码。编码分为信源编码与信道编码，其中信源编码又分为无失真和限失真。由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。信源编码的基本途径有两个，一是解除相关性；二是概率均匀化。信源编码的编码定理有两个，无失真编码定理和限失真编码定理。信源编码定理出现后，编码方法就趋于合理化。其中以香浓码、费诺码和哈夫曼码为无失真编码的最佳码。[1]第2章香农编码原理2.1信源编码原理信源编码就是从信源符号到码符号的一种映射f，它把信源输出的符号ui变换成码元序列wi。f：ui——wi，i=1，2，…，q信源编码定义如图2.1：凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可以称为最佳码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳码的编码方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。[2]2.2香农编码原理香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度Ki满足下式X{x1，…，xR}W{w1,w2,…,wK}U{u1,u2,…,uL}信源编码器图2.1信源编码器I(xi)≤K﹤I(xi)+1,i就可以得到这种码。这种编码方法就是香农编码。2.3编码步骤香农编码法冗余度稍大，实用性不大，但有重要的理论意义。编码步骤如下：（1）将信源消息符号按其出现的概率大小依次排列p（x1）≥p（x2）≥…≥p（xn）（2）确定满足下列不等式整数码长Ki：-log2p(xi)≤Ki＜-log2p(xi)+1（3）为了编成唯一可译码，计算第i个消息的累加概率Pi=11ikp(xk)（4）将累加概率Pi变成二进制数。（5）取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字。第3章香农编码的算法介绍3.1C语言算法介绍C语言是目前世界上流行,使用最广泛的高级程序设计语言。C是结构式语言，结构式语言的显著特点是代码及数据的分隔化,即程序的各个部分除了必要的信息交流外彼此独立.这种结构化方式可使程序层次清晰,便于使用,维护以及调试.C语言是以函数形式提供给用户的,这些函数可方便的调用,并具有多种循环,条件语句控制程序流向,从而使程序完全结构化.[3]实验目的编写一个可以实现对一组概率进行香农编码的程序。实验环境VC++6.0实验内容编写一个程序，对给定的一组概率进行香农编码，并写入文件。源程序：===================================#includestdio.h#includemath.h#includestdlib.h#defineN7main(){inti,j;//doublep[7]={0,0.25,0.25,0.2,0.15,0.1,0.05};//原始数组doublep[N]={0},temp;doubleq[N]={0};//概率数组intKL[N];//码字长度数组doublek[N]={0},l[N]={0};//求码字长度的中间数组inta[N][N]={0,};//二进制存储数组FILE*fp,*fp1;if((fp=fopen(in.dat,r+))==NULL){printf(不能打开文件！\n);exit(1);}if(!(fp1=fopen(out.dat,w))){printf(不能打开文件！\n);exit(1);}//读取文件中的数据，并保存为数组p[i]for(i=1;iN;i++)fscanf(fp,%lf,&p[i]);printf(从文件中读取的概率为：\n);fprintf(fp1,从文件中读取的概率为：\n);//输出读取的概率for(i=0;iN;i++){printf(p[%d]=,i);fprintf(fp1,p[%d]=,i);printf(%lf,p[i]);fprintf(fp1,%lf,p[i]);printf(\n);fprintf(fp1,\n);}printf(\n);fprintf(fp1,\n);//将概率进行排序操作for(i=1;iN;i++){for(j=i+1;jN;j++){if(p[i]p[j]){temp=p[i];p[i]=p[j];p[j]=temp;}}}//输出排序后的数组printf(排序后的概率为：\n);fprintf(fp1,排序后的概率为：\n);for(i=0;iN;i++){printf(p[%d]=,i);fprintf(fp1,p[%d]=,i);printf(%lf,p[i]);fprintf(fp1,%lf,p[i]);printf(\n);fprintf(fp1,\n);}printf(\n);fprintf(fp1,\n);//求累加概率for(i=0;iN;i++){j=i+1;q[j]=q[i]+p[i];}//输出累加概率数组printf(累加概率为：\n);fprintf(fp1,累加概率为：\n);for(i=1;iN;i++){printf(q[%d]=%lf\n,i,q[i]);fprintf(fp1,q[%d]=%lf\n,i,q[i]);}//求码字长度for(i=0,j=0;iN;i++,j++){k[j]=-log(p[i])/log(2);l[j]=1-log(p[i])/log(2);if(l[j](int)(k[j]+1))KL[j]=l[j];elseKL[j]=k[j];}//输出码字长度printf(码字长度为：\n);fprintf(fp1,码字长度为：\n);for(i=1;iN;i++){printf(KL[%d]=%d,i,KL[i]);fprintf(fp1,KL[%d]=%d,i,KL[i]);printf(\n);fprintf(fp1,\n);}//求累加概率的二进制形式，即码字for(i=1;iN;i++){for(j=1;j=KL[i]+1;j++){q[i]=q[i]*2;if(q[i]=1){q[i]=q[i]-1;a[i][j]=1;}elsea[i][j]=0;}}//输出码字printf(码字为：);fprintf(fp1,码字为：);for(i=0;iN;i++){for(j=1;jKL[i]+1;j++){printf(%d,a[i][j]);fprintf(fp1,%d,a[i][j]);}if(i){printf((0.);fprintf(fp1,(0.);}for(j=1;jKL[i]+1;j++){printf(%d,a[i][j]);fprintf(fp1,%d,a[i][j]);}if(i){printf()2);fprintf(fp1,)2);}printf(\n);fprintf(fp1,\n);}}