Scientific Disciplinary Sector (SSD)
MAT/02 - ALGEBRA
II semestre dal Mar 2, 2020 al Jun 12, 2020.
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.
The course consists of lectures. Notes and homework will be provided.
-Review on groups, rings, 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
-Encoding, decoding, and Shannon’s Theorem
- 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
|W. C. Huffman, V. Pless
||Fundamentals of Error-Correcting Codes
||Cambridge University Press
|Lint, J. H. van
||Introduction to Coding Theory
||Springer-Verlag Berlin Heidelberg
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 abstact and the computational point of view
- they support their argumentation with mathematical rigor.
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 2019).