# Error Control Coding (ECC)

(In English)

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

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

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

### Lectures and Exercises

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

Deputy Director