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.
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.