信息论与编码实验报告

计算机与信息学院信息论与编码实验报告专业班级学生姓名及学号周伟康20112910课程教学班号任课教师苏兆品实验指导教师实验地点2013~2014学年第一学期仅供参考1信息论与编码课程设计目录一．课程设计目的................................................................2二．课程设计要求................................................................2三．课程设计描述................................................................2四．程序结构.......................................................................2五．算法及部分源码............................................................3六．用例测试.......................................................................9七．总结.............................................................................20仅供参考2一．课程设计目的通过编程实现，在理解掌握的基础上进一步扩展课授的几种无失真信源编码算法。以实践检验理论。二．课程设计要求1.对一灰度图像进行游程编码的设计实现（将Huffman与游程结合）。2.试对任意的数字序列（如学号、电话号码）进行自适应算术编码。3.围绕设计题目查阅资料，掌握编码的基本原理。4.按设计要求和编码原理进行算法的设计，算法的设计应满足正确性、可读性、健壮性、高效率等要求。5.在此基础上，可以进行扩展三．课程设计描述本次设计实现内容：1.对任意的信源符号序列进行N元Huffman编码/译码。2.对任意的信源符号序列进行N元Fano编码/译码。3.对任意的信源符号序列进行N元Elias编码/译码。4.对像素矩阵进行游程与上述编码方式结合的编码/译码。5.数字串的自适应算数编码/译码。6.对任意给定译码规则的译码和判断其是否为即时码。输入数据从键盘或磁盘文件读入，运算结果显示到屏幕或保存到文件。编写可视化图形交互界面。本次设计程序用Java实现，由本人独立完成。四．程序结构本次设计采用MVC设计模式：控制包下为文件读写线程执行包下是执行主类模式包分编码译码两部分Item：封装每个码元符号信息和操作AnlysisModel：信源序列统计分析模型其他如右图顾名思义视图包也分编码译码两部分MainFrame：主框架界面编码下：算数编码面板分组码编码面板译码下：算数译码面板分组码译码面板仅供参考3五．算法及部分源码a)N元Huffman编码：算法：1)将每个信源符号加入优先队列Heap。2)(1)qnn，由信源符号数q和码元数n，求出正整数。3)求出满足上式所需添加的虚拟信源符号数z。4)加入z个虚拟符号到Heap。5)每次从Heap中取n个信源符号进行缩减，合成新元素加入Heap。同时构建Huffman树。6)广搜Huffman树，生成每个符号的码字并记录码长。代码：仅供参考4b)N元Fano编码：算法：1)按概率从大到小对信源符号排序。2)初始化n-1个断点为1~n-13)若n=N则返回4)否则扫描序列中余下的值，从后往前调整断点，维护每段和的方差尽可能小。5)按顺序将每个段赋上一位码符号6)递归处理每个小段。代码略c)N元Elias编码：算法：1)遍历信源符号集，求出所对应的下列参数：2)累积分布函数：1()(),kkikiiFaPaaaA3)修正累积分布函数：1_1()()(),2kkikkiiFaPapaaaA4)码长：()log()1irilaPa5)将_()kFa的r进制数截取()kla位作为ka对应码字。代码：仅供参考5d)信源符号序列解析：算法：1)对于单字符信源符号序列编码，统计每个字符频数。计算频率()iPa2)对于灰度图像按行游程编码，以像素作为统计元，计算其频率()iPa并记录每个游程长。以最大游程长-1对应R进制数位数作为游程长度等长码长度。忽略回车符。代码：e)数字串的自适应算数编码算法：1)初始化0~9每个数字的频数为1，频率为0.1，2)初始化概率区间为[0,1]，区间长度为1.0。3)依次获得数字串每位数字，调整区间、数字频数和频率。4)计算码长：()log()1rls最后区间长度5)在最后的区间中任选一数，取其r进制数小数点后()ls位作为码字。代码：仅供参考6f)数字串的自适应算数解码算法：1)获取译码R进制字串，化为十进制小数result。2)初始化0~9每个数字的频数为1，频率为0.1，3)初始化概率区间为[0,1]，区间长度为1.0。4)确定result落在的区间，并调整区间，以其对应码符号作为解码第i位数字，修正区间对应数字频数和频率。5)计算解码码长：()log()1rls当前区间长度。6)()ls待译码串长度，重复4，5，6步，依次得出原序列。代码：仅供参考7g)平均码长和编码效率：算法：1)平均码长_()iiLPal，算数编码平均码长_-logP(s)1=LLlL编码串长信源串长2)编码效率()rHsL代码：h)即时码的判断和译码算法：仅供参考81)两两码字公共前缀判断，若存在则不是即时码。2()Onk2)对每个码字，以其码符号为枝构造码树。若存在某一码字对应节点不为叶子，则不是即时码。()Onk3)对即时码译码规则，在码字串中搜索匹配码字，找到其对应信源符号。还原信源符号序列。4)对于游程结合其他方法的编码，还需译出游程长。还原灰度矩阵。代码：仅供参考9i)六．用例测试Huffman编码解码。输入文件打开：仅供参考10信源序列分析：仅供参考11n=4元Huffman编码：译码：仅供参考12仅供参考13n=2元Elias编码：仅供参考14译码：仅供参考15灰度图像游程编码（+Huffman）：仅供参考16译码：仅供参考17自适应算数编码：译码：仅供参考18任意规则译码：仅供参考19仅供参考20七．总结本次课程设计实验在完成基本要求的基础上，对实验内容和深度都进行了一定程度的扩展。对几种编码译码的理论算法有了更加深化的认识。本次试验是继数据库课设之后，第二个上两千行代码规模的程序。相对前者，此次取得的进步值得一提：1.同样是Swing编写的图形交互界面，此次编写之前先仔细阅读学习了JFC，参考了若干文档和实例。使得编写更加熟练，开发速度也显著提升。2.此次开发过程中，将软件工程学以致用。参考了多种设计模式，提高了代码质量，切实体会到了代码复用、易于维护的好处。3.此次开发过程中，接触了一些英文资料。包括JavaPlatfromSE7文档的Swing模块，TheTheoryofInformationandCoding变长码部分等。提高了本人信息收集运用的能力。与此同时，本人对此次项目的最大遗憾是：仅作为一个简单的算法演示集合，无实际应用价值。接下来可以考虑将某些编码方法与本学期所学的密码学或网络结合起来，尽量真实的模拟或完全实现解决现实问题。最后，写上此次设计收获的最大感悟：编程确如软件工程学所说，是整个软件开发项目流程中偏后且极小的一部分。当需求十分明确、精细的时候，依纲实现劳力居多。而当需求模糊或者说需要创新、设计、提炼需求的时候，脑力居多。分析深化的细节越精细，产品越优秀。所以程序设计不仅是要会编程，经验丰富，更重要的是一种追求卓越的习惯。