Linear codes from a generic construction

Abstract

A generic construction of linear codes over finite fields has recently received a lot of attention, and many one-weight, two-weight and three-weight codes with good error correcting capability have been produced with this generic approach. The first objective of this paper is to establish relationships among some classes of linear codes obtained with this approach, so that the parameters of some classes of linear codes can be derived from those of other classes with known parameters. In this way, linear codes with new parameters will be derived. The second is to present a class of three-weight binary codes and consider their applications in secret sharing.

1 Introduction

Throughout this paper, let p be a prime and let q = p ^m for some positive integer m. An [n, κ, ω] linear code ${\mathcal {C}}$ over GF(p) is a κ-dimensional subspace of GF(p)ⁿ with minimum (Hamming) distance ω. Let A _i denote the number of codewords with Hamming weight i in a code ${\mathcal {C}}$ of length n. The weight enumerator of ${\mathcal {C}}$ is defined by 1 + A ₁ z + A ₂ z ² + ⋯+A _n z ⁿ. A code ${\mathcal {C}}$ is said to be a t-weight code if the number of nonzero A _i in the sequence (A ₁, A ₂,⋯ , A _n ) is equal to t.The sequence (1, A ₁, A ₂,⋯ , A _n ) is called the weight distribution of ${\mathcal {C}}$. An [n, κ, ω] code ${\mathcal {C}}$ is called optimal if its parameters [n, κ, ω] meet a bound on linear codes, and almost optimal if [n, κ, ω+1] or [n,κ+1,ω] meets a bound on linear codes.

A generic construction of linear codes over finite fields has attracted a lot of attention in the past eight years (see, for example, [8–11, 13, 14, 17]). Many classes of one-weight, two-weight and three-weight codes were obtained with this approach. The first goal of this paper is to establish a few relations among some classes of linear codes obtained with this approach, so that the parameters of some classes of linear codes can be derived from those of other classes with known parameters. In this way, linear codes with new parameters will be derived. The second is to present a class of three-weight binary codes and consider their applications in secret sharing.

2 Group characters in GF(q)

An additive character of GF(q) is a nonzero function χ from GF(q) to the set of nonzero complex numbers such that χ(x + y) = χ(x)χ(y) for any pair (x, y) ∈ GF(q)². For each b ∈ GF(q), the function

$$ \chi_{b}(c)=\epsilon_{p}^{{\text{Tr}}(bc)} \;\; \text{ for all } c\in{\text{GF}}(q) $$

(1)

defines an additive character of GF(q), where and whereafter $\epsilon _{p}=e^{2\pi \sqrt {-1}/p}$ is a primitive complex pth root of unity. When b = 0, χ ₀(c) = 1 for all c ∈ GF(q), and is called the trivial additive character of GF(q). The character χ ₁ in (1) is called the canonical additive character of GF(q). It is known that every additive character of GF(q) can be written as χ _b (x) = χ ₁(b x) [16, Theorem 5.7].

3 A generic construction of linear codes

Let D = {d ₁, d ₂, …, d _n } ⊆ GF(q), where again q = p ^m. Let Tr denote the trace function from GF(q) onto GF(p) throughout this paper. We define a linear code of length n over GF(p) by

$$ {\mathcal{C}}_{D}=\{({\text{Tr}}(xd_{1}), {\text{Tr}}(xd_{2}), \ldots, {\text{Tr}}(xd_{n})): x \in {\text{GF}}(q)\}, $$

(2)

and call D the defining set of this code ${\mathcal {C}}_{D}$. By definition, the dimension of the code ${\mathcal {C}}_{D}$ is at most m.

The code ${\mathcal {C}}_{D}$ depends on the specific ordering of the elements in the defining set D. However, up to column permutations, the codes obtained from different orderings are equivalent with respect to coordinate permutations. Hence, in this paper, we do not specify the specific ordering of the elements in D when we consider the code ${\mathcal {C}}_{D}$.

This construction is generic in the sense that many classes of known codes could be produced by properly selecting the defining set D ⊆ GF(q). This construction technique was employed in [8–11, 13, 14, 17] for obtaining linear codes with a few weights.

This construction is generic and can produce a lot of linear codes. The parameters of the code ${\mathcal {C}}_{D}$ depend on the selection of the defining set D. Linear codes with both poor and good error-correcting capability can be obtained with this approach.

Many classes of linear codes with a few weights and good parameters have been already obtained with this approach. In this paper, we will present a few relations among some subclasses of linear codes obtained with this approach. In this way, we are able to derive the parameters of some other linear codes.

It is convenient to define for each x ∈ GF(q),

$$ {\mathbf{c}}_{x}=({\text{Tr}}(xd_{1}), \, {\text{Tr}}(xd_{2}), \, \ldots, \, {\text{Tr}}(xd_{n})). $$

(3)

The Hamming weight wt(c _x ) of c _x is n−N _x (0), where

$$N_{x}(0)=\left|\{1 \le i \le n: {\text{Tr}}(xd_{i})=0\}\right| $$

for each x ∈ GF(q).

It is easily seen that for any D = {d ₁, d ₂, …, d _n } ⊆ GF(q) we have

$$\begin{array}{@{}rcl@{}} pN_{x}(0) = \sum\limits_{i=1}^{n} \sum\limits_{y \in {\text{GF}}(p)} e^{2\pi \sqrt{-1} y{\text{Tr}}(xd_{i})/p} = \sum\limits_{i=1}^{n} \sum\limits_{y \in {\text{GF}}(p)} \chi_{1}(yxd_{i}) = n + \sum\limits_{y \in {\text{GF}}(p)^{*}} \chi_{1}(yxD), \end{array} $$

where χ ₁ is the canonical additive character of GF(q), a D denotes the set {a d:d ∈ D}, and $\chi _{1}(S):={\sum }_{x \in S} \chi _{1}(x)$ for any subset S of GF(q). Hence,

$$ {\text{wt}}({\mathbf{c}}_{x})=n-N_{x}(0)=\frac{(p-1)n-{\sum}_{y \in {\text{GF}}(p)^{\ast}} \chi_{1}(yxD)}{p}. $$

(4)

4 Shortening and expanding a linear code obtained from this construction

Let D ⊂ GF(q)^∗ and $\hat {D}=E D$, where E is a subset of GF(p)^∗ and

