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

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

06/02 - Correction: I forgot a previous appointment; I will be available Wednesday, from 10:00 to 12:30, and Thursday, from 11:30 to 12:30.

05/02 - The grades of the second exam, as well as the updated final grades, have been published. I will be available to discuss any questions about the exam and the grades Wednesday, from 10:00 to 12:00 and from 14:00 to 16:00. If needed, a different office hour may be scheduled on demand.

29/01 - A mistake in the calculation of the final grade has been corrected.

29/01 - The grades of the last homework and of the exam have been published, together with the resulting final grade. Due to the date of this publication, for which I apologize, I'll accept possible suggestions to delay the second exam, scheduled for tomorrow afternoon, for a few days. In any case, I ask each student enrolled in the course to confirm if he or she is willing to take the second exam.

15/01 - Annotations to the lecture notes are allowed, but no other consultation material can be used.

14/01 - Attending hours (correction): I'll be available on Monday, from 10:00 to 12:00 and Tuesday, from 14:00 to 15:30.

12/01 - Exam and attending hours: I recall that the final exam will take place next Wednesday, 17/01, at 10:30, in room P8. The course lecture notes may be used in the exam as consultation material. I'll be available, in my office, next Monday and Tuesday, from 10:00 to 12:00.

27/12 - Homework: The fifth homework assignment is due no later than Tuesday, 09/01. I call everyone's attention that the subject of code concatenation is an integral part of the course and is included in some of the exercises.

18/12 - I had to leave Tecnico now due to a urgent family health problem. I apologize in case I'm not back around 3 p.m. for our class. If that is the case, we'll schedule an extra class. Once again, my apologies for the inconvenience.

04/12 - New Notes and Homework: a new version of Notes VII, on Finite Fields, has been published. The fourth homework assignement consists in Exercise 23, proof of Proposition 67 and Problems 78, 80 and 86 from the updated Notes, and is due Monday, 11/12.

22/11 - Office hour: starting next week, I'll be available in my office every Friday, from 09:30 to 11:00.

13/11 - a mistake in the statement of the first problem in the homework has been corrected.

11/11 - Homework: The third homework assignment is due no later than Monday, 20/11.

11/11 - Unfortunately, I was unable, until now, to publish the new versions of some of the Notes. My apologies for that.

23/10 - The grades of Homework 1 have been published.

16/10 - New Notes and Homework: new version of the first sets of Notes have been published. The second Homework assignment consists of Problems 20, 21 and 25 from Notes II, and problems 44 and 46 from Notes III (these are the new Notes). The assignment is due next Thursday, 26/10.

06/10 - Homework: the correction of the error in the statement of problem 2 was completed. Once again, my apologies.

02/10 - Homework: there was an obvious (?) mistake in the statement of problem 2 which has been corrected. My apologies.

29/09 - Homework: here's the first homework assignment . Because next Thursday is an holiday, this assignment is due no later than Monday, 09/10.

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

New versions

Notes I: Introduction. Source Encoding.

Notes II: Information and Entropy.

Notes III: Channels, Block Codes and Shannon's Theorem.

Notes VII: Finite Fildes.

Older versions

Notes I: Introduction. Source Encoding.