**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)**