Algebraic Error-Correcting Codes

• Explain the mathematical model of error-correcting codes and its relevance in traditional communication.
• Derive using a constructive method that there exist codes with good parameters.
• Give an algorithm (with exponential running time) for maximum likelihood decoding.
• Define Reed-Solomon codes using polynomials in one variable and derive their basic parameters.
• Prove mathematically the correctness of a decoding algorithm for Reed-Solomon codes and understand how to implement this decoding algorithm in a computer algebra system.
• Define the ways in which transmission can fail, and estimate for a simple error-model the probability of these events.
• Define Reed-Muller codes using polynomials in several variables and derive their basic parameters.
• Prove Bézout’s theorem concerning intersection points of algebraic curves and explain its role in Algebraic Geometry codes.
• Define Algebraic Geometry codes using algebraic curves, derive their basic parameters and describe a decoding algorithm for them.
• Execute a project on algebraic codes and evaluate their efficiency.
• Work effectively in a group on a project with a mathematical and algorithmic core.
• Write a report on a subject within algebraic error-correcting codes.

The course consists of lectures and exercise sessions. We start with introducing the mathematical model in the framework of linear algebra over finite fields, and we investigate the overall boundaries within it: Gilbert-Varshamov bound and exponential time decoding. Next important algebraic codes are introduced, Reed-Solomon codes, where univariate polynomials are used as an algebraic tool. Vi consider an efficient decoding algorithm for these codes and show how it can be implemented in a computer algebra system. After this we generalize to Reed-Muller codes using multivariate polynomials. This in turn motivates the usage of algebraic curves, leading to Algebraic Geometry codes, where Bézout’s theorem is used as an essential tool for analysis.

01018, Understanding of basic concepts from algebra: linear algebra, finite fields, quotient rings, the isomorphism theorem, polynomial rings. Some programming experience.

The course consists of lectures, exercises and project work in groups.

See also the homepage of the Algebra research group: http://algebra.compute.dtu.dk