$$ED=\{ ed: e \in E \text{ and } d \in D\}. $$

Let n = |D|, $\hat {n}=|\hat {D}|$, and ℓ = |E|.

Our goal of this section is to establish a relation between the parameters of the two codes ${\mathcal {C}}_{D}$ and $\mathcal {C}_{\hat {D}}$ under the condition that |E D|=|E||D|. Specifically, we have the following general result.

Theorem 1

Let symbols and notation be the same as above. Assume that $\hat {n}=n\ell$. Then ${\mathcal {C}}_{D}$ is an [n, k] linear code with weight enumerator

$$1+A_{1}z+A_{2}z^{2}+ {\cdots} + A_{n} z^{n} $$

if and only if ${\mathcal {C}}_{\hat {D}}$ is an [nℓ, k] linear code with weight enumerator

$$1+A_{1}z^{\ell}+A_{2}z^{2\ell}+ {\cdots} + A_{n} z^{n\ell}. $$

Proof

Note that Tr(z x) = zTr(x) for all z ∈ GF(p) and x ∈ GF(q). We have that Tr(z x) = 0 if and only if Tr(x) = 0 for all z ∈ GF(p)^∗ and x ∈ GF(q).

Let E = {e ₁, e ₂,⋯ , e _ℓ }. By assumption we have that |E D|=|E||D|. Up to column permutations, every codeword $\hat {{\mathbf {c}}}_{x}$ in ${\mathcal {C}}_{\hat {D}}$ can be expressed as

$$\hat{{\mathbf{c}}}_{x} = (e_{1} {\mathbf{c}}_{x}, e_{2} {\mathbf{c}}_{x}, \cdots, e_{\ell} {\mathbf{c}}_{x}), $$

where c _x is the corresponding codeword in ${\mathcal {C}}_{D}$. It then follows that ${\text {wt}}(\hat {{\mathbf {c}}}_{x})=\ell {\text {wt}}({\mathbf {c}}_{x})$. In addition, $\hat {{\mathbf {c}}}_{x}$ is the zero codeword in ${\mathcal {C}}_{\hat {D}}$ if and only if c _x is the zero codeword in $\mathcal {C}_{D}$. The desired conclusions then follow. □

It should be noticed that the condition |E D|=|E||D| in Theorem 1 is necessary. Without this condition, there may be no specific relation among the parameters of the two codes ${\mathcal {C}}_{D}$ and ${\mathcal {C}}_{\hat {D}}$.

Theorem 1 can be employed to derive parameters of a shortened or expanded code of a linear code obtained from this generic construction in some special cases. We now demonstrate this possibility in the rest of this section.

Corollary 1

Let $\hat {D}={\text {GF}}(q)^{\ast }, E={\text {GF}}(p)^{\ast }$, and let D be the coset representatives of the quotient group GF(q)^∗/GF(p)^∗. Then $\hat {D}=ED$, and ${\mathcal {C}}_{D}$ is a one-weight code with parameters [(q − 1)/(p − 1), m] and weight enumerator $1+(p^{m}-1)z^{p^{m-1}}$.

Proof

Note that $\hat {D}={\text {GF}}(q)^{*}$. For every x ∈ GF(q)^∗, the codeword $\hat {{\mathbf {c}}}_{x}$ has Hamming weight (p−1)p ^m−1. Hence, ${\mathcal {C}}_{\hat {D}}$ is a [p ^m − 1, m] code over GF(p) with the only nonzero weight (p−1)p ^m−1. The desired conclusions on ${\mathcal {C}}_{D}$ then follow from Theorem 1. □

The code ${\mathcal {C}}_{D}$ in Corollary 1 is the well-known simplex code. The purpose of presenting this code is to demonstrate that it is a shortened version of the code ${\mathcal {C}}_{\hat {D}}$ obtained from the generic construction. In addition, in the next corollary, we will show that this code can be extended into many ways so that many one-weight linear codes can be obtained.

Corollary 2

Let D be the coset representatives of the quotient group GF(q)^∗/GF(p)^∗. Let E be any subset of GF(p)^∗. Define $\tilde {D}=ED$. Then ${\mathcal {C}}_{\tilde {D}}$ is a one-weight code with parameters [ℓ(q − 1)/(p − 1), m] and weight enumerator $1+(p^{m}-1)z^{\ell p^{m-1}}$, where ℓ is the cardinality of E and 1 ≤ ℓ ≤ p − 1.

Proof

It was proved in Corollary 1 that ${\mathcal {C}}_{D}$ is a one-weight code with parameters [(q−1)/(p−1), m] and weight enumerator $1+(p^{m}-1)z^{p^{m-1}}$. By the definition of D, we have that |E D|=|E||D|. The desired conclusions on the code ${\mathcal {C}}_{\tilde {D}}$ then follow from Theorem 1. □

The codes ${\mathcal {C}}_{\tilde {D}}$ in Corollary 2 are extensions and generalizations of the codes from skew sets presented in [9]. Since the total number of nonempty sets of GF(p)^∗ is 2^p−1 − 1, the construction in Corollary 2 yields 2^p−1 − 1 one-weight codes over GF(p).

We inform that the technique of shortening a linear code obtained from this generic construction was already employed in [14]. Theorem 1 is a formal description and generalization of this technique.

5 Combining two linear codes obtained from this generic construction

5.1 A method for combining two codes

Theorem 2

Let D ₁ ⊂ GF(q) and D ₂ ⊂ GF(q) with D ₁ ∩ D ₂ = ∅. Define D = D ₁ ∪ D ₂. Let n _i =|D _i | for i∈{1,2}. Assume that ${\mathcal {C}}_{D}$ is an [n ₁ + n ₂, k] one-weight code over GF(p) with nonzero-weight w, and ${\mathcal {C}}_{D_{i}}$ has also dimension k for each i. Then ${\mathcal {C}}_{D_{1}}$ has weight enumerator

$$1+A_{1}z+A_{2}z^{2}+ {\cdots} + A_{n_{1}} z^{n_{1}} $$

if and only if ${\mathcal {C}}_{D_{2}}$ has weight enumerator

$$1+A_{1}z^{w-1}+A_{2}z^{w-2}+ {\cdots} + A_{n_{1}} z^{w-n_{1}}. $$

Proof

