Shannon _Fano_ Elias编码的实现

云南大学数学与统计学院上机实践报告课程名称：信息论基础实验年级：2009级上机实践成绩：指导教师：xxx姓名：xxx上机实践名称：Shannon-Fano-Elias编码与Shannon编码学号：xxx上机实践日期：2012-5-15上机实践编号：No.2专业：xxxx上机实践时间：2学时一、实验目的1. 进一步熟悉Shannon-Fano-Elias编码算法2. 进一步熟悉Shannon编码算法3. 学习编码程序的调试二、实验内容1.编程实现Shannon-Fano-Elias编码算法2.编程实现Shannon编码算法三、实验环境Microsoft visual c++6.0和个人计算机四、实验结果1. Shannon-Fano-Elias编码算法的源代码：#include<stdio.h>#include<math.h>#define n 4void main(){int i,j,a,k,t,x[n],l[n],code[n][n]={0};float p[n],F[n],F1[n],F2[n],s,b,q;printf("输入一组数组符号：x[n]\n");for(i=0;i<n;i++)scanf("%d",&x[i]);printf("\n");printf("输入符号的相应概率：p[n]\n");for(i=0;i<n;i++)scanf("%f",&p[i]);printf("\n");a=x[0];for(i=0;i<n;i++){if(x[i]>=a){k=i;s=0;for(j=0;j<k;j++){s=s+p[j];}F[i-1]=s;a=x[k];}if(a==x[n-1]){F[n-1]=1.0;}}a=x[0];for(i=0;i<n;i++){if(a==x[0]){F1[0]=p[0]/2;}if(a<x[i]){k=i;s=0;for(j=0;j<k;j++){s=s+p[j];}F1[i]=s+p[i]/2;a=x[k];}}for(i=0;i<n;i++){s=0;k=10;q=F1[i];code[i][j]=0;for(t=0,j=0;t<10;t++){if(q!=0){a=(int)(q*2);code[i][j]=a;b=(float)a/k;s=s+b;q=q*2-a;k=k*10;j++;}}F2[i]=s;}for(i=0;i<n;i++){q=log(1/p[i])/log(2)+1;l[i]=(int)(log(1/p[i])/log(2)+1);if((q-l[i])>0){l[i]=l[i]+1;}}printf("输出l[n]:\n");for(i=0;i<n;i++)printf("%4d",l[i]);printf("\n");printf("x p(x) F(x) F1(x) F2(x) l(x) Codeword:\n");for(i=0;i<n;i++){printf("%-5d%-8.3f%-8.4f%-8.4f%-8.4f%4d ",x[i],p[i],F[i],F1[i],F2[i],l[i]);for(j=0;j<l[i];j++){printf("%d",code[i][j]);}printf("\n");}}2.香农编码源代码：#include<stdio.h>#include<math.h>#define n 6void main(){int i,j,t,x[n],L[n],code[n][n]={0};float p[n],Pa[n],l[n],q,max;printf("输入一组数组符号：x[n]\n");for(i=0;i<n;i++)scanf("%d",&x[i]);printf("\n");printf("输入符号的相应概率：p[n]\n");for(i=0;i<n;i++)scanf("%f",&p[i]);printf("\n");for(j=0;j<n-1;j++) /*排序*/{for(i=0;i<n-j;i++){if(p[i+1]>p[i]){max=p[i];p[i]=p[i+1];p[i+1]=max;t=x[i];x[i]=x[i+1];x[i+1]=t;}}}Pa[0]=0; /*累加*/ for(i=1;i<n;i++){Pa[i]=Pa[i-1]+p[i-1];}for(i=0;i<n;i++) /*码字长度*/{l[i]=log(1/p[i])/log(2);L[i]=(int)(log(1/p[i])/log(2));if(l[i]==L[i]){L[i]=(int)(log(1/p[i])/log(2));}else{L[i]=(int)(log(1/p[i])/log(2))+1;}}for(i=0;i<n;i++) /*编码*/{q=Pa[i];for(j=0;j<L[i];j++){q=q*2;if(q>1){code[i][j]=1;q=q-1;}else{code[i][j]=0;}}}printf("x p(x) P(x) l(x)=log(1/p(x)) 码字长L(x) Codeword:\n"); for(i=0;i<n;i++){printf("%-5d%-8.3f%-8.2f%-20.4f%-8d ",x[i],p[i],Pa[i],l[i],L[i]);for(j=0;j<l[i];j++){printf("%d",code[i][j]);}printf("\n");}}1. Shannon-Fano-Elias编码的结果如下：2.香农编码结果：五、实验总结：通过Shannon-Fano-Elias编码与Shannon编码可以知道，Shannon-Fano-Elias编码与Shannon编码类似，只是香农编码首先进行排序，然后按照其公式计算其码字。

