is equal to unity). For instance, considering the sequence xxyxxxy, we have Fx = 5 and Fy = 2, thus p(ag = x|aja2...a7) =6/9=2/3 and p(ag = y/aja2 a7) = 3/9 1/3. For an n-event source X = {X1,X2,...,Xn}, Laplace's rule is: (10.2) Note that the Laplace rule only represents a model to determine the conditional proba- bilities heuristically. Such an assignment is arbitrary and does not need to be exact or accurate. What matters is that both encoder and decoder use the same definition. It can yet be refined using the Dirichlet model: (10.3) where a is an adjustable constant, for instance a = 0.05 - 0.01. With the knowledge the distributions p(xi) and p(xila1a2, ak-1), the encoder can then implement the arithmetic-coding algorithm described in Appendix H. From the decoder's side, the calibration process is similar, except that it operates in the opposite way. The decoder, which has the same resolution as the encoder, identifies the different message codewords received and assigns a probability interval to each possible prefix, as Fig. 10.1 illustrates, reading from right to left. The correspondence between the identified codewords and the original source symbols is only a matter of convention, like the A-Z sequence of characters in the English alphabet. It can be shown that arithmetic coding is near optimal, as the codeword length, 1(s), for a given symbol sequence, S, closely approaches the Shannon limit -log p(s), which represents the information contents of the sequence. Owing to its versatility with respect to source types and its capability of coding and decoding "on the fly," arithmetic coding is used in many still or motion image-compression standards, such as JPEG and MPEG (see Appendix G). Another interesting application of arithmetic coding concerns the generation of ran- dom numbers. Indeed, random-bit strings can be generated by feeding an arithmetic decoder with uniformly distributed bit streams, such as produced by a pseudo-random word generator. The decoder then outputs what it interprets to be a suite 