PaperlayerView exact revision on arXiv

Source-linked AI summary

Some quaternary additive codes outperform linear counterparts

Chaofeng Guan, Ruihu Li, Yiting Liu, Zhi Ma

arXiv:2303.07156v4cs.ITmath.IT

TL;DR

Constructing additive codes that outperform linear codes remains challenging, particularly for greater distances at the same lengths and dimensions. The paper develops a symplectic-distance bound and combinatorial constructions based on quasi-cyclic codes. It reports that additive codes can have higher rates in optimal cases and greater distances than same-length, same-dimension linear codes in non-optimal cases.

  • Problem

    Constructing additive codes that outperform linear codes is challenging, especially when seeking greater distance at the same length and dimension.

    Source: §I · p. 1

  • Method

    The paper combines a lower bound for even-index 1-generator quasi-cyclic codes with combinatorial constructions and derivations of additive codes.

    Source: §I · p. 1, §III · p. 3, §V · p. 7

  • Results

    In optimal cases, additive codes can have higher rates than linear codes; in non-optimal cases, they can have larger distances at the same lengths and dimensions.

    Source: §VI · p. 7

  • Takeaways & Limitations

    The constructions yield additive codes that outperform best-known linear codes, including cases with greater distance at matched length and dimension.

    Source: §IV · p. 5, §VI · p. 7

Abstract

from arXiv · show

The additive codes may have better parameters than linear codes. However, it is still a challenging problem to efficiently construct additive codes that outperform linear codes, especially those with greater distances than linear codes of the same lengths and dimensions. This paper focuses on constructing additive codes that outperform linear codes based on quasi-cyclic codes and combinatorial methods. Firstly, we propose a lower bound on the symplectic distance of 1-generator quasi-cyclic codes of index even. Secondly, we get many binary quasi-cyclic codes with large symplectic distances utilizing computer-supported combination and search methods, all of which correspond to good quaternary additive codes. Notably, some additive codes have greater distances than best-known quaternary linear codes in Grassl's code table (bounds on the minimum distance of quaternary linear codes http://www.codetables.de) for the same lengths and dimensions. Moreover, employing a combinatorial approach, we partially determine the parameters of optimal quaternary additive 3.5-dimensional codes with lengths from $28$ to $254$. Finally, as an extension, we also construct some good additive complementary dual codes with larger distances than the best-known quaternary linear complementary dual codes in the literature.

I. INTRODUCTION

Additive codes can have better parameters than linear codes, but practical construction approaches using quasi-cyclic codes remain limited. This paper proposes a symplectic-distance lower bound and combinatorial constructions of additive and complementary-dual codes.

I. INTRODUCTION

  • Additive codes are closed under vector addition but need not be closed under scalar multiplication, so they can have better parameters than linear codes.The introduction also notes their applications in quantum information, computer memory, deep-space communication, and secret sharing.Source: §I · p. 1
  • Quaternary additive codes have been studied for short lengths and low dimensions, while additive complementary dual codes have applications in quantum codes and side-channel resistance.Prior work determined optimal quaternary additive-code parameters through length 12; later work covered lengths through 15 and 2.5-dimensional codes.Source: §I · p. 1
  • Practical approaches for constructing additive codes from quasi-cyclic codes remain lacking, despite their potential to outperform linear codes.The paper proposes a lower bound for even-index 1-generator quasi-cyclic codes and combinatorial construction methods.Source: §I · p. 1
  • The paper constructs additive and additive complementary dual codes that outperform best-known linear or linear complementary dual counterparts.The paper also gives a lower bound on the symplectic distance of even-index 1-generator quasi-cyclic codes.Source: §I · p. 1
  • Magma is used to compute the code parameters reported in the paper.The paper is organized around preliminaries, the symplectic-distance bound, additive-code constructions, and complementary-dual-code constructions.Source: §I · p. 1

II. PRELIMINARIES

The preliminaries section introduces fundamentals of additive and quasi-cyclic codes and points readers to references for further details.

II. PRELIMINARIES

  • The section presents fundamentals of additive and quasi-cyclic codes, with further details referred to prior works.The cited references are,, and.Source: §II · p. 1

A. Additive codes

The section defines additive codes and symplectic codes, then gives a mapping that connects binary symplectic codes with quaternary additive codes. It also specifies how the paper judges when an additive code is better than a linear counterpart.

