Error control coding: Algebraic and convolutional codes (ECC)

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.

Visualizing decoding of Reed-Solomon codes using polynomials