Computational algebra (2019/2020)

Course code
4S001098
Name of lecturer
Francesca Mantese
Coordinator
Francesca Mantese
Number of ECTS credits allocated
6
MAT/02 - ALGEBRA
Language of instruction
English
Location
VERONA
Period
II semestre dal Mar 2, 2020 al Jun 12, 2020.

Learning outcomes

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.

Syllabus

The course consists of lectures. Notes and homework will be provided.

-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

 Author Title Publisher Year ISBN Note W. C. Huffman, V. Pless Fundamentals of Error-Correcting Codes Cambridge University Press 2010 0521131707 Lint, J. H. van Introduction to Coding Theory (Edizione 2) Springer-Verlag Berlin Heidelberg 1992 978-3-662-00174-5

Assessment methods and 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 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).