A. Additive codes

  • An additive code Ca over Fq2 is a subgroup of Fq2^n; its codewords need not remain in the code under scalar multiplication, and its dimension ka is defined over Fq.Source: A. Additive codes · p. 2
  • A symplectic code [2n, k, d_s]_q has minimum symplectic distance d_s, with symplectic weight counting nonzero coordinate pairs.The symplectic inner product is defined over paired coordinates.Source: A. Additive codes · p. 2
  • The map Φ is one-to-one and preserves weight, connecting symplectic codes to additive codes with the same distance.A symplectic [2n, k, d_s]_q code is equivalent to an additive (n, k/2, d_s)_q^2 code; binary symplectic LCD codes correspond to quaternary ACD codes.Source: A. Additive codes · p. 2
  • The paper calls an additive code better than its linear counterpart when it has greater distance at matched length and dimension, higher information rate at matched length and distance, or fills a distance gap.For even k, the strict same-dimension comparison requires the linear code to have distance below d_s.Source: A. Additive codes · p. 2

B. Cyclic codes and quasi-cyclic codes

The section represents cyclic codes through polynomials in a quotient ring and describes quasi-cyclic codes through block shifts and circulant matrices. These representations underlie the generator-matrix construction presented here.

B. Cyclic codes and quasi-cyclic codes

  • A cyclic code corresponds to an ideal in F_q[x]/⟨x^n−1⟩ generated by a unique monic nonzero polynomial.The generator polynomial has degree n−k, and the parity-check polynomial is (x^n−1)/g(x).Source: B. Cyclic codes and quasi-cyclic codes · p. 2
  • A quasi-cyclic code of index ℓ is closed under a cyclic shift of each length-n block.Its generator matrix is formed from blocks of circulant matrices, each determined by a polynomial in the quotient ring.Source: B. Cyclic codes and quasi-cyclic codes · p. 2
  • A circulant matrix is represented by a polynomial whose coefficients are its first-row entries.This correspondence lets the generator-matrix blocks be specified by polynomials.Source: B. Cyclic codes and quasi-cyclic codes · p. 2

III. BOUND ON THE SYMPLECTIC WEIGHT OF 1-GENERATOR QUASI-CYCLIC CODES OF INDEX EVEN

For even-index 1-generator quasi-cyclic codes, the paper derives a symplectic-distance lower bound and uses polynomial-based constructions to obtain additive codes. Its examples include optimal additive codes that outperform corresponding best-known quaternary linear codes.

III. BOUND ON THE SYMPLECTIC WEIGHT OF 1-GENERATOR QUASI-CYCLIC CODES OF INDEX EVEN

  • The even-index theorem bounds symplectic distance under polynomial coprimality and degree conditions.It relates the distance to the minimum Hamming distance of the cyclic code generated by g(x).Source: §III · p. 3
  • A binary cyclic code [31, 5, 16]_2 produces an optimal additive code (31, 2.5, 24)_4, better than the optimal linear code [31, 2, 24]_4.The paper uses the concatenation and Griesmer-bound argument to establish optimality.Source: §III · p. 3
  • The resulting codes retain cyclic or quasi-cyclic structure, which the authors say makes them easier to encode and decode.Source: §III · p. 3
  • Theorem 2 constructs additive codes from a 1-generator quasi-cyclic code using two polynomials that satisfy stated coprimality and degree conditions.The proof forms a new generator from the original code and the two polynomials.Source: §III · p. 3
  • The constructions yield optimal (127, 3.5, 96)_4 and (254, 3.5, 192)_4 additive codes, outperforming corresponding linear codes [127, 3, 96]_4 and [254, 3, 192]_4.The 127-length code comes from a binary quasi-cyclic code; a further construction gives the 254-length code.Source: §III · p. 4
  • The selected polynomials guarantee the distance lower bound but not necessarily the best distance; computation can help find stronger codes.The search can start from the generator polynomial of a good cyclic code.Source: §III · p. 4

IV. GOOD QUATERNARY ADDITIVE CODES OUTPERFORM BEST-KNOWN LINEAR CODES

The section combines quasi-cyclic and combinatorial constructions to produce quaternary additive codes with strong parameters. It reports examples that outperform best-known linear codes and determines optimal 3.5-dimensional additive-code parameters for lengths 28–254.

