Several classes of binary linear codes and their weight enumerators

Abstract

In the past decades, linear codes with a few weights have been extensively studied for their applications in space communication, data storage and cryptography etc. We construct several classes of binary linear codes and determine their weight distributions. Most of these codes can be used in secret sharing schemes.

1 Introduction

Throughout this paper, let $q=2^{m}$ for a positive integer m. Let ${\mathbb {F}}_q$ denote the finite field with q elements and g be a generator of ${\mathbb {F}}_q^{*}={\mathbb {F}}_{q}\backslash \{0\}$.

Let ${\mathbb {F}}_2^{n}$ denote the vector space of all n-tuples over the binary field ${\mathbb {F}}_2$. A binary code C of length n is a subset of ${\mathbb {F}}_2^{n}$. Usually, the vectors in C are called codewords of C. For any codewords ${\mathbf {x}}$ and ${\mathbf {y}}$ in C, the Hamming distance $d({\mathbf {x}},{\mathbf {y}})$ is defined as the number of coordinates in which ${\mathbf {x}}$ and ${\mathbf {y}}$ differ. The minimum distance of a code C is the smallest distance between distinct codewords. An [n, k, d] binary linear code C is defined as a k-dimensional subspace of ${\mathbb {F}}_2^{n}$ with minimum (Hamming) distance d.

For a codeword ${\mathbf {c}}\in C$, the (Hamming) weight $wt({\mathbf {c}})$ is the number of nonzero coordinates in ${\mathbf {c}}$. We use $A_{i}$ to denote the number of codewords of weight i in C. Then $(1, A_1,\ldots ,A_{n})$ is called the weight distribution of C,  and the weight enumerator is defined as the polynomial $1+A_1x+A_2x^{2}+\cdots +A_{n}x^{n}$. If the number of nonzero $A_{i}$ ($1\le i\le n$) equals t, then C is called a t-weight code. The reader is referred to [23] for the general theory of linear codes.

The weight distribution is an important research topic in coding theory, as it contains crucial information for computing the probability of error correction and detection. A great deal of researchers are devoted to constructing and determining specific linear codes [6, 15, 17, 26, 29, 30, 33]. The weight distribution of Reed–Solomon codes was determined by Blake [1] and Kith [24]. A survey of the Hamming weights of irreducible cyclic codes was given by Ding and Yang in [16]. The weight distributions of reducible cyclic codes can be found in [13, 19,20,21, 25, 35].

Recently, in [9, 14], Ding proposed a generic construction of linear codes as follows.

Let $D=\{d_1,d_2,\ldots , d_n\} \subseteq {\mathbb {F}}_{q}^{*}$ and ${\mathrm {Tr}}$ denote the absolute trace function from ${\mathbb {F}}_q$ onto its prime subfield ${\mathbb {F}}_p$. A linear code $C_D$ of length n can be constructed by

$$\begin{aligned} C_{D}=\{\left( {\mathrm {Tr}}(xd_1), {\mathrm {Tr}}(xd_2),\ldots , {\mathrm {Tr}}(xd_{n})\right) :x\in \mathbb {F}_{q}\}. \end{aligned}$$

Here and hereafter D is called the defining set of $C_{D}$. This method has been widely used in the literature to acquire linear codes with a few weights [8, 10,11,12, 18, 31, 32, 34, 37,38,39].

Choosing the defining set D is an important and interesting problem. Several kinds of defining sets were discussed in [9]. For example, D can optionally be the preimage of quadratic forms over ${\mathbb {F}}_q$ for odd characteristic p [33, 34]. Using the theory of quadratic forms, the authors of [33, 34] determined the weight distributions.

Motivated by the work in [9] and [10], for a subset D of ${\mathbb {F}}_{q}^{*},$ we can construct a class of linear codes $\overline{C}_{D}$ by the image (multiset) of D under a function f over ${\mathbb {F}}_{q}.$ Namely, we define $\overline{C}_{D}$ as

$$\begin{aligned} \overline{C}_{D}=\left\{ \left( {\mathrm {Tr}}\left( xf(d)\right) \right) _{d\in D}: x\in {\mathbb {F}}_q \right\} . \end{aligned}$$

(1)

In the paper, we choose $f(x)=x^{2^{h}+1},$ where $h<m$ is a positive factor of m. Note that f is a quadratic form over ${\mathbb {F}}_q$.

Generally speaking, the theory and results of quadratic forms on a finite field with an odd characteristic cannot be easily extended to those of quadratic forms on a finite field with characteristic 2. We shall employ exponential sums to investigate the weight distributions of the following two classes of binary linear codes $\overline{C}_{D}$ with

