tions are exhausted (except for a dummy 22222 codeword, which is never used). The codeword length corresponding to this character-codeword map- ping is shown in Table 8.3 in Column 8 as l'(x). Column 9 of Table 8.3 details the calculation of the mean codeword length L'. The result is L' = 2.744 trit/ symbol, which corresponds to a coding efficiency of n = H3/L = 96.23%. This coding efficiency is far greater than any efficiency obtained SO far with fixed and variable-length codes for the English A-Z character source. What we have learnt from the above examples is that there exist many possibilities for assigning variable-length codewords to a given symbol source. Also, we have seen that the coding tree can be used as a tool towards generating codes with shorter mean codeword length. We must now formalize our approach, in order to determine the shortest mean codeword length achievable for any given source, and a method of finding the corresponding optimal code, which is described next. Information coding Shannon's source-coding theorem In this section, we address the following question: Given a symbol source, what is the smallest mean codeword length achievable? The answer is provided by a relatively simple demonstration. Let HM(X) be the entropy of a M-ary source X={x} = with codeword lengths 1(x) and corresponding probability p(x). The mean codeword length is L(X) = 1(x)p(x). We then estimate the difference = L(X) - HM(X) according to: = = L(X) - HM(X) (8.5) (1+10gmp)x. A sufficient (but not necessary) condition for the difference A to vanish is that each 1(x) takes the specific value l*(x), as defined by (8.6) The above result means that if the codeword length 1(x) of symbol x is chosen to be specifically equal to 1*(x) = -logm p(x), then A = 0 and the mean codeword length L equals the source entropy HM. We note that this optimal length l*(x) represents the information contained in the symbol x, which was defined in Chapter 3 as being I(x) = -logm p(x), and which is a measure of the symbol uncertainty. Thus, the