Saltar al contingut Saltar a navegacio

# Information and Coding Theory (TIC)

Credits Dept. Type Requirements
7.5 (6.0 ECTS) MAII
• Elective for DIE
• Elective for DCSFW
• Elective for DCSYS
AL - Prerequisite for DIE , DCSYS , DCSFW
MATD - Prerequisite for DIE , DCSYS , DCSFW

## Instructors

 Person in charge: Sebastian Xambo Descamps (sebastia.xamboupc.edu) Others: (-)

## General goals

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.

## Specific goals

### 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.

## Contents

Estimated time (hours):

 T P L Alt Ext. L Stu A. time Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Information and entropy.
T      P      L      Alt    Ext. L Stu    A. time Total
3,0 4,0 0 0 0 7,0 0 14,0
Informació. Entropia i propietats. Informació mútua.

2. Source codes and channel codes.
T      P      L      Alt    Ext. L Stu    A. time Total
3,0 4,0 0 0 0 7,0 0 14,0
Codis de longitud variable. Desigualtat de Kraft. Codis de Huffman. Extensions d'una font. Primer teorema de Shannon.
Capacitat d'un canal. Esquemes de decisió. Teorema de la codificació amb soroll.

3. Block codes.
T      P      L      Alt    Ext. L Stu    A. time Total
3,0 4,0 0 0 0 7,0 0 14,0
Distància de Hamming. Radis de tangència i de cobertura. Detecció i correcció d'errors. El problema fonamental de la teoria de codis.
Els codis ISBN, DNI, EAN, etc. Codi decimal corrector de dos errors.

4. Linear codes.
T      P      L      Alt    Ext. L Stu    A. time Total
5,0 6,0 0 0 0 13,0 0 24,0
Finite fields and vector spaces over finite fields. Linear codes. Generating and control matrices. Error-correction by syndromes. Erasures. Operations with linear codes.
Perfect codes. Hamming codes. The binary and ternary Golay codes.

5. Cyclic codes.
T      P      L      Alt    Ext. L Stu    A. time Total
7,0 8,0 0 0 0 18,0 0 33,0
Ideals en anells de polinomis sobre cossos finits. Polinomis generador i de control. Codificació. Exemples de codis cíclics. Correcció. El mètode de Meggit.

6. Reed-Solomon codes.
T      P      L      Alt    Ext. L Stu    A. time Total
5,0 5,0 0 0 0 10,0 0 20,0
Versió original dels codis de Reed-Solomon. La transformada de Fourier finita. Correcció. Codis de Reed-Solomon retallats. Descens de cos. Aplicació al disc compacte.

7. Binary BCH codes
T      P      L      Alt    Ext. L Stu    A. time Total
6,0 8,0 0 0 0 14,0 0 28,0

 Total per kind T P L Alt Ext. L Stu A. time Total 32,0 39,0 0 0 0 76,0 0 147,0 Avaluation additional hours 6,0 Total work hours for student 153,0

## Docent Methodolgy

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.

## Evaluation Methodgy

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 %).

## Basic Bibliography

• 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.

## Complementary Bibliography

• 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.

## Previous capacities

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.

Compartir