PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Ternary Cyclic Codes from Monomials

Cunsheng Ding, Tor Helleseth

arXiv:1305.0061v1cs.ITmath.IT

TL;DR

Cyclic codes offer efficient encoding and decoding, and prior work used planar monomials to construct optimal ternary cyclic codes. This paper uses APN and other monomials over GF(3^m) to construct codes with the same parameters, and presents nine open problems.

  • Problem

    The paper studies how to construct optimal ternary cyclic codes with parameters [3^m-1, 3^m-1-2m, 4] using monomials beyond the previously used planar monomials.

    Source: §I · p. 1

  • Method

    The paper uses APN monomials and other monomial classes over GF(3^m) to construct ternary cyclic codes.

    Source: §I · p. 1

  • Results

    The paper reports optimal ternary cyclic codes with parameters [3^m-1, 3^m-1-2m, 4] from planar monomials and APN monomials over GF(3^m).

    Source: §V · p. 4, §VI · p. 7

  • Takeaways & Limitations

    The paper presents nine open problems on optimal ternary cyclic codes.

    Source: §I · p. 1

Abstract

from arXiv · show

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. Perfect nonlinear monomials were employed to construct optimal ternary cyclic codes with parameters $[3^m-1, 3^m-1-2m, 4]$ by Carlet, Ding and Yuan in 2005. In this paper, almost perfect nonlinear monomials, and a number of other monomials over $\gf(3^m)$ are used to construct optimal ternary cyclic codes with the same parameters. Nine open problems on such codes are also presented.

I. INTRODUCTION

Cyclic codes support efficient encoding and decoding in storage and communication, and the paper uses monomials over GF(3^m) to construct optimal ternary cyclic codes with parameters [3^m-1, 3^m-1-2m, 4].

I. INTRODUCTION

  • A linear [n,k,d] code is a k-dimensional subspace of GF(p)^n, and cyclicity means codewords remain in the code after a one-position cyclic shift.The minimum nonzero Hamming weight is d.Source: §I · p. 1
  • A cyclic code corresponds to an ideal in GF(p)[x]/(x^n−1), generated by a monic polynomial of least degree.The associated parity-check polynomial is (x^n−1)/g(x).Source: §I · p. 1
  • Cyclic codes have applications in storage and communication because they offer efficient encoding and decoding algorithms.The passage also names consumer electronics, data transmission, broadcast systems, and computer applications.Source: §I · p. 1
  • APN monomials and other monomial classes over GF(3^m) are used to construct optimal ternary cyclic codes with parameters [3^m-1, 3^m-1-2m, 4].The paper also presents nine open problems on such codes.Source: §I · p. 1

II. PRELIMINARIES

The preliminaries establish notation and introduce the function classes and cosets used later in the paper.

II. PRELIMINARIES

  • The section fixes basic notation for use throughout the paper.Source: §II · p. 1
  • It introduces almost perfect nonlinear and planar functions for use in subsequent sections.Source: §II · p. 1
  • It also introduces q-cyclotomic cosets for use in subsequent sections.Source: §II · p. 1

A. Some notation fixed throughout this paper

This subsection fixes the paper’s standing notation and identifies the code-table collection it calls the Database.

A. Some notation fixed throughout this paper

B. The p-cyclotomic cosets modulo n = pm −1

This subsection defines p-cyclotomic coset terminology modulo n and states a coset-length result for a particular gcd condition.

B. The p-cyclotomic cosets modulo n = p^m −1

C. Perfect and almost perfect nonlinear functions on GF(q)

The section introduces APN and planar functions, then motivates using these function classes over GF(3^m) to construct optimal ternary cyclic codes. It contrasts their availability over odd-characteristic fields with the absence of planar functions over GF(2^m).

III. THE CODES DEFINED BY PAIRS OF MONOMIALS

The section defines cyclic codes C(1,e) through a pair of monomials and describes their dimension. It narrows the paper's focus to ternary codes, where many monomial classes yield optimal codes.

  • C(1,e) is generated by the product of the minimal polynomials of α and α^e, and its dimension is n−(m+ℓ_e), where ℓ_e is the size of e's p-cyclotomic coset.The code is defined by the pair of monomials x and x^e over GF(q).Source: §III · p. 3
  • Earlier results link binary C(1,e) codes to APN monomials and treat odd-characteristic planar monomials; for p>3 with ℓ_e=m, the minimum distance is 2 or 3.Source: §III · p. 3
  • The paper studies p=3 and proves that C(1,e) is optimal for many classes of monomials x^e over GF(3^m).Source: §III · p. 3

IV. A BASIC THEOREM ABOUT THE TERNARY CYCLIC CODES C(1,e)

For ternary C(1,e) with ℓ_e=m and e outside C_1, the basic theorem characterizes exactly when the code has parameters [3^m−1, 3^m−1−2m, 4]. Its proof connects the weight-2 and weight-3 codeword tests to the conditions for attaining that distance.

  • [3^m−1, 3^m−1−2m, 4] holds exactly when e is even, (x+1)^e+x^e+1=0 has only x=1 in GF(3^m)*, and (x+1)^e−x^e−1=0 has only x=0 in GF(3^m).The theorem assumes e∉C_1 and ℓ_e=m.Source: §IV · p. 3
  • A weight-2 codeword is absent exactly when e is even.Source: §IV · p. 3
  • The weight-3 analysis reduces, by symmetry, to two coefficient cases and equations tested for solutions outside {0,1}.Source: §IV · pp. 3–4
  • The Sphere Packing bound gives d≤4, so satisfying C1, C2, and C3 yields d=4.Source: §IV · pp. 3–4
  • At these parameters, the ternary linear code is optimal because its minimum distance is maximal for the fixed length and dimension.Source: §IV · p. 4

