二进制算术编码的分段计算算法及应用

Segmentation Calculation Algorithm and Application of Binary Arithmetic Coding

算术编码作为一种无损压缩方法得到广泛应用,但该算法对区间参数的运算采用递推模式,这种串行流程在多核及并行等资源环境下不适用,且执行效率较低。从固定概率空间二进制算术编码角度,先推导出编码序列区间参数非递推模式计算公式,进而得出序列分段各自编码,再合并计算原序列区间参数的计算公式,并从理论上证明了算法可行性。给出了算法物理意义描述和典型编码流程,针对多核和并行等资源环境提出了纵向和横向分段思路,并采用实际序列验证了算法正确性。该算法在某情报网关设备中应用可见,在确保压缩效果不变基础上,可使各中央处理器(CPU)核之间负载基本持平,有效利用了多核计算资源,将情报报文吞吐量提升近1倍,效果良好。

The arithmetic coding is widely used as a lossless compression method.But the algorithm adopts the recursive mode to the interval parameter,this serial process does not suitable for the multi-cored and paralleled resources environment,and has the low execution efficiency.Aimed at the fixed probability space binary arithmetic coding,a formula of the non-recursive mode for coding sequence interval is derived firstly,the sequential coding is obtained,the calculation formula of the interval parameters of the original sequence is calculated,and the feasibility of the algorithm is theoretically proved.The physical meaning description of the algorithm and the typical coding process are proposed,and the thinking paragraphed from vertical and horizontal aspects is provided for the multi-cored and paralleled resources environment,and the correctness of the algorithm is verified by the actual sequence.The algorithm is applied in some intelligence gateway device.The result shows that the loads between each central processing unit(CPU)cores are basically equaled based on the same compression effect,the throughput of the information message is doubled by the multi-core computing resources,thus its result is good.