In this monograph, we develop the theory of one of the most fascinating topics in coding theory, namely, perfect codes and related structures. Perfect codes are considered to be the most beautiful structure in coding theory, at least from the mathematical side. These codes are the largest ones with their given parameters. The book develops the theory of these codes in various metrics — Hamming, Johnson, Lee, Grassmann, as well as in other spaces and metrics. It also covers other related structures such as diameter perfect codes, quasi-perfect codes, mixed codes, tilings, combinatorial designs, and more. The goal is to give the aspects of all these codes, to derive bounds on their sizes, and present various constructions for these codes. The intention is to offer a different perspective for the area of perfect codes. For example, in many chapters there is a section devoted to diameter perfect codes. In these codes, anticodes are used instead of balls and these anticodes are related to intersecting families, an area that is part of extremal combinatorics. This is one example that shows how we direct our exposition in this book to both researchers in coding theory and mathematicians interested in combinatorics and extremal combinatorics. New perspectives for MDS codes, different from the classic ones, which lead to new directions of research on these codes are another example of how this book may appeal to both researchers in coding theory and mathematicians. The book can also be used as a textbook, either on basic course in combinatorial coding theory, or as an advance course in combinatorial coding theory.
Author(s): Tuvi Etzion
Publisher: World Scientific Publishing
Year: 2022
Language: English
Pages: 435
City: Singapore
Contents
Preface
1. Introduction
1.1 Notes
2. Definitions and Preliminaries
2.1 Nonlinear Codes
2.2 Finite Fields
2.3 Linear Codes
2.4 Definitions of Perfect Codes
2.5 Notes
3. Combinatorial Designs and Bounds
3.1 Steiner Systems and Generalized Steiner Systems
3.2 Orthogonal Designs
3.4 The Plotkin Bound and the Griesmer Bound
3.5 Association Schemes
3.6 Notes
4. Linear Perfect Codes
4.1 Hamming Codes
4.2 Golay Codes
4.3 Diameter Perfect Codes
4.4 Notes
5. Nonlinear Perfect Codes
5.1 Constructions of Nonlinear Perfect Codes
5.2 Weight and Distance Distribution
5.3 Intersection Numbers
5.4 Intersection Numbers of Linear Codes
5.5 Full-Rank Perfect Codes
5.6 Kernels of Perfect Codes
5.7 Enumeration of Nonequivalent Codes
5.8 On the Nonexistence of Perfect Codes
5.9 Playing Games of Hats
5.10 Notes
6. Density and Quasi-Perfect Codes
6.1 Density of Codes
6.2 The Johnson Bound
6.3 The Preparata Code
6.4 Quasi-Perfect Codes
6.5 Asymptotically 2-Perfect Covering Codes
6.6 Dense Covering Codes with Radius Three
6.7 Notes
7. Codes with Mixed Alphabets
7.1 Perfect Mixed Codes with Radius One
7.2 Byte-Correcting Codes and Group Partitions
7.3 Codes with a Larger Radius and Mixed Steiner Systems
7.4 Notes
8. Binary Constant-Weight Codes
8.1 The Johnson Scheme
8.2 Configuration Distribution
8.3 Steiner Systems Embedded in a Perfect Code
8.4 Tradeoff between Length, Weight, and Radius
8.5 Regularity of Codes
8.6 Regularity of Codes with Radius One
8.7 Regularity of Codes with Larger Radius
8.8 Diameter Perfect Codes
8.9 Notes
9. NonBinary Constant-Weight Codes
9.1 Nonbinary Perfect Constant-Weight Codes
9.2 Nonbinary Diameter Perfect Constant-Weight Codes
9.3 Diameter Perfect Codes for which w = n
9.4 Codes with Alphabet Size 2k + 1 for which w = n − 1
9.5 Generalized Steiner Systems
9.6 Maximum Distance Separable Constant-Weight Codes
9.7 Codes for which d = w + 1
9.8 Multiple Orthogonal Arrays Constant-Weight Codes
9.9 Comparison Between Maximum Size Anticodes
9.10 Notes
10. Codes Over Subspaces
10.1 No Perfect Codes in the Grassmann Scheme
10.2 q-Steiner Systems
10.3 Normal Spreads
10.4 Nonexistence of Perfect Codes in the Projective Space
10.5 Rank-Metric Codes
10.6 Constant-Dimension MDS Codes
10.7 Notes
11. The Lee and the Manhattan Metrics
11.1 The Lee and the Manhattan Distances
11.2 Lattice Tiling
11.3 Constructions of Perfect Codes
11.4 Diameter Perfect Codes
11.5 Nonperiodic Codes and Enumeration of Codes
11.6 The Nonexistence of Perfect Codes
11.7 Notes
12. Tiling with a Cluster of Unit Cubes
12.1 Group Splitting
12.2 Crosses and Semi-Crosses
12.3 Codes for Nonvolatile Memories and Quasi-Crosses
12.4 Tiling with Quasi-Crosses
12.5 Tiling with Notched Cubes
12.6 Notes
13. Codes in Other Metrics
13.1 Perfect Deletion-Correcting Codes
13.2 Perfect Poset-Correcting Codes
13.3 Perfect Burst-Correcting Codes
13.4 Notes
Bibliography
