Griesmer and Optimal Linear Codes from the Affine Solomon-Stiffler Construction

Hao Chen

TL;DR

This paper introduces a novel geometric framework for constructing "affine" and "modified affine" Solomon-Stiffler codes. By deleting specific subspaces from affine spaces, the author generates numerous new infinite families of optimal linear codes and provides a simplified, unified method for determining their exact weight distributions.

What Problem Does This Paper Address?

In coding theory, one of the "Holy Grails" is finding linear codes that achieve the Griesmer bound—a fundamental limit on how short a code can be for a given dimension and minimum distance. Codes that meet this bound are called Griesmer codes, and those that come close are termed "optimal" or "almost optimal."

While Solomon and Stiffler introduced a famous construction for such codes back in 1965, two major hurdles remained:

  1. Weight Distribution: Calculating exactly how many codewords of each weight exist in these codes is mathematically grueling and has only been solved for very specific cases.
  2. Complexity of Modern Methods: Recent breakthroughs in finding optimal codes often rely on complex techniques like Gray images of codes over finite rings. These methods can be highly technical and sometimes obscure the underlying geometric structure of the codes.

This paper seeks to bridge these gaps by providing a simpler, geometric way to build and analyze these high-performance codes.

Methods

The author shifts the perspective from projective geometry (the traditional home of Solomon-Stiffler codes) to affine geometry.

  • Affine Solomon-Stiffler Codes: The construction starts with all nonzero vectors in an affine space $\mathbb{F}_q^k$ and deletes vectors belonging to a set of disjoint subspaces.
  • Modified Affine Solomon-Stiffler Codes: This variation picks specific representatives from the vectors (scaling them by elements of a subgroup) to create codes that are even closer to the Griesmer bound.
  • Geometric Weight Calculation: Instead of using complex algebraic transforms, the author determines weight distributions by analyzing how hyperplanes in the vector space intersect the deleted subspaces. This "counting" approach is more intuitive and reveals why certain codes have only a few distinct weights (e.g., two-weight or three-weight codes).

Datasets

As a theoretical mathematics paper, it does not use "datasets" in the machine-learning sense. Instead, it uses:

  • Grassl’s List (codetables.de): A well-known database of the best-known linear codes. The author uses this as a benchmark to show that their new construction can replicate (and provide a structural explanation for) many previously documented optimal codes.
  • Finite Fields ($\mathbb{F}_q$): The codes are constructed over various finite fields, specifically focusing on $q \leq 9$.

Key Insights and Ideas

  • Unified Structure: Many optimal codes previously thought to be "special cases" or requiring complex ring-theoretic constructions are actually just (modified) affine Solomon-Stiffler codes.
  • Flexibility of Affine Space: Moving to affine space allows for more "room" to delete subspaces compared to projective space, leading to a wider variety of code parameters.
  • Subcode Optimality: A surprising "aha moment" is that taking a codimension-one or two subcode of a known Griesmer code often results in a new code that is itself distance-optimal.
  • Puncturing for Performance: The paper proves that puncturing a Griesmer code at a position within its minimum-weight support can yield another distance-optimal code, providing a systematic way to "shrink" codes while maintaining high performance.

Key Results

  • New Infinite Families: The paper successfully constructs several new infinite families of $q$-ary Griesmer and optimal codes with 2, 3, 4, and 5 weights.
  • Table of Success: Table 1 and Table 6 in the paper list dozens of specific codes (e.g., $[52, 4, 34]_3$, $[206, 5, 136]_3$, $[100, 3, 80]_5$) that are proven to be optimal or near-optimal using this new construction.
  • Simplification: The author demonstrates that their geometric method reaches the same results as recent complex papers in IEEE Transactions on Information Theory (2017, 2019) but with much less restrictive conditions and simpler proofs.

Limitations and Future Work

  • Griesmer Defect: The author notes that if the number of deleted subspaces ($h$) becomes very large, the "Griesmer defect" (the gap between the code and the theoretical bound) can increase.
  • Projective vs. Affine: While the paper shows that projective Solomon-Stiffler codes are a special case of the modified affine version, there is still room to explore if other projective constructions can be "affined" to find even better parameters.
  • Decoding Algorithms: The paper focuses on construction and weight distribution; it does not discuss efficient decoding algorithms for these specific new families of codes, which would be a natural next step for practical engineering applications.

Summary updated

Abstract

In their fundamental paper published in 1965, G. Solomon and J. J. Stiffler invented infinite families of codes meeting the Griesmer bound. These codes are then called Solomon-Stiffler codes and have motivated various constructions of codes meeting or close the Griesmer bound. In this paper, we give a geometric construction of infinite families of affine and modified affine Solomon-Stiffler codes. Projective Solomon-Stiffler codes are special cases of our modified affine Solomon-Stiffler codes. Several infinite families of $q$-ary Griesmer, optimal, almost optimal two-weight, three-weight, four-weight and five-weight linear codes are constructed as special cases of our construction. Weight distributions of these Griesmer, optimal or almost optimal codes are determined. Many optimal linear codes documented in Grassl's list are re-constructed as (modified) affine Solomon-Stiffler codes. Several infinite families of optimal or Griesmer codes were constructed in two published papers in IEEE Transactions on Information Theory 2017 and 2019, via Gray images of codes over finite rings. Parameters and weight distributions of these Griesmer or optimal codes and very special case codes in our construction are the same. We also indicate that more general distance-optimal binary linear codes than that constructed in a recent paper of IEEE Transactions on Information Theory can be obtained directly from codimension one subcodes in binary Solomon-Stiffler codes.
BibTeX
@misc{chen2024griesmer,
  author = {Hao Chen},
  title = {{Griesmer and Optimal Linear Codes from the Affine Solomon-Stiffler Construction}},
  year = {2024},
  eprint = {2406.10825},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.10825},
}
Figure