PaperlayerView exact revision on arXiv

Source-linked AI summary

Hamming Weights in Irreducible Cyclic Codes

Cunsheng Ding, Jing Yang

arXiv:1108.3887v1cs.IT

TL;DR

Irreducible cyclic-code weight distributions are difficult to determine and remain known only in limited cases. The paper surveys and extends distribution results, relates weights to Gaussian periods, proves divisibility and constant-weight theorems, and develops weight bounds.

  • Problem

    Weight distributions of irreducible cyclic codes have been determined only for a small number of special cases, while their difficult computation motivates further study.

  • Method

    The paper surveys and extends prior results, expresses code weights through Gaussian periods, and derives divisibility, constant-weight, and related distribution theorems.

  • Results

    The paper establishes a weight-divisibility theorem and characterizes constant-weight irreducible cyclic codes by gcd((r − 1)/(q − 1), N) = 1.

  • Takeaways & Limitations

    Irreducible cyclic-code weight analysis can be reduced to Gaussian-period determination, with divisibility and constant-weight criteria available in the stated settings.

Abstract

from arXiv · show

Irreducible cyclic codes are an interesting type of codes and have applications in space communications. They have been studied for decades and a lot of progress has been made. The objectives of this paper are to survey and extend earlier results on the weight distributions of irreducible cyclic codes, present a divisibility theorem and develop bounds on the weights in irreducible cyclic codes.

I. INTRODUCTION

The paper introduces irreducible cyclic codes and surveys tools for studying their weight distributions, while extending prior results and motivating divisibility and weight bounds.

  • Cyclic codes correspond to ideals in GF(q)[x]/(x^n − 1), with generator and parity-check polynomials defining their algebraic representation.
  • The code C(r, N) is constructed from trace evaluations over GF(r) at powers of θ, producing an irreducible cyclic code over GF(q).
  • Irreducible cyclic codes are minimal cyclic codes with applications including the Golay code’s use on the Mariner Jupiter-Saturn Mission.
  • The paper surveys and extends earlier weight-distribution results, presents a divisibility theorem, and develops bounds on irreducible cyclic-code weights.
  • Explicit Gaussian sums are generally challenging and are known only in several special cases, including small orders, semi-primitive cases, and index-2 cases.

B. Cyclotomy

This section develops cyclotomic classes, cyclotomic numbers, and multiset identities used to analyze irreducible cyclic-code weights.

  • Cyclotomic classes of order N partition GF(r)^* into cosets α^i⟨α^N⟩ for 0 ≤ i ≤ N − 1.
  • Cyclotomic numbers are defined from these classes and provide algebraic counts indexed by pairs of class labels.
  • A multiset identity describes how elements from C(gcd((r − 1)/(q − 1), e1), r) occur with specified multiplicity.
  • The proof counts representations through products xy while tracking unique exponents and GF(q)^* scalars.

C. Gaussian periods

Gaussian periods are linked to Gaussian sums through the discrete Fourier transform, but their explicit values are available only in selected cases.

  • The section also records basic period identities, including their total sum and correlation relations.
  • Gaussian periods are closely related to Gaussian sums, with the discrete Fourier transform providing the connecting relationship.
  • The paper introduces period polynomials because Gaussian-period values are generally difficult to compute explicitly.
  • For N = 3 and N = 4, the paper gives parameterized results concerning period-polynomial factorizations and irreducibility over the rationals.
  • In the semi-primitive case, Gaussian periods satisfy explicit case-dependent formulas under assumptions involving pj ≡ −1 (mod N).

III. THE WEIGHTS IN IRREDUCIBLE CYCLIC CODES

