Single-Course English 5 ECTS

Algebraic Error-Correcting Codes

Overall Course Objectives

This is a course on mathematics focusing on the engineering application Error-Correcting Codes. The main fields we will be concerned with are discrete mathematics, linear algebra and algebra.

Error-correcting codes is not about programming, but about representing digital information in ways that are resilient to noise. It is used everywhere: in a DVD which can play flawlessly even though it is scratched, or a satellite-transmission which is understood through bad atmospheric disturbance in stormy weather, or in high-speed internet and in mobile phone conversations. Without exaggerating, the information era would have been impossible without Coding Theory.

Many of the best error-correcting codes we know are based on ingenious algebraic methods. This course is an introduction to the fundamental mathematical model in coding theory and to the mathematics behind these algebraic codes. In order for the recipient to correct whatever errors appear, efficient algorithms will be needed for handling the algebraic objects; we will deal with this using both theoretical algebra and using a computer-algebra system.

In a nutshell: we will use algebra and develop algebraic methods to find good solutions to mathematical problems inspired by applications of Error-correcting Codes.

Learning Objectives

  • 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 of discrete mathematics and algebra.

Course Content

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.

Recommended prerequisites

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

Teaching Method

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

Faculty

Remarks

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

See course in the course database.

Registration

Language

English

Duration

13 weeks

Institute

Compute

Place

DTU Lyngby Campus

Course code 01405
Course type Candidate
Semester start Week 5
Semester end Week 19
Days Fri 8-12
Price

7.500,00 DKK

Registration