This course focuses on the applications of Computational Commutative Algebra to error-correcting codes. Coding theory studies algebraic, geometric, and combinatorial methods for constructing error-correcting codes that enable reliable communication and storage over noisy channels.

The course starts with the basics of coding theory, providing an historical overview on block codes, convolutional codes, LDPC codes, and subspace codes. In the second part of the course, we explore the algebraic foundations of rank-metric codes, beginning with their interpretation as spaces of matrices (possibly over more infinite fields). We then introduce a natural and powerful framework for studying these codes: the ring of skew polynomials, introduced by O. Ore, non-commutative polynomials defined via a field automorphism, over a cyclic Galois field extension.

In this course, we will give the basics of coding theory, providing an historical overview on block codes, convolutional codes, LDPC codes, subspace codes. In the second part of the course, we explore the algebraic foundations of rank-metric codes, beginning with their interpretation as spaces of matrices (possibly over more infinite fields). We then introduce a natural and powerful framework for studying these codes: the ring of skew polynomials, non-commutative polynomials defined via a field automorphism, over a cyclic Galois field extension.

Lecture 1: Block Codes and Convolutional Codes

In its most general setting, Coding Theory studies subsets of a vector space V over a (typically finite) field F, equipped with a distance function. The most classical case is the Hamming metric: vectors of length n over F, with distance given by the number of differing coordinates. A (linear) Hamming-metric code is then a k-dimensional subspace of F^n. Such codes are known as block codes.

Beyond block codes, convolutional codes extend coding to sequences of arbitrary length via polynomial generator matrices, and are efficiently decoded by algorithms such as the Viterbi decoder, making them a cornerstone of streaming communication.

Lecture 2: Low-Density Parity-Check Codes

More recent advances exploit graph-theoretic structures. Low-density parity-check (LDPC) codes are defined by sparse parity-check matrices and admit efficient decoding via iterative message-passing algorithms on Tanner graphs, achieving near-capacity performance over a wide range of channels.

Lecture 3: Subspace Codes

In contrast to symbol-based error models, subspace codes are designed for network coding environments where information is transmitted as subspaces of a vector space. Their distance is measured in terms of the dimension of intersections, enabling robustness against packet erasures and random linear mixing.

Lecture 4: Rank-Metric Codes

In 2008, the rank metric gained attention due to applications to network coding and the relation with subspace codes. In 1978, Delsarte introduced rank-metric codes as linear spaces of matrices over finite fields, equipped with the rank distance that measures the minimal rank of their difference.

Lecture 5: Gabidulin Codes

Independently, in 1985, Gabidulin developed rank-metric codes from a polynomial perspective, defining them as evaluation codes of linearized polynomials over finite fields F_{q^m}, and constructing what are now known as Gabidulin codes, optimal codes with respect to the rank metric.

References

• E.M. Gabidulin, Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21 (1985), 3-16.
• R. Kötter and F.R. Kschischang, Coding for errors and erasures in random network coding, IEEE Transactions on Information Theory 54 (2008), 3579-3591.
• O. Ore, Theory of non-commutative polynomials, Annals of Mathematics 34 (1933), 480–508.
• I.S. Reed and G. Solomon, Polynomial codes over certain finite fields, Journal of the society for industrial and applied mathematics 8 (1960), 300-304.

Domains: Algebraic Coding Theory

Sessions:

• Joachim Rosenthal:  5 sessions * 90 minutes

Exercise Sessions for Course 3:

• Exercise Session 1: Compute the designed distance for some specific Reed-Solomon codes, BCH codes and cyclic codes. Go through the Berlekamp Massey algorithm, key for understanding the decoding complexity of BCH codes. Derive the generalized Singleton code for block code.
• Exercise Session 2: Implement some simple decoding algorithms (e.g. bit flipping) for LDPC codes. Study how this algorithms degrade as the density increases. Find a construction of LDPC codes whose Tanner graph has no 4-cycles.
• Exercise Session 3: For some small parameter construct partial spreads. Study subspace codes contained in some sub-variety of the Grassmannian.
• Exercise Session 4: Derive a formula for the number of code words which an MRD code has. Construct subspace codes from good rank metric codes.
• Exercise Session 5: Study the relation of the Gabidulin construction with the Reed-Solomon construction. Study why Gabidulin codes are not suitable for code based cryptography.

Domains: Algebraic Coding Theory

Sessions:

• Gianira Alfarano: 5 sessions * 75 minutes

Related posts