A Course in Algebraic Error-Correcting Codes

Description

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