Order-preserving, fast-decoding arithmetic coding arithmetic coding and

Abstract

An efficient, fast-decoding, order-preserving, easily implementable, length-based (L-based) arithmetic coding method, apparatus, and manufacture for an m-ary alphabet {1, . . . , i, . . . , m} is provided. A coding method in accordance with the invention combines recursive division of intervals on a number line into sub-intervals whose lengths are proportional to symbol probability and which are ordered in lexical order with the constraint that probabilities be estimated as negative powers of two (1/2, 1/4, 1/8, etc.). As a consequence, the advantageous preservation of lexical order and computational efficiency are both realized. Also, a coding system in accordance with the invention is simple to implement, and high speed operation is achieved, because shifts take the place of multiplications. A coding apparatus in accordance with the invention preferably includes either a single decoding table to achieve fast decoding, or two decoding tables to achieve fast decoding as well as order preservation. The decoding process can conveniently be performed by constructing a decoding table for the C register. The C register is initialized with the leading bits of the codestring. The decoded symbol is the symbol i, i being the greatest integer that makes the C-register value greater than or equal to P(i).