elias编码原理
Elias编码原理是一种对正整数进行编码的统一编码，由Peter Elias发明。

适用于预先无法获知最大编码整数的情况，而且小整数出现频率高，大整数出现频率低的情况。

其编码原理是对任何正整数NUM，对INT（Log2（NUM））+1进行一元编码，后缀上NUM二进制串除去最高位的子串。

例如：5的编码为001，01。

Elias编码可以分为Elias Delta Coding和Elias Gamma Coding两种。

1、Elias Delta Coding原理是对任何正整数NUM，对INT（Log2（NUM））+1进行Delta编码，后缀上NUM二进制串除去最高位的子串。

2、Elias Gamma Coding原理是对任何正整数NUM，对INT（Log2（NUM））+1进行Gamma编码，后缀上NUM二进制串除去最高位的子串。

关于Elias编码的解码思路，首先需要计算出Elias编码的开始的0的个数n，然后根据n可以确定数字的长度，再根据长度就可以通过截取字符串的方式得到原始数字。

Elias编码是一种非常优秀的压缩算法，它可以将任何正整数转化为一个二进制字符串，并且当数字较大时，转化出来的字符串仍然比较短。

此外，它还可以根据数字的大小动态地调整压缩后的长度，使得压缩后的数据既简洁又易于理解。

因此，Elias编码在实际应用中具有广泛的应用价值。

实验报告课程名称：信息论与编码姓名：系：专业：年级：学号：指导教师：职称：年月日实验三 Shannon 编码一、实验目的1、熟悉离散信源的特点；2、学习仿真离散信源的方法3、学习离散信源平均信息量的计算方法4、熟悉 Matlab 编程二、实验原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、信源符号按概率从大到小排列；12.......n p p p ≥≥≥2、确定满足下列不等式的整数码长i K 为()()1i i i lb p K lb p -≤<-+3、为了编成唯一可译码，计算第i 个消息的累加概率：4、将累加概率i P 变换成二进制数；5、取i P 二进制数的小数点后i K 位即为该消息符号的二进制码字。

三、实验内容1、写出计算自信息量的Matlab 程序2、写出计算离散信源平均信息量的Matlab 程序。

3、将程序在计算机上仿真实现，验证程序的正确性并完成习题。

