t need to be computed. From this property, we also have 1 = R(X, a1, A2, ak-1)=Q(X,a1, = A2, ak-1) + p(xn/a1, A2, ak-1), which eliminates the need to compute the sum involved in the function Q as well. We can then redefine the algorithm in Eq. (H13) according to the much simpler form: Uk=Wk-1 (H16) Wk=Uk-Uk. Arithmetic coding algorithm It is easily verified that Eqs. (H15) and (H16) yield the correct values UN, UN for the strings of lengths N=1...3 previously analyzed. Note that the algorithm defined by these equations is valid only for the case of interest where the last symbol of the message string, an, is equal to Xn. This algorithm represents a simpler variant of that described in the reference², which is valid for any symbol values of an (namely all subintervals). The generalization of the above algorithm to the general case (an = xj) simply consists of modifying Eq. (H14) to: (H17) X,a1ap with, by convention, Q being set to zero when j=1. D.J.C. MacKay, A Short Course in Information Theory (1995), www.inference.phy.cam.ac.uk/mackay/info theory/course.html; see also D.J.C. MacKay, Information Theory, Inference and Learning Algorithms (Cambridge, UK: Cambridge University Press, 2003), p. 113. Appendix I (Chapter 10) Lempel-Ziv distinct parsing In this appendix I show, based on the demonstration of Cover and Thomas (1991)¹ and a few useful explanations, that for a given string sequence (or message) of length n, the number of distinct-parsing phrases c(n) is bounded according to: where En vanishes as n Distinct parsing This is the action of partitioning a given message into different substrings, or phrases, with variable length m. Assume that the maximum phrase length allowed is K. The number of distinct phrases having m bits is 2m The length LK of a sequence made from concatenating all possible phrases of length < K is, therefore, In a note at the end of this appendix, I show that this length is equal to Lk = (K - 1)2 x +1 + Consider first the simple case where the message length is n = LK. The number of phras