By assumption, D ₁ ∩ D ₂ = ∅. It follows that up to coordinate permutations every codeword c _x in ${\mathcal {C}}_{D}$ can be expressed as

$${\mathbf{c}}_{x} =\left( {\mathbf{c}}_{x}^{(1)}, {\mathbf{c}}_{x}^{(2)}\right), $$

where ${\mathbf {c}}_{x}^{(i)}$ is the codeword in ${\mathcal {C}}_{D_{i}}$. It then follows that $\text {wt}(\mathbf {c}_{x})=\text {wt}(\mathbf {c}_{x}^{(1)})+\text {wt}(\mathbf {c}_{x}^{(2)})$. By the assumptions of this theorem, all three codes have the same dimension. Hence, c _x is the zero codeword in $\mathcal {C}_{D}$ if and only if ${\mathbf {c}}_{x}^{(1)}$ and ${\mathbf {c}}_{x}^{(2)}$ are the zero codeword in ${\mathcal {C}}_{D_{1}}$ and ${\mathcal {C}}_{D_{2}}$ respectively. The desired conclusions then follow. □

It should be pointed out that the condition D ₁ ∩ D ₂ = ∅ in Theorem 2 is necessary for the correctness of the conclusion. This is implied by the proof of Theorem 2 above.

Let D ⊂ GF(q). Starting from now on, let $\overline {D}$ denote the complement GF(q)∖D of D. As a corollary of Theorem 2, we have the following.

Corollary 3

Let D ⊂ GF(q). Assume that ${\mathcal {C}}_{D}$ is an [n, m] linear code with

$$\max\limits_{{\mathbf{c}} \in {\mathcal{C}}_{D}} {\text{wt}}({\mathbf{c}}) < (p-1)p^{m-1} $$

and weight enumerator

$$1+A_{1}z+A_{2}z^{2}+ {\cdots} + A_{n} z^{n}. $$

Then ${\mathcal {C}}_{\overline {D}}$ has parameters [q − n, m] and weight enumerator

$$1+A_{1}z^{(p-1)p^{m-1}-1}+A_{2}z^{(p-1)p^{m-1}-2}+ {\cdots} + A_{n} z^{(p-1)p^{m-1}-n}. $$

Proof

Note that ${\mathcal {C}}_{{\text {GF}}(q)}$ is a [q, m] linear code over GF(p), and has the only nonzero weight (p−1)p ^m−1. By definition, up to column permutations, every codeword c in ${\mathcal {C}}_{{\text {GF}}(q)}$ can be expressed as ${\mathbf {c}}=\left ({\mathbf {c}}_{x}^{(1)}, {\mathbf {c}}_{x}^{(2)}\right )$, where ${\mathbf {c}}_{x}^{(1)}$ and ${\mathbf {c}}_{x}^{(2)}$ are the corresponding codewords in ${\mathcal {C}}_{D}$ and ${\mathcal {C}}_{\overline {D}}$, respectively. Since ${\mathcal {C}}_{D}$ has dimension m, c _x is the zero codeword in ${\mathcal {C}}_{{\text {GF}}(q)}$ if and only if ${\mathbf {c}}_{x}^{(1)}$ is the zero codeword in ${\mathcal {C}}_{D}$. Note that ${\mathcal {C}}_{{\text {GF}}(q)}$ is a one-weight code with nonzero weight (p−1)p ^m−1 and $\max _{{\mathbf {c}} \in {\mathcal {C}}_{D}} {\text {wt}}({\mathbf {c}}) < (p-1)p^{m-1}$. c _x is a nonzero codeword in ${\mathcal {C}}_{{\text {GF}}(q)}$ if and only if ${\mathbf {c}}_{x}^{(2)}$ is a nonzero codeword in ${\mathcal {C}}_{\overline {D}}$. We then deduce that the dimension of ${\mathcal {C}}_{\overline {D}}$ is also m. The rest of the desired conclusions follows from Theorem 2. □

It is noticed that the condition $\max _{{\mathbf {c}} \in {\mathcal {C}}_{D}} {\text {wt}}({\mathbf {c}}) < (p-1)p^{m-1}$ in Corollary 3 is necessary. Without this condition, the dimension of ${\mathcal {C}}_{\overline {D}}$ may be less than m.

Corollary 3 could be employed to determine the weight enumerator of many classes of linear codes ${\mathcal {C}}_{\overline {D}}$ from those of the code ${\mathcal {C}}_{D}$. In the next subsections, we will demonstrate this with a few examples.

5.2 A class of one-weight and two-weight codes

Let f(x) be a function from GF(q) to GF(q). We define

$$D(f):=\{f(x): x \in {\text{GF}}(q)\} \setminus \{0\}. $$

A polynomial f over GF(q) of the form

$$ f(x)=\sum\limits_{i \in I} \sum\limits_{j \in J} a_{i,j} x^{p^{i}+p^{j}} $$

(5)

is called a quadratic form over GF(q), where a _{i, j} ∈GF(q), and I and J are subsets of {0,1,2,…, m−1}.

Note that GF(q) is a vector space of dimension m over GF(p). The rank of the quadratic form f over GF(q) is defined to be the codimension of the GF(p)-vector space

$$V_{f}=\{x \in {\text{GF}}(q): f(x+z)-f(x)-f(z)=0 \text{ for all } z \in {\text{GF}}(q)\}. $$

That is |V _f |=p ^m−r, where r denotes the rank of f.

It is still very difficult to determine the length n _f of the code ${\mathcal {C}}_{D(f)}$ for general quadratic forms f, let alone the weight distribution of the code ${\mathcal {C}}_{D(f)}$. However, under certain conditions the weight distribution of ${\mathcal {C}}_{D(f)}$ can be worked out [9]. Below we derive a general result on the code ${\mathcal {C}}_{\overline {D(f)}}$ from known results on the code ${\mathcal {C}}_{D(f)}$.

Corollary 4

Let f be a quadratic form of rank r over GF(q) such that

• f(0) = 0 and f(x) ≠ 0 for all x ∈ GF(q)^∗; and

• f is e-to-1 on GF(q)^∗ (i.e. f(x) = u has either e solutions x ∈ GF(q)^∗ or no solution for each u ∈ GF(q)^∗), where e is a positive integer.