$$\begin{aligned}&D=D_{a}=\{x\in {\mathbb {F}}_q^{*}: {\mathrm {Tr}}(x)=a\}, \ a \in {\mathbb {F}}_{2}, \end{aligned}$$

(2)

$$\begin{aligned}&D={\mathbb {F}}_q^{*}. \end{aligned}$$

(3)

Naturally, a generalization of the code $\overline{C}_{D}$ is defined as

$$\begin{aligned} \overline{C}^{\prime }_{D}=\left\{ \left( {\mathrm {Tr}}\left( xd^{2^{h}+1}+u\right) \right) _{d\in D}: u\in {\mathbb {F}}_{2},\ x\in {\mathbb {F}}_{q} \right\} . \end{aligned}$$

(4)

The weight distributions of linear codes $\overline{C}_{D_{a}}$ and $\overline{C}^{\prime }_{D_{a}}$ are then settled and the main results are listed as follows.

Table 1 The weight distribution of the codes of Theorem 1

Theorem 1

Let m / h be odd. Then, the code $\overline{C}_{D_{a}}$ of (2) is a $[2^{m-1}-1+a, m]$ binary linear code with the weight distribution in Table 1.

Corollary 1

Let m / h be odd. Then, the code $\overline{C}^{\prime }_{D_{1}}$ defined in (4) is a $[2^{m-1}, m+1]$ binary linear code with the weight distribution in Table 2.

Table 2 The weight distribution of the codes of Corollary 1

Corollary 2

Let m / h be odd. Then, the code $\overline{C}^{\prime }_{D_{0}}$ defined in (4) is a $[2^{m-1}-1, m+1]$ binary linear code with the weight distribution in Table 3.

Table 3 The weight distribution of the codes of Corollary 2

The above theorem presents the parameters of $\overline{C}_{D_a}$$(a=0,1)$ for the case in which $m/h\equiv 1\pmod {2}$. Next, we assume m / h is even and $m=2e$ for a positive integer $e>1$. In this case, the parameters of $\overline{C}_{D_a}$$(a=0,1)$ are given in the two theorems below.

Theorem 2

Let m / h be even and $m/h>2$. Then, the code $\overline{C}_{D_{0}}$ of (2) is a $[2^{m-1}-1, m]$ binary linear code with the weight distribution in Table 4.

Table 4 The weight distribution of the codes of Theorem 2

Corollary 3

Let m / h be even. Then, the code $\overline{C}^{\prime }_{D_{0}}$ defined in (4) is a $[2^{m-1}-1, m+1]$ binary linear code with the weight distribution in Table 5.

Table 5 The weight distribution of the codes of Corollary 3

Theorem 3

Let m / h be even and $m/h>2$. Then, the code $\overline{C}_{D_{1}}$ of (2) is a $[2^{m-1}, m]$ binary linear code with the weight distribution in Table 6.

Table 6 The weight distribution of the codes of Theorem 3

Corollary 4

Let m / h be even. Then, the code $\overline{C}^{\prime }_{D_{1}}$ defined in (4) is a $[2^{m-1}, m+1]$ binary linear code with the weight distribution in Table 7.

Table 7 The weight distribution of the codes of Corollary 4

Let $D={\mathbb {F}}_{q}^{*}$. If m / h is odd, then $\gcd \left( 2^{h}+1,2^{m}-1\right) =1$ (Lemma 2.1, [5]). So $f(x)=x^{2^{h}+1}$ is a permutation polynomial over ${\mathbb {F}}_{q}^{*}.$ It is well known that $|\{x \in {\mathbb {F}}_{q}^{*}: {\mathrm {Tr}}(\alpha x)=0\}|=2^{m-1}-1$ for every $\alpha \in {\mathbb {F}}_{q}^{*}.$ Therefore, we have that $\overline{C}_D$ of (3) is a constant-weight linear code with parameters $[2^m-1,m,2^m-2^{m-1}]$. It is optimal by the Griesmer bound (Chapter 2, [23]) in this case. If $m/h>2$ is even, the code $\overline{C}_D$ is a two-weight binary linear code, and the weight distribution of $\overline{C}_{D}$ is given in Theorem 4 below.

Theorem 4

Let $m/h>2$ be even and $D={\mathbb {F}}_{q}^{*}$. Then the code $\overline{C}_{D}$ of (3) is a $[2^{m}-1, m]$ binary linear code with the weight distribution in Table 8.

