合工大信息论课程设计-费诺编码和自适应算术编码

信息论课程设计合肥工业大学计算机与信息学院第1页信息论课程设计课题名称：四元费诺编码自适应算术编码专业班级：任课教师:姓名：学号：完成时间：2012-12信息论课程设计合肥工业大学计算机与信息学院第2页四元费诺编码1.问题描述费诺编码方法属于概率匹配编码。这种编码方法不是最佳的编码方法，但有时也可得到最佳码的性能。设计一个程序对输入的一个字符串实现费诺编码。2.基本要求书本上大多讲解的二元的费诺编码，但是多元的费诺编码也能实现。请设计程序用以对输入字符串实现4元费诺编码，并且设计译码函数使满足根据编码的结果，输入任意的4进制数字串能够正确唯一的译码，最后计算编码效率。3.二元费诺编码基本原理首先,将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。依次下去，直至每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。编码方法：1.将信源消息符号按其出现的概率大小依次排列。2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。4.如此重复，直至每个组只剩下一个信源符号为止。5.信源符号所对应的码字即为费诺码。4.费诺编码特点费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率达，信息论课程设计合肥工业大学计算机与信息学院第3页编码效率高，但它属于概率匹配编码它不是最佳的编码方法。5.二元费诺编码思想费诺编码最困难的是根据信源概率对信源进行分组，本次借鉴了《信息编码与加密实践》（夏娜蒋建国丁志忠编著）中的二元费诺编码的思想，设定一个中间判断值—‘old’为每次分组总概率的一半大小，‘sum’为每次相加的概率和，每次相加后与该段的中间值差得绝对值与‘old’比较，小于其值则分为一组，大于其值则为另一组。递归调用这段程序，直到每个分组只含一个信源结束。6.四元费诺编码流程图开始输入字符窜统计各个字符出现的频率按字符出现的概率大小对符号进行排列调用编码对函数进行编码输出编码结果输入要编码的数字串字符都已编码完？NY信息论课程设计合肥工业大学计算机与信息学院第4页7.四元费诺编码思想与函数模块划分四元费诺编码主要在二元费诺编码的基础上修改编码函数，即二元费诺编码每次递归分两组，四元费诺编码每次就要分为四组。具体修改方法如下：参数说明结束调用译码函数译码输出编码结果信息论课程设计合肥工业大学计算机与信息学院第5页递归结束条条件递归函数信息论课程设计合肥工业大学计算机与信息学院第6页递归分组信息论课程设计合肥工业大学计算机与信息学院第7页8.程序测试与结果9.总结费诺编码：由实验结果可得，在一般情况下，费诺编码不一定能使短码得到充分利用，尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合就会很多，可能某种分大组的结果，会出现后面小组的概率和相差较远，因而使平均码长增加。所以，费诺码通常不是最佳码。程序：由于时间比较仓促，无法对程序进行美化和进一步的编写窗口化程序，界面比较传统和简陋。信息论课程设计合肥工业大学计算机与信息学院第8页自适应算术编码1.问题描述是图像压缩的主要算法之一。是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0≤n1.0)的小数n。2.基本要求请设计程序用以对输入字符串实现自适应的算术编码，其中要有相应的概率调整的过程，并且设计译码函数使满足根据编码的结果，能够正确的译码。3.算术编码原理在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。例:对一个简单的信号源进行观察，得到的统计模型如下：60%的机会出现符号中性20%的机会出现符号阳性10%的机会出现符号阴性10%的机会出现符号数据结束符.中性对应的区间是[0,0.6)阳性对应的区间是[0.6,0.8)阴性对应的区间是[0.8,0.9)数据结束符对应的区间是[0.9,1)当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和使用的模型参数即可以解码重建得到该符号序列。实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。在实用中，只要传输足够的该小数足够的位数(不论几进制)，以保证以这些位数开头的所有小数都位于结果区间就可以了。4.自适应算术编码信息论课程设计合肥工业大学计算机与信息学院第9页自适应算术编码即上述的模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。不管编码器使用怎样的模型，解码器也必须使用同样的模型。编码过程的每一步，除了最后一步，都是相同的。编码器通常需要考虑下面三种数据：1.下一个要编码的符。2.当前的区间(在编第一个符号之前，这个区间是[0,1),但是之后每次编码区间都会变化3.编码其将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为在下一步编码中的初始区间。5.自适应算术编码特点1）不必预先定义概率模型,自适应模式具有独特的优点;2）信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码;3）算术编码绕过了用一个特定的代码替代一个输入符号的想法,用一个浮点输出数值代替一个流的输入符号,较长的复杂的消息输出的数值中就需要更多的位数。4）算术编码实现方法复杂一些,但JPEG成员对多幅图像的测试结果表明,算术编码比Huffman编码提高了5%左右的效率,因此在PEG扩展系统中用算术编码取代Huffman编码。6.自适应算法流程图开始初始化概率空间和准备数据信息论课程设计合肥工业大学计算机与信息学院第10页7.自适应算术编码编程思想算法主要基于算术编码，其中编码译码都要增加一个概率调整的式子。编程思想如下：区间内任选一树调整指针指向下一字符输入字符串调整字符概率序列字符找到相应的概率空间字符都已编码？结束转二进制并去相应的有效位输出编码结果NY信息论课程设计合肥工业大学计算机与信息学院第11页（1）对一组信源符号按照符号的概率排序，将[0,1)设为当前分析区间。按信源符号的概率序列在当前分析区间划分比例间隔。（2）检索“输入消息序列”，锁定当前消息符号（初次检索的话就是第一个消息符号）。找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。并把当前分析区间的起点（即左端点）指示的数“补加”到编码输出数里。当前消息符号指针后移。（3）根据输如的字符，相应的调整信源的概率序列。（4）按照新的信源符号的概率序列在当前分析区间划分比例间隔。然后重复第二步。直到“输入消息序列”检索完毕为止。（5）最后的编码输出数就是编码好的数据。修改信源概率序列方法：Cnt[i]为相应信源符号的出现次数，初始化都为1；Sum为总共的信源符号Proc[i]为相应信源符号的概率areaBegin为区间起始概率areaEnd为区间结束概率信息论课程设计合肥工业大学计算机与信息学院第12页8.程序测试与结果9.总结自适应算术编码：不必预先定义概率模型,自适应模式具有独特的优点，没有对个输入符号的信息量为整数的限制，随着编码结果的小数随位数的增加，它的精度也随之增高，从信息的角度来说，它所含的信息量也随之增加。信源符号概率接近时编码效率比较好，其效率高于哈夫曼编码。程序：自己在指导书的程序基础上修改了编码译码函数，总体来说还是比较轻松简单的。但是因为时间比较紧，没有足够的时间对程序进行可视化窗口编程和美化，所以程序基于黑白对话框比较简陋；输入字符要手动输入，过程比较繁琐，容易出错，可以在以后增加文件操作和成熟美化等工作，使程序简单实用。信息论课程设计合肥工业大学计算机与信息学院第13页附录一：费诺编码源程序//Fano编括?码?.cpp:定¨义?控?制??应畖用?程ì序ò的?入?口ú点?。￡////Fano编码.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestdio.h#includemath.h#includestring.h#includealgorithmusingnamespacestd;typedefstruct{chardata;floatweight;charcode[1000];}fnode;fnodef[50];intnum;intforwd,mid,last;intjsq(char*s,intcnt[],charstr[]){char*p;inti,j,k=0;inttemp[257];for(i=0;i257;i++)temp[i]=0;for(p=s;*p!='\0';p++)temp[*p]++;for(i=0,j=0;i=256;i++)if(temp[i]!=0){j++;str[j]=i;cnt[j]=temp[i];}returnj;}//shuruvoidInput(charreceive[],intcnt[],charstr[]){unsignedintlen=0;信息论课程设计合肥工业大学计算机与信息学院第14页printf(输入要编码的字符串：);gets(receive);len=strlen(receive);num=jsq(receive,cnt,str);for(inti=1;i=num;i++){f[i-1].data=str[i];f[i-1].weight=float(cnt[i])/len;}}//编码voidcode(fnodef[],doubletotal,intbegin,intend){//doublesum=0.0,tsum=0.0,temp1old=total/2;doublesum=0.0,fsum=0.0,msum=0.0,lsum=0.0,temp1=0.0,temp2=0.0,temp3=0.0,old1=total/4,old2=total/4,old3=total/4;//intforwd,mid,last;if(end-begin==0)return;elseif(end-begin==1){strcat(f[begin].code,0);strcat(f[begin+1].code,1);return;}elseif(end-begin==2){strcat(f[begin].code,0);strcat(f[begin+1].code,1);strcat(f[begin+2].code,2);return;}elseif(end-begin==3){strcat(f[begin].code,0);strcat(f[begin+1].code,1);strcat(f[begin+2].code,2);strcat(f[begin+3].code,3);return;信息论课程设计合肥工业大学计算机与信息学院第15页}elsefor(inti=begin;i=end;i++){sum+=f[i].weight;temp1=fabs(sum-tota