PaperlayerView exact revision on arXiv

Source-linked AI summary

LCD Cyclic Codes over Finite Fields

Chengju Li, Cunsheng Ding, Shuxing Li

arXiv:1608.02170v2cs.IT

TL;DR

LCD cyclic codes, also known as reversible cyclic codes, are studied because of their coding-theoretic and cryptographic relevance. The paper constructs reversible cyclic-code families over finite fields, analyzes their parameters, and reports many optimal codes alongside a broad treatment of the subject.

  • Problem

    The paper addresses limited knowledge of BCH-code dimensions and minimum distances, especially for code lengths whose q-cyclotomic coset structures are complex.

  • Method

    The paper constructs reversible BCH and other cyclic-code families using q-cyclotomic cosets, then derives dimensions and minimum-distance bounds or values.

  • Results

    The paper determines parameters for several reversible cyclic-code families, including a minimum-distance bound d ≥ 2(δ−1) for C(q,n,δ,0) when n=q^ℓ+1.

  • Takeaways & Limitations

    The constructions provide reversible cyclic codes with generally strong parameters, including many codes reported as optimal.

Abstract

from arXiv · show

In addition to their applications in data storage, communications systems, and consumer electronics, LCD codes -- a class of linear codes -- have been employed in cryptography recently. LCD cyclic codes were referred to as reversible cyclic codes in the literature. The objective of this paper is to construct several families of reversible cyclic codes over finite fields and analyse their parameters. The LCD cyclic codes presented in this paper have very good parameters in general, and contain many optimal codes. A well rounded treatment of reversible cyclic codes is also given in this paper.

I. INTRODUCTION

The paper situates LCD cyclic codes within coding theory and cryptography, then aims to construct reversible cyclic-code families over finite fields and determine their parameters. It also connects these codes to applications, prior constructions, and databases of best-known linear codes.

  • LCD cyclic codes were previously called reversible cyclic codes in the literature.
  • Prior work established constructions, complementary-dual conditions, asymptotically good LCD codes, bounds, and side-channel applications.
  • LCD codes have applications in data storage, communications, consumer electronics, and cryptography.
  • The paper constructs several LCD cyclic-code families, determines their dimensions, and settles or bounds their minimum distances.
  • Many constructed codes are optimal under the best-possible-parameter criterion, with comparisons to Grassl’s database of best-known linear codes.

II. q-CYCLOTOMIC COSETS MODULO n AND AUXILIARIES

This section develops q-cyclotomic cosets and the factorization machinery needed to study cyclic codes over GF(q). Under gcd(n,q)=1, coset structure controls irreducible factors of x^n−1, and a lemma gives explicit coset sizes and leaders in a specified range.

  • The paper assumes gcd(n,q)=1 so that x^n−1 has no repeated factors over GF(q).
  • q-cyclotomic cosets partition the residue ring Z_n, with distinct coset leaders indexing disjoint cosets.
  • Minimal polynomials of powers of a primitive n-th root of unity provide the irreducible factors of x^n−1 over GF(q).
  • Each q-cyclotomic coset size divides ord_n(q), which equals the size of the coset C_1.
  • If q⌊m/2⌋ < n ≤ q^m−1 with m=ord_n(q), then specified cosets have cardinality m and nonzero non-q-divisible indices in the range are coset leaders.

III. CHARACTERISATIONS OF LCD CYCLIC CODES OVER FINITE FIELDS

The paper characterizes LCD cyclic codes through reversibility and reciprocal polynomials. For cyclic codes, being LCD, having a self-reciprocal generator, and closure under inverse roots are equivalent, with a sufficient condition making every code reversible.

  • The reciprocal polynomial reverses the coefficient order of a polynomial with nonzero leading and constant coefficients.
  • A polynomial is self-reciprocal when it coincides with its reciprocal.
  • The same equivalence includes closure of the generator’s roots under inversion: β^-1 is a root whenever β is a root.
  • If −1 is a power of q modulo n, every cyclic code over GF(q) of length n is reversible.
  • For a cyclic code, LCD status is equivalent to reversibility and to having a self-reciprocal generator polynomial.

IV. A CONSTRUCTION OF ALL REVERSIBLE CYCLIC CODES OVER GF(q)