If r is odd and e > 1, then ${\mathcal {C}}_{\overline {D(f)}}$ is a one-weight code over GF(p) with parameters

$$\left[\frac{(e-1)q+1}{e}, m, \frac{(e-1)(p-1)q}{ep}\right]. $$

If r ≥ 2 is even and e > 1, then ${\mathcal {C}}_{\overline {D(f)}}$ is a two-weight code over GF(p) with parameters

$$\left[\frac{(e-1)q+1}{e}, m, \frac{(p-1)((e-1)q-p^{m-r/2})}{ep}\right] $$

and weight enumerator

$$1+ \frac{q-1}{2} z^{\frac{(p-1)((e-1)q-p^{m-r/2})}{ep}} + \frac{q-1}{2} z^{\frac{(p-1)((e-1)q+p^{m-r/2})}{ep}}. $$

Proof

The parameters of the code ${\mathcal {C}}_{D(f)}$ were determined in [9]. In addition, it is easily verified that the conditions of Corollary 3 were satisfied by ${\mathcal {C}}_{D(f)}$. The desired conclusions on the code ${\mathcal {C}}_{\overline {D(f)}}$ then follow from Corollary 3 and Theorem 3 in [9]. □

Example 1

$f(x)=x^{p^{\ell }+1}$ is a quadratic form over GF(q) satisfying the conditions of Corollary 4, if $e=\gcd (q-1, p^{\ell } +1)>1$.

Example 2

f(x) = x ¹⁰ − u x ⁶ − u ² x ² is a quadratic form over GF(3^m) satisfying the conditions of Corollary 4, where u ∈ GF(3^m), m is odd, and e = 2.

5.3 The parameters of some binary codes

Let f be a Boolean function from GF(2^m) to GF(2). The support of f is defined to be

$$D_{f}=\{x \in{\text{GF}}(2^{m}) : f(x)=1\} \subseteq {\text{GF}}(2^{m}). $$

Recall that n _f = |D _f |.

The Walsh transform of f is defined by

$$ \hat{f}(\mathit{w})=\sum\limits_{x \in {\text{GF}}(2^{m})} (-1)^{f(x)+{\text{Tr}}(\mathit{w}x)} $$

(6)

where w ∈ GF(2^m). The Walsh spectrum of f is the following multiset

$$\left\{\left\{ \hat{f}(\mathit{w}): \mathit{w} \in {\text{GF}}(2^{m}) \right\}\right\}. $$

It is in general a very hard to determine the weight distribution of the binary code ${\mathcal {C}}_{D_{f}}$ with length n _f and dimension at most m. However, in a number of special cases, this can be done. Below we describe the weight distribution of the code ${\mathcal {C}}_{\overline {D_{f}}}$ by making use of some results on the binary code ${\mathcal {C}}_{D_{f}}$ obtained in [9].

The main result of this section is described in the following corollary.

Corollary 5

Let symbols and notation be the same as above. If $2n_{f} \neq \hat {f}(\mathit {w})$ for all w ∈ GF(2^m)^∗ and

$$ \max\limits_{\mathit{w} \in {\text{GF}}(2^{m})} \hat{f}(w) < 2(2^{m}-n_{f}), $$

(7)

then ${\mathcal {C}}_{\overline {D_{f}}}$ is a binary linear code with length 2^m − n _f and dimension m, and its weight distribution is given by the following multiset:

$$ \left\{\left\{ \frac{2(2^{m}-n_{f})-\hat{f}(\mathit{w})}{4}: \mathit{w} \in {\text{GF}}(2^{m})^{*}\right\}\right\} \cup \left\{\left\{ 0 \right\}\right\}. $$

(8)

Proof

According to Theorem 9 in [9], the code ${\mathcal {C}}_{D_{f}}$ has dimension m and the maximum nonzero Hamming weight of codewords in ${\mathcal {C}}_{D_{f}}$ is

$$\max\limits_{w \in {\text{GF}}(2^{m})} \frac{2n_{f}+\hat{f}(w)}{4} < 2^{m-1} $$

due to the condition of (7). The desired conclusions then follow from Corollary 3 and Theorem 9 in [9]. □

For all the two-weight and three-weight codes ${\mathcal {C}}_{D_{f}}$ from bent, semibent and almost bent functions described in [9], the corresponding binary codes ${\mathcal {C}}_{\overline {D_{f}}}$ are also two-weight and three-weight codes with the weight distribution given in Corollary 5. We omit the details of the weight distributions here.

5.4 A class of ternary codes

In this subsection, we determine the parameters of a class of ternary codes.

Our main result of this section is the following.

Theorem 3

Let h be an odd positive integer and let m = 3h ≥ 3. Let ℓ = 3^2h − 3^h + 1. Define

$$ D=\left\{ \alpha^{t}: {\text{Tr}}_{3^{m}/3}(\alpha^{t} + \alpha^{t\ell})=0, \ 0 \leq t \leq (3^{m}-3)/2 \right\}, $$

(9)

where α is a generator of GF(3^m)^∗.

Then the ternary code ${\mathcal {C}}_{\overline {D}}$ has parameters

$$\left[ \frac{5 \times 3^{3h-1}+1}{2}, 3h, 5 \times 3^{3h-2}-3^{2h-2}\right] $$

and the weight distribution of Table 1.

Table 1 The weight distribution of the codes of Theorem 3

Proof

According to Theorem 15 in [9], the ternary code ${\mathcal {C}}_{D}$ has dimension m = 3h and the maximum nonzero Hamming weight of codewords in ${\mathcal {C}}_{D_{f}}$ is

$$3^{3h-2}+3^{2h-2} < 2 \times 3^{3h-1}. $$

The desired conclusions then follow from Corollary 3 and Theorem 15 in [9]. □

We remark that the code ${\mathcal {C}}_{\overline {D}}$ of Theorem 3 has more than three nonzero weights if h is even.

5.5 Other two-weight and three-weight codes

Corollary 3 can be employed to obtain many linear codes with a few weights. For instances, it can be applied to all the codes in [13, 14, 17] to obtain two-weight and three-weight codes.

6 A class of binary linear codes and their parameters

The objective of this section is to present a class of three-weight binary codes and consider their application in secret sharing. In this section, let p = 2 and we consider only binary codes ${\mathcal {C}}_{D}$ within the generic construction of this paper.

