urce with five symbols, called A, B, C, D, and E, with the associated probabilities shown below: x = A p(x) = 0.05 8.5 Optimizing coding efficiency Codewords Figure 8.1 Coding tree for the source x = {A, B, C, D, E} with associated probability distribution p(x) = {0.05, 0.2, 0.05, 0.4, 0.3}. This source entropy is easily calculated to be H = 1.946 bit/symbol. One method of assigning a code to each of these symbols is to draw a logical coding tree, as shown in Figs. 8.1 and 8.2. The two figures show that each leaf of the coding tree represents a unique codeword. In both figures, the symbols shown at the right are placed in decreasing order of probability. The coding tree thus assigns each codeword according to successive choices between and 1 as the branches split up. In Fig. 8.1, for instance, symbol D is assigned the codeword 0, meaning that the other source symbols, A, C, B, and E, should be assigned codewords beginning with a 1, and SO on. Alternatively (Fig. 8.2), we can assign 0 as the leftmost codeword bit of symbols D, and E, and 1 to all others, and SO on. It is straightforward to calculate the mean codeword length from Eq. (8.4), which gives L = 2.0 bit/symbol and L = 2.3 bit/symbol, for the two coding trees, respectively. The coding efficiencies are found to be 97.3% and 84.6%, respectively, showing that the first code (Fig. 8.1) is much closer to optimality that the second code (Fig. 8.2). In the last case, the efficiency is relatively low because we have chosen a minimum codeword length of 2 bits, as opposed to one bit in the first case. In these examples, the choice of codewords (not codeword lengths) seemed to be arbitrary, but in fact such a choice obeyed some implicit rules. First, different symbols should be assigned to strictly different codewords. In this case, the code is said to be nonsingular. Second (and as previously seen), the code should be uniquely decodable, meaning that an uninterrupted string of codewords leads to only one and strictly one symbol-sequence Information coding Table 8.4