搜索
1实验报告书课程名称：信息论与编码实验实验名称：算术编解码2一、实验内容借助C++编程来实现对算术编码的编码及其译码算法的实现二、实验环境1.计算机2.VC++6.0三、实验目的1.进一步熟悉算术编码的原理，及其基本的算法；2.通过编译，充分对于算术编码有进一步的了解和掌握；3.掌握C++语言编程（尤其是数值的进制转换，数值与字符串之间的转换等）四、实验原理算术编码算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。给定事件序列的算术编码步骤如下：（1）编码器在开始时将“当前间隔”设置为[0，1)。（2）对每一事件，编码器按步骤（a）和（b）进行处理（a）编码器将“当前间隔”分为子间隔，每一个事件一个。（b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。（3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。编码过程假设信源符号为{A，B，C，D}，这些符号的概率分别为{0.1，0.4，0.2，0.3}，根据这些概率可把间隔[0，1]分成4个子间隔：[0，0.1]，[0.1，0.5]，[0.5，0.7]，[0.7，1]，其中[x，y]表示半开放间隔，即包含x不包含y。上面的信息可综合在表03-04-1中。下表为信源符号，概率和初始编码间隔3如果二进制消息序列的输入为：CADACDB。编码时首先输入的符号是C，找到它的编码范围是[0.5，0.7]。由于消息中第二个符号A的编码范围是[0，0.1]，因此它的间隔就取[0.5，0.7]的第一个十分之一作为新间隔[0.5，0.52]。依此类推，编码第3个符号D时取新间隔为[0.514，0.52]，编码第4个符号A时，取新间隔为[0.514，0.5146]，…。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图03-04-1所示。编码和译码的全过程分别表示在下表：编码过程步骤输入符号编码间隔编码判决1C[0.5，0.7]符号的间隔范围[0.5，0.7]2A[0.5，0.52][0.5，0.7]间隔的第一个1/103D[0.514，0.52][0.5，0.52]间隔的最后一个1/104A[0.514，0.5146][0.514，0.52]间隔的第一个1/105C[0.5143，0.51442][0.514，0.5146]间隔的第五个1/10开始，二个1/106D[0.514384，0.51442][0.5143，0.51442]间隔的最后3个1/107B[0.5143836，0.514402][0.514384，0.51442]间隔的4个1/10，从第1个1/10开始8从[0.5143876，0.514402]中选择一个数作为输出：0.5143876译码过程步骤间隔译码符号译码判决1[0.5，0.7]C0.51439在间隔[0.5，0.7)2[0.5，0.52]A0.51439在间隔[0.5，0.7)的第1个符号ABCD概率0.10.40.20.3初始编码间隔[0，0.1)[0.1，0.5)[0.5，0.7)[0.7，1]41/103[0.514，0.52]D0.51439在间隔[0.5，0.52)的第7个1/104[0.514，0.5146]A0.51439在间隔[0.514，0.52]的第1个1/105[0.5143，0.51442]C0.51439在间隔[0.514，0.5146]的第5个1/106[0.514384，0.51442]D0.51439在间隔[0.5143，0.51442]的第7个1/107[0.51439，0.5143948]B0.51439在间隔[0.51439，0.5143948]的第1个1/108译码的消息：CADACDB五、实验思路算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码。而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0≤n1.0)的小数n。所以用两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。算术编码的算法思想如下：（1）对一组信源符号按照符号的概率从大到小排序，将[0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。（2）检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。（3）仍然按照信源符号的概率序列在当前分析区间划分比例间隔。然后重复第二步。直到“输入消息序列”检索完毕为止。（4）最后的编码输出数就是编码好的数据。六、实验数据记录及分析源程序：#includeiostream.h#includemath.h//定义所需要用到的变量及数组charS[100],A[10];5floatP[10],f[10],gFs;//编码程序voidbianma(inta,inth){inti,j;floatfr;floatps=1;floatFs=0;floatSp[100],b[100],F[100];//以待编码的个数和字符个数为循环周期，将待编码的字符所对应的概率存入到Fs中for(i=0;ih;i++){for(j=0;ja;j++){if(S[i]==A[j]){Sp[i]=P[j];fr=f[j];//将划分好的[0,1)区间的对应点赋值给fr}}Fs=Fs+ps*fr;//从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有符号编码完毕。ps*=Sp[i];//求Ps}coutFs=Fsendl;//显示最终的算术编码gFs=Fs;floatl=log(1/ps)/log(2);//计算算术编码的码字长度lif(l(int)l)l=(int)l+1;elsel=int(l);//将Fs转换成二进制的形式intd[20];intm=0;while(lm){Fs=2*Fs;if(Fs1){Fs=Fs-1;d[m]=1;}elseif(Fs1)d[m]=0;else{d[m]=1;break;}m++;}6intz=m;//解决有关算术编码的进位问题,给二进制数加1if(m=l){while(1){d[m-1]=(d[m-1]+1)%2;//最后位加1if(d[m-1]==1)break;elsem--;}}couts=;for(inte=0;ez+1;e++)coutd[e];coutendl;}//解码程序voidjiema(inta,inth){inti,j;floatFt,Pt;floatFs=0,Ps=1;for(i=0;ih;i++)//以编码个数和符号个数为循环周期，对其进行解码{for(intj=a-1;j-1;j--){Ft=Fs;Pt=Ps;Ft+=Pt*f[j];//对进行逆编码Pt*=P[j];if(gFs=Ft)//对其进行判断，并且将值存入到数组A中{Fs=Ft;Ps=Pt;coutA[j];break;}}}coutendl;}voidmain(){cout输入所要编码的符号的个数，并按回车跳转：endl;7inta,i,h=0;cina;cout请输入符号及其相对应的概率值，并按回车跳转：endl;for(i=0;ia;i++){charx;floaty;cinx;A[i]=x;//将字符依次存入数组A中ciny;P[i]=y;//将字符所对应的概率依次存入到数组P中}for(i=1;ia;i++){f[0]=0;f[i]=f[i-1]+P[i-1];//将要编码的数据映射到一个位于[0,1)的实数区间中}cout请输入所要编码的符号序列，并以*结尾：endl;while(1)//这个while语句的作用是将要编码的字符存入到数组S中{charss;cinss;if(ss=='*')break;//在以“*”为结尾的时候结束存储S[h++]=ss;}cout输入的字符经过算术编码之后为：endl;bianma(a,h);cout由上述所对应的解码为：endl;jiema(a,h);运行结果：8七、实验心得体会通过这一次算术编解码的实验，我学到了算术编解码的方法，也进一步巩固了C语言编程。刚开始老师讲的时候，有点蒙，不是理解的很好，后来通过跟老师同学的进一步请教，终于搞明白了其中的奥妙，编码过程是先对一组信源符号按照符号的概率从大到小排序，将[0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔，然后锁定当前消息符号（初次检索的话就是第一个消息符号），进行放大然后再根据比例划分间隔。重复这个过程，直到“输入消息序列”检索完毕为止。这个过程同时懂得了十进制的小数怎么转换成为二进制。此次实验，受益匪浅，希望下次实验能有更大的收获。