IV. GOOD QUATERNARY ADDITIVE CODES OUTPERFORM BEST-KNOWN LINEAR CODES

  • (63, 5, 45)4 has greater minimum distance than the best-known linear code [63, 5, 44]4.The additive code's real distance is computed as 45 after mapping the symplectic code.Source: §IV · p. 4
  • Lemma 6 gives an optimal additive (40, 3.5, 30)4 code that performs better than the optimal linear code [30]4.The construction selects (5, 2, 4)4 as an auxiliary code.Source: §IV · p. 5
  • The (47, 35, 7)4 quasi-cyclic additive code surpasses the best-known linear code [47, 35, 6]4.The code is found by computer search using a 2-generator quasi-cyclic construction.Source: §IV · p. 5
  • The (55, 10.5, 29)4 code extends to (56, 10.5, 30)4, and augmenting it gives (56, 11, 30)4, which surpasses [56, 11, 29]4.The extension also fills the gap between the cited linear codes [56, 10, 32]4 and [56, 11, 29]4.Source: §IV · p. 5
  • A combination method yields optimal quaternary additive 3.5-dimensional codes for lengths 28–254, most outperforming optimal 3-dimensional linear codes.The authors report that these comparisons are omitted for space.Source: §IV · p. 5
  • For the same length and dimension, the additive codes have greater distance than best-known linear codes; other comparisons use codes with higher information rates.In the latter comparisons, the additive codes have twice as many codewords for the same length and distance.Source: §IV · p. 5

V. SOME QUATERNARY ACD CODES HAVE LARGER DISTANCE THAN LCD CODES

This section combines ACD codes with trace-Hermitian self-orthogonal codes and uses further constructions to obtain ACD codes with larger distances than known quaternary LCD codes. A computer-aided search also finds ACD codes that exceed the best-known LCD distances at matching lengths and dimensions.

V. SOME QUATERNARY ACD CODES HAVE LARGER DISTANCE THAN LCD CODES

  • Combining an ACD code with a trace-Hermitian self-orthogonal code yields an ACD code with distance at least d1 + d2.An example gives a (29, 4, ≥19)4 ACD code, outperforming the [29]4 LCD code in.Source: §V · pp. 6–7
  • By Lemma 8, combining Φ(Cs2) and Φ(Cs3) yields a (27, 4, ≥18)4 ACD code, which performs better than the 4 LCD code in the literature.Source: §V · p. 7
  • A second construction combines nested ACD codes with a trace-Hermitian self-orthogonal auxiliary code, giving distance min{δ + d1, d2}.Using a (6, 3, 4)4 auxiliary code yields a (30, 4, 20)4 ACD code, exceeding the (30, 4, 19)4 code in.Source: §V · p. 7
  • ACD extend, shorten, and puncture operations produce codes with parameters (n + i, k, ≥d), (n − i, k − i, ≥d), and (n − i, k, ≥d − i), respectively.The stated conditions are i ≥ 1 for extension and i ≤ k or i ≤ d for shortening or puncturing, respectively.Source: §V · p. 7
  • The computer-aided ACD codes have greater distances than the best quaternary LCD codes at the same lengths and dimensions.The comparison is reported in Table IV.Source: §V · p. 7, Table IV · p. 7

VI. CONCLUSION

The paper reports additive codes with higher rates than linear codes in optimal cases and larger distances at matching lengths and dimensions in non-optimal cases. Whether optimal additive codes can exceed optimal linear counterparts in distance remains open.

VI. CONCLUSION

  • The paper reports higher code rates for optimal additive codes and larger distances than linear codes of matching lengths and dimensions in non-optimal cases.The authors leave open whether optimal additive codes can have greater distance than optimal linear counterparts.Source: §VI · pp. 7–8
  • Most additive codes in the paper can also be considered additive cyclic codes, whose construction the authors identify as a future research direction.Source: §VI · p. 8

APPENDIX

The appendix abbreviates generator polynomials and marks derived codes with construction labels.

APPENDIX

  • Generator polynomials are abbreviated by listing coefficients in ascending order, with indices indicating successive elements of the same coefficient.For example, 1 + x^2 + x^3 + x^4 over F2 is written as 1013; derived codes use labels including Au, DoubleAu, and X.Source: APPENDIX · p. 8
Loading 2303.07156v4…