Conway and Sloane, Sphere Packings, Lattices, and Groups, is one of the best survey-style mathematics books ever written. It certainly does extend the discussion to error-correcting codes, even though the main theme is Euclidean sphere packings.
The most important relationship between sphere packings and codes, but not the only relationship, is as an extended analogy that leads to uniformly argued bounds and constructions. The Hamming metric and the Euclidean metric are both metrics, and in both cases you are interested in minimum distance sets which you then call codes. But the analogy is more than just that. The Hamming cube is a normed abelian group, and Euclidean space is a normed abelian group. In both cases, there is a special interest in codes that are subgroups. If a code is a subgroup, you only have to check the minimum distance from the 0 vector. Also, recall Pontryagin-Fourier duality: If $A$ is a locally compact abelian group, it has a dual group $hat{A}$ which is its group of characters. The Hamming cube and Euclidean space are both canonically self-dual in the sense that $A = widehat{A}$. If $C subset A$ is a subgroup, it has a dual code $C^perp$ which is by defining the subgroup $widehat{A/C} subset widehat{A} = A$. (In other words, it is the group of characters which are trivial on $C$.) $C$ has a weight enumerator, which in the Euclidean case is called a theta series, and the weight enumerators of $C$ and $C^perp$ are related by a transform. The transform is called the MacWilliams identity in the Hamming case and the Jacobi identity in the Euclidean case. The transform is possible because of another fundamental common feature: The Hamming cube and Euclidean space are both 2-point transitive metric spaces.
When a metric space is 2-point transitive, there is a construction due to Delsarte for finding upper bounds on the sizes of codes. The construction is a certain relaxation of the distance distribution of a code that reduces the bound to linear programming. The linear constraints come from harmonic analysis. It is easier in the compact case, and it is explained in SPLAG in the Hamming case and the spherical geometry case, where you get bounds on kissing numbers and other spherical sphere packings. The Euclidean case of the linear programming bounds were later developed by Henry Cohn and Noam Elkies.
On the construction side, the analogy is sometimes more direct. A sphere packing in $mathbb{R}^n$ could be both a subset of $mathbb{Z}^n$ and union of cosets of $(2mathbb{Z})^n$. When it is of this form, it comes from a binary code in $(mathbb{Z}/2)^n$. Sometimes this leads to the best known sphere packing. In fact one of these cases uses the Best code with $n=10$ (found by Marc Roelant Best). A simpler case is the $D_n$ lattice, which is the best packing when $n=3$, the best lattice packing when $n=4,5$, and thought to be the best packing in these two cases. It comes from the parity code.
This transfer of codes extends to another important case, codes over $mathbb{Z}/k$ in the Lee metric. The Lee metric on $mathbb{Z}/k$ is just the graph metric of a $k$-gon, i.e., $d(a,b) = |a-b|$ if you choose residues so that the answer is at most $k/2$. The standard Lee metric on $mathbb{Z}/k$ is the $ell^1$ sum of the Lee distances on the factors, but you can view this as an approximation to $ell^2$ and again lift to the Euclidean case. You can obtain the $E_8$ lattice with way with $k=4$. $k=4$ is also separately because $mathbb{Z}/4$ is isometric to $(mathbb{Z}/2)^2$, and this isometry leads to what are called $mathbb{Z}/4$-linear binary codes. (The Best code mentioned in the previous paragraph is one of these codes.)
No comments:
Post a Comment