V. THE OPTIMAL CYCLIC CODES DEFINED BY PLANAR MONOMIALS xe OVER GF(3m)

The section gives planar-monomial criteria for constructing optimal ternary cyclic codes, including two exponent families with explicit parameter conditions. It also presents an example and compares its dual code with the best known parameters.

  • For planar or APN x^e, the proof establishes e even, gcd(e,3^m−1)=2, ℓ_e=m, and e∉C_1.Source: §V · p. 4
  • If x^e is planar over GF(3^m), C(1,e) is an optimal ternary cyclic code with parameters [3^m−1, 3^m−1−2m, 4].Source: §V · p. 4
  • Known planar monomials include x^(3h+1) when m/gcd(m,h) is odd and x^((3h+1)/2) when gcd(m,h)=1 and h is odd.For (m,h)=(4,3), e=14 gives a code with parameters [80,72,4].Source: §V · p. 5
  • The dual of C(1,e) is a ternary cyclic code with parameters [80,8,48], matching the best known ternary linear code in the Database with those parameters; the upper bound on minimum distance for length 80 and dimension 8 is 49.Its weight enumerator is 1+1320x^48+2400x^51+80x^54+1920x^57+840x^60.Source: §V · p. 5
  • For e=(3h+1)/2, the code has parameters [3^m−1, 3^m−1−2m, 4] exactly when h is odd and gcd(m,h)=1, equivalently when x^e is planar.Source: §V · p. 5
  • For d=4, the necessity argument requires h odd; sufficiency holds when m/gcd(m,h) is odd, yielding C(1,e) parameters [3m−1, 3m−1−2m, 4].Source: §V · pp. 5–6
  • For e=3h+1, the code has those parameters exactly when m/gcd(m,h) is odd, equivalently when x^e is planar over GF(3^m).Source: §V · p. 6
  • For e=3h+1, an even m/gcd(m,h) violates C3, while an odd ratio gives planarity and the stated code parameters.Source: §V · p. 6

VI. THE OPTIMAL CYCLIC CODES DEFINED BY APN MONOMIALS xe OVER GF(3m)

The section presents seven classes of optimal ternary cyclic codes defined by APN monomials over GF(3^m). It establishes that an APN monomial yields codes with parameters [3^m−1, 3^m−1−2m, 4] and illustrates the result with a concrete code.

VI. THE OPTIMAL CYCLIC CODES DEFINED BY APN MONOMIALS xe OVER GF(3m)

  • Any APN monomial x^e over GF(3^m) gives C(1,e) parameters [3^m−1, 3^m−1−2m, 4].The section presents seven classes of such monomials.Source: §VI · p. 7
  • The proof uses the APN property to establish the two solution conditions needed for minimum distance 4.The argument rules out extra solutions to the equations underlying Conditions C2 and C3.Source: §VI · p. 7
  • For m=3 and e=8, C(1,e) has parameters, and its dual has parameters.The example code is optimal, while the database's optimal ternary code with the same parameters is not known to be cyclic.Source: §VI · p. 8

VII. THE OPTIMAL CYCLIC CODES DEFINED BY OTHER MONOMIALS xe OVER GF(3m)

This section constructs optimal ternary cyclic codes from monomials that are neither planar nor APN, and states several exact criteria and unresolved cases. Some parameter choices are shown to yield codes with minimum distance 3 or to be almost optimal, rather than optimal.

VII. THE OPTIMAL CYCLIC CODES DEFINED BY OTHER MONOMIALS xe OVER GF(3m)

  • For e=(3^h−1)/2, Theorem 7.1 characterizes when the code has parameters [3^m−1, 3^m−1−2m, 4]; the stated criteria include odd m, even h, gcd(h,m)=1, and gcd(h−1,m)=1.The section gives the exponent range 2≤h≤m−1.Source: §VII · p. 8
  • For m=5 and e=4, C(1,e) has parameters [242,232,4], and its dual has parameters [242,10,153].The dual has the same parameters as the best known ternary linear code in the database; the stated upper bound on its minimum distance is 155.Source: §VII · p. 9
  • For e=2(1+3^h) and even m, the ternary cyclic code C(1,e) has minimum distance 3; it is almost optimal when h ≠ m/2, and optimal for (m,h)=(2,1) or (4,2).Source: §VII · pp. 9–10
  • The section leaves open whether several other exponent families produce the target parameters, while reporting positive Magma checks for specified finite ranges.The open questions include odd m for e=2(1+3^h), conditions for even m with e=(3^h−5)/2, and further cases with e=3^h+5.Source: §VII · pp. 10–11
  • For e=3h−1, C(1,e) has parameters [3^m−1, 3^m−1−2m, 4] exactly when gcd(h,m)=1 and gcd(3h−2,3^m−1)=1.The theorem also requires 1≤h≤m−1.Source: §VII · p. 10

VIII. CONCLUDING REMARKS

The code C(1,e) has optimal parameters when x^e is planar or APN, but the paper shows these conditions are not necessary. The authors note that full characterization remains difficult, pose nine open problems, and report additional examples from Magma experiments.

  • C(1,e) has parameters [3m−1, 3m−1−2m, 4] when x^e is planar or APN over GF(3^m).Source: §VIII · p. 11
  • The code may retain those parameters when x^e is neither planar nor APN.Source: §VIII · p. 11
  • The authors present nine open problems because fully characterizing these codes is difficult, and report other optimal examples from Magma experiments.Source: §VIII · p. 11
Loading 1305.0061v1…