四、实验环境Microsoft Windows 7 Matlab 6.5五、编码程序计算如下信源进行香农编码，并计算编码效率：⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡01.01.015.017.018.019.02.06543210a a a a a a a P X MATLAB 程序：(1) a=[0.2 0.18 0.19 0.15 0.17 0.1 0.01]; k=length(a);y=0; for i=1:k-111()i i k k P p a -==∑for n=i+1:kif (a(i)<a(n))t=a(i);a(i)=a(n);a(n)=t;endendends=zeros(k,1);b=zeros(k,1);for m=1:ks(m)=y;y=y+a(m);b(m)=ceil(-log2(a(m)));z=zeros(b(m),1);x=s(m);p=b2d10(x);for r=1:b(m)z(r)=p(r);enddisp('Êä³ö½á¹ûΪ£º')disp('³öʸÅÂÊ'),disp(a(m))disp('ÇóºÍ½á¹û'),disp(s(m))disp('±àÂëλÊý'),disp(b(m))disp('×îÖÕ±àÂë'),disp(z')end(2) function y=b2d10(x)for i=1:8temp=x.*2;if(temp<1)y(i)=0;x=temp;elsex=temp-1;y(i)=1;endend(3) p=[0.2 0.19 0.18 0.17 0.15 0.1 0.01]; sum=0;sum1=0;for i=1:7a(i)=-log2(p(i));K(i)=ceil(a(i));R(i)=p(i)*K(i);sum=sum+R(i);c(i)=a(i)*p(i);sum1=sum1+c(i);endK1=sum;H=sum1;Y=H/K1;disp('ƽ¾ùÐÅÏ¢Á¿'),disp(H)disp('ƽ¾ùÂ볤'),disp(K1)disp('±àÂëЧÂÊ'),disp(Y)六、实验结果输出结果为：出事概率0.2000，求和结果0，编码位数3，最终编码000出事概率0.1900，求和结果0.2000，编码位数3，最终编码001出事概率0.1800，求和结果0.3900，编码位数3，最终编码011出事概率0.1700，求和结果0.5700，编码位数3，最终编码100出事概率0.1500，求和结果0.7400，编码位数3，最终编码101出事概率0.1000，求和结果0.8900，编码位数4，最终编码1110出事概率0.0100，求和结果0.9900，编码位数7，最终编码1111110编码效率：平均信息量2.6087平均码长3.1400编码效率0.8308七、实验总结通过本次的实验，掌握了Shannon编码的实验原理以及编码过程。

信息论基础Shannon-Fano-Elias编码与Shannon编码一、实验目的1. 进一步熟悉Shannon-Fano-Elias编码算法2. 进一步熟悉Shannon编码算法3. 学习编码程序的调试二、实验内容1.编程实现Shannon-Fano-Elias编码算法2.编程实现Shannon编码算法三、实验环境Microsoft visual c++6.0和个人计算机四、实验结果1.编程实现Shannon-Fano-Elias编码算法#include"iostream.h"#include<iomanip.h>#include"vector"#include"algorithm"#include"math.h"using namespace std;struct bitree{//定义结构用于存储编码结果的二叉树结构,在译码时用到char ch; //用于存储码符号char mz; //用于存储码字bitree * lchild;bitree * rchild;};struct data{//用于存储相关的信源符号以及其概率double p;char ch;vector<char> code;int ml;};bool sortspecial(data dt1,data dt2){//用于排序时用return dt1.p>dt2.p;}void print2(vector<char>vd){//用于打印译码结果for(int i=0;i<vd.size();i++)cout<<vd[i]<<" ";cout<<endl;}void read(vector <data> &vd){//用于读入相关的信源符号以及概率int n;while(true){cout<<"请输入信源符号数:";cin>>n;cout<<"请输入相应的信源符号及其概率:"<<endl;data dt;int i=0;while(i<n){cin>>dt.ch;cin>>dt.p;dt.ml=0;vd.push_back(dt);i++;}double sum=0;vector<data>::iterator pit;/* for(pit=vd.begin();pit!=vd.end();pit++){sum+=pit->p;}if(sum!=1){cout<<"你输入的概率不符合要求,请重新输入."<<endl;sum=0;continue;}*/sort(vd.begin(),vd.end(),sortspecial);break;}}void append(char ch1,char ch2,bitree *&bt){//用于再构造码字二叉树时向其中添加结点bitree * bit=new bitree;bit->ch=ch1;bit->mz=ch2;bit->lchild=NULL;bit->rchild=NULL;if(ch1=='0')bt->rchild=bit;else bt->lchild=bit;}void Creatmz1(vector<data>& vd,int begin1,int end1 ,double pn ,bitree *&bt) {//进行编码,用递归的方法进行编码int begin=begin1,end=end1;if(begin==end) return;else if(begin+1==end){return;}else if(begin+2==end){vd[begin].code.push_back('0');vd[begin].ml++;append('0',vd[begin].ch,bt);vd[end-1].code.push_back('1');vd[end-1].ml++;append('1',vd[end-1].ch,bt);return;}else{double sum0=0,sum1=0,sum2=0;do{sum1+=vd[begin].p;sum2=sum1+vd[begin+1].p;begin++;}while(fabs(sum1/pn-0.5)>fabs(sum2/pn-0.5));//用于找到上下两组码的分点使得其概率和近于相同for(int i=begin1;i<begin;i++){vd[i].code.push_back('0');vd[i].ml++;}if(begin1+1 == begin){append('0',vd[begin1].ch,bt);}else append('0','0',bt);for(int j=begin;j<=end1-1;j++){vd[j].code.push_back('1');vd[j].ml++;}if(begin+1 == end1){append('1',vd[begin].ch,bt);}else append('1','0',bt);Creatmz1(vd,begin1 ,begin,sum1,bt->rchild );//对分点前的进行编码Creatmz1(vd,begin ,end1,pn-sum1,bt->lchild);//对分点后的进行编码*/ }}void print1(vector<data> vd){//用于打印编码结果cout<<"xi"<<setw(8)<<"P(xi)"<<setw(8)<<"码长"<<setw(8)<<"码字"<<setw(8)<<endl;for(int i=0;i<vd.size();i++){cout<<vd[i].ch<<setw(8)<<vd[i].p<<setw(8)<<vd[i].ml<<setw(8);for(int j=0;j<vd[i].code.size();j++)cout<<vd[i].code[j];cout<<setw(8)<<endl;}}void clear(bitree * & bt){//对二叉树的动态存储空间进行释放if(bt!=NULL&&bt->lchild!=NULL)clear(bt->lchild);if(bt!=NULL&&bt->rchild!=NULL)clear(bt->rchild);delete bt;}bool des_code(vector <char> & vr,vector <char> vt,bitree *bt){//用二叉编码树进行解码if(bt==NULL){cout<<"码树不存在!!!"<<endl;return false;}int pit=0;bitree * mbt=bt;while ((mbt->lchild!=NULL||mbt->rchild!=NULL)||pit<vt.size()){if(mbt->lchild==NULL&&mbt->rchild==NULL&&mbt->mz!='0'){vr.push_back(mbt->mz);mbt=bt;}if(mbt->lchild!=NULL&& vt[pit]=='1'){mbt=mbt->lchild;pit++;}else if(mbt->rchild!=NULL&& vt[pit]=='0'){mbt=mbt->rchild;pit++;}else if(mbt->lchild!=NULL&&mbt->rchild!=NULL) break;}if(mbt->lchild!=NULL&&mbt->rchild!=NULL){cout<<"你输入的是一个错误的码序列,请较正后再输入."<<endl;return false;}else {vr.push_back(mbt->mz);return true;}}void read1(vector<char>& vd){//用于读入要解码的序列cout<<"请输要译码的序列(以'#'结束):"<<endl;char dt;int i=0;cin>>dt;while(dt!='#'){vd.push_back(dt);cin>>dt;}}void print_H_L_R(vector<data>vd){//用于计算并打印信息熵,平均码长,效率double H=0,L=0,R=0;for(int i=0;i<vd.size();i++){H+=vd[i].p*(log10(1/vd[i].p)/log10(2));L+=vd[i].p*(double)vd[i].ml;}R=H/L;cout<<"此码的信息熵(H)是:"<<H<<endl;cout<<"此码的平均码长(L)为:"<<L<<endl;cout<<"此码的效率(U)为:"<<R<<endl;}int main(){bitree * bt=new bitree;bt->ch = '#';bt->mz = '*';bt->lchild=NULL;bt->rchild=NULL;vector <data> vd;vector <char> vr;vector <char> vt;cout<<"************下面将对Fano编,译码的过程进行演示*************"<<endl;cout<<"__________________________________________________________"<<endl;cout<<endl;cout<<"************下面显示编码的过程及相关参数和结果************"<<endl;read(vd);if(vd.size()==1){vd[0].code.push_back('0');vd[0].ml++;append('0',vd[0].ch,bt);}cout<<endl;Creatmz1(vd,0,vd.size(),1,bt);cout<<"************** 编码结果**************"<<endl;print1(vd);print_H_L_R(vd);cout<<endl;cout<<"************ 下面将进行译码过程操作的演示************"<<endl;cout<<endl;read1(vt);if(des_code(vr,vt,bt))print2(vr);clear(bt);return 1;}2.编程实现Shannon编码算法#include<stdio.h>#include<string.h>#include<math.h>void main(){ FILE *fp1,*fp2;int i,j,q,n,c[100][100]={0},l[100]={0};float f[100]={0}, p[100]={0},x[100]={0};char ch1,ch2;fp1=fopen("in2.txt","r");fp2=fopen("out2.txt","w");for(q=0;q<2;q++){fscanf(fp1,"%d",&n);printf("%d\n",n);for(i=0;i<n;i++){fscanf(fp1,"%c%f",&ch1,&p[i]);printf("%f ",p[i]);}printf("\n");f[0]=0;for(i=1;i<n;i++){f[i]=f[i-1]+p[i-1];}for(i=0;i<n;i++){x[i]=1/p[i];l[i]=ceil((log(x[i])/log(2))) ;}for(i=0;i<n;i++)for(j=0;j<l[i];j++){c[i][j]=(int)(f[i]*2);f[i]=f[i]*2-c[i][j];}for(i=0;i<n;i++){ for(j=0;j<l[i];j++){printf("%d",c[i][j]);fprintf(fp2,"%d",c[i][j]);}printf("\n");fprintf(fp2,"\n");}fscanf(fp1,"%c",&ch2);}}五、实验总结1．遇到的问题、分析并的出方案（列出遇到的问题和解决办法，列出没有解决的问题）：Shannon-Fano-Elias编码算法和Shannon编码算法的程序不会编，在参考了大量文献后得出以上程序，调试过程很复杂，得出的最终结果不确定是正确的。

数字通信中的信源编码和信道编码摘要：如今社会已经步入信息时代，在各种信息技术中,信息的传输及通信起着支撑作用.而对于信息的传输，数字通信已经成为重要的手段。

本论文根据当今现代通信技术的发展，对信源编码和信道编码进行了概述性的介绍。

关键词：数字通信；通信系统;信源编码；信道编码Abstract：Now it is an information society。

In the all of information technologies，transmission and communication of information take an important effect。

For the transmission of information，Digital communication has been an important means。

In this thesis we will present an overview of source coding and channel coding depending on the development of today’s communica tion technologies.Key Words：digital communication; communication system; source coding; channel coding1.前言通常所谓的“编码”包括信源编码和信道编码。

编码是数字通信的必要手段。

使用数字信号进行传输有许多优点, 如不易受噪声干扰，容易进行各种复杂处理，便于存贮，易集成化等。

编码的目的就是为了优化通信系统.一般通信系统的性能指标主要是有效性和可靠性.所谓优化，就是使这些指标达到最佳。

除了经济性外，这些指标正是信息论研究的对象.按照不同的编码目的，编码可主要分为信源编码和信道编码。

在本文中对此做一个简单的介绍.2.数字通信系统通信的任务是由一整套技术设备和传输媒介所构成的总体—-通信系统来完成的.电子通信根据信道上传输信号的种类可分为模拟通信和数字通信.最简单的数字通信系统模型由信源、信道和信宿三个基本部分组成.实际的数字通信系统模型要比简单的数字通信系统模型复杂得多。

2009年5月第14卷第3期 西　安　邮　电　学　院　学　报JOURNAL OF XI ’AN UN IV ERSIT Y OF POST AND TEL ECOMMUN ICA TIONS May 2009Vol 114No 13收稿日期:2009-03-02作者简介:谢　勰(1981-),女,安徽安庆人,西安邮电学院信息与控制系助教。

关于Shannon 编码的若干注记谢　勰(西安邮电学院信息与控制系,陕西西安　710121)摘要:通过反例指出若干对Shannon 编码中关于舍入的误解,并利用区间二叉树给出Shannon 编码的简单证明。

提出了Shannon 编码成立的弱条件,它能保证Shannon 编码仍是前缀码。

关键词:Shannon 编码;区间二叉树;前缀码中图分类号:TN911.21 文献标识码:A 文章编号:1007-3264(2009)03-0058-03引言信息论起源于Shannon [1],Shannon 全面且深入地介绍了经典信息论的概念、定理和应用,其中最重要的是熵概念。

由熵的定义可得到合适的码长,并进而构造出性能较好的前缀码,即Shannon 编码[1]。

不过,Shannon 编码要求概率值按递减次序排列,还要对累积分布函数进行舍入。

鉴于其限制条件和具体操作步骤不够直观,无法显露出Shannon 编码为前缀码的本质原因,因此有必要对Shannon 编码给出直观的证明,还需要给出更为本质的限制条件。

1　若干对Shannon 编码的误解由于[1]仅对Shannon 编码作了相当简短的介绍与证明,容易引起误解。

虽然[2]是一本信息论领域的权威著作,但它对Shannon 编码的描述也存在一定的含糊性。

而[3]给出的方法更是完全错误的。

其根源在于[1-3]均未对舍入做出严格的表述,为此必须给出关于二进制小数舍入(R ound )的准确定义。

为方便起见,不妨记1/2l 的二进制小数形式为(0.1)l 。

shannon第三编码定理-回复什么是Shannon第三编码定理？Shannon第三编码定理是由美国数学家克劳德·E·香农于1948年提出的一项重要定理，也被称为数据压缩定理或信息论中的定理。

该定理阐述了在具有随机性的数据中，编码后的平均编码长度与数据的熵之间的关系。

香农第三编码定理的公式可以表示为：H(X) ≤L(X) < H(X) + 1其中，H(X)代表数据的熵，L(X)代表编码后数据的平均编码长度。

为什么需要数据压缩？数据压缩是信息技术中非常重要的一部分。

在我们日常的生活、工作和学习中，我们的电脑、手机等设备都需要存储和传输大量的数据。

然而，存储和传输大量的数据所需的时间、空间和成本都非常高昂。

因此，对数据进行压缩可以帮助我们节省存储空间、提高数据传输速度，并降低相关的成本。

此外，数据压缩在网络传输和存储过程中也起到了重要的作用。

尤其在互联网时代，我们需要轻松快捷地共享和传输各种类型的数据。

因此，数据压缩技术成为必不可少的工具。

如何理解Shannon第三编码定理？Shannon第三编码定理揭示了数据压缩的基本原理。

从定理中可以看出，任何具有随机性的数据都可以通过编码来减少存储空间和传输成本。

定理中的L(X)表示编码后数据的平均编码长度，而H(X)表示数据的熵，也就是数据中所包含的信息的量。

定理表明，编码后的平均编码长度L(X)必然大于等于数据的熵H(X)，但是小于熵加一。

也就是说，通过合理的编码方法，我们可以将数据的平均编码长度控制在非常接近熵的范围内，从而实现高效的压缩效果。

举例来说，假设我们有一个具有随机性的二进制数据，其中0和1的出现频率大致相等。

根据Shannon第三编码定理，我们可以将每个0和每个1分别编码为不等长的比特串，使得整个数据的平均编码长度尽可能接近熵。

这样就可以实现对原始数据的高效压缩。

Shannon第三编码定理的应用Shannon第三编码定理的应用非常广泛。