(In English)

Error Control Coding (ECC)

Correcting errors in data transmission and data storage (Summer Semester)

Due to the current COVID-19 outbreak no in-class sessions will be held until further notice. However, video recordings of the lectures as well as annotated lecture notes will be provided on ILIAS. Regular Q&A sessions will be held via Webex.

Synopsis

Transmission errors are inherent to digital communication systems both in space (from here to there) and time (from now to later, usually referred to as storage systems). A transmitted "1" might be detected as a "0" by the receiver and vice versa due to various channel impairments. A naive approach for correcting such errors is to transmit every bit, say, n > 1 times and then take a majority decision at the receiver. This simple example already explains the basic concept behind error control coding: a block of information (here a single bit) is augmented by redundancy (here n-1 bits) in order to correct a certain number of transmission errors (here no more than (n-1)/2 bits). In other words, transmission rate is traded in for error resilience. In this self-contained course we develop the theory and practice of the two most fundamental types of error control codes, that is, algebraic codes and convolutional codes. We introduce the necessary math of finite fields, their polynomial rings, and their vector spaces. We go all the way from the basic repetition code described above to the elaborate generalized Reed–Solomon (RS) codes and their state-of-the art list decoding algorithms. Along the way, we meet important constructions such as the parity check, Hamming, cyclic redundancy check, Bose–Chaudhuri–Hocquengheim (BCH) codes as well as locally recoverable codes for distributed data storage. After that, we show how a more engineering-oriented approach to error control coding leads to convolutional codes.

Table of Contents (Subject to Change)

  1. Motivation and introduction
  2. Your new best friend, F2, and its vector space
  3. A simple error control game
  4. Detecting errors
  5. Some nomenclature
  6. Binary Hamming codes
  7. Hamming distance
  8. Hard decision decoders
  9. Calculating dmin
  10. Systematic encoders and encoder inverses
  11. Identical and equivalent codes
  12. Groups and cosets
  13. Standard array decoders
  14. Bounds on code parameters
  15. Asymptotic bounds for linear codes
  16. Prime fields and extension fields
  17. Roots of polynomials
  18. Polynomial evaluation codes
  19. GRS, RS, and BCH codes
  20. Convolutional codes
  21. The free distance
  22. Punctured convolutional codes
  23. Catastrophic convolutional codes
  24. Terminated convolutional codes
  25. Trellis diagrams
  26. The hard decision Viterbi algorithm
  27. The soft decision Viterbi algorithm

Educational Objectives

At the end of the course, students should have a good understanding of the most important algebraic and convolutional codes on a level that is sufficient to understand research papers in the area. Students should be able to choose appropriate code constructions and parameters when provided with the constraints of a communication or storage system. They should also be able to implement efficient encoders and decoders.

Course Information

6 ECTS Credits

Lecturer Dr.-Ing. Christian Senger
Time Slots Monday, 9:45-11:15 and 14:00-15:30
Lecture Hall PW47, 2.314 (INÜ Auditorium)
Weekly Credit Hours 4
Christian  Senger
Dr.-Ing.

Christian Senger

Deputy Director

To the top of the page