Table 8 The weight distribution of the codes of Theorem 4

If m / h is even, we know $\gcd (2^{h}+1,2^{m}-1)=2^{h}+1$, i.e., $2^{h}+1 \mid 2^{m}-1$. Hence $f(x)=x^{2^{h}+1}$ is a $(2^{h}+1)$-to-1 function over ${\mathbb {F}}_{q}^{*}$ in the case that $m/h\equiv 0\pmod {2}$. This implies that a binary code can be punctured from the code $\overline{C}_{D}$ in Theorem 4.

Let $\overline{D}=\{x^{2^{h}+1}:x\in {\mathbb {F}}_{q}^{*}\}$ and

$$\begin{aligned} {\overline{C}}_{\overline{D}}=\left\{ \left( {\mathrm {Tr}}(xd)\right) _{d\in \overline{D}}:x\in {\mathbb {F}}_{q}\right\} . \end{aligned}$$

(5)

Then the parameters of $\overline{C}_{\overline{D}}$ can easily be derived from those of the code $\overline{C}_{D}$ in Theorem 4, and are given in the following corollary.

Corollary 5

Let $m/h>2$ be even. Then the code $\overline{C}_{\overline{D}}$ is a $[(2^{m}-1)/(2^{h}+1), m]$ binary linear code with the weight distribution in Table 9.

Table 9 The weight distribution of the codes of Corollary 5

Example 1

Let $(m,h)=(5,1)$. A Magma program shows that $\overline{C}_{D_0}$ has parameters [15, 5, 6] and weight enumerator $1+10x^{6}+15x^{8}+6x^{10},$ while $\overline{C}_{D_1}$ has parameters [16, 5, 6] and weight enumerator $1+6x^{6}+15x^{8}+10x^{10},$ which both agree with Theorem 1. Here $\overline{C}_{D_0}$ is almost optimal since the optimal one has parameters [15, 5, 7].

Example 2

If $(m,h)=(6,1),$ a Magma program shows that $\overline{C}_{D_0}$ has parameters [31, 6, 8] and weight enumerator $1+3x^{8}+16x^{12}+26x^{16}+18x^{20}.$ If $(m,h)=(8,2),$ a Magma program shows that $\overline{C}_{D_0}$ has parameters [127, 8, 56] and weight enumerator $1+108x^{56}+98x^{64}+48x^{80}+x^{96}.$ Therefore, our experimental results here agree with Theorem 2. Note that the code $\overline{C}_{D_0}$ with parameters [31, 6, 8] is far from being optimal, since an optimal [31, 6] code has minimum distance 15. And the code $\overline{C}_{D_1}$ with parameters [127, 8, 56] is close to an optimal code, since an optimal [127, 8] code has minimum distance 63.

Example 3

If $(m,h)=(6,1),$ a Magma program shows that $\overline{C}_{D_1}$ has parameters [32, 6, 8] and weight enumerator $1+2x^{8}+16x^{12}+21x^{16}+24x^{20}.$ If $(m,h)=(8,2),$ a Magma program shows that $\overline{C}_{D_1}$ has parameters [128, 8, 56] and weight enumerator $1+96x^{56}+109x^{64}+48x^{80}+2x^{96}.$ Therefore, our experimental results here agree with Theorem 3.

Example 4

If $(m,h)=(8,1),$ a Magma program shows that $\overline{C}_{D}$ has parameters [255, 8, 120] and weight enumerator $1+170x^{120}+85x^{144}.$ If $(m,h)=(8,2),$ a Magma program shows that $\overline{C}_{D}$ has parameters [255, 8, 120] and weight enumerator $1+204x^{120}+51x^{160}.$ Therefore, our experimental results here agree with Theorem 4. Here the code $\overline{C}_{\overline{D}}$ in Corollary 5 in the two specific cases has parameters [85, 8, 40] and [51, 8, 24],  respectively, both of which are optimal due to the Griesmer bound.

2 Preliminaries

In this section, we present some results on exponential sums, which will be needed in calculating the weight distributions of the codes of (2).

An additive character of ${\mathbb {F}}_{q}$ is a group homomorphism $\chi$ from $\left( {\mathbb {F}}_{q},+\right)$ into the multiplicative group of complex numbers of absolute value 1, i.e., $\chi (g_1+g_2)=\chi (g_1)\chi (g_2)$ for all $g_1$, $g_2\in {\mathbb {F}}_{q}.$ Each additive character over ${\mathbb {F}}_{q}$ can be given by

