PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Codes from Some 2-Designs

Cunsheng Ding

arXiv:1503.06511v1cs.IT

TL;DR

Existing work commonly constructs codes from t-design incidence matrices, while this paper studies a different approach based on special 2-designs and defining sets. It obtains few-weight codes from almost difference sets, difference sets, and semibent-function-associated designs, including two optimal families and stated applications.

  • Problem

    The paper addresses the need to study a construction method for linear codes using specific classes of 2-designs beyond the extensively investigated incidence-matrix approach.

  • Method

    The paper constructs defining-set linear codes from almost difference sets, difference sets, and 2-designs associated with semibent functions.

  • Results

    The constructions produce one-, two-, and three-weight codes, and two code families are optimal.

  • Takeaways & Limitations

    The resulting few-weight codes have applications in secret sharing, authentication, consumer electronics, communication, and data storage systems.

Abstract

from arXiv · show

A classical method of constructing a linear code over $\gf(q)$ with a $t$-design is to use the incidence matrix of the $t$-design as a generator matrix over $\gf(q)$ of the code. This approach has been extensively investigated in the literature. In this paper, a different method of constructing linear codes using specific classes of $2$-designs is studied, and linear codes with a few weights are obtained from almost difference sets, difference sets, and a type of $2$-designs associated to semibent functions. Two families of the codes obtained in this paper are optimal. The linear codes presented in this paper have applications in secret sharing and authentication schemes, in addition to their applications in consumer electronics, communication and data storage systems. A coding-theory approach to the characterisation of highly nonlinear Boolean functions is presented.

I. INTRODUCTION

The paper contrasts incidence-matrix constructions with a different approach using special 2-designs and defining sets to obtain few-weight linear codes. These codes include constructions from almost difference sets, difference sets, and designs associated with semibent functions, with stated applications and optimal families.

  • Classical construction: Incidence matrices of t-designs span linear codes over GF(p), an extensively studied construction in which every t-design yields a code.The incidence matrix is defined by point-block membership and is unique up to row and column permutations.
  • Paper objective: The paper studies a different method for constructing linear codes from certain special types of 2-designs.
  • Constructions: One-, two-, and three-weight linear codes are obtained from almost difference sets, difference sets, and 2-designs associated with semibent functions.
  • Applications: The resulting few-weight codes are presented as applicable to secret sharing, authentication, consumer electronics, communication, and data storage systems.The paper also presents a coding-theory approach to characterising highly nonlinear Boolean functions.
  • Difference-set designs: Difference-set developments are 2-(v,k,λ) designs, and each such design automatically defines a linear code through its incidence structure.
  • Defining-set method: The defining-set construction selects D ⊆ GF(q) to define a length-n code over GF(p) whose dimension is at most m.The construction may produce good or optimal parameters when D is well chosen, but may otherwise produce bad parameters.

B. The weights in the linear codes CD

The weights of codewords are related to additive-character sums over scaled defining sets. This character-sum representation provides the basis for determining code weights.

  • Character-sum weight formula: For each x ∈ GF(q), the codeword weight is represented through an additive-character expression involving the defining set D.

IV. LINEAR CODES FROM SKEW SETS

The paper constructs few-weight linear codes from special 2-design-related sets and quadratic forms, deriving one- and two-weight families under explicit conditions. Skew sets yield an optimal one-weight code, while quadratic-residue and other function-image constructions extend the approach.

  • Skew sets: A skew set D produces a one-weight code CD over GF(p) with parameters [(q−1)/2, m, (p−1)q/2p].The construction uses the partition of GF(q) into D, −D, and {0}.
  • Skew sets: The skew-set code is optimal because it meets the Griesmer bound.Skew Hadamard difference sets are a subclass that also produce one-weight codes through this construction.
  • Scope: Determining code lengths and weight distributions remains difficult for general quadratic forms, so the paper focuses on forms satisfying specific conditions.The stated conditions include f(0)=0, nonzero values on GF(q)*, and an e-to-1 property.
  • Quadratic forms: For quadratic forms f that are e-to-1 on GF(q)*, CD(f) has length (q−1)/e and is one-weight when r is odd but two-weight when r is even.The rank r controls which weight pattern occurs under Theorem 3's additional hypotheses.
  • Quadratic residues: Quadratic residues give a one-weight code when m is odd and a two-weight code when m is even.The construction specializes Theorem 3 to f(x)=x^2 with e=2.

B. The codes CD(f ) from the images of some quadratic functions on GF(2m)

This section constructs binary codes from images of quadratic functions and difference sets under conditions on the mapping Γρ, obtaining few-weight codes and a conjectural Glynn II family.

  • The construction includes Singer, Segre, Glynn I, and Glynn II choices of ρ that yield difference sets under the stated mapping conditions.The listed cases include ρ = 2, 6, 2^σ+2^π, and 3·2^σ+4.
  • Under the stated two-to-one and gcd conditions, Γρ yields binary codes CD(Γρ) with parameters [2^m−1−1, m, 2^m−2−2^((m−3)/2)].The weight distribution is given in Table I.
  • The Segre case satisfies Theorem 7 and produces a class of binary linear codes with three weights.Here ρ = 6 and Γρ is known to be two-to-one.
  • The Glynn I case also satisfies Theorem 7 and produces a class of binary linear codes with three weights.The parameters of (i,j,κ) depend on m modulo 4.

