ISO/IEC 10918-1 : 1993(E)
Annex D
Arithmetic coding
(This annex forms an integral part of this Recommendation | International Standard)
An adaptive binary arithmetic coding procedure may be used for entropy coding in any of the coding processes except
the baseline sequential process. Coding models for adaptive binary arithmetic coding are defined in Annexes F, G,
and H. In this annex the arithmetic encoding and decoding procedures used in those models are defined.
In K.4 a simple test example is given which should be helpful in determining if a given implementation is correct.
NOTE There is no requirement in this Specification that any encoder or decoder shall implement the procedures in
precisely the manner specified by the flow charts in this annex. It is necessary only that an encoder or decoder implement the function
specified in this annex. The sole criterion for an encoder or decoder to be considered in compliance with this Specification is that it
satisfy the requirements given in clause 6 (for encoders) or clause 7 (for decoders), as determined by the compliance tests specified in
Part 2.
D.1
Arithmetic encoding procedures
Four arithmetic encoding procedures are required in a system with arithmetic coding (see Table D.1).
Table D.1 Procedures for binary arithmetic encoding
Procedure
Purpose
Code_0(S)
Code a "0" binary decision with context-index S
Code_1(S)
Code a "1" binary decision with context-index S
Initenc
Initialize the encoder
Flush
Terminate entropy-coded segment
The "Code_0(S)"and "Code_1(S)" procedures code the 0-decision and 1-decision respectively; S is a context-index
which identifies a particular conditional probability estimate used in coding the binary decision. The "Initenc" procedure
initializes the arithmetic coding entropy encoder. The "Flush" procedure terminates the entropy-coded segment in
preparation for the marker which follows.
D.1.1
Binary arithmetic encoding principles
The arithmetic coder encodes a series of binary symbols, zeros and ones, each symbol representing one possible result of a
binary decision.
Each "binary decision" provides a choice between two alternatives. The binary decision might be between positive and
negative signs, a magnitude being zero or nonzero, or a particular bit in a sequence of binary digits being zero or one.
The output bit stream (entropy-coded data segment) represents a binary fraction which increases in precision as bytes are
appended by the encoding process.
D.1.1.1
Recursive interval subdivision
Recursive probability interval subdivision is the basis for the binary arithmetic encoding procedures. With each binary
decision the current probability interval is subdivided into two sub-intervals, and the bit stream is modified (if necessary)
so that it points to the base (the lower bound) of the probability sub-interval assigned to the symbol which occurred.
In the partitioning of the current probability interval into two sub-intervals, the sub-interval for the less probable symbol
(LPS) and the sub-interval for the more probable symbol (MPS) are ordered such that usually the MPS sub-interval is
closer to zero. Therefore, when the LPS is coded, the MPS sub-interval size is added to the bit stream. This coding
convention requires that symbols be recognized as either MPS or LPS rather than 0 or 1. Consequently, the size of the
LPS sub-interval and the sense of the MPS for each decision must be known in order to encode that decision.
54
CCITT Rec. T.81 (1992 E)