A new class of self-orthogonal linear codes and their applications

Yaozong Zhang, Dabin Zheng, Xiaoqiang Wang

TL;DR

Researchers have developed a new method for constructing self-orthogonal linear codes using a "defining-set" approach based on trace functions over finite fields. These codes are not only mathematically elegant but also yield new quantum codes and Linear Complementary Dual (LCD) codes that reach or approach theoretical optimality bounds.

What Problem Does This Paper Address?

In the world of error-correcting codes, self-orthogonal codes are a special breed where every codeword is "perpendicular" to every other codeword (including itself) under a standard inner product. They are the bedrock of quantum error correction—specifically for the construction of Calderbank-Shor-Steane (CSS) codes.

The challenge in coding theory is finding codes that are "optimal." An optimal code packs the maximum amount of information (dimension) with the best possible error-correction capability (minimum distance) for a given length. While many codes exist, finding new classes with explicitly determined weight distributions (knowing exactly how many codewords have a certain number of non-zero entries) is difficult. This paper fills a gap by providing a systematic construction for codes that are often Maximum Distance Separable (MDS) or Almost MDS (AMDS), meaning they sit at the absolute limit of what physics and math allow.

Methods

The authors use a defining-set approach. Instead of building a generator matrix at random, they define the code $C_D$ using a specific set $D$ of elements from a finite field $\mathbb{F}_{p^s}$.

  1. The Defining Set: They chose a set $D$ based on the solutions to a trace equation involving squares: $D = \{(x, y) \in (\mathbb{F}_{p^s}, \mathbb{F}_{p^s}) : \text{Tr}_{s_1}^s(x^2 + y^2) = 0\}$.
  2. Weight Distribution Analysis: To understand the code's performance, they employed Gauss sums and the orthogonal properties of additive characters. This allowed them to calculate the exact weight of every codeword, leading to the detailed tables (Tables 1-3) seen in the paper.
  3. Augmentation: They utilized an augmentation technique to extend these codes, making them suitable for practical applications like quantum and LCD codes.
  4. Verification: The theoretical results were verified using Magma, a high-level computer algebra system designed for computations in algebra, number theory, and combinatorics.

Datasets

As a theoretical mathematics and coding theory paper, it does not use traditional "big data" datasets. Instead, it relies on:

  • Grassl’s Code Tables: The standard benchmark for the "best known" linear codes.
  • Bierbrauer’s Quantum Tables: A repository of the best-known parameters for quantum twisted codes.
  • Magma Simulations: Used to generate specific examples (like Example 4.2 and 5.12) to prove the existence of codes with the calculated parameters.

Key Insights and Ideas

  • The Power of Trace Functions: By carefully choosing the divisors ($s_1, s_2$) of the field extension degree $s$, the authors could "tune" the properties of the code.
  • Dual Code Optimality: A major "aha" moment in the paper is that the duals of these constructed codes are frequently AMDS. In coding theory, the dual code is often just as important as the code itself, and finding AMDS duals is a significant result.
  • Self-Orthogonality via Divisibility: The authors leveraged a lemma stating that if a code is $p$-divisible (all weights are multiples of the field characteristic $p$) and contains the all-ones vector, it is self-orthogonal. This provided a shortcut to proving the codes were suitable for quantum applications.

Key Results

  • Classical Optimality: Several constructed codes, such as the $[33, 28, 3]_3$ and $[225, 218, 3]_3$ codes, were proven to be optimal according to Grassl’s tables.
  • Quantum Advancements: The paper produced new quantum codes that are MDS or AMDS relative to the quantum Singleton bound. For instance, they found a $[[33, 27, 3]]_3$ AMDS code that outperforms the best-known quantum twisted codes previously recorded.
  • LCD Codes: They introduced a new class of LCD codes (useful for resisting side-channel attacks in cryptography) that are "almost optimal" according to the sphere packing bound.
  • Locally Recoverable: The authors demonstrated that their codes are "locally recoverable," meaning a single lost coordinate can be repaired by looking at only a small subset of other coordinates—a vital feature for distributed storage systems.

Limitations and Future Work

The paper primarily focuses on odd prime powers ($q = p^s$). The behavior of these specific defining sets in fields of characteristic 2 (binary fields) is not explored here, which is a common area for follow-up research given the prevalence of binary systems in hardware.

Additionally, while the weight distributions are explicit, the construction relies on specific relationships between divisors $s_1$ and $s_2$. Future work could investigate more complex defining sets (e.g., higher-degree polynomials beyond $x^2 + y^2$) to see if even better parameters can be squeezed out of the defining-set method.

Summary updated

Abstract

Self-orthogonal codes are a subclass of linear codes that are contained within their dual codes. Since self-orthogonal codes are widely used in quantum codes, lattice theory and linear complementary dual (LCD) codes, they have received continuous attention and research. In this paper, we construct a class of self-orthogonal codes by using the defining-set approach, and determine their explicit weight distributions and the parameters of their duals. Some considered codes are optimal according to the tables of best codes known maintained at \cite{Grassl} and a class of almost maximum distance separable (AMDS) codes from their duals are obtained. As applications, we obtain a class of new quantum codes, which are MDS or AMDS according to the quantum Singleton bound under certain conditions. Some examples show that the constructed quantum codes have the better parameters than known ones maintained at \cite{Bierbrauer}. Furthermore, a new class of LCD codes are given, which are almost optimal according to the sphere packing bound.
BibTeX
@misc{zhang2023new,
  author = {Yaozong Zhang and Dabin Zheng and Xiaoqiang Wang},
  title = {{A new class of self-orthogonal linear codes and their applications}},
  year = {2023},
  eprint = {2311.18432},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2311.18432},
}
Figure