bilities p(x1,x2) = p(x2/x1)p(x1) of either joint events aa, ab, ac, or ba, bb, bc. The regions corresponding to labels 0 and 1 are also divided into two equal parts, which are labeled with prefixes 00, 01, 10, and 11. We observe from the figure that: The prefix 11 corresponds to either aa or ab; The prefix 10 corresponds to either ab, ac, or ba; The prefix 01 corresponds to either ba, bb, or bc; The prefix 00 corresponds to either bc or c; Step 3: Each of the previous subintervals, except the last ones corresponding to final events c, is divided again into three subintervals, the widths of which correspond to the joint probabilities p(x1, x2, X3) = p(x3/x1,x2)p(x3) of joint events aaa, aab, aac, aba, abb, abc, baa, bab, bac, bba, bbb, bbc. The region corresponding to prefixes 00, 01, 10, and 11 are also divided into two equal parts, which are labeled 000 to 111 and correspond to different joint-event possibilities, except for 000 which is exclusively attached to event C. The encoder is capable of executing the above steps an arbitrary number of times in order to find the prefix attached to a string of any length and ending in C. To clarify this point, assume that the string (or joint event) to encode is bc. We observe from Fig. 10.1(a) that the unique subinterval which is fully contained in the region defined by string bc has the prefix 00111. We can then use this prefix as the unique codeword for string bc. The same observation applies, for instance, to the string aac, which gets 11001 as a unique prefix and codeword. Assume next that the machine must encode the string babc. The magnification in Fig. 10.1(b) shows that the subinterval corresponding to prefix 1000001 is the only one to be fully contained in the region defined by string babc, and, therefore, it should be used as the unique codeword. In summary, the encoder assigns a unique codeword to any symbol string (or joint event) X1X2, , XnC by slicing down the interval [0, 1) into as many subintervals of widths p(x1, X2, , X2, Xn) p(c). The algorithm to pe