Informatics Publishing Limited

Jyotika Doshi ¹, Savita Gandhi ²

Affiliations
1 GLS Institute of Computer Technology, Ahmedabad, Gujarat, IN
2 Gujarat University, Ahmedabad, Gujarat, IN

Abstract

Arithmetic coding is a very efficient and most popular entropy coding technique. Arithmetic coding method is based on the fact that the cumulative probability of a symbol sequence corresponds to a unique subinterval of the initial interval [0,1]. In this method, when encoding a symbol, it first computes new interval [low, high] based on cumulative probability segment of the symbol. Thereafter it iterates in a loop to output code bits till the interval becomes 2b-2 wide, where b is number of bits used to store range of an interval. In conventional implementation of arithmetic coding algorithm, in single loop iteration, only one bit is processed at a time. When most significant bit (msb) of low and high of a subinterval matches, it writes this msb in coded message and doubles the interval by extracting msb. When underflow occurs, it extracts second msb to expand an interval. Processing such single bit and expanding an interval is also called renormalization in a loop. In this paper, an upgradation of this conventional arithmetic coding algorithm is proposed, wherein more than one bit is processed at a time instead of just single bit in single iteration. This proposed multi-bit processing arithmetic coding algorithm is implemented here to reduce the iterations needed in renormalizing an interval. It is observed that processing multiple output bits at a time leads to big improvement in execution time. To determine the number of maximum possible matching most significant bits to output, two alternatives are used here; (i) Using shift operation in a loop (ii) Using log function. It is found that first technique is far better than second one with respect to execution time. As compared to conventional implementations processing single bit at a time, about 52% overall saving in execution time is observed when processing multi-bits using shift operation in a loop; whereas about 31% overall loss in performance is observed with the technique of using log function. We have also tried these two alternative ways to determine the number of consecutive occurrences of underflow and process them all in single iteration; but it has not shown any significant gain in speed. As expected, in using any of the above methods, there is no compromise in compression ratio.

Keywords

Arithmetic Coding, Computing Number of Output Bits and Underflow, Lossless Data Compression, Multi-Bit Processing, Renormalizing Interval.

Full Text

     

Jyotika Doshi ¹

Affiliations
1 GLS Institute of Computer Technology, Ahmedabad, Gujarat, IN

Abstract

A novel data structure, namely Cumulative Frequency Matrix (CFM), is proposed here for maintaining cumulative frequencies used in adaptive arithmetic data compression method. Arithmetic coding is based on cumulative probability interval of symbols. It computes subintervals using cumulative frequency of a symbol while encoding and decoding. While decoding, it also needs to find subinterval in which a given value falls. Adaptive methods need to compute cumulative frequencies on fly. CFM is suggested here for efficiency of algorithms to operate on cumulative frequency at runtime. CFM is a 2-D array of 16 rows and 16 columns for order-0 model. In order-0 model, a symbol is of single byte and it has two nibbles; say L for left and R for right. In CFM, row corresponds to left nibble and column corresponds to right nibble. As each nibble is of four bits, row index and column index varies from 0 to 15. Within row L, it stores partial cumulative frequency of only those symbols whose left nibble is L. Thus matrix element (L, R) contains the partial cumulative frequency of a symbol with right nibble as R among all the symbols with left nibble as L. This paper analyses algorithm forvarious operations needed in adaptive arithmetic coding. Operations are discussed here for initializing data structure, maintainin cumulative frequencies, computing subinterval, finding subinterval. CFM data structure is compared with Heap as described by Solomon and Fenwick's Binary Indexed Tree data structure. As compared with these related data structures in use, proposed data structure CFM is much simpler and efficient as well.

Keywords

Adaptive Arithmetic Coding, Algorithm Analysis, Cumulative Frequency Maintenance, Data Compression, Data Structure.

Full Text