This section constructs and counts reversible cyclic codes by pairing q-cyclotomic cosets and their negatives, using self-reciprocal irreducible factors. It derives a general code count and gives specialized counts for lengths q^m−1 over even and odd prime-power fields.

  • An irreducible polynomial m_a(x) is self-reciprocal exactly when n−a belongs to the q-cyclotomic coset C_a.
  • The least common multiple of m_a(x) and m_{n−a}(x) is self-reciprocal for every a.
  • Cosets can be grouped as C_a ∪ C_{n−a}, and these unions partition Z_n when indexed by coset leaders.
  • The total number of reversible cyclic codes over GF(q) of length n is 2^|Π(q,n)|−1.
  • For (n,q)=(15,2), the construction yields 15 reversible binary cyclic codes of length 15.
  • For n=q^m−1 with odd prime m, the even-q case has only x−1 as a self-reciprocal irreducible divisor, while the odd-q case has x−1 and x+1.

V. BCH CODES

This section defines BCH codes through minimal-polynomial generators and identifies reversible parameter families. It also records dimension results and the main limitations of the available dimension theorem.

  • BCH code definitions: BCH codes C(q,n,δ,b) are cyclic codes defined by a generator polynomial formed from minimal polynomials of consecutive powers of an n-th root of unity.The designed distance is δ, and the Bose distance can strengthen the BCH lower bound.
  • Dimension results: The narrow-sense BCH code C(q,n,δ,1) has dimension k = n−m⌈(δ−1)(1−1/q)⌉ when q⌊m/2⌋ < n ≤ q^m−1 and the stated δ range holds.
  • Limitations: The dimension theorem applies only to narrow-sense BCH codes with small designed distances and is useful only when n is close to q^m−1.
  • Reversible BCH families: Reversible BCH families arise for b = −t with δ = 2t + 2, for odd n with b = (n−t)/2 and δ = t + 2, and for even n with b = (n−2t)/2 and δ = 2t + 2.
  • Known parameters: All these reversible BCH codes satisfy the BCH bound d ≥ δ, but their dimensions are generally difficult to determine.

VI. SOME REVERSIBLE BCH CODES OF LENGTH qℓ+1 OVER GF(q) AND THEIR PARAMETERS

For lengths n = q^ℓ + 1, every cyclic code over GF(q) is reversible, but the relevant cyclotomic-coset structure is difficult. The paper therefore targets dimensions and improved distance bounds for selected families.

  • Reversibility: Every cyclic code of length n = q^ℓ + 1 over GF(q) is reversible.
  • Motivation: The q-cyclotomic cosets modulo q^ℓ + 1 have an extremely complex structure, leaving relatively little prior work on these lengths.
  • Contribution: For m = 2ℓ and n = q^ℓ + 1, the paper determines dimensions of selected reversible cyclic-code families and improves BCH minimum-distance bounds using reversibility.

A. A basic result on q-cyclotomic cosets modulo n

This subsection establishes the cyclotomic-coset structure needed for lengths n = q^ℓ + 1. In particular, it determines the order of q and identifies many coset leaders with full-size cosets.

  • Order calculation: For n = q^ℓ + 1, the multiplicative order satisfies ord_n(q) = 2ℓ.
  • Coset leaders: Every positive a ≤ q^⌊(ℓ−1)/2⌋ + 1 with a not divisible by q is a coset leader, and its q-cyclotomic coset has size 2ℓ.
  • Coset structure: The cosets associated with those nonmultiples of q are pairwise disjoint, while the remaining positive integers in the stated range are not coset leaders.
  • Proof strategy: The proof analyzes q^j a modulo n across four ranges of j to show that the residues exceed a, establishing the coset-leader property.

B. Reversible BCH codes over GF(q) of length n = qℓ+1

The paper uses the coset structure at lengths n = q^ℓ + 1 to construct reversible BCH codes with improved distance bounds and explicit dimensions in several cases. Binary and ternary examples include codes attaining best-known or best-possible cyclic parameters.

  • Distance bounds: For n = q^ℓ + 1, the reversible BCH code C(q,n,δ,0) satisfies d ≥ 2(δ−1), improving the ordinary BCH bound.
  • Limitations: The dimension problem remains difficult in general, despite experimental evidence that the improved minimum-distance lower bound is quite tight.
  • General parameters: For 3 ≤ δ ≤ q^⌊(ℓ−1)/2⌋ + 3, Theorem 17 gives explicit parameters for C(q,n,δ,0) using the coset structure.
  • Binary families: For q = 2, the codes with designed distances 4, 6, 8, and 10 have dimensions 2^ℓ−2ℓ, 2^ℓ−4ℓ, 2^ℓ−6ℓ, and 2^ℓ−8ℓ, respectively, with listed distance guarantees 6, 10, 14, and 18.
  • Examples: Several binary and ternary instances are best possible for cyclic codes, and one ternary instance matches the best known database parameters.
  • Ternary families: For q = 3, the constructed families have parameters [3^ℓ+1,3^ℓ−2ℓ,d ≥4], [3^ℓ+1,3^ℓ−4ℓ,d ≥8], and [3^ℓ+1,3^ℓ−6ℓ,d ≥10].

