Information and Coding Theory (TIC)

This subject consists of two parts, which correspond to two objectives. In the first part, the aim is to provide students with Shannon's mathematical theory of information for memoryless discrete channels. In the second part, the objective is for students to be aware of the basic problems in coding and to provide them with the most commonly used techniques for writing error-detection and correction code.

Knowledges

1. To learn the concepts of information of an event and the entropy of a probability distribution Shannon's theorems.
2. To learn the parameters associated with a code block and their relationship to the error-detecting and error-correcting abilities of a code block. To learn the main applications of modular arithmetic to the construction of popular block codes.
   
   
   
   
3. To learn the basic structure of finite fields, mainly those of characteristic 2, and finite dimensional vector spaces over a finite field. To learn the ways of defining a linear code, determining its parameters and decoding using the algorithm based on syndromes.
   
   To learn the particularities of some specific linear codes (specially the perfect codes) and their corresponding error-correction algorithms.
4. To learn the general structure of cyclic codes and Meggit"s algorithm. To learn the binary BCH codes and their error-correction algorithms. To learn Reed-Solomon codes and their application to compact disks.

Abilities

1. To learn how to calculate uncertainty of an event, the entropy of a probability distribution, and the mutual information of two random variables. To learn how to construct Huffman codes. To learn how to calculate the channel capacity of some simple channels.
2. To learn how to calculate the parameters of a code block in simple cases. To learn how to use modular arithmetic in error-detection and error-correction of codes over Z_n.
3. To learn how to express linear codes in terms of generating and control matrices, and switch from one to the other. To learn how to use the syndrome algorithm for error-correction purposes. To learn how to use correction algorithms for Hamming codes, and binary and ternary Golay codes.
4. Know how to relate generating and control matrices of a cyclic code with its generating and control polynomials. Konw how to apply Meggitt's algorithm. Know how to buil binary BCH codes and correct errors with them. Know how to build Reed-Solomon codes and correct erros with them.
   
   
   
   Learn how to apply the Meggit correction algorithm.
   
   
   
   Learn how to construct and correct Reed-Solomon codes.

Competences

1. Ability to solve problems through the application of scientific and engineering methods.
2. Ability to apply mathematical knowledge and logic in solving problems.
3. Know-how to apply the solution cycle to common scientific and engineering problems: specification, coming with ideas and alternatives, design solution strategies, carrying out the strategy, validation, interpretation and evaluation of results. Ability to analyse the process on completion.
4. Ability to relate and structure information from various sources and thus integrate ideas and knowledge.
5. Ability to effectively convey one"s ideas in writing.

(-)

A first partial exam accounting for 25% of total marks and covering course objectives 1, 2 and 3 (information theory).

A second partial exam accounting for 75% of total marks. This covers the remainder objectives (error-correcting codes).

Both exams are eliminatory.

A final exam (100%) if the course is failed using the above formula.

The two exams include both knowledge and skills but are more heavily weighted towards the latter (60-70 %).

• Raymond Hill A First course in coding theory, Clarendon Press, 1986.
• Sweeney, Peter Error control coding : an introduction, Prentice Hall, 1991.
• Shu Lin, Daniel J. Costello Error control coding : fundamentals and applications, Pearson Prentice-Hall, 2004.
• Josep M. Brunat Blay, Enric Ventura Capell Informació i codis , Edicions UPC, 2001.

• Steven Roman Coding and information theory, Springer-Verlag,, 1992.
• F. J. MacWilliams, N. J. A. Sloane The Theory of error correcting codes, North-Holland, 1977.
• Vera Pless Introduction to the theory of error-correcting codes, John Wiley & Sons, 1998.
• Robert J. Mc Eliece The Theory of information and coding, Addison-Wesley Publ. Co., 1982.
• Justesen, Jrn A Course in error-correcting codes, European Mathematical Society, 2004.
• Stephen B. Wicker, Vijay K. Bhargava editores Reed-Solomon codes and their applications, IEEE Press, 1994.
• Jirí Adámek Foundations of coding : theory and applications of error-correcting codes, with an introduction to cryptography and information theory, Wiley, 1991.
• Sebastià Xambó-Descamps Block error-correcting codes : a computational primer, Springer,, 2003.

1. http://www-ma2.upc.es/~brunat/iic.html
   

Students should be able:
(a) to learn about integer class rings and know how to carry out calculations using them;
(b) to know how to construct and carry out operations on finite fields.;
(c) to be familiar with the concepts of dependence and independence, base and dimension, and to know how to operate with matrices (sums and products) and calculate inverses;
(d) to be familiar with logarithmic function and its properties.

AL and MATD should be prerequisites for taking this course.