Channel Coding: Algebraic Methods for Communications and Storage

This course focuses on the formal and mathematical basics for the design of coding schemes in digital communication systems. These include schemes for data transmission, data storage and networking. Besides codes that are important for data transmission applications we also investigate codes for the efficient storage and reconstruction of data in distributed systems (locally repairable codes) and codes that can be used to realize data encryption schemes that cannot be cracked by a hypothetical quantum computer. Real applications are always given to discuss practical aspects and implementations of these coding schemes. Many of these applications are illustrated by example code in software (python/MATLAB).

The course starts by introducing the necessary fundamentals of coding theory and information theory, to understand the fundamental limitations of what channel coding can achieve and where it will not be useful to employ channel coding. We introduce abstract and simplified channel models and compute their capacity limits, determining how much data can be transmitted over a channel. The following pictures shows for instance the q-ary symmetric channel, which is used to model a communication with errors and its capacity.

Following the fundamentals, we will introduce the basics of algebra needed to construct codes. We will learn how to construct so-called Galois fields, which form the basis for most algebraic codes. Besides the construction, the implementation of algebra with Galois fields on computer hardware will also be an essential part of the lecture. Based on the algebraic concepts of Galois fields, we will then introduce the code family of generalized Reed-Solomon (GRS) codes, which form the basis for many practical coding schemes. We will both learn how to implement encoders using shift registers, as shown in the following picture and how to carry out decoding.

We will show how algebraic methods can be used to derive a very simple and elegant decoding algorithm, the so-called Berlekamp-Welch algorithm, which is summarized in the following box. The Berlekamp-Welch decoding algorithm is illustrated with MATLAB codes and participants will be able to program their own communication system based on generalized Reed-Solomon codes.

Reed-Solomon codes are used in a variety of communication systems, ranging from deep-space application to optical storage media like, e.g., BluRay discs. Another prominent application of Reed-Solomon codes are the ubiquitous QR-codes, which store information protected with Reed-Solomon codes. For this reason, QR codes are very robust against changes in the data and against errors. After the lecture, participants will be able to understand error correction in QR codes and related applications and apply decoding/error correction. Despite their age, Reed-Solomon codes continue to be employed widely in communication systems and data storage systems due to their outstanding theoretical properties. Another example where Reed-Solomon codes are widely used is, e.g., RAID data storage systems and protection against packet losses in communication networks.

Channel codes form also the basis of future encryption systems. Current asymmetric encryption schemes like RSA are under heavy threats from hypothetical quantum computers running Shor’s algorithm. In order to guarantee security of data in a world with quantum computers, we need to develop novel encryption schemes. One quantum-computer-safe encryption scheme is the so-called McEliece scheme, which uses a code with intentional errors as encryption device. Its security relies on the fact that a general decoding algorithm is hard, unless the specific code construction is known. The specific construction will be obfuscated in the public encryption key, making it hard to crack. The basic concept of the McEliece scheme is illustrated in the following picture.

The lecture concludes with a discussion of coding schemes for storage devices, in particular large-scale data storage in data centers. In such applications, it frequently happens that a single server or storage device fails and needs to be restored. With classical coding schemes, this requires network traffic from various other servers in order to restore the failed device. In the lecture, we will highlight locally repairable codes and regenerating codes, which alleviate this problem and enable the recovery of a failed server/device with minimized network traffic.