A. The Boolean case

The Boolean case studies binary codes defined from supports of Boolean functions, linking their weight distributions to Walsh spectra and focusing on supports that form 2-designs.

  • The code CD_f has length n_f and dimension at most m when defined from the support D_f of a Boolean function.The section determines weight distributions for selected function classes whose supports are certain 2-designs.
  • For non-affine f, Theorem 9 gives CD_f dimension m and a weight distribution determined by the Walsh spectrum.The theorem states that CD_f is a binary linear code with length n_f.
  • The Hamming weight of c_w is expressed using the Walsh transform, so determining the code’s weight distribution is equivalent to determining that spectrum.For non-affine f, every nonzero w gives a nonzero codeword.
  • Selecting Boolean functions appropriately can produce codes with only a few weights and potentially good parameters.

1) Linear codes from bent functions:

Bent functions produce two-weight binary codes through their supports as difference sets, with parameters determined by the support size and examples that are optimal or near-optimal.

  • Bent functions are equivalent to difference sets in the additive group of GF(2^m), connecting their Walsh spectra with code weight distributions.
  • For even m, a bent function with f(0)=0 gives an [n_f, m, (n_f−2^((m−2)/2))/2] two-weight binary code.The nonzero weights are (n_f−2^((m−2)/2))/2 and (n_f+2^((m−2)/2))/2.
  • When m = 6 and n_f = 28, the resulting code has parameters and is optimal.
  • When m = 8 and n_f = 120, the code has parameters [120, 8, 56], compared with [120, 8, 58] for the optimal binary code.

2) Linear codes from semibent functions:

Semibent functions on GF(2^m) for odd m yield three-weight binary codes whose parameters follow from their Walsh spectra and support sizes.

  • The support of a semibent function gives a 2-design, while the coding-theory analysis focuses on the resulting code.
  • For odd m, a semibent function with f(0)=0 gives an [n_f, m, (n_f−2^((m−1)/2))/2] three-weight binary code.Its weight distribution is given in Table III.
  • When m = 7 and |D_f| = 56, the code has parameters [56, 7, 24], compared with [56, 7, 26] for the optimal binary code.

3) Linear codes from almost bent functions:

Almost bent functions yield three-weight binary codes through their trace functions, with parameters determined by the associated Walsh-spectrum values.

  • An almost bent function has Walsh-spectrum values 0 or ±2^(m+1)/2 for nonzero first arguments, and exists only when m is odd.
  • Defining f = Tr(g) for an almost bent function g links the resulting code to the function's spectral values.
  • CD_f is an [n_f, m, (n_f − 2^(m−1)/2)/2] three-weight binary code when Tr(g(0)) = 0 and m is odd.
  • The code has minimum dual weight at least 3, while its three weight frequencies are determined in the proof of the corollary.
  • This construction differs from earlier codes from almost bent functions because both their dimensions and lengths differ.

4) Linear codes from quadratic Boolean functions:

Quadratic Boolean functions produce binary codes whose lengths, dimensions, and weight distributions follow from their Walsh spectra and ranks.

  • The Walsh spectrum of a quadratic Boolean function is used to determine the support size and resulting code weights.
  • Theorem 14 gives CD_f length n_f, dimension m, and a weight distribution determined by the value of f-hat(0).
  • For quadratic Boolean functions, the resulting code differs from any subcode of the second-order Reed–Muller code in length and weight distribution.

B. A ternary case

The ternary construction uses cyclic difference sets and quadratic forms over GF(3^m) to obtain codes with explicitly determined weight distributions under an odd-parameter condition.

  • Construction: The set D is a difference set in GF(3^m)^*/GF(2)^*, and {D, −D, {0}} partitions the preimage of f^−1(0).
  • Scope: When h is even, the code has more than three nonzero weights, so the three-weight result is restricted to odd h.
  • Construction: The construction fixes p = 3, m = 3h, and e = 3^h with h odd, then studies a quadratic form over GF(3^m).
  • Quadratic-form analysis: The quadratic-form ranks used in the analysis are restricted: r_Qu is m, m−h, or m−2h, while at least one of Q_u and Q_{−1−u} has rank m.
  • Weight determination: For each nonzero b, N(b,0) and the triple (N(b,0), N(b,1), N(b,2)) take only three possible values.
  • Results: Theorem 16 establishes ternary code parameters and the weight distribution in Table VI, with the three code weights derived from character sums.
  • Results: Examples with h = 1 and h = 3 give [4,3,2] and [3280,9,2106] ternary codes, respectively.

VII. CONCLUDING REMARKS

The paper's codes are constructed differently from classical incidence-matrix codes and can support secret sharing, while parameter determination remains difficult for broader difference-set families.

  • The paper constructs one-, two-, and three-weight codes from 2-designs, with applications to secret sharing and authentication codes.
  • Many other difference sets automatically yield codes in this framework, but determining their parameters may be difficult.
  • The construction differs from earlier nonlinear-function code constructions because its codes usually have dimension m and length n smaller than q−1.
  • Unlike the classical incidence-matrix approach, this construction produces codes with a different length.
  • The desired secret-sharing access structures motivate codes whose minimum-to-maximum nonzero weight ratio exceeds p−1.
  • Almost all of the paper's codes can support secret-sharing schemes with certain access structures when m is sufficiently large.
Loading 1503.06511v1…