并行MPS算术编码的性能分析

《并行MPS算术编码的性能分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第31卷第12期电子与信息学报Vol.31No.122009年12月JournalofElectronics&InformationTechnologyDec..2009并行MPS算术编码的性能分析①②③①王前吕东强葛宝珊①(北京航空航天大学计算机学院北京100083)②(解放军61081部队北京100094)③(第二炮兵装备研究院四所北京100085)摘要：利用多维二进制码流的统计规律，基于MPS并行的算术编码不但避免了传统并行算术编码的复杂运算，且不会影响其基本概率估计规律。该文运用全概率定理和

2、统计平均思想从理论上分析了并行度与加速比、编码效率之间的关系，指出并行度为2的MPS并行编码方案在编码速度和效率方面较其它并行度占有很大优势，并行度3和4的编码方案在编码效率方面基本持平，并加以试验证明。关键词：算术编码；并行；大概率符号；状态转移中图分类号：TN919.81文献标识码：A文章编号：1009-5896(2009)12-2907-05PerformanceAnalysisofArithmeticCodeonParallelizedMPS①②③①WangQianLüDong-qiangG

3、eBao-shan①(SchoolofComputerScienceandEngineering,BeihangUniversity,Beijing100083,China)②(61081armyofPLA,Beijing100094,China)③(TheFourthInstituteoftheSecondArtilleryEquipmentAcademe,Beijing100085,China)Abstract:ArithmeticcodeonparallelizedMPS(MostProbab

4、leSymbol)notonlyavoidscomplexoperationofclassicalparallelizedarithmeticcode,butalsodoesnotinflectitsbasicprobabilityestimationrulesinceutilizingstatisticlawofmultidimensionalbinarycoding.Therelationbetweenparalleldegree,speedupratioandcodingefficiencyi

5、stheoreticallyanalyzedbasedonthetheoremofcompleteprobabilityandstatisticaverage.Itispointedoutthealgorithmwith2paralleldegreeissuperiortoothersonthecodingefficiencyandspeed,thealgorithmof3paralleldegreeisequaltotheoneof4paralleldegreeonthecodingefficie

6、ncy.Theresultisverifiedbytheexperiment.Keywords:Arithmeticcode;Parallelization;MPS(MostProbableSymbol);Statetransition1引言100%，但系统复杂度较高，不利于硬件的快速实现。文献[5,6]的算法都属于近似并行，即改变标准算术算术编码算法能够灵活地适应数据的概率变编码的流程，所产生的压缩码流不能与标准算术解化，压缩效率明显高于变长编码，但实现复杂度高，码兼容。如文献[5]运用线性近似法

7、和并行概率模型处理速度慢，难以满足大数据量处理时的实时性要实现并行编码，文献[6]运用MPS并行来提高并行求，因此在实际应用中受到很大的限制。针对算术度。近似并行吞吐率高，且实现难度小，但引起一编码的特点，流水线和并行处理是其中最主要的加个值得考虑的问题：即编码效率。本文针对MPS速措施。并行算术编码算法，分析其给编码过程带来的影响，并行可分为等价并行和近似并行两类。如文献利用数值解析法确定其编码效率的变化范围，为今[1-4]提出的并行算法都属于等价并行，但文献[2]系后优化编码设计提供依据。统的吞

8、吐率提高幅度较低，只有24%，属于部分并行范畴；文献[3]设计出5种不同形式的算术编码并2算法思想行结构，吞吐率提高幅度从10%到120%不等。文二值算术编码的主要思想是根据输入信源符号献[4]采用完全并行算法，吞吐率比单输入系统提高的概率分布计算序列所对应的区间，然后进行区间截断，并把截断结果作为压缩码流的输出。考虑信2008-12-01收到，2009-05-11改回源序列Uu=(,,12uu"L)，二值化的特点使得编码序国家863计划项目(2006AA701121