An FPGA-Based Implementation of Multi-Alphabet Arithmetic Coding

A fully parallel implementation of the multi-alphabet arithmetic-coding algorithm, an integral part of many lossless data compression systems, had so far eluded the research community. Although schemes were in existence for performing the encoding operation in parallel, the data dependencies involved in the decoding phase prevented its parallel execution. This paper presents a scheme for the parallel-pipelined implementation of both the phases of the arithmetic-coding algorithm for multisymbol alphabets in high-speed programmable hardware. The compression performance of the proposed scheme has been evaluated and compared with an existing sequential implementation in terms of average compression ratio as well as the estimated execution time for the Canterbury Corpus test set of files. The proposed scheme facilitates hardware realization of both coder and decoder modules by reducing the storage capacity necessary for maintaining the modeling information. The design has been synthesized for Xilinx field-programmable gate arrays and the synthesis results obtained are encouraging, paving the way for further research in this direction.