Error control coding: Algebraic and convolutional codes (ECC)

  Lecture
Lecturer Dr.-Ing. Christian Senger
Date Mon 8:00 - 9:30 am and 2:00 to 3:30 pm
Lecture hall Pfaff. 47, V 47.04 (PF47/U1/V 47.04)
Extent 4 credit hours, 6 credit points
Language English
Learning outcome 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 system. They should also be able to implement efficient encoders and decoders.
Content

Transmission errors are inherent to digital communication systems both in space (from here to there) and time (from now to later). 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, and Bose–Chaudhuri–Hocquengheim (BCH) codes. After that, we show how a more engineering-oriented approach to error control coding leads to convolutional codes.

Closely related to this course, though curricularly independent, are the courses “Information Theory” and a follow-up lecture on error control coding using iterative and graph-based methods, both offered by the Institute of Telecommunications. The first one explores the fundamental limits of digital data  transmission with error control coding while the latter one uses certain algebraic and convolutional codes as building blocks for powerful code constructions used in current standards and communication systems.

Literature Roth: Introduction to Coding Theory (Cambridge University Press)
Figure Example

ecc_4

Visualizing decoding of Reed-Solomon codes using polynomials

Material ILIAS

Module description in LSF