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

 
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

12/02 - A mistake in the formula for the grades was corrected. My apologies.

12/02 - A table with the grades of the Exam and Final grades has been published. I will be available to clarify any questions about the exam and grading. Students willing to take a second exam must send me, as soon as possible, a message expressing their preference for a date near the end of this week.

07/02 - A table with the grades of the homeworks has been published.

25/01 - Exam: some examples of past exams have been published. It should be noticed that they were given not exactly the same time and that possibly some results were later included in the Notes. I'll send an e-mail message with information on the exam.

17/01 - Final Exam: The final exam will take place on 30/01, as discussed previously.

17/01 - An old version of Notes XI, on Convolutional Codes, has been published. My apologies for the delay.

28/12 - Homework Assignement to be delivered until 06/01 (either in class or by e-mail): Exercises 59, 60 and 61 from Notes VIII, exercise 35 from Notes X.

28/12 - Notes X have been published.

12/12 - The class scheduled to Wednesday 14/12 will not take place and will be replaced to a convenient date.

04/12 - Notes IX have been published.

01/12 - Due to a mild health problem, tomorrow's attending period is cancelled. It will be replaced later.

22/11 - The regular schedule for attending hours has changed: Thursday, from 3.00 to 4.00, by Zoom (link: https://videoconf-colibri.zoom.us/j/98545216673) and Friday, from 10:00 to 11.00, in my office.

16/11 - Notes VIII have been published. Homework assignment, to be delivered until 25/11: proofs of Propositions 67 and 68, Problems 71, 72, 73 and 76, all from Notes VII. The grades of the previous homeworks will be published as soon as possible, my apologies for the delay.

25/10 - I will not be able to be present for today's attending hour, due to a personal problem. My apologies for the possible inconvenience. We may decide a substitution session if needed.

25/10 - Notes VI and VII have been published. There will be a new version of Notes VI as soon as possible.

17/10 - Homework Assignement to be delivered until 28/10 (either in my office or by e-mail): proof of Proposition 43, Problems 54, 56, 59, 60, and proof of Proposition 67, all from Notes III.

16/10 - Notes V have been published.

14/10 - I'll probably arrive at my office this afternoon only at 2.00, or even a bit later. My apologies for the possible inconvenience.

11/10 - Notes IV (an old version) have been published.

27/09 - Homework Assignement to be delivered until 07/10 (either in my office or by e-mail): proof of Lemma 22, Problems 33, 34, 40, 43, all from Notes I.

27/09 - Today there will be no attending hour due to Prof. Cristina Sernadas last lecture.

21/09 - The regular schedule for attending hours will be Tuesday, from 4.30 to 5.30, by Zoom (link: https://videoconf-colibri.zoom.us/j/98545216673) and Friday, from 1.30 to 2.30, in my office.

21/09 - Notes II and III have been published.

14/09 - Classes start Monday, 19/09 with a presentation and introduction to the course. The first set of Notes has been published.

29/07 - Presentation: This short presentation gives an informal overview of the subject and structure of the course.



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

Notes I: Introduction. Source Encoding.

Notes II: Transmission Channels and Conditional Entropy.

Notes III: Channel Encoding. Linear Codes.

Notes IV: Channels and Codes. Shannon's Theorem.

Notes V: Bounds for Code Parameters.

Notes VI: Weight Enumerators.

Notes VII: Finite Fields.

Notes VIII: Cyclic Codes.

Notes IX: Reed-Solomon Codes.

Notes X: Algebraic Constructions of Codes.

Notes XI: Convolutional Codes.

Exam (example 1)

Exam (example 2)

Exam (example 3)

Exam (example 4)



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

HomeWorks

HomeWork, Exam and Final Grade