a codes. Table 10.7 Data for Exercise 10.1. Symbol 0.302 0.105 0.125 0.025 0.177 0.016 0.125 0.125 10.2 (T): Determine the Fibonacci code of order m = 3 up to the first 31 integers (Clue: use level-three coding and be sure to obtain a prefix code). 10.3 (M): Determine the Golomb code with parameter m = 3 for integers i = 0 to i = 12. 10.4 (M): Determine the step-by-step coding assignment in dynamic Huffman coding for the message sequence AABCABB and the resulting coding efficiency. 10.5 (M): Determine a Lempel-Ziv code for the 30-symbol sequence ABBABBBABABAAABABBBAABAABAABAE and the corresponding compression rate. 17 See: D. .A. Lelewer and D.S. Hirschberg, Data compression. Computing Surveys, 19 (1987), 261-97, www.ics.uci.edu/~dan/pubs/DataCompression.html and D.J.C. MacKay, Information Theory, Inference and Learning Algorithms (Cambridge: Cambridge University Press, 2003). Error correction This chapter is concerned with a remarkable type of code, whose purpose is to ensure that any errors occurring during the transmission of data can be identified and automatically corrected. These codes are referred to as error-correcting codes (ECC). The field of error-correcting codes is rather involved and diverse; therefore, this chapter will only constitute a first exposure and a basic introduction of the key principles and algorithms. The two main families of ECC, linear block codes and cyclic codes, will be considered. I will then describe in further detail some specifics concerning the most popular ECC types used in both telecommunications and information technology. The last section concerns the evaluation of corrected bit-error-rates (BER), or BER improvement, after information reception and ECC decoding. Communication channel The communication of information through a message sequence is made over what we shall now call a communication channel or, in Shannon's terminology, a channel. This channel first comprises a source, which generates the message symbols from some alphabet. Next to the source comes an encoder, 