6.1 The description of the codes

In this subsection, we only describe the binary codes and introduce their parameters, but will present the proofs of their parameters in the next subsection.

In this subsection, the defining set D of the code ${\mathcal {C}}_{D}$ of (2) is given by

$$ D=\{x \in {\text{GF}}(2^{m})^{*}: {\text{Tr}}(x^{3}+x)=0\}. $$

(10)

Since 0∉D, the minimum distance d ^⊥ of the dual code ${\mathcal {C}}_{D}^{\perp }$ of ${\mathcal {C}}_{D}$ cannot be 1. Note that the elements in D are pairwise distinct, the minimum distance d ^⊥ of the dual code ${\mathcal {C}}_{D}^{\perp }$ cannot be 2. Hence, we have the following lemma.

Lemma 1

The minimum distance d ^⊥ of the dual code ${\mathcal {C}}_{D}^{\perp }$ of C _D is at least 3 if n = |D| ≥ 3.

Theorem 4

Let m ≥ 5 be odd, and let D be defined in (10). Then the set ${\mathcal {C}}_{D}$ of (2) is a $[2^{m-1}-1+(-1)^{\frac {m^{2}-1}{8}}2^{\frac {m-1}{2}}, m]$ binary code with the weight distribution in Table 2. The dual code ${\mathcal {C}}_{D}^{\perp }$ has parameters

$$\left[2^{m-1}-1+(-1)^{\frac{m^{2}-1}{8}}2^{\frac{m-1}{2}}, 2^{m-1}-1+(-1)^{\frac{m^{2}-1}{8}}2^{\frac{m-1}{2}}-m, d^{\perp}\right], $$

where d ^⊥ ≥ 3.

Table 2 The weight distribution of the codes ${\mathcal {C}}_{D}$ of Theorem 4

Example 3

Let m = 5. Then the code ${\mathcal {C}}_{D}$ has parameters [11,5,4] and weight enumerator 1+10z ⁴ + 16z ⁶ + 5z ⁸. This code is optimal. Its dual ${\mathcal {C}}_{D}^{\perp }$ has parameters [11,6,3] and is almost optimal.

Example 4

Let m = 7. Then the code ${\mathcal {C}}_{D}$ has parameters [71,7,32] and weight enumerator 1+35z ³² + 64z ³⁶ + 28z ⁴⁰. Its dual ${\mathcal {C}}_{D}^{\perp }$ has parameters [71,64,3] and is optimal.

Theorem 5

Let m ≥ 4 be even, and let D be defined in (10). Then the set ${\mathcal {C}}_{D}$ of (2) is a [2^{m − 1} − 1, m] binary code with the weight distribution in Table 3 when m ≡ 2(mod 4), and a $[2^{m-1}-1-2^{\frac {m}{2}}(-1)^{\frac {m}{4}}, m]$ binary code with the weight distribution in Table 4 when m ≡ 0(mod 4).

Table 3 The weight distribution of the codes ${\mathcal {C}}_{D}$ of Theorem 5 when m ≡ 2(mod4)

Table 4 The weight distribution of the codes ${\mathcal {C}}_{D}$ of Theorem 5 when m ≡ 0(mod 4)

The dual code ${\mathcal {C}}_{D}^{\perp }$ has parameters [2^{m − 1} − 1, 2^{m − 1} − 1 − m, d ^⊥ ≥ 3] when m ≡ 2(mod 4), and parameters

$$[2^{m-1}-1-2^{\frac{m}{2}}(-1)^{\frac{m}{4}}, 2^{m-1}-1-2^{\frac{m}{2}}(-1)^{\frac{m}{4}}-m, d^{\perp}\geq 3] $$

when m ≡ 0(mod 4).

Example 5

Let m = 6. Then the code ${\mathcal {C}}_{D}$ has parameters [31,6,12] and weight enumerator 1+10z ¹² + 47z ¹⁶ + 6z ²⁰. Its dual ${\mathcal {C}}_{D}^{\perp }$ has parameters [31,25,3] and is almost optimal.

Example 6

Let m = 10. Then the code ${\mathcal {C}}_{D}$ has parameters [511,10,240] and weight enumerator 1+136z ²⁴⁰ + 767z ²⁵⁶ + 120z ²⁷². Its dual ${\mathcal {C}}_{D}^{\perp }$ has parameters [511,501,3].

Example 7

Let m = 4. Then the code ${\mathcal {C}}_{D}$ has parameters [11,4,4] and weight enumerator 1+2z ⁴ + 12z ⁶ + z ⁸. This code is almost optimal. Its dual ${\mathcal {C}}_{D}^{\perp }$ has parameters [11,7,3] and is optimal.

Example 8

Let m = 8. Then the code ${\mathcal {C}}_{D}$ has parameters [111,8,48] and weight enumerator 1+36z ⁴⁸ + 192z ⁵⁶ + 27z ⁶⁴. Its dual ${\mathcal {C}}_{D}^{\perp }$ has parameters [111,103,3] and is almost optimal.

6.2 The proofs of Theorems 4 and 5

For any a and b in GF(q), we define the following exponential sum

$$ S(a,b) = \sum\limits_{x \in {\text{GF}}(q)} \chi_{1}\left( a x^{3}+bx\right). $$

(11)

To prove the weight distributions of the codes in Theorems 4 and 5, we need the values of the sum S(a, b).

We now define a constant as follows. Let

$$n_{0}=\left|\left\{x \in {\text{GF}}(q): {\text{Tr}}\left( x^{3}+x\right)=0\right\}\right|. $$

By definition, the length n of the code ${\mathcal {C}}_{D}$ of (2) is equal to n ₀−1. We have

$$\begin{array}{@{}rcl@{}} n_{0} &=& \frac{1}{2} \sum\limits_{y \in {\text{GF}}(2)} \sum\limits_{x \in {\text{GF}}(q)} (-1)^{y{\text{Tr}}(x^{3}+x)}\\ &=& \frac{1}{2} \sum\limits_{y \in {\text{GF}}(2)} \sum\limits_{x \in {\text{GF}}(q)} \chi_{1}(y x^{3}+y x)\\ &=& 2^{m-1} + \frac{1}{2} \sum\limits_{x \in {\text{GF}}(q)} \chi_{1}(x^{3}+x). \end{array} $$

