This textbook provides a rigorous mathematical perspective on error-correcting codes, starting with the basics and progressing through to the state-of-the-art. Algebraic, combinatorial, and geometric approaches to coding theory are adopted with the aim of highlighting how coding can have an important real-world impact. Because it carefully balances both theory and applications, this book will be an indispensable resource for readers seeking a timely treatment of error-correcting codes.
Early chapters cover fundamental concepts, introducing Shannon’s theorem, asymptotically good codes and linear codes. The book then goes on to cover other types of codes including chapters on cyclic codes, maximum distance separable codes, LDPC codes, p-adic codes, amongst others. Those undertaking independent study will appreciate the helpful exercises with selected solutions.
A Course in Algebraic Error-Correcting Codes suits an interdisciplinary audience at the Masters level, including students of mathematics, engineering, physics, and computer science. Advanced undergraduates will find this a useful resource as well. An understanding of linear algebra is assumed.
Author(s): Simeon Ball
Series: Compact Textbooks in Mathematics
Edition: 1
Publisher: Birkhäuser
Year: 2020
Language: English
Pages: 176
Tags: Entropy, Finite Fields, Codes
Preface
Table of Parameters for Codes in the Text
Contents
1 Shannon's Theorem
1.1 Entropy
1.2 Information Channels
1.3 System Entropies and Mutual Information
1.4 Decoding and Transmission Rate
1.5 Shannon's Theorem
1.6 Comments
1.7 Exercises
2 Finite Fields
2.1 Definitions and Construction
2.2 Properties of Finite Fields
2.3 Factorisation of Cyclotomic Polynomials
2.4 Affine and Projective Spaces over Finite Fields
2.5 Comments
2.6 Exercises
3 Block Codes
3.1 Minimum Distance
3.2 Bounds on Block Codes
3.3 Asymptotically Good Codes
3.4 Comments
3.5 Exercises
4 Linear Codes
4.1 Preliminaries
4.2 Syndrome Decoding
4.3 Dual Code and the MacWilliams Identities
4.4 Linear Codes and Sets of Points in Projective Spaces
4.5 Griesmer Bound
4.6 Constructing Designs from Linear Codes
4.7 Comments
4.8 Exercises
5 Cyclic Codes
5.1 Basic Properties
5.2 Quadratic Residue Codes
5.3 BCH Codes
5.4 Comments
5.5 Exercises
6 Maximum Distance Separable Codes
6.1 Singleton Bound
6.2 Reed–Solomon Code
6.3 Linear MDS Codes
6.4 MDS Conjecture
6.5 Comments
6.6 Exercises
7 Alternant and Algebraic Geometric Codes
7.1 Subfield Subcodes
7.2 Generalised Reed–Solomon Codes
7.3 Alternant Codes Meeting the Gilbert–Varshamov Bound
7.4 Algebraic Geometric Codes
7.5 Algebraic Geometric Codes Surpassing the Gilbert–Varshamov Bound
7.6 Comments
7.7 Exercises
8 Low Density Parity Check Codes
8.1 Bipartite Graphs with the Expander Property
8.2 Low Density Parity Check Codes
8.3 Decoding LDPC Codes
8.4 Comments
8.5 Exercises
9 Reed–Muller and Kerdock Codes
9.1 Binary Reed–Muller Codes
9.2 Decoding Reed–Muller Codes
9.3 Kerdock Codes
9.4 Non-binary Reed–Muller Codes
9.5 Comments
9.6 Exercises
10 p-Adic Codes
10.1 p-Adic Numbers
10.2 Polynomials over the p-Adic Numbers
10.3 p-Adic Codes
10.4 Codes over Z/phZ
10.5 Codes over Z/4Z
10.6 Comments
10.7 Exercises
Hints and Answers to Selected Exercises
Bibliography
Index
