Information and Coding Theory (TIC)

This subject consists of two parts, which correspond to two objectives. In the first part, the aim is to get acquainted with Shannon's information theory (mainly for memoryless discrete channels). In the second part, the goal is to understand the basic problems in coding engineering and acquire the most commonly used techniques to address them.

Knowledges

1. To know the concepts of information of an event and the entropy of a probability distribution. To know the concepts of information source, information chanel and the significance of Shannon's theorems.
2. To know the parameters associated with a block code and their relationship to its error-detecting and error-correcting capabilities. To understand the main applications of modular arithmetic to the construction of popular block codes.
   
   
   
   
3. To know the basic structure of finite fields (Galois fields), mainly those of characteristic 2, and of the finite dimensional vector spaces over a finite field. To know the basic methods of defining a linear code, determining its parameters and decoding it by the syndrome algorithm.
   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 applications (mainly 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 for binary and ternary Golay codes.
4. To know how to relate generating and control matrices of a cyclic code with its generating and control polynomials. To know how to apply Meggitt's algorithm. To know how to buil binary BCH codes and correct errors with them. To know how to build Reed-Solomon codes and correct erros with them.

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, generating ideas and alternatives, designing 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, to integrate ideas and knowledge.
5. Ability to effectively convey one's ideas in writing.

With specific materials that will be made available on the Web, the methodology relies on the following elements: lectures to present general topics, problem solving on given assignments, group discussions on agreed issues (panel format), a writing assignment (including an implementation of an algorithm studied in class), and a final "class conference" to present the papers.

P1 (15%): A written examen on the objectives 1, 2 i 3 (information theory).

P2 (45%): A written examen on the remaining objectives (error-correcting codes).

P (20%): Assessment of problem solving in class.

T (20%): Assessment of the written assignment and its presentation.

P1+P2 (60%) can be recovered, or improved, in a final exam.

Note: P1 and P2 include test knowledge and abilities, with more weight for 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.edu/sxd/Teaching/TIC12.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.