rform this operation is described in detail in Appendix H. Our description represents a simplification of the more general algorithm described in MacKay (2003). D.J.C. MacKay, A Short Course in Information Theory (Cambridge, UK: Cambridge University Press, 2003). Codeword 00000 00001 00010 0001 [0.8, 1.0) 00011 00100 0010 001 00101 00110 0011 00111 01000 0100 010 01001 01010 0101 01011 [0.4, 0.8) 01100 0110 011 01101 01110 0111 01111 10000 10001 10010 1001 10011 10100 10101 10110 1011 10111 11000 [0.0, 0.4) 11001 11010 11011 11100 11101 11110 11111 Codeword 0111100 011110 01111 0111101 0111110 011111 0111111 1000000 100000 10000 1000001 1000010 100001 1000011 1000100 100010 10001 1000101 1000110 100011 1000111 1001000 100100 10010 1001001 1001010 100101 1001011 Figure 10.1 Principle of arithmetic coding for the symbol sequence babc from event source X = {a, b, c}, showing coding of joint probabilities: (a) up to three events with five-bit codewords; (b) up to four events with seven-bit codewords. 10.2 Arithmetic coding Given a source X = {x1, X2, xn} and its probability characteristics, the coding algorithm enables the encoding machine (encoder) to calculate rapidly the subinterval [UN, UN) corresponding to any sequence aja2. , an-1xn, where the symbols ak can take any value, save Xn. If the message source and characteristics are unknown, the encoder must acquire the entire sequence a1, A2, aN-1, identify the different sym- bols used (xi), and calculate the corresponding probability distribution p(xi) attached to each of the message symbols specifically used in this sequence. We can, however, assume that the incoming messages always use the same type of source (e.g., English text, programming-language source code, bank datafiles, etc.), in which case, such an operation simply consists of prior calibration work. In this sense, the code is adap- tive, but it is supposed to be extensively used once it has been thus defined, just like any other variable-length static code. The key difference here with a purely static