Syntax based arithmetic coder and decoder

Abstract

A coder/decoder selects one of a set of look-up tables for encoding/decoding a symbol. Each look-up table contains boundary values that result from an arithmetic coding model partitioning a first interval. A second interval contains an arithmetic code. During encoding, look-up table entries for a symbol value are converted to the scale of the second interval. The scaled values indicate a smaller interval containing the arithmetic code. Code bits are generated when most significant bits of upper and lower scaled values are equal. During decoding, a code word, which is a part of an arithmetic code, is normalized from the scale of the second interval to the scale for a look-up table and then compared to entries of the look-up table. When a segment containing the code word is identified, a decoded symbol value is known. A scaling circuit converts boundary values for the segment to the scale of the second interval then changes the second interval. Identical most significant bits in the boundary values are shifted out of a register to prevent overflow during encoding/decoding. To increase the effective size of the register, the next to most significant bit can be removed while a counter counts the number of bits removed.