The paper connects irreducible cyclic-code weights to Gaussian periods, proves a weight-divisibility theorem, and characterizes important constant-weight cases.

  • The key weight expression makes determining an irreducible cyclic code’s weight distribution equivalent to determining Gaussian periods of order N1 = gcd((r − 1)/(q − 1), N).
  • Every codeword weight is divisible by gcd(q − 1, N/N1), where N1 = gcd((r − 1)/(q − 1), N).
  • When N divides (r − 1)/(q − 1), every codeword weight is divisible by q − 1.
  • For q = 5, m = 4, and N = 4, the listed nonzero weights are 112, 124, 128, and 136, whose common divisor is 4.

IV. THE WEIGHT DISTRIBUTION IN THE CASE THAT gcd((r −1)/(q −1), N) = 1

When gcd((r −1)/(q −1), N) = 1, C(r, N) is a constant-weight irreducible cyclic code, and this condition exactly characterizes that property.

  • C(r, N) is a [(q^m −1)/N, m, (q −1)q^m−1/N] constant-weight code over GF(q).
  • Under this gcd condition, N divides q −1.
  • The proof derives codeword weights from equation (11) and Lemma 12, followed by the weight distribution and dimension.
  • The code C(r, N) is constant-weight if and only if gcd((r −1)/(q −1), N) = 1.
  • The characterization extends earlier results that restricted N to divisors of q −1.

V. THE WEIGHT DISTRIBUTION IN THE CASE THAT gcd((r −1)/(q −1), N) = 2

When gcd((r −1)/(q −1), N) = 2, the paper gives a two-weight construction under stated parity conditions and illustrates distinct resulting distributions.

  • gcd((r −1)/(q −1), N) = 2 yields a code with parameters [(q^m −1)/N, m, (q −1)(r −√r)/Nq] and a two-weight enumerator.
  • The derivation uses that m is even and q is odd, together with equation (11) and Lemma 12.
  • For q = 9, m = 2, the cases N = q −1 and N = 2(q −1) produce [10, 2, 8] and [5, 2, 4] codes, respectively.
  • For q = 3, m = 4, and N = q −1 = 2, the construction gives a [40, 4, 24] code with weights 24 and 30.
  • With q = 3, m = 4, and N = 2(q −1) = 4, the resulting [20, 4, 12] code has a different distribution from Theorem 18.

VI. THE WEIGHT DISTRIBUTION IN THE CASE THAT gcd((r −1)/(q −1), N) = 3

When gcd((r −1)/(q −1), N) = 3, the weight distribution depends on the characteristic and on sm modulo 4, with explicit constructions for both cases.

  • If p ≡ 1 (mod 3), C(r, N) has parameters [(q^m −1)/N, m] and the stated three-case weight distribution.
  • For p ≡ 2 (mod 3), the analysis uses three distinct Gaussian-period values to obtain codeword weights and distributions.
  • Theorem 19 extends results previously given by Baumert and McEliece and other cited authors.
  • Examples over GF(7), GF(4), and related parameter choices instantiate the theorem’s different cases.
  • If p ≡ 2 (mod 3) and sm ≡ 0 (mod 4), C(r, N) has minimum distance (q −1)(r −√r)/Nq and the stated weight distribution.

VII. THE WEIGHT DISTRIBUTION IN THE CASE THAT gcd((r −1)/(q −1), N) = 4

When gcd((r −1)/(q −1), N) = 4, the paper gives separate weight-distribution results according to whether p is 1 or 3 modulo 4.

  • If p ≡ 1 (mod 4), C(r, N) is a [(r −1)/N, m] code with the stated weight distribution.
  • If p ≡ 3 (mod 4), C(r, N) is a [(r −1)/N, m] code with the stated weight distribution and conditions on u1.
  • The proof obtains the formula using Lemma 11 and equation (11), similarly to Theorem 19.
  • Theorem 21 extends two earlier results cited in the paper.
  • For q = 5, m = 4, and N = 4, the code is [156, 4, 112] with four nonzero weights shown in its enumerator.
  • For q = 5, m = 4, and N = 16, the code is [39, 4, 28] with the displayed weight distribution.

VIII. THE WEIGHT DISTRIBUTION IN THE QUADRATIC RESIDUE CASE

