2021 EIMS Intensive Lecture Series
Error-Correcting Codes
Ewha Institute of Mathematical Sciences (EIMS)
Ewha Womans University, S. Korea, Nov 2021
Error-Correcting Codes
Ewha Institute of Mathematical Sciences (EIMS)
Ewha Womans University, S. Korea, Nov 2021
DAY 1. Error-Correcting Codes: The Beginning
The development of error-correcting codes began in the late 1940s with the work of Richard W. Hamming, Claude E. Shannon, and Marcel J. E. Golay. We begin by showing how to encode 16 messages in both efficient and inefficient ways to protect against errors, eventually leading to Hamming’s initial code. A model for a communication channel is presented along with a discussion of Shannon’s work that guarantees efficient communication can occur over that channel. Decoding procedures and the analysis of Hamming’s code are given. Finally the problem of finding perfect codes is discussed leading to Golay’s generalization of the Hamming code and to the codes that bear his name.
DAY 2. Error-Correcting Codes: Self-Dual Codes
The basics of linear codes over fields are given including dual codes using both the Euclidean and Hermitian inner products and the MacWilliams Identity relating the weight enumerator of a code and its dual. Several self-dual codes are given and general observations about these codes are made, which motivate the discussion of divisible codes. The Gleason–Peirce–Ward Theorem and Gleason polynomials are described. Bounds can be placed on the minimum distance of self-dual codes, which lead to the notion of extremal codes. Finally techniques used for the classification and enumeration of self-dual codes are discussed, and the current status of the classification problem is described.
DAY 3. Error-Correcting Codes: Additive Codes and Their Generalizations
Additive codes were developed in the late 1990s to aid in the construction of codes for quantum computing. Additive codes over fields naturally generalize to codes over fields that are closed under addition and closed under multiplication by elements from a subfield. These generalized additive codes also include classical linear codes; it is natural to ask how the standard results of the theory of linear codes change in the additive code context. Appropriate inner products are given and dual codes are described. The classification and enumeration of self-dual codes is presented. Finally the theory of cyclic generalized additive codes is discussed along with counting and classification results.