$$\begin{aligned} \chi _{b}(c)=(-1)^{{\mathrm {Tr}}(bc)} \ {\text {for all }}\ c\in {\mathbb {F}}_{q}, \end{aligned}$$

for some $b\in {\mathbb {F}}_{q}.$ The additive character $\chi _0$ is called trivial, whereas other characters $\chi _{b}$ with $b\in {\mathbb {F}}_{q}^{*}$ are called nontrivial. Among the additive characters of ${\mathbb {F}}_{q},$ we have the canonical additive character$\chi _{1}$ defined by $\chi _1(c)=(-1)^{{\mathrm {Tr}}(c)}$ for all $c\in {\mathbb {F}}_{q}$. See [27] for more information about characters over finite fields.

Define the exponential sum

$$\begin{aligned} S_{h}(a,b)=\sum _{x\in {\mathbb {F}}_{q}}\chi _1\left( ax^{2^{h}+1}+bx\right) , \end{aligned}$$

where $a\in {\mathbb {F}}_{q}^{*}$, $b \in {\mathbb {F}}_{q},$ and h is a proper positive divisor of m. In general, to evaluate an exponential sum over a finite field is challenging. So far it has been determined only in certain special cases [2,3,4,5, 20, 22]. The following lemmas present the values of $S_h(a,b).$

Lemma 1

(Theorem 4.1, [5]) If m / h is odd, then $\sum _{x\in {\mathbb {F}}_{q}}\chi _1\left( ax^{2^{h}+1}\right) =0$ for each $a\in {\mathbb {F}}_{q}^{*}.$

Lemma 2

(Theorem 4.2, [5]) Let $b\in {\mathbb {F}}_{q}^{*}$ and suppose m / h is odd. Then, $S_{h}(a,b)=S_{h}(1,bc^{-1}),$ where $c\in {\mathbb {F}}_{q}^{*}$ is the unique element satisfying $c^{2^{h}+1}=a.$ Further, we have