This section presents a known quadratic-residue or index-2 case, gives Theorem 22 with its proof basis, and illustrates resulting weight distributions through two examples.

  • The quadratic-residue, or index-2, case has a known weight distribution described by a theorem.
  • Theorem 22 derives Hamming weights for codewords c(β) with β ∈ C(r,N1), using a defined expression and the conventions A0 = Aλ+1 = Bλ+1 = 0.
  • Theorem 22 extends main results of Baumert and Mykkeltveit and of [2, §11.7].
  • Theorem 22’s explicit formulas, together with recursive relations for A(s,λ)t and B(s,λ)t, yield recursive algorithms presented in.
  • [89756051247, 42, 44877307904] is the binary code in Example 15, whose weight distribution has five displayed nonzero-weight terms.
  • [1441729016604299000588186, 55, 961152677733830625644778] is the ternary code in Example 16, with four displayed nonzero-weight terms.

IX. THE WEIGHT DISTRIBUTION IN THE CASE THAT n IS PRIME POWER

This section treats prime-power lengths through a theorem covering constant-weight and cyclic-code cases, then connects semiprimitive results to broader two-weight-code questions.

  • For j ≤ ℓ−d, C(r,N) is a [t^j, 1, t^j] constant-weight code over GF(q) with weight enumerator 1 + (q −1)x^t^j.
  • For j > ℓ−d, C(r,N) is a [t^j, t^j−(ℓ−d)] cyclic code over GF(q) with a stated weight enumerator.
  • Example 17 gives a [9, 3, 3] cyclic code over GF(4) with weight enumerator 1 + 9x^3 + 27x^6 + 27x^9.
  • Under the semiprimitive-related assumptions, Theorem 24 gives code cases (a) and (b) with length (q^m−1)/N and dimension m, each having a stated weight enumerator.
  • When N1 = N, the setting is the classical semiprimitive case; when N1 < N, it may not be semiprimitive for N.
  • For q = 7, m = 2, and N = 12, Theorem 24 yields a GF(7) code of length 4, dimension 2, and weight enumerator 1 + 12x^2 + 36x^4.
  • Theorem 24 shows that some non-semiprimitive cases can be settled using semiprimitive-case results.
  • Theorem 24 describes a class of two-weight irreducible cyclic codes, while a complete characterization remains an identified problem in the cited discussion.

XI. THE WEIGHT DISTRIBUTION IN A FEW OTHER CASES AND OTHER RESULTS

The paper develops weight-distribution results for irreducible cyclic codes, including a theorem giving code parameters and weight bounds. It also identifies divisibility properties, special constant-weight cases, and remaining characterization problems.

  • Other cases: Gaussian periods can determine weight distributions in some special cases, although the resulting formulas may be complicated.Periods of orders 5, 6, 8, and 12 are cited as examples; two-weight projective codes have also been characterized.
  • Bounds: Because weight distributions are difficult to determine generally, tight weight bounds are sought for their implications for error-correcting capability.The section explicitly motivates bounds as a way to obtain information about this capability.
  • Bounds: Theorem 25 establishes that C(r, N) is a cyclic [(q^m −1)/N, m0] code whose nonzero codeword weights satisfy stated lower and upper bounds.The theorem assumes N divides r−1 and defines N1 = gcd((r−1)/(q−1), N).
  • Bounds: When N1(N1 −1) < r, the multiplicative order satisfies m0 = m.
  • Bounds: Theorem 25's lower bound is tight when gcd((r−1)/(q−1), N) is small, while the bounds coincide and are achieved for gcd((r−1)/(q−1), N) = 1.In the latter case, the code is constant-weight.
  • Contributions and open problems: The paper surveys earlier results, extends and generalizes them, characterizes one-weight codes, proves weight divisibility, develops weight bounds, and establishes a Gaussian-period property.It also identifies simpler characterization of two-weight irreducible cyclic codes as an open problem.
Loading 1108.3887v1…