(12)

To prove Theorems 4 and 5, we also define the following parameter

$$N_{b}=\left|\left\{x \in {\text{GF}}(q): {\text{Tr}}\left( x^{3}+x\right)=0 \text{ and } {\text{Tr}}(bx)=0\right\}\right|, $$

where b ∈ GF(q)^∗. By definition and the basic facts of additive characters, for any b ∈ GF(q)^∗ we have

$$\begin{array}{@{}rcl@{}} N_{b} &=& \frac{1}{4} \sum\limits_{x \in {\text{GF}}(q)} \left( \sum\limits_{y \in {\text{GF}}(2)} (-1)^{y{\text{Tr}}(x^{3}+x)}\right) \left( \sum\limits_{z \in {\text{GF}}(2)}(-1)^{z{\text{Tr}}(bx)} \right)\\ &=& \frac{1}{4} \sum\limits_{x \in {\text{GF}}(q)}(-1)^{{\text{Tr}}(bx)} + \frac{1}{4} \sum\limits_{x \in {\text{GF}}(q)} (-1)^{{\text{Tr}}(x^{3}+x)}\\ && + \frac{1}{4} \sum\limits_{x \in {\text{GF}}(q)}(-1)^{{\text{Tr}}(x^{3}+(b+1)x)} + 2^{m-2}\\ &=& \frac{1}{4} \left( \sum\limits_{x \in {\text{GF}}(q)} \left( \chi_{1}(x^{3}+x) + \chi_{1}(x^{3}+(b+1)x) \right) + 2^{m}\right). \end{array} $$

(13)

For any b ∈ GF(q)^∗, the Hamming weight wt(c _b ) of the following codeword

$$ {\mathbf{c}}_{b}=({\text{Tr}}(bd_{1}), {\text{Tr}}(bd_{2}), \ldots, {\text{Tr}}(bd_{n})) $$

(14)

of the code ${\mathcal {C}}_{D}$ of (2) is equal to n ₀−N _b .

Let m ≥ 4 be odd. It is well known that Tr(x ³) is a semibent function from GF(q) to GF(2). Thus, we have

$$ \sum\limits_{x \in {\text{GF}}(q)} \chi_{1}(x^{3}+(b+1)x))\in \{0,2^{\frac{m+1}{2}},-2^{\frac{m+1}{2}}\} $$

(15)

for each b ∈ GF(q)^∗.

The following lemma is proved in Theorem 2 of [5].

Lemma 2

When m is odd, we have

$$S(1,1)=\sum\limits_{x \in {\text{GF}}(q)} \chi_{1} \left( x^{3}+x\right)=(-1)^{\frac{m^{2}-1}{8}}2^{\frac{m+1}{2}}. $$

We are now ready to prove Theorem 4. Let m ≥ 4 be odd.

It follows from (12) and Lemma 2 that the length n of the code ${\mathcal {C}}_{D}$ in Theorem 4 is equal to $2^{m-1}+(-1)^{\frac {m^{2}-1}{8}}2^{\frac {m-1}{2}}-1$, as $n_{0}=2^{m-1}+(-1)^{\frac {m^{2}-1}{8}}2^{\frac {m-1}{2}}$.

It follows from (13), (15) and Lemma 2 that

$$N_{b} \in \left\{ 2^{m-2}+ (-1)^{\frac{m^{2}-1}{8}}2^{\frac{m-3}{2}}, \, 2^{m-2}+ [(-1)^{\frac{m^{2}-1}{8}}\pm 1]2^{\frac{m-3}{2}} \right\} $$

for any b ∈ GF(q)^∗. Hence, the weight wt(c _b ) of the codeword c _b in (14) satisfies

$${\text{wt}}({\mathbf{c}}_{b})=n_{0}-N_{b} \in \left\{ 2^{m-2}+ (-1)^{\frac{m^{2}-1}{8}}2^{\frac{m-3}{2}}, \, 2^{m-2}+ [(-1)^{\frac{m^{2}-1}{8}}\mp 1]2^{\frac{m-3}{2}} \right\}. $$

Define

$$\begin{array}{@{}rcl@{}} \mathit{w}_{1} &=& 2^{m-2}+ (-1)^{\frac{m^{2}-1}{8}}2^{\frac{m-3}{2}},\\ \mathit{w}_{2} &=& 2^{m-2}+ \left[(-1)^{\frac{m^{2}-1}{8}}- 1\right]2^{\frac{m-3}{2}},\\ \mathit{w}_{3} &=& 2^{m-2}+ \left[(-1)^{\frac{m^{2}-1}{8}} + 1\right]2^{\frac{m-3}{2}}. \end{array} $$

We now determine the number $A_{\mathit {w}_{i}}$ of codewords with weight w _i in ${\mathcal {C}}_{D}$. By Lemma 1, the minimum weight of the dual code ${\mathcal {C}}_{D}^{\perp }$ is at least 3. The first three Pless Power Moments [15, p.260] lead to the following system of equations:

