background image
ISO/IEC 10918-1 : 1993(E)
The subdivision of the current probability interval would ideally require a multiplication of the interval by the probability
estimate for the LPS. Because this subdivision is done approximately, it is possible for the LPS sub-interval to be larger
than the MPS sub-interval. When that happens a "conditional exchange" interchanges the assignment of the sub-intervals
such that the MPS is given the larger sub-interval.
Since the encoding procedure involves addition of binary fractions rather than concatenation of integer code words, the
more probable binary decisions can sometimes be coded at a cost of much less than one bit per decision.
D.1.1.2
Conditioning of probability estimates
An adaptive binary arithmetic coder requires a statistical model ­ a model for selecting conditional probability estimates to
be used in the coding of each binary decision. When a given binary decision probability estimate is dependent on a
particular feature or features (the context) already coded, it is "conditioned" on that feature. The conditioning of
probability estimates on previously coded decisions must be identical in encoder and decoder, and therefore can use only
information known to both.
Each conditional probability estimate required by the statistical model is kept in a separate storage location or "bin"
identified by a unique context-index S. The arithmetic coder is adaptive, which means that the probability estimates at
each context-index are developed and maintained by the arithmetic coding system on the basis of prior coding decisions
for that context-index.
D.1.2
Encoding conventions and approximations
The encoding procedures use fixed precision integer arithmetic and an integer representation of fractional values in which
X'8000' can be regarded as the decimal value 0.75. The probability interval, A, is kept in the integer
range
X'8000'
A
<
X'10000' by doubling it whenever its integer value falls below X'8000'. This is equivalent to
keeping A in the decimal range 0.75
A
<
1.5. This doubling procedure is called renormalization.
The code register, C, contains the trailing bits of the bit stream. C is also doubled each time A is doubled. Periodically
­ to keep C from overflowing ­ a byte of data is removed from the high order bits of the C-register and placed in the
entropy-coded segment.
Carry-over into the entropy-coded segment is limited by delaying X'FF' output bytes until the carry-over is resolved. Zero
bytes are stuffed after each X'FF' byte in the entropy-coded segment in order to avoid the accidental generation of
markers in the entropy-coded segment.
Keeping A in the range 0.75
A
<
1.5 allows a simple arithmetic approximation to be used in the probability interval
subdivision. Normally, if the current estimate of the LPS probability for context-index S is Qe(S), precise calculation of
the sub-intervals would require:
Qe(S)
×
A
Probability sub-interval for the LPS;
A ­ (Qe(S)
×
A) Probability sub-interval for the MPS.
Because the decimal value of A is of order unity, these can be approximated by
Qe(S)
Probability sub-interval for the LPS;
A ­ Qe(S)
Probability sub-interval for the MPS.
Whenever the LPS is coded, the value of A ­ Qe(S) is added to the code register and the probability interval is reduced to
Qe(S). Whenever the MPS is coded, the code register is left unchanged and the interval is reduced to A ­ Qe(S). The
precision range required for A is then restored, if necessary, by renormalization of both A and C.
With the procedure described above, the approximations in the probability interval subdivision process can sometimes
make the LPS sub-interval larger than the MPS sub-interval. If, for example, the value of Qe(S) is 0.5 and A is at the
minimum allowed value of 0.75, the approximate scaling gives one-third of the probability interval to the MPS and two-
thirds to the LPS. To avoid this size inversion, conditional exchange is used. The probability interval is subdivided using
the simple approximation, but the MPS and LPS sub-interval assignments are exchanged whenever the LPS sub-interval is
larger than the MPS sub-interval. This MPS/LPS conditional exchange can only occur when a renormalization will be
needed.
Each binary decision uses a context. A context is the set of prior coding decisions which determine the context-index, S,
identifying the probability estimate used in coding the decision.
Whenever a renormalization occurs, a probability estimation procedure is invoked which determines a new probability
estimate for the context currently being coded. No explicit symbol counts are needed for the estimation. The relative
probabilities of renormalization after coding of LPS and MPS provide, by means of a table-based probability estimation
state machine, a direct estimate of the probabilities.
CCITT Rec. T.81 (1992 E)
55
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186]