Introdução à Teoria de Códigos (Introduction to Coding Theory) (Semestre 1 - 2021-2022)

 
Licenciatura em Matemática Aplicada e Computação e Mestrado em Matemática Aplicada



Docente: Pedro Martins Rodrigues - pmartins@math.tecnico.ulisboa.pt



Information and News        Program     Bibliography       Notes and Problems

Evaluation       Grades



Information and News

10/10 - The file Notes II has been published.

06/10 - Here's the updated information on attending hours: Wednesday, 16:00-17:00 Meeting ID: 823 5757 7843 Thursday, 10:00-11:00 Meeting ID: 857 4613 3500

Extra periods may be scheduled occasionally, if necessary.

04/10 - Attending hours: the attending hours will be online. The schedule and access information for the Zoom sessions are: Wednesday, 16:00-17:00 Meeting ID: 823 5757 7843 Thursday, 10:00-11:00 Meeting ID: 857 4613 3500

01/10 The file Notes II has been published; this will be the subject of our next lecture.

29/09 I haven't fixed a schedule of attending periods yet. In the meanwhile, if anyone wants to ask questions or discuss any topic from the Notes, he or she may send me a message.

29/09 The file Notes I has been published. The following Homework must be delivered until 08/10: Exercise 20 and Problems 33, 34, 35d) and 39c).

26/09 A slightly more detailed program is now available. The order of subjects is only approximate.

25/09 A short file of warm-up Notes has been published.

13/09 - A short presentation. The main theme of this course is the theory of error-correcting codes, giving emphasis to its algebraic and combinatorial aspects, and with an introduction to information theory. Topics include source encoding and entropy, linear codes, combinatorial and algebraic constructions of codes, code parameters, probability of error and Shannon's theorem, an introduction to finite fields, cyclic codes, convolutional codes, etc. The course covers also a review of enumeration, based on generating functions. The prerequisites are very modest: a basic knowledge of linear algebra and rudiments of probability theory are sufficient.

The notes, homework, exams, etc, as well as oral presentation in class, will be in English. Naturally, questions in class and solutions for homework and exams may be given in English or Portuguese (or French, if necessary).

The course is intended to depend strongly on the autonomous work of students, encouraging independent study and exploration of subjects. With this purpose, course notes will be given, whenever feasible, in advance, and as most as possible in the form of problems. Error-correcting codes is, by its own nature, both a theoretical and practical area. In order to perform computations and experiment with concrete codes, students are encouraged to use appropriate software (Mathematica or MatLab, for example). However, this is not a course on computation; its essence is on the understanding, deduction and proof of general properties of codes and of its encoding and decoding capabilities.

A detailed outline of the course will be published soon.



Program

Uniquely decipherable and instantaneously decipherable codes. Prefix codes, rooted trees and decision problems. Kraft’s inequality and McMillan’s theorem. Entropy function and its properties. Shannon’s noiseless channel theorem. Mathematical model of communication channels. Fundamentals of block codes: length, size and Hamming distance. Minimal distance decoding and information rate. Error detection and error correction capability. Linear codes over finite fields. Syndrome decoding. Dual codes, self-dual and self-orthogonal codes. Basic parameters and bounds for block codes. Decision schemes, ideal observer and maximum likelihood decoding. Shannon’s theorem for noisy channels. Finite Fields, polynomials, and their application to coding: cyclic codes, Reed–Solomon codes, subfield and trace codes. Weight enumerators and MacWilliams equalities. Introduction to convolutional codes.




Bibliography

A Course in Error-Correcting Codes, J. Justensen & T. Høholdt, EMS Textbooks in Mathematics, 2017.

Coding Theory, a First Course, San Ling & Chaoping Xing, Cambridge University Press, 2004.

Fundamentals of Error-Correcting Codes, W. Cary Huffman & Vera Pless, Cambridge University Press, 2003.

Coding and Information Theory, Steven Roman, Springer-Verlag, 1992.

Notes and Problems

Warm-up notes 1      Notes I

Notes II

Notes III



Evaluation
The evaluation consists of homeworks and an exam (03/02/22).

The final grade, in a scale 0-20, will be given by 0.5 Exam+0.5 Homework.



Grades