$$ \left\{ \begin{array}{lll} A_{\mathit{w}_{1}}+A_{\mathit{w}_{2}}+A_{\mathit{w}_{3}} &=& 2^{m}-1,\\ \mathit{w}_{1}A_{\mathit{w}_{1}}+\mathit{w}_{2}A_{\mathit{w}_{2}}+\mathit{w}_{3}A_{\mathit{w}_{3}} &=& n 2^{m-1},\\ {\mathit{w}_{1}^{2}}A_{\mathit{w}_{1}}+{\mathit{w}_{2}^{2}}A_{\mathit{w}_{2}}+{\mathit{w}_{3}^{2}}A_{\mathit{w}_{3}} &=& n(n+1) 2^{m-2}, \end{array}\right. $$

(16)

where $n=2^{m-1}+(-1)^{\frac {m^{2}-1}{8}}2^{\frac {m-1}{2}}-1$. Solving the system of equations in (16) yields the weight distribution of Table 2. The dimension of the code ${\mathcal {C}}_{D}$ is m, as wt(c _b )>0 for each b ∈ GF(q)^∗. The conclusions on the dual code ${\mathcal {C}}_{D}^{\perp }$ then follow on the length and the dimension of ${\mathcal {C}}_{D}$ and Lemma 1. This completes the proof of Theorem 4.

Below we prove Theorem 5

Let m ≥ 4 be even. To prove Theorem 5, we need the next two lemmas proved by Coulter [6].

Lemma 3

Let m ≥ 4 be even and a ∈ GF(q)^∗. Then

$$S(a, 0)=\left\{ \begin{array}{l} (-1)^{\frac{m}{2}} 2^{\frac{m}{2}} \quad\text{ if}\; a \ne g^{3t}\; \text{for any}\; t, \\ -(-1)^{\frac{m}{2}} 2^{\frac{m}{2}+1} \text{ if}\; a = g^{3t}\; \text{for some}\; t, \end{array} \right. $$

where g is a generator of GF(q) ^∗.

Lemma 4

Let m ≥ 4 be even, b ∈ GF(q)^∗, f(x) = a ² x ⁴ + ax ∈ GF(q)[x], and let g be a generator of GF(q)^∗. There are the following two cases.

• (i) If a ≠ g ^3t for any t, then f is a permutation polynomial of GF(q). Let x ₀ be the unique element satisfying f(x ₀) = b ². Then

  $$S(a,b)=(-1)^{\frac{m}{2}} 2^{\frac{m}{2}} \chi_{1}\left( a {{x}_{0}^{3}}\right)=(-1)^{\frac{m}{2}} 2^{\frac{m}{2}} (-1)^{{\text{Tr}}\left( a {{x}_{0}^{3}}\right)}. $$

• (ii) If a = g ^3t for some t, then S(a, b) = 0 unless the equation f(x) = b ² is solvable. If this equation is solvable, with solution x ₀ say, then

  $$S(a,b)=\left\{ \begin{array}{ll} -(-1)^{\frac{m}{2}} 2^{\frac{m}{2}+1} (-1)^{{\text{Tr}}\left( a {{x}_{0}^{3}}\right)} & \text{ if}\; {\text{Tr}}(a)=0,\\ (-1)^{\frac{m}{2}} 2^{\frac{m}{2}} (-1)^{{\text{Tr}}\left( a {{x}_{0}^{3}}\right)} & \text{ if}\; {\text{Tr}}(a)\ne 0, \end{array}\right. $$

  where Tr is the trace function from GF(q) onto GF(2).

According to [7, p.29], the following lemma can be easily proved.

Lemma 5

Let m ≥ 4 be even and f(x) = a ² x ⁴ + ax ∈ GF(q)[x]. If a = 1 = g ^3t for some t, then the equation f(x) = 1 is solvable if and only if m ≡ 0(mod 4), where g is a generator of GF(q)^∗.

The next lemma will be employed later.

Lemma 6

Let m ≥ 4 be even. Then

$$S(1,1)=\left\{ \begin{array}{ll} 0 & \text{ if}\; m \equiv 2~(\text{mod}\, {4}),\\ -(-1)^{\frac{m}{4}} 2^{\frac{m}{2}+1} & \text{ if}\; m \equiv 0~(\text{mod}\, {4}). \end{array}\right. $$

Proof

Let m ≥ 4 be even. It is well known that $\gcd (3,2^{m}-1)=3$. Hence, there exists $t=\frac {2^{m}-1}{3}$ such that g ^3t = 1. Note that TR(1)=0, as m is even. It then follows from Lemmas 4 and 5 that

$$\begin{array}{lll} S(1,1) &=& \left\{ \begin{array}{ll} 0 & \text{ if}\; m \equiv 2~(\text{mod}\, {4})\\ -2^{\frac{m}{2}+1} (-1)^{{\text{Tr}}\left( {{x}_{0}^{3}}\right)} & \text{ if}\; m \equiv 0~(\text{mod}\, {4}) \end{array}\right.\\ &=& \left\{ \begin{array}{ll} 0& \text{ if}\; m \equiv 2~(\text{mod}\, {4})\\ -2^{\frac{m}{2}+1} (-1)^{\frac{m}{4} (\text{mod}\, {2})} & \text{ if}\; m \equiv 0~(\text{mod}\, {4}) \end{array}\right.\\ &=& \left\{ \begin{array}{ll} 0 & \text{ if}\; m \equiv 2~(\text{mod}\, {4}),\\ -2^{\frac{m}{2}+1} (-1)^{\frac{m}{4}} & \text{ if}\; m \equiv 0~(\text{mod}\, {4}), \end{array}\right. \end{array} $$

where x ₀ is a solution of the equation x ⁴ + x = 1 when m ≡ 0(mod 4). This completes the proof. □

We are now ready to prove Theorem 5. Recall that m ≥ 4 is even. It follows from (12) and Lemma 6 that the length n of the code ${\mathcal {C}}_{D}$ in Theorem 5 is given by

$$ n = \left\{ \begin{array}{ll} 2^{m-1}-1 & \text{ if}\; m \equiv 2\, (\text{mod}\, {4}),\\ 2^{m-1}-2^{\frac{m}{2}} (-1)^{\frac{m}{4}}-1 & \text{ if}\; m \equiv 0\, (\text{mod}\, {4}). \end{array}\right. $$

(17)

Since $\gcd (3, 2^{m}-1)=3$, there exists $t=\frac {2^{m}-1}{3}$ such that g ^3t = 1. Note that Tr(1)=0, as m is even. It follows from Lemmas 3 and 4 that

$$ S(1,b+1) \in \left\{0, \pm (-1)^{\frac{m}{2}} 2^{\frac{m}{2}+1} \right\} $$

(18)

for any b ∈ GF(q)^∗.

It then follows from (13), (18) and Lemma 6 that

$$N_{b} \in \{u_{1},~\pm u_{2}+u_{1}\} $$

when m ≡ 2 (mod 4), and

$$N_{b} \in \left\{u_{1}-(-1)^{\frac{m}{4}}u_{2},(-(-1)^{\frac{m}{4}}\pm 1)u_{2}+u_{1}\right\} $$

when m ≡ 0 (mod 4), for any b ∈ GF(q)^∗, where u ₁ = 2^m−2 and $u_{2}=2^{\frac {m}{2}-1}$. Hence, the weight wt(c _b ) of the codeword of (14) satisfies

$${\text{wt}}({\mathbf{c}}_{b})=n_{0}-N_{b} \in \left\{ \begin{array}{l} \{u_{1},u_{1}\pm u_{2}\} \text{ if \(m \equiv 2 (\text{mod}\, {4}) \)} \\ \{u_{1}-(-1)^{\frac{m}{4}}u_{2},u_{1}-((-1)^{\frac{m}{4}}\pm 1)u_{2}\} \text{ if \(m \equiv 0 (\text{mod}\, {4}) \)} \end{array}\right. $$

and the code ${\mathcal {C}}_{D}$ has all the three weights in the set above.

Define u ₁ = 2^m−2, $u_{2}=2^{\frac {m}{2}-1}$, $u=u_{1}-(-1)^{\frac {m}{4}}u_{2}$ and

$$\left\{ \begin{array}{ll} w_{1}=u_{1},\ w_{2}=u_{1}+u_{2},\ w_{3}=u_{1}-u_{2} & \text{if \(m \equiv 2\, (\text{mod}\, {4}) \)}\\ w_{1}=u,\ w_{2}=u-u_{2},\ w_{3}=u+u_{2} & \text{if \(m \equiv 0\, (\text{mod}\, {4}) \)}. \end{array}\right. $$

We now determine the number $A_{w_{i}}$ of codewords with weight w _i in ${\mathcal {C}}_{D}$. By Lemma 1, the minimum weight of the dual code ${\mathcal {C}}_{D}^{\perp }$ is at least 3. The first three Pless Power Moments [15, p.260] lead to the following system of equations:

$$ \left\{ \begin{array}{lll} A_{w_{1}}+A_{w_{2}}+A_{w_{3}} &=& 2^{m}-1,\\ w_{1}A_{w_{1}}+w_{2}A_{w_{2}}+w_{3}A_{w_{3}} &=& n 2^{m-1},\\ {w_{1}^{2}}A_{w_{1}}+{w_{2}^{2}}A_{w_{2}}+{w_{3}^{2}}A_{w_{3}} &=& n(n+1) 2^{m-2}, \end{array}\right. $$

(19)

where n is given in (17). Solving the system of equations in (19) proves the weight distribution of the code ${\mathcal {C}}_{D}$ in Tables 3 and 4. The dimension of the code ${\mathcal {C}}_{D}$ is m, as wt(c _b )>0 for each b ∈ GF(q)^∗. The conclusions on the dual code ${\mathcal {C}}_{D}^{\perp }$ then follow on the length and the dimension of ${\mathcal {C}}_{D}$ and Lemma 1. This completes the proof of Theorem 5.

6.3 Applications of the binary codes in secret sharing

Any linear code over GF(p) can be employed to construct secret sharing schemes [1, 4, 18]. In order to obtain secret sharing schemes with interesting access structures, one would like to have linear codes ${\mathcal {C}}$ such that $w_{\min }/w_{\max } > \frac {p-1}{p}$ [18], where w _min and w _max denote the minimum and maximum nonzero weight of the linear code.

When m ≡ 2 (mod 4) and m ≥ 6, the code ${\mathcal {C}}_{D}$ of Section 6.1 satisfies that

$$\frac{w_{\min}}{w_{\max}} = \frac{2^{m-2}-2^{(m-2)/2}}{2^{m-2}+2^{(m-2)/2}} > \frac{1}{2}. $$

When m ≡ 4 (mod 8) and m > 4, the code ${\mathcal {C}}_{D}$ of Section 6.1 satisfies that

$$\frac{w_{\min}}{w_{\max}} = \frac{2^{m-2}}{2^{m-2}+2^{m/2}} > \frac{1}{2}. $$

When m ≡ 0 (mod 8) and m ≥ 8, the code ${\mathcal {C}}_{D}$ of Section 6.1 satisfies that

$$\frac{w_{\min}}{w_{\max}} = \frac{2^{m-2}-2^{m/2}}{2^{m-2}} > \frac{1}{2}. $$

When m ≡ ±1 (mod 8) and m ≥ 7, the code ${\mathcal {C}}_{D}$ of Section 6.1 satisfies that

$$\frac{w_{\min}}{w_{\max}} = \frac{2^{m-2}}{2^{m-2}+2^{(m-1)/2}} > \frac{1}{2}. $$

When m ≡ ±3 (mod 8) and m > 5, the code ${\mathcal {C}}_{D}$ of Section 6.1 satisfies that

$$\frac{w_{\min}}{w_{\max}} = \frac{2^{m-2}-2^{(m-1)/2}}{2^{m-2}} > \frac{1}{2}. $$

Hence, the linear codes ${\mathcal {C}}_{D}$ of Section 6.1 satisfy the condition that $w_{\min }/w_{\max } > \frac {1}{2}$ when m ≥ 6, and can thus be employed to obtain secret sharing schemes with interesting access structures using the framework in [18]. Note that binary linear codes can be employed for secret sharing bit by bit. Hence, a secret of any size can be shared with a secret sharing scheme based on a binary linear code. We remark that the dimension of the code ${\mathcal {C}}_{D}$ of this paper is small compared with its length and this makes it suitable for the application in secret sharing.

7 Concluding remarks

In this paper, we established a few relations among the parameters of a few subclasses of linear codes ${\mathcal {C}}_{D}$ (i.e., Theorem 1, Corollaries 1 and 2, Theorem 2, Corollary 5). With these relations, a number of classes of one-weight, two-weight and three-weight codes are derived from some known classes of one-weight, two-weight and three-weight codes. Instead of writing down all these codes, we documented a few classes of them as examples in this paper. We also constructed a class of three-weight binary codes described in Theorems 4 and 5.

The codes presented in this paper are interesting, as one-weight codes, two-weight codes and three-weight codes have applications in secret sharing [1, 4, 18], authentication codes [12], combinatorial designs and graph theory [2, 3], and association schemes [2].

Every linear code over a finite field is generated by a generator matrix. Different ways of constructing the generator matrix give different constructions of linear codes. Similarly, different ways of constructing the defining set D for the generic constriction of linear codes in this paper are different constructions of the linear codes ${\mathcal {C}}_{D}$. There are a huge number of ways of constructing the defining D, and thus many different constructions of the codes ${\mathcal {C}}_{D}$. The difficulty is the selection of D so that the code ${\mathcal {C}}_{D}$ has good parameters. Note that the generic construction of linear codes ${\mathcal {C}}_{D}$ of this paper is different from the one in [4].