 of any coding algorithm out of an infinite number of possibilities, and how close the algorithm is to the ideal or optimal case. The following chapter will take us one step further into the issue of coding optimality, which stems from the introduction of Huffman codes. Exercises 8.1 (B): Consider the source with the symbols, codewords and associated probabilities shown in Table 8.6: Table 8.6 Data for Exercise 8.1. Symbol Codeword x Probability p(x) Calculate the mean codeword length, the source entropy and the coding efficiency. 8.2 (M): Provide an example of a dyadic source for a dictionary of four binary code- words, and illustrate Shannon's source-coding theorem. 20 See T.M. Cover and J.A. Thomas, Elements of Information Theory (New York: John Wiley & Sons, 1991). Information coding 8.3 (M): Assign a uniquely decodable code to the symbol-source distribution given in Table 8.7. Table 8.7 Data for Exercise 8.3. Symbol x Probability p(x) 0.302 0.105 0.125 0.025 0.177 0.016 0.250 1.000 and determine the corresponding coding efficiency. 8.4 (M): Assign a Shannon-Fano code to the source defined in Exercise 8.3, and deter- mine the corresponding coding efficiency n = H(X)/L**(X) and code redundancy L**(X) - H(X). Optimal coding and compression The previous chapter introduced the concept of coding optimality, as based on variable- length codewords. As we have learnt, an optimal code is one for which the mean codeword length closely approaches or is equal to the source entropy. There exist several families of codes that can be called optimal, as based on various types of algorithms. This chapter, and the following, will provide an overview of this rich subject, which finds many applications in communications, in particular in the domain of data compression. In this chapter, I will introduce Huffman codes, and then I will describe how they can be used to perform data compression to the limits predicted by Shannon. I will then introduce the principle of block codes, which also enable data compression. Huffman codes As 