基于时间最优的费诺编码算法研究与设计-论文.pdf

《基于时间最优的费诺编码算法研究与设计-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第34卷第2期武汉轻工大学学报Vo1．34No．22015年6月JournalofWuhanPolytechnicUniversityJun．20l5文章编号：2095-7386(2015)02-0065-05DOI：10．3969／j．issn．2095-7386．2015．02．015基于时问最优的费诺编码算法研究与设计王防修，刘春红(1．武汉轻工大学数学与计算机学院，湖北武汉430023，2．鄂钢驰久钢板弹簧有限责任公司，湖北鄂州436000)摘要：针对费诺编码的算法研究与实现问题，提出一种最优偏差值与分治法相结合的算法。算法以最小偏差值为目标，在概率序列中

2、寻找最佳断开位置，通过最佳断开位置实现费诺编码。鉴于费诺编码算法的递归属性，分别设计了编码的多模块算法和单模块算法。通过对算法时间复杂度的分析，对设计的算法进行了改进。算例仿真表明，不同算法时同一信源编码所耗费的时间差异很大，选择时间最优的费诺编码算法能更好地满足费诺编码系统对适时性的要求。关键词：时间最优；多模块算法；单模块算法；最优偏差值；分治法中图分类号：TP391文献标识码：AFanoCodingalgorithmresearchanddesignbasedontimeoptimalmatchingWANGFang-xiu‘，LIUChun—hong(1．

3、SchoolofMathematicsandComputerScience，WuhanPolylethnicUniversity，Wuhan430023，China；2．EzhouIronandSteelPlateSpringCoLtd，Ezhou436000，China)Abstract：AccordingtothealgorithmResearchandimplementationproblemsofFanocoding，thispaperpresentsanalgorithmwithoptimaldeviationCombinedwithdivideandc

4、onqueroInordertogainoptimaldeviationvalue，thealgorithmmustfindthebestopenpositionintheprobabilityseriesandachievefanocodingbytheposition．GiventherecursivepropertyinFanocodingalgorithm，codingalgorithmisdesignedformulti-moduleandsingle-modulealgorithm．Bythetimecomplexityanalysisofthealg

5、orithm．thealgorithmisimproved．Examplessimulationre—suitsshow，diferenceintime—consumingisverylargefordiferentalgorithmstoencodethesameinformationsource，andChosethebesttimeFanocodingalgorithmcallbettermeettherequirementsfortimelinessforthecodingsys-tern．Keywords：timeoptimal；multi—module

6、algorithm；singlemodulealgorithm；optimaldeviation；divideandconquer1引言蔷要凳黑在三大经典变长编码⋯中，哈夫曼编码的编码被广泛研究和应用，而费诺编码的算法原理及实现效率最高，香农编码的编码效率最低，而费诺编码的尚未见之于文献。虽然文献[1]给出了费诺编码的收稿日期：20l5l-l2．作者简介：王防修(1973．)，男，副教授，E-mail：wfx323@126．cofn武汉轻工大学学报2015年思想和几个具体的例子，但费诺编码的原理并没有设pi>P>⋯>和is<，定义两个函给出．本文针对费诺编码的算法

7、实现问题，提出了用数如下：k分治法进行费诺编码的算法思想，设计了几种不同()=∑Pm(i，)．(9)的算法来实现费诺编码。通过对不同算法对同一信f=源编码所花费的时间进行算法比较，从中得出时间打(后)=∑P=m(Ji}+l√)．(10)最优的费诺编码算法。如果用s(iJ)表示将概率序列pip⋯pj断开2用分治法实现费诺编码的基本原理为两个概率子序列的断开位置，则根据费诺编码的所谓用分治法进行费诺编码，就是是将一个规原理，其断开位置s(i)必须满足下列关系：模为儿的问题分解为两个规模较小的子问题，这两s(i，)=，=l，2，⋯，n．(11)个子问题相互独立与原问题相

8、同。递归地