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

《合工大信息论课程设计-费诺编码和自适应算术编码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息论课程设计课题名称：四元费诺编码自适应算术编码专业班级：任课教师:姓名：学号：完成时间：2012-12四元费诺编码1.问题描述费诺编码方法属于概率匹配编码。这种编码方法不是最佳的编码方法，但有时也可得到最佳码的性能。设计一个程序对输入的一个字符串实现费诺编码。2.基本要求书本上大多讲解的二元的费诺编码，但是多元的费诺编码也能实现。请设计程序用以对输入字符串实现4元费诺编码，并且设计译码函数使满足根据编码的结果，输入任意的4进制数字串能够正确唯一的译码，最后计算编码效率。3.二元费诺编码基本原理首先,将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使第组的概率和近于

2、相同,并各赋于一个二元码符号”0”和”1”.然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。依次下去，直至每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。编码方法：1.将信源消息符号按其出现的概率大小依次排列。　　2.将依次排列的信源符号按概率值分为两大组，使两个组的概

3、率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。　　3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。　　4.如此重复，直至每个组只剩下一个信源符号为止。　　5.信源符号所对应的码字即为费诺码。4.费诺编码特点费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率达，编码效率高，但它属于概率匹配编码它不是最佳的编码方法。5.二元费诺编码思想费诺编码最困难的是根据信源概率对信源进行分组，本次借鉴了《信息编码与加密实践》（夏娜蒋建国丁志忠编著）中的二元费诺编码的思想，设定一个中间判断值—‘old’为每次分组总概

4、率的一半大小，‘sum’为每次相加的概率和，每次相加后与该段的中间值差得绝对值与‘old’比较，小于其值则分为一组，大于其值则为另一组。递归调用这段程序，直到每个分组只含一个信源结束。6.四元费诺编码流程图开始输入字符窜统计各个字符出现的频率按字符出现的概率大小对符号进行排列调用编码对函数进行编码N字符都已编码完？Y输出编码结果输入要编码的数字串调用译码函数译码输出编码结果结束7.四元费诺编码思想与函数模块划分四元费诺编码主要在二元费诺编码的基础上修改编码函数，即二元费诺编码每次递归分两组，四元费诺编码每次就要分为四组。具体修改方法如下：参数说明递归结束条条件递归函数递归分组8.程序测试

5、与结果9.总结费诺编码：由实验结果可得，在一般情况下，费诺编码不一定能使短码得到充分利用，尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合就会很多，可能某种分大组的结果，会出现后面小组的概率和相差较远，因而使平均码长增加。所以，费诺码通常不是最佳码。程序：由于时间比较仓促，无法对程序进行美化和进一步的编写窗口化程序，界面比较传统和简陋。自适应算术编码1.问题描述是图像压缩的主要算法之一。是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一

6、个数，一个满足(0.0≤n<1.0)的小数n。1.基本要求请设计程序用以对输入字符串实现自适应的算术编码，其中要有相应的概率调整的过程，并且设计译码函数使满足根据编码的结果，能够正确的译码。2.算术编码原理在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。　　例:对一个简单的信号源进行观察，得到的统计模型如下：　　60%的机会出现符号中性　　20%的机会出现符号阳性　　10%的机会出现符号阴性　　10%的机会出现符号数据结束符.中性对应的区间是[0,0.6)　　

7、阳性对应的区间是[0.6,0.8)　　阴性对应的区间是[0.8,0.9)　　数据结束符对应的区间是[0.9,1)　　当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和使用的模型参数即可以解码重建得到该符号序列。　　实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。在实用中，只要传输足够的该小数足够的位数(不论几进制)，以保证以这些位数开头的所有小数都位于结果