VII. REVERSIBLE CYCLIC CODES OF LENGTH n = qm −1 OVER GF(q)

This section constructs reversible cyclic codes of length n = q^m − 1 from punctured generalized Reed–Muller codes and analyzes their parameters. The constructions yield several codes with best-known or optimal parameters, while some minimum-distance questions remain open.

  • Construction: The paper constructs reversible cyclic codes R(q,m,ℓ) from punctured generalized Reed–Muller codes R_q(ℓ,m).The construction uses reciprocal generator polynomials and the intersection properties of q-adic weight sets.
  • General construction: Theorem 21 gives a reversible code R(q,m,ℓ) for q(m−1)−2 ≥ ℓ ≥ 1+(q−1)m−⌈(q−1)m/2⌉, with a BCH-based minimum-distance bound.The stated parameter range ensures the required generator-polynomial relation, after which the minimum-distance conclusion follows from the BCH bound.
  • Binary specialization: For q = 2, the construction specializes to reversible cyclic codes R(2,m,ℓ) in the range m−2 ≥ ℓ ≥ m−⌊(m−2)/2⌋.The section presents explicit binary examples within this family.
  • Examples: The examples R(2,5,3) and R(2,6,4) have parameters [31,20,6] and [63,50,6], respectively, and both have the best possible parameters for cyclic codes.Their duals have parameters [31,11,10] and [63,13,24], respectively; the latter is also reported as best possible for linear codes.
  • Examples: The example R(2,6,3) has parameters [63,20,14], while its dual has [63,43,6], reported as best possible parameters.The section also notes that these constructions are generally not BCH codes.
  • Open problem: The exact minimum distance d = 2((q−ℓ_0)q^{m−ℓ_1−1} − 1) for the codes of Theorem 21 is posed as an open problem.The paper does not settle whether this expression always equals the minimum distance.

VIII. TWO CLASSES OF REVERSIBLE BCH CYCLIC CODES OF LENGTH (qm −1)/(q−1) OVER GF(q)

This section develops two families of reversible BCH cyclic codes of length (q^m − 1)/(q − 1), using cyclotomic-coset structure to determine dimensions and distance bounds. Several resulting codes attain best possible parameters for cyclic or linear codes.

  • First BCH family: The section constructs reversible BCH codes C(q,n,2δ,1−δ) with n = (q^m − 1)/(q − 1) for 2 ≤ δ ≤ q⌊(m−1)/2⌋.Their reversibility follows from the structure of the relevant q-cyclotomic cosets, and their distance satisfies d ≥ 2δ.
  • Cyclotomic-coset analysis: The constructions rely on q-cyclotomic coset leaders and show that selected cosets have cardinality m or, in an exceptional case, m/2.The lemmas classify coset leaders in the relevant range and use their intersections with negatives to establish the needed structure.
  • Second BCH family: For even m ≥ 4 and 2 ≤ δ ≤ q^m/2, another family C(q,n,2δ,1−δ) has d ≥ 2δ and dimensions determined by ε.The dimension is 2 when ε ≥ ⌊(q−1)/2⌋ and m⌈(δ−1)(q−1)/q⌉ otherwise.
  • Boundary case: When m is even and δ = q^m/2, the corresponding reversible BCH code has a specialized dimension formula and retains length n = (q^m − 1)/(q − 1).The corollary isolates the largest stated designed-distance case for this family.

IX. CONCLUDING REMARKS

The paper’s concluding contributions construct and analyze several families of reversible cyclic codes over finite fields, including three important length families. Dimensions are determined, distance bounds are derived, and many resulting codes are optimal.

  • The paper constructs all documented reversible cyclic codes over finite fields.
  • It constructs and analyzes reversible cyclic codes of length n = qℓ + 1 over GF(q).
  • It analyzes reversible cyclic codes of length n = q^m − 1 over GF(q).
  • It analyzes reversible cyclic codes of length n = (q^m − 1)/(q − 1) over GF(q).
  • The dimensions of these codes are determined, while BCH-derived lower bounds are established for their minimum distances.The paper conjectures that these lower bounds equal the actual minimum distances in most cases.
  • Many of the constructed codes are optimal because they have the best possible parameters.
Loading 1608.02170v2…