$$\begin{aligned} S_{h}(1,b)=\left\{ \begin{array}{ll} 0, &{}\quad {\text {if }} \ {\mathrm {Tr}}_{h}(b)\ne 1, \\ \pm 2^{\frac{m+h}{2}}, &{}\quad {\text {if }} \ {\mathrm {Tr}}_{h}(b)= 1, \end{array} \right. \end{aligned}$$

where and hereafter ${\mathrm {Tr}}_{h}$ is the trace function from ${\mathbb {F}}_{q}$ to ${\mathbb {F}}_{2^{h}}.$

Lemma 3

(Theorem 5.2, [5]) Let m / h be even and $m=2e$ for some integer e. Then,

$$\begin{aligned} S_{h}(a,0)=\left\{ \begin{array}{ll} (-1)^{\frac{e}{h}}2^{e}, &{}\quad {\text {if }}\ \ a\ne g^{t(2^{h}+1)} {\text { for any integer }} t, \\ -(-1)^{\frac{e}{h}}2^{e+h}, &{}\quad {\text {if }} \ a= g^{t(2^{h}+1)} {\text { for some integer }} t, \end{array} \right. \end{aligned}$$

where g is a generator of ${\mathbb {F}}_{q}^{*}.$

Lemma 4

(Theorem 5.3, [5]) Let $b\in {\mathbb {F}}_{q}^{*}$ and suppose m / h is even such that $m=2e$ for some integer e. Let $f(x)=a^{2^{h}}x^{2^{2h}}+ax \in {\mathbb {F}}_{q}[x].$ There are two cases.

• 1. If $a\ne g^{t\left( 2^{h}+1\right) }$ for any integer t,  then f is a permutation polynomial of ${\mathbb {F}}_{q}.$ Let $x_{0}$ be the unique element satisfying $f(x)=b^{2^{^{h}}}.$ Then,

  $$\begin{aligned} S_{h}(a,b) =(-1)^{\frac{e}{h}}2^{e}\chi _1\left( ax_{0}^{2^{h}+1}\right) . \end{aligned}$$

• 2. If $a= g^{t\left( 2^{h}+1\right) },$ then $S_{h}(a,b)=0$ unless the equation $f(x)=b^{2^{^{h}}}$ is solvable. If the equation is solvable, with solution $x_{0}$ say, then,

  $$\begin{aligned} S_{h}(a,b) =\left\{ \begin{array}{ll} -(-1)^{\frac{e}{h}}2^{e+h}\chi _1\left( ax_{0}^{2^{h}+1}\right) , &{}\quad {\text {if }} \ {\mathrm {Tr}}_{h}(a)= 0, \\ (-1)^{\frac{e}{h}}2^{e}\chi _1\left( ax_{0}^{2^{h}+1}\right) , &{}\quad {\text {if }} \ {\mathrm {Tr}}_{h}(a)\ne 0. \end{array} \right. \end{aligned}$$

Lemma 5

(Theorem 3.1, [5]) Let g be a primitive element of ${\mathbb {F}}_{q}$. For any $a\in {\mathbb {F}}_{q}^{*},$ consider the equation $a^{2^{h}}x^{2^{2h}}+ax=0$ over ${\mathbb {F}}_{q}$.

• 1. If m / h is odd, then there are $2^{h}$ solutions to this equation for any choice of $a\in {\mathbb {F}}_{q}^{*}$.

• 2. If m / h is even, then there are two possible cases. If $a=g^{t(2^{h}+1)}$ for some t, then there are $2^{2h}$ solutions to this equation. If $a\ne g^{t(2^{h}+1)}$ for any t,  then there exists one solution only, $x=0$.

3 Proofs

We follow the notation from Sect. 2 above. In this section, we determine the length of the code $\overline{C}_{D_a}$$(a=0,1)$ of (2) and provide a formula for the weight of a codeword ${\mathbf {c}}_{b}$$(b\in {\mathbb {F}}_{q}^{*})$ in $\overline{C}_{D_a}$$(a=0,1).$ We also provide the proofs of the presented theorems. As for the corollaries, it is not difficult to prove them via their corresponding theorems, thus we omit the details.

By the definition of $D_a$$(a=0,1),$ we know

$$\begin{aligned} |D_{a}|=\left\{ \begin{array}{ll} 2^{m-1}-1, &{}\quad {\text {if }} \ a=0, \\ 2^{m-1}, &{}\quad {\text {if }} \ a=1. \end{array} \right. \end{aligned}$$

We define $N(a,b)=\{x\in {\mathbb {F}}_{q}: {\mathrm {Tr}}(x)=a {\text { and }} {\mathrm {Tr}}(bx^{2^{h}+1})=0\},$ and denote by $wt({\mathbf {c}}_b)$ the Hamming weight of the codeword ${\mathbf {c}}_b$ with $b\in {\mathbb {F}}_{q}^{*}$ of the code $\overline{C}_{D_{a}}$$(a=0,1)$. It can be easily checked that

$$\begin{aligned} wt({\mathbf {c}}_{b})=2^{m-1}-|N(a,b)|. \end{aligned}$$

(6)

In terms of exponential sums, for $b\in {\mathbb {F}}_{q}^{*},$ we have

$$\begin{aligned} |N(a,b)|= & {} 2^{-2}\sum \nolimits _{x\in {\mathbb {F}}_{q}}\left( \sum \nolimits _{y \in {\mathbb {F}}_{2}}(-1)^{y{\mathrm {Tr}}(x)-ya}\right) \left( \sum \nolimits _{z \in {\mathbb {F}}_{2}}(-1)^{z{\mathrm {Tr}}\left( bx^{2^{h}+1}\right) }\right) \\= & {} 2^{-2}\sum \nolimits _{x\in {\mathbb {F}}_{q}}\left( 1+(-1)^{{\mathrm {Tr}}(x)-a}\right) \left( 1+(-1)^{{\mathrm {Tr}}\left( bx^{2^{h}+1}\right) }\right) \\= & {} 2^{m-2} + 2^{-2}\sum \nolimits _{x\in {\mathbb {F}}_{q}}(-1)^{{\mathrm {Tr}}\left( bx^{2^{h}+1}\right) } \quad + 2^{-2}\sum \nolimits _{x\in {\mathbb {F}}_{q}}(-1)^{{\mathrm {Tr}}\left( x+bx^{2^{h}+1}\right) -a} \\= & {} 2^{m-2} + 2^{-2}\left( S_{h}(b,0)+(-1)^{a}S_{h}(b,1)\right) . \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ (6^{\prime }) \end{aligned}$$

Based on the above discussion, the weight distribution of $\overline{C}_{D_a}$ can be determined by using the value distribution of $S_h(b,c)$ with $b\in {\mathbb {F}}_{q}^{*}$ and $c\in {\mathbb {F}}_{2}$. By the lemmas presented in Sect. 2, we are ready to compute the weight distributions of the codes $\overline{C}_{D_a}$$(a=0,1)$.

Proof of Theorem 1

We present only the proof for $\overline{C}_{D_0},$ since the proof for the case in which $a=1$ is similar. By Lemma 1, we have $S_{h}(b,0)=0$ for $b \in {\mathbb {F}}_{q}^{*}.$ It follows from Lemma 2 that

$$\begin{aligned} S_{h}(b,1)=S_{h}\left( 1,c^{-1}\right) =\left\{ \begin{array}{ll} 0, &{}\quad {\text {if }} \ {\mathrm {Tr}}_{h}\left( c^{-1}\right) \ne 1, \\ \pm 2^{\frac{m+h}{2}}, &{}\quad {\text {if }} \ {\mathrm {Tr}}_{h}\left( c^{-1}\right) = 1, \end{array} \right. \end{aligned}$$

(7)

where $b\in {\mathbb {F}}_{q}^{*}$ and $c^{2^{h}+1}=b$. We get

$$\begin{aligned} |N(0,b)| \in \left\{ 2^{m-2},2^{m-2}-2^{\frac{m+h-4}{2}},2^{m-2}+2^{\frac{m+h-4}{2}}\right\} . \end{aligned}$$

Hence, the weight $wt({\mathbf {c}}_b)$ of the codeword ${\mathbf {c}}_b$$(b\in {\mathbb {F}}_{q}^{*})$ in $\overline{C}_{D_0}$ satisfies

$$\begin{aligned} wt({\mathbf {c}}_{b})\in \left\{ 2^{m-2},2^{m-2}\pm 2^{\frac{m+h-4}{2}}\right\} . \end{aligned}$$

Suppose $w_{1}=2^{m-2}-2^{\frac{m+h-4}{2}},\ w_{2}=2^{m-2},\ w_{3}=2^{m-2}+2^{\frac{m+h-4}{2}}.$ Note that if m / h is odd, then $\gcd \left( 2^{h}+1,2^{m}-1\right) =1$. This means that when b ranges over ${\mathbb {F}}_{q}^{*}$, the element c with $c^{2^{h}+1}=b$ takes on each element of ${\mathbb {F}}_{q}^{*}$ exactly once. Hence, we obtain

$$\begin{aligned}&\left| \left\{ c\in {\mathbb {F}}_{q}^{*}:{\mathrm {Tr}}_{h}\left( c^{-1}\right) \ne 1,c^{2^{h}+1}=b {\text { and }} b\in {\mathbb {F}}_{q}^{*}\right\} \right| \\&\quad =2^{m}-1-\left| \left\{ c\in F_{q}^{*}:{\mathrm {Tr}}_{h}\left( c^{-1}\right) =1,c^{2^{h}+1}=b {\text { and }} b\in {\mathbb {F}}_{q}^{*}\right\} \right| \\&\quad =2^{m}-2^{m-h}-1, \end{aligned}$$

i.e., $A_{w_{2}}=2^{m}-2^{m-h}-1$. (Please see the definition of $A_{i}$ in the second paragraph of page 2.) The first two Pless Power Moments (Page 260, [23]) yield the following two equations:

$$\begin{aligned} \left\{ \begin{array}{l} A_{w_1}+A_{w_2}+A_{w_3}=2^{m}-1, \\ w_1A_{w_1}+w_2A_{w_2}+w_3A_{w_3}=n2^{m-1}. \end{array} \right. \end{aligned}$$

(8)

Here $n=2^{m-1}-1.$ Solving the system of equations (8), we get Theorem 1. And we complete the proof. $\square$

Next, we assume $m/h \equiv 0 \pmod {2}$, $m=2e,$ and g is a generator of ${\mathbb {F}}_{q}^{*}.$ In order to give a proof of Theorem 2, we need the following auxiliary lemma. This lemma can be found in equation (10) in [10].

Lemma 6

Let $T_{0}=\left\{ x\in {\mathbb {F}}_{q}:{\mathrm {Tr}}\left( x^{2^{h}+1}\right) =0\right\}$ and $T_{1}={\mathbb {F}}_{q}\backslash T_{0}.$ If m / h is even with $m=2e$, then $|T_{0}|=2^{m-1}-(-1)^{\frac{e}{h}}2^{e+h-1}$ and $|T_{1}|=2^{m-1}+(-1)^{\frac{e}{h}}2^{e+h-1}.$

Proof of Theorem 2

For $b\in {\mathbb {F}}_{q}^{*}$, if $b\ne g^{t\left( 2^{h}+1\right) }$ for any integer t, then by Lemma 3, we have $S_{h}(b,0)=(-1)^{\frac{e}{h}}2^{e},$ and by Lemma 4, we get

$$\begin{aligned} S_{h}(b,1)=(-1)^{\frac{e}{h}}2^{e}\chi _{1}\left( bx_{0}^{2^{h}+1}\right) , \end{aligned}$$

where $x_0$ satisfies $b^{2^{h}}x_{0}^{2^{2h}}+bx_{0}=1.$

If $b= g^{t\left( 2^{h}+1\right) }$ for some integer t,  then by Lemma 3, we obtain

$$\begin{aligned} S_{h}(b,0)=-(-1)^{\frac{e}{h}}2^{e+h}. \end{aligned}$$

Assume $c=g^{t}$, then $b=c^{2^{h}+1}$ and it follows from Lemma 2 that $S_{h}(b,1)=S_{h}\left( 1,c^{-1}\right) .$ For the above $c\in {\mathbb {F}}_{q}^{*}$, let $f_c(x)=x^{2^{2h}}+x-\left( c^{-1}\right) ^{2^{h}}.$ If $f_c(x)$ has no root in ${\mathbb {F}}_{q}^{*},$ by Lemma 4, we obtain $S_{h}(b,1)=S_{h}(1,c^{-1})=0.$ Note that ${\mathrm {Tr}}_{h}(1)=0$, since m / h is even. If $f_c(x)$ has a root $x_0$ in ${\mathbb {F}}_{q}^{*},$ by Lemma 4, we get

$$\begin{aligned} S_{h}(b,1)=S_{h}(1,c^{-1})=-(-1)^{\frac{e}{h}}2^{e+h}\chi _{1}\left( x_{0}^{2^{h}+1}\right) . \end{aligned}$$

By Equations (6) and $(6^{\prime }),$ we know that for $b\in {\mathbb {F}}_{q}^{*}, \ wt({\mathbf {c}}_b)$ belongs to the set

$$\begin{aligned} \left\{ 2^{m-2}+(-1)^{\frac{e}{h}}2^{e+h-1}, 2^{e-2}(2^{e}+(-1)^{\frac{e}{h}}2^{h}), 2^{m-2}, 2^{m-2}-(-1)^{\frac{e}{h}}2^{e-1} \right\} . \end{aligned}$$

Define $w_1=2^{m-2}+(-1)^{\frac{e}{h}}2^{e+h-1}, \ w_2=2^{e-2}(2^{e}+(-1)^{\frac{e}{h}}2^{h}),\ w_3=2^{m-2}, \ w_4=2^{m-2}-(-1)^{\frac{e}{h}}2^{e-1}.$

The next step is to determine the number $A_{w_i}$ of codewords with weight $w_i$. If $f_c(x)=0$ (for some $c\in {\mathbb {F}}_{q})$ is solvable in ${\mathbb {F}}_{q},$ by Lemma 5, there are $2^{2h}$ solutions of this equation over ${\mathbb {F}}_{q}$. Since $\gcd (2^h,2^m-1)=1$, it can be easily checked that $\left\{ x_0\in {\mathbb {F}}_{q}: x_0^{2^{2h}}+x_0=(c^{-1})^{2^{h}}, c\in {\mathbb {F}}_{q} \right\} ={\mathbb {F}}_{q}.$ Hence we get

$$\begin{aligned} \left| \left\{ c\in {\mathbb {F}}_{q}^{*}: x^{2^{2h}}+x=(c^{-1})^{2^{h}} {\text { is solvable in }} {\mathbb {F}}_{q}\right\} \right| =2^{m-2h}-1, \end{aligned}$$

and $\left| \left\{ c\in {\mathbb {F}}_{q}^{*}: x^{2^{2h}}+x=(c^{-1})^{2^{h}} {\text { has no root in }} {\mathbb {F}}_{q}\right\} \right| =2^{m}-2^{m-2h}.$

Since $x^{2^{h}+1}$ is a $(2^{h}+1)$-to-1 function on ${\mathbb {F}}_{q}$, there are $\frac{2^{m}-2^{m-2h}}{2^{h}+1}$ elements b ($b=c^{2^{h}+1}\in {\mathbb {F}}_{q}^{*}$) such that $S_{h}(b,1)=0$, i.e., $A_{w_{2}}=\frac{2^{m}-2^{m-2h}}{2^{h}+1}.$ It follows from Lemmas 4 and 6 that

$$\begin{aligned} \left| \left\{ c\in {\mathbb {F}}_{q}^{*}:S_{h}(1,c^{-1})=(-1)^{\frac{e}{h}}2^{e+h}\right\} \right| =\frac{2^{m-1}+(-1)^{\frac{e}{h}}2^{e+h-1}}{2^{2h}}. \end{aligned}$$

Then we have

$$\begin{aligned} \left| \left\{ b\in {\mathbb {F}}_{q}^{*}:b=c^{2^{h}+1} {\text { and }} S_{h}(b,1)=(-1)^{\frac{e}{h}}2^{e+h}\right\} \right| =\frac{2^{m-1}+(-1)^{\frac{e}{h}}2^{e+h-1}}{2^{2h}(2^{h}+1)}. \end{aligned}$$

Therefore, $A_{w_{1}}=\frac{2^{m-2h-1}-1-(-1)^{\frac{e}{h}}2^{e-h-1}}{2^{h}+1}.$ By the Pless Power Moments (Page 260, [23]), we obtain the following two equations:

$$\begin{aligned} \left\{ \begin{array}{l} A_{w_1}+A_{w_2}+A_{w_3}+A_{w_4}=2^{m}-1, \\ w_1A_{w_1}+w_2A_{w_2}+w_3A_{w_3}+w_4A_{w_4}=2^{m-1}(2^{m-1}-1). \end{array} \right. \end{aligned}$$

(9)

The solutions to the set of equations in (9) yield the weight distribution presented in Table 4. The proof of Theorem 2 is completed. $\square$

We omit a proof for Theorem 3, since it is similar to that of Theorem 2. By the proof of Theorem 2, it is also straightforward to prove Theorem 4. So the proof for Theorem 4 is left to the reader.

4 Concluding remarks

In this paper, we presented several classes of binary linear codes with a few weights. A number of linear codes with at most five weights were discussed in [7, 8, 11, 12, 38, 39]. Further, some interesting binary linear codes constructed by a similar method were presented in [10, 28, 30]. The binary codes presented in our paper were rather different than the above due to the following three reasons:

• 1. Most differently, the binary codes in our paper were defined by $C_{D}=\{({\mathrm {Tr}}(xf(d)))_{d\in D}: x \in {\mathbb {F}}_{q}\},$ where $f(d)=d^{2^{h}+1},$ whereas $f(d)=d$ was used in [10, 28, 30].

• 2. We selected the defining sets using a different approach, thereby causing the codes in our paper to have different lengths.

• 3. The binary linear codes in our paper were constructed with new parameters and have at most nine weights, whereas the binary codes in [10, 28, 30] have two or three weights.

It should be remarked that the parameters of the binary linear codes $\overline{C}_{D_{0}}$ in Theorem 1 are the same as those in Theorem 1 in [10]. By Magma, we found the code $\overline{C}_{D_{0}}$ to be equivalent to that in Theorem 1 of [10] for $(m,h)=(3,1).$ But for $(m,h)=(5,1)$ and (7, 1),  they are not equivalent. It is open whether the two classes of codes are equivalent or not. The reader is invited to attack this problem.

A polynomial of the form

$$\begin{aligned} f(x)=\sum _{i=0}^{m-1}\sum _{j=0}^{m-1}a_{ij}x^{2^{i}+2^{j}}, a_{ij} \in {\mathbb {F}}_{q} \end{aligned}$$

is called a quadratic form over ${\mathbb {F}}_{2^{m}}.$ It should be interesting to settle the parameters and weight distribution of $\overline{C}_{D}$ if we replace $x^{2^{h}+1}$ with more general quadratic forms.

Denote the minimum and maximum nonzero weights of a linear code C over ${\mathbb {F}}_{p}$ by $w_{\min }$ and $w_{\max },$ respectively. By the results in [36], if the code C satisfies the inequality

$$\begin{aligned} \frac{w_{\min }}{w_{\max }}> \frac{p-1}{p}, \end{aligned}$$

then C can be employed to construct secret sharing schemes with interesting properties.

Let $m > h+2.$ Then, for the codes in Theorem 1, we have

$$\begin{aligned} \frac{w_{\min }}{w_{\max }}=\frac{2^{m-2}-2^{\frac{m+h-4}{2}}}{2^{m-2}+2^{\frac{m+h-4}{2}}} >\frac{1}{2}. \end{aligned}$$

If $(m,h)\ne (4,1)$ or (6, 1),  then for the codes in Theorems 2 and 3, it can be easily checked that

$$\begin{aligned} \frac{w_{\min }}{w_{\max }}> \frac{1}{2}. \end{aligned}$$

This conclusion is also true for Theorem 4 and Corollary 5.

Hence, the binary linear codes presented in Theorems 1–4 and Corollary 5 are suitable for constructing secret sharing schemes in many cases.