Teaching code

4S001098

Teacher

Francesca Mantese

Coordinator

Francesca Mantese

Credits

6

Language

English

Scientific Disciplinary Sector (SSD)

MAT/02 - ALGEBRA

Period

Semester 1 dal Oct 2, 2023 al Jan 26, 2024.

Courses Single

Authorized

Lessons timetable Moodle Seminars 0

Learning objectives

The course provides an introduction to coding theory, presenting the main notions and techniques for error detection and correction. In particular, linear and cyclic codes will be studied. The topics will be presented both from a teorical and computational point of view. In the first part of the course, basic concept from algebra will be reviewd, and finite fields will be deeply studied. At the end of the course the students will know the main terminology and main results in coding theory, the more relevant linear and cyclic codes, their decoding algorithms. They will be able to produce rigorous arguments and proofs on these topics and they will be able to read articles and advanced texts.

Prerequisites and basic notions

Linear algebra, basic notions of group theory and ring theory

Program

-Review on groups, rings, fields.
-finite fields
- Polynomials and the Euclidean Algorithm
- Primitive elements
- Constructing finite fields
-Cyclotomic cosets and minimalpolynomials
-Basic concepts of linear codes
- Linear codes, generator and parity check matrices
- Dual codes
- Weights and distances
- New codes from old
- Permutation equivalent codes
-More general equivalence of codes
-Hamming codes
-Encoding, decoding, and Shannon’s Theorem
- Encoding
- Decoding and Shannon’s Theorem
- Sphere Packing Bound, covering radius, and perfect codes
-Basic theory of cyclic codes
- Idempotents and multipliers
- Zeros of a cyclic code
- Minimum distance of cyclic codes
- BCH codes 168
- Reed–Solomon codes
- Decoding BCH codes
- The Peterson–Gorenstein–Zierler Decoding Algorithm
- The Berlekamp–Massey Decoding Algorithm
- The Sugiyama Decoding Algorithm
- Coding for the compact disc
- Codes from algebraic geometry
- Generalized Reed–Solomon codes revisited
- Classical Goppa codes
- The Gilbert–Varshamov Bound revisited
- Goppa codes meet the Gilbert–Varshamov Bound

Bibliography

Didactic methods

Lectures and exercises will take place in presence. Notes, exercises and additional material will be made available on the Moodle platform of the course.

Learning assessment procedures

The exam consists of a written test in which the student will have to solve exercises and answer to question on the topics presented during the lectures. The mark obtained in the written examination can be improved by the mark obtained for the homework and/or by an optional oral examination. Only students who have passed the written exam will be admitted to the oral examination. If positive, the mark obtained in the written test will be valid until the last session of the present academic year (February 2025)

Evaluation criteria

To succes in the exam, students must show that:
- they know and understand the fundamental concepts of coding theory
- they have abilities in solving problems in coding theory, both from the abstract and the computational point of view
- they support their argumentation with mathematical rigor.

Criteria for the composition of the final grade

The final mark will be given by the mark obtained in the written test, or by the average of the written test and the oral exam.

Exam language

Inglese