Abstract
This paper presents four classes of linear codes from coset representatives of subgroups and cyclotomic coset families of certain finite field, and determines their weight enumerators. These linear codes may have applications in consumer electronics, communications and secret sharing schemes.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let q be a power of a prime p and \( {\mathbb F}_q\) be a finite field of size q. An [n, k, d] linear code \( {\mathcal C}\) over \( {\mathbb F}_q\) is a k-dimensional subspace of \( {\mathbb F}_q^{n}\) with minimum distance d. Let \(A_{i}\) denote the number of codewords with Hamming weight i in \( {\mathcal C}\). The weight enumerator of \( {\mathcal C}\) is defined by \(1+ A_1 x+ A_{2}x^{2} + \cdots + A_{n}x^{n}\). The weight distribution of a code not only gives the error correcting ability of the code, but also allows the computation of the probability of error detection and correction [12]. So the study of the weight distributions of linear codes is important in both theory and applications.
Let \( {\mathbb F}_{{q}^{m}}\) be a finite field with \({q}^{m}\) elements. Note that \( {\mathbb F}_{{q}^{m}}\) is the unique degree m extension of \( {\mathbb F}_q\). Let \(\mathrm{Tr}_q^{{q}^{m}}\) be the trace function from \( {\mathbb F}_{{q}^{m}}\) onto \( {\mathbb F}_q\). From a subset \(D=\{d_1, d_2, \ldots , d_n\}\subset {\mathbb F}_{{q}^{m}}\), we define a class of generic linear code of length \(n=|D|\) over \( {\mathbb F}_q\) as follows:
The dimension of \( {\mathcal C}_D\) equals the dimension of the vector space \(V_D\) generated by \(d_1, d_2, \ldots , d_n \in {\mathbb F}_{{q}^{m}}\) over \( {\mathbb F}_q\) [5]. If \(e=dim_{ {\mathbb F}_q} V_D<m\), then \( {\mathcal C}_D\) has repeated codewords and each codeword repeats \(q^{m-e}\) times. If \(e=m\) then each codeword occurs once. One may get different codes \( {\mathcal C}_D\) from different orderings of the elements of D, but these codes are permutation equivalent and have the same lengths, dimensions and weight distributions. Hence, the orderings of the elements of D will not affect the results in this correspondence.
Let \(\zeta _p\) be a primitive p-th root of an unity, and let
be canonical additive characters over \( {\mathbb F}_{{q}^{m}}\) and \( {\mathbb F}_q\), respectively. For a codeword \(\mathbf{c}_y\) in \( {\mathcal C}_D\), its Hamming weight is equal to
From (2) the weight distribution of \( {\mathcal C}_D\) is directly derived from the value distribution of the exponential sum over the subsets \( {\mathbb F}_{q}^{*}Dy\) of \( {\mathbb F}_{{q}^{m}}^{*}\) for \(y\in {\mathbb F}_{{q}^{m}}\). If the set D is well chosen, \( {\mathcal C}_D\) may have good parameters. This construction technique was employed in [5, 7] for obtaining linear codes with only a few weights. Following this generic construction, in the past three years, many authors present works [2,3,4, 9,10,11, 14, 15, 20, 21, 24] on constructions of linear codes with few weights. Along this line we will give four classes of linear codes with a defining set from representatives of coset decomposition of subgroups or cyclotomic cosets families of some finite fields. By using some combinatorial techniques and Gauss sums with index 2 case, we determine the weight distributions of these linear codes.
The rest of the paper is organized as follows. Section 2 recalls the theory of Gauss sums over finite fields. Section 3 presents a class of linear codes from coset representatives of some subgroup of \( {\mathbb F}_{q}^{*}\), and determines their weight distributions. In Sect. 4 we give three classes of cyclic codes from cyclotomic cosets and determine their weight distributions. Section 5 concludes this paper.
2 Gauss sums
Let \( {\mathbb F}_{{q}^{m}}\) be a finite field with \({q}^{m}\) elements, where q is a power of a prime p. The canonical additive character \(\chi _m\) over \( {\mathbb F}_{{q}^{m}}\) is defined by
where \(\zeta _p\) is a primitive p-th root of an unity and \(\mathrm{Tr}_p^{{q}^{m}}(\cdot )\) is the trace function from \( {\mathbb F}_{{q}^{m}}\) to \( {\mathbb F}_p\). As \(m=1\) the \(\chi _1\) is the canonical additive character over \( {\mathbb F}_q\), and we denote it by \(\chi \) for short. The additive characters have the following orthogonal property,
Let \(\psi \) be a multiplicative character of \( {\mathbb F}_{q}^{*}\). The Gauss sum over \( {\mathbb F}_q\) is defined by
Gauss sums can be viewed as the Fourier coefficients in the Fourier expansion of \(\psi |_{\mathbb {F}_q^{*}}\) in terms of the multiplicative characters of \(\mathbb {F}_q^{*}\).
Lemma 1
(see [16]) Let q be a prime power, \(\chi \) the canonical additive character of \(\mathbb {F}_q\) is defined by \(\chi (y) =\zeta _p^{\mathrm{Tr}_p^{q}(y)},\) where \(y\in \mathbb {F}_q.\) And let \(\psi \) be a multiplicative character of \(\mathbb {F}_q\). Then, for every \(y\in \mathbb {F}_q^{*}\),
where \(\bar{\psi }=\psi ^{-1}\) and \(\widehat{\mathbb {F}}_q^{*}\) denotes the character group of \(\mathbb {F}_q^{*}\).
In general, the explicit evaluation of Gauss sums is very difficult. There are only a few cases where the Gauss sums have been evaluated [13, 17, 18]. We state here some results in the index 2 case which will be used in our constructions. Below we use \(\phi (N)\) to denote the number of integers k with \(0<k\le N\) such that gcd\((k,N)=1\) and \(ord_N(p)\) to denote the order of p modulo N, which is the smallest positive integer f such that \(p^f\equiv 1 \pmod N\).
Lemma 2
([22], Theorem 4.12) Let \(N=2p_1^{m}\), where m is a positive integer, and \(p_1>3\) is a prime such that \(p_1\equiv 3 \pmod 4\). Assume that p is a prime such that \([\mathbb {Z}_N^{*}:\langle p \rangle ]=2\). Let \(f=\phi (N)/2, q=p^f\), and let \(\psi \) be a multiplicative character of order N of \(\mathbb {F}_q\). Then for \(0\le t<m\) we have
where \(p^{*}=(-1)^{\frac{p-1}{2}}p\), and h is the class number of \(\mathbb {Q}(\sqrt{-p_1})\), and b, c are integers determined by \(4p^{h}=b^2+p_1c^2\) and \(bp^{\frac{f-h}{2}}\equiv -2 \pmod {p_1}\).
Lemma 3
([22], Theorem 4.10) Let \(N=p_1^{m_1}p_2^{m_2}\), where \(m_1, m_2\) are positive integers, \(p_1, p_2\) are primes such that \(p_1\equiv 3 \pmod 4\) and \(p_2 \equiv 1 \pmod 4\). Assume that p is a prime such that \([\mathbb {Z}_N^{*}:\langle p \rangle ]=2\), ord\(_{p_1^{m_1}}(p)=\phi (p_1^{m_1})\) and ord\(_{p_2^{m_2}}(p)=\phi (p_2^{m_2})\). Let \(f=\phi (N)/2, q=p^f\), and \(\psi \) be a multiplicative character of order N of \(\mathbb {F}_q\). Then for \(0\le s<m_1\) and \(0\le t<m_2,\) we have
where \(h_{12}\) is the class number of \(\mathbb {Q}(\sqrt{-p_1p_2})\), and b, c are integers determined by \(b,c\not \equiv 0 \pmod {p}\), \(4p^{h_{12}}=b^2+p_1p_2c^2\) and \(b\equiv 2p^{\frac{1}{2}h_{12}} \pmod {p_1}\).
Lemma 4
([22], Theorem 4.14) Let \(N=4p_1^m\), where m is a positive integer, and \(p_1\) is a prime such that \(p_1\equiv 1 \pmod 4\). Assume that p is a prime such that \(p\equiv 3\pmod 4\), \([\mathbb {Z}_N^{*}: \langle p \rangle ]=2\) and ord\(_{p_1^m}(p)=\phi (p_1^m)\). Let \(f=\phi (N)/2, q=p^f\), and let \(\psi \) be a multiplicative character of order N of \(\mathbb {F}_q\). Then for \(0\le s<m\) we have
where b, c are integers determined by \(p^{\frac{f}{2}}=b^2+p_1c^2\) and \(b\equiv -p^{\frac{f}{4}} \pmod {p_1}\).
3 A class of linear codes from coset representatives of some subgroup of \( {\mathbb F}_{q}^{*}\)
Let G be a subgroup of \( {\mathbb F}_{q}^{*}\) with order \(\lambda \). Then \(\lambda | (q-1)\) and \(\lambda | ({q}^{m}-1)\). Let \(\alpha \) be a primitive element of \( {\mathbb F}_{{q}^{m}}\), then \(\beta =\alpha ^{\frac{{q}^{m}-1}{q-1}}\) is a primitive element of \( {\mathbb F}_{q}\). It is clear that \( {\mathbb F}_{{q}^{m}}^{*}\) has the following coset decomposition,
In this section we will study a class of linear codes over \( {\mathbb F}_q\) as follows,
where \(D=\{d_1, d_2, \ldots , d_n\}\subset {\mathbb F}_{{q}^{m}}\) is a defining set. By choosing proper coset representatives in (3) as the defining set D, we can obtain linear codes \( {\mathcal C}_D\) with only few weights. To this end, we introduce some preliminary lemmas.
Lemma 5
Let k be a positive integer with \(k\le m\), and let \(\alpha _1, \alpha _2, \ldots , \alpha _k\in {\mathbb F}_{{q}^{m}}\) be linearly independent over \( {\mathbb F}_{q}\). Denote by
Let I and J be subsets of \(\{1,2,\ldots , k\}\) such that \(I \cap J =\emptyset \) and \(I \cup J = \{1,2,\ldots , k\}\). Let \(S_I= \mathop \cap \limits _{i\in I} V_i\) and \(S_\emptyset = {\mathbb F}_{{q}^{m}}\). Then
Proof
It is clear that \(|I|+|J|=k\), and \(|S_I| = q^{m-|I|}\). Let \(A_j = S_I\cap V_j\) for \(j\in J\).
\(\square \)
Lemma 6
Let \(D_k\) be a set with k elements in \( {\mathbb F}_{{q}^{m}}\) which are linearly independent over \( {\mathbb F}_{q}\). Let \(\chi _m\) be the canonical additive character over \( {\mathbb F}_{{q}^{m}}\). For y running through \( {\mathbb F}_{{q}^{m}}\), the value distribution of the exponential sum
is as follows,
Values | Frequency |
---|---|
\(iq-k\) | \( q^{m-k} {k \atopwithdelims ()i}(q-1)^{k-i}\), \(i=0,1,\ldots , k\) |
Proof
It is clear that
where \(\chi \) is the canonical additive character on \( {\mathbb F}_q\). With notations introduced in Lemma 5 we set \(\varDelta _{IJ}= S_I{\setminus } (\mathop \cup \nolimits _{j\in J} V_j)\). If \(y \in \varDelta _{IJ}\) with \(|I|=i\), then
Moreover, the number of such y is \({ k \atopwithdelims ()i } |\varDelta _{IJ}|\) for \(|I|=i\), and by Lemma 5 it equals \({ k \atopwithdelims ()i } q^{m-k} (q-1)^{k-i}\). \(\square \)
Let \(\alpha \) and \(\beta \) be as in (3), and \(T=\{\beta ^j, \beta ^j\alpha , \ldots , \beta ^j\alpha ^{\frac{{q}^{m}-q}{q-1}}\}\) for some j with \(0\le j\le \frac{q-1}{\lambda }-1\). Let \(D_n\) with \(1\le n\le m\) be a n-subset of T, and elements in \(D_n\) are linearly independent over \( {\mathbb F}_q\).
Theorem 1
With notations as above, we have
-
(1)
If \(D=T\), then \( {\mathcal C}_D\) is a one-weight code with parameters \([\frac{{q}^{m}-1}{q-1}, m , q^{m-1}]\).
-
(2)
If \(D=D_n\), then \( {\mathcal C}_D\) is an [n, n, 1] code with the weight enumerator as follows,
$$\begin{aligned} \sum _{i=0}^n {n \atopwithdelims ()i}(q-1)^{n-i} x^{n-i} . \end{aligned}$$ -
(3)
If \(D= T {\setminus } D_n\) and \({q}^{m}>4\), then \( {\mathcal C}_D\) is a \([\frac{{q}^{m}-1}{q-1}-n, m, q^{m-1}-n]\) code with the weight enumerator as follows,
$$\begin{aligned} 1+ \sum _{i=0}^{n-1} q^{m-n}{n \atopwithdelims ()i} (q-1)^{n-i} x^{q^{m-1}+i-n} + (q^{m-n}-1) x^{q^{m-1}}. \end{aligned}$$
Proof
-
(1)
When \(D= \{\beta ^j, \beta ^j\alpha , \ldots , \beta ^j\alpha ^{\frac{{q}^{m}-q}{q-1}}\}\), we have \( {\mathbb F}_{{q}^{m}}^{*}= D {\mathbb F}_{q}^{*}\). For \(y\in {\mathbb F}_{{q}^{m}}^{*}\),
$$\begin{aligned} S_{D}(y) = \sum _{d\in D} \sum _{z\in {\mathbb F}_{q^{*}}} \chi (dz y)=\sum _{z'\in {\mathbb F}_{{q}^{m}}^{*}} \chi (z'y)=-1 . \end{aligned}$$It is clear that the dimension of \( {\mathcal C}_D\) is m and it has a constant weight \(q^{m-1}\) from equation (2).
-
(2)
When \(D= D_n\), from equation (2) and Lemma 6 we can easily get the weight enumerator. Since n elements in D are linearly independent over \( {\mathbb F}_q\) we know that the dimension of \( {\mathcal C}_D\) is n.
-
(3)
When \(D= T {\setminus } D_n\), for \(y\in {\mathbb F}_{{q}^{m}}^{*}\) we have
By (2) and Lemma 6 we get the weight enumerator of \( {\mathcal C}_D\).
Remark 1
Let E be a subset of \( {\mathbb F}_{q}^{*}\), and \(ED=\{ed\,\, |\,\, e\in E, d\in D\}\) where D is introduced in Theorem 1. For each case in Theorem 1, if choose ED as a new defining set we get new linear codes with longer codewords. This result also can be derived from Theorem 1 in [21].
Remark 2
When \(|D_n|\) is small, and \(D=T{\setminus } D_n\), from (3) of Theorem 1 we get linear codes \( {\mathcal C}_D\) with only few weights. Moreover, the code constructed in (3) of Theorem 1 has minimum nonzero weight \(w_{min} = q^{m-1}-n\) and maximum weight \(w_{max}= q^{m-1}\), and so it satisfies that \(w_{min}/w_{max}>\frac{q-1}{q}\) whenever \(n<q^{m-2}\). Thus the code can be employed to obtain secret sharing schemes with interesting access structures using the framework in [23].
Example 1
Using the primitive polynomial \(f(x)=x^3+x^2-x+1\) \(\in \mathbb {F}_{3}[x]\), we construct the \(\mathbb {F}_{3^3}\) as \(\mathbb {F}_{3}[\alpha ]\) where \(f(\alpha )=0\). Let \(D=\{1,\alpha \}\) be a defining set. Then each codeword in \(\mathcal{C}_D\) repeats once and its weight enumerator of the irreducible cyclic code \( {\mathcal C}_D\) defined by (4) is
This is confirmed by Magma.
4 Three classes of linear codes from cyclotomic cosets
In this section, we investigate the weight distribution of linear codes with a defining set from some cyclotomic cosets, and their Hamming weights of the codewords can be expressed by Gauss sums with index 2 case.
Let N be a divisor of \(q-1\) and \(\beta \) a fixed primitive element of \( {\mathbb F}_{q}\). Define \(C_i^{(N, q)}=\beta ^i \langle \beta ^N\rangle \) for \(i=0,1,\ldots , N-1\), where \(\langle \beta ^N\rangle \) is a subgroup of \( {\mathbb F}_{q}^{*}\) generated by \(\beta ^N\). Let \( {\mathcal C}_D\) be a linear code as follows,
with a defining set
where \(n=\frac{q-1}{N}\). It is known that \( {\mathcal C}_D\) is an irreducible cyclic code. When \(\gcd (\frac{q-1}{p-1}, N)\) is small or N is small, Ding and Yang in [6] studied the weight distribution of \( {\mathcal C}_D\) by some known Gauss sums and Gauss periods. In this paper, we will use Gauss sum of index 2 case to determine Hamming weight of the codeword in \( {\mathcal C}_D\). To this end, we firstly introduce some preliminary lemmas.
Lemma 7
Let q be a prime power and let s be an integer such that \( s \,|\,(q-1)\). Let \(\tau \) be a multiplicative character of \( {\mathbb F}_{q}^{*}\) with order s and \(x\in {\mathbb F}_q\), then
Lemma 8
Let q be a prime power and let \(p'\) be an odd prime such that \(p'|(q-1)\). Let \(\tau \) be a multiplicative character of \(\mathbb {F}_q^{*}\) defined by \(\tau (\beta )=\zeta _{p'}\), where \(\beta \) is a primitive element of \(\mathbb {F}_q\) and \(\zeta _{p^\prime }\) is a primitive \(p^\prime \)-th root of an unity. Then
where \(\left( \frac{ \cdot }{p'}\right) \) is the Legendre symbol.
Proof
If \(\tau (x)=1\), we have \(\sum \limits _{0< s< p'}\left( \frac{s}{p'}\right) \tau ^{s}(x)=\sum \limits _{0< s< p'}\left( \frac{s}{p'}\right) =0.\) Since \(\tau (\beta )=\zeta _{p'}\), \(x\in C_i^{(p',q)}\) and \(i\not =0\), we have \(\tau (x)=\tau ^i(\beta )=\zeta _{p'}^i\). It follows that
This completes the proof. \(\square \)
In order to determine Hamming weight of the codeword \(\mathbf{c}_x\) in (5) we need to calculate the following number.
Let \(\varphi \) be a multiplicative character of \( {\mathbb F}_{q}^{*}\) of order \(q-1\) and \(\widehat{\mathbb {F}}_q^{*}=\{\varphi ^j:~ 0\le j<q-1\}\). By Fourier expansion formula, Lemma 1 and Lemma 7,
where \(l=\frac{p-1}{\gcd (n, p-1)}\). From \(q-1=n\cdot N\) we know that \(l \,\,|\,\, N\).
Next we will construct three classes of irreducible cyclic codes as in (5) and (6) by choosing a proper defining set D, and determine their weight distributions.
Theorem 2
Let \(N=2p_1\), where \(p_1>3\) is a prime such that \(p_1\equiv 3 \pmod 4\). Assume that p is a prime such that \([\mathbb {Z}_N^{*}:\langle p\rangle ]=2\). Let \(f=\phi (N)/2\) and \(q=p^f\). Let h be the class number of \(\mathbb {Q}(\sqrt{-p_1})\), and b, c be integers determined by \(4p^{h}=b^2+p_1c^2\) and \(bp^{\frac{f-h}{2}}\equiv -2 \pmod {p_1}\). Let \( {\mathcal C}_D\) be a linear code defined in (5) and (6), then the weight enumerator of \(\mathcal{C}_D\) is as follows:
Proof
Since \(p_1\) is a prime with \(p_1\equiv 3 \pmod 4\), we have that \(f=\frac{p_1-1}{2}\) is odd, and \(\frac{q-1}{p-1}=p^{f-1}+\cdots +1\equiv 1 \pmod 2\). Since \(p_1>3\) and \([\mathbb {Z}_N^{*}:\langle p\rangle ]=2\), we know that \(p\not \equiv 1 \pmod {p_1}\). Since \(N=2p_1\, |\, (q-1)\), we have \(l=\frac{p-1}{\gcd (n, p-1)}=\frac{(p-1)2p_1}{\gcd (q-1, (p-1)2p_1)}=\frac{2p_1}{\gcd (\frac{q-1}{p-1}, 2p_1)}=2\).
Let \(\psi \) be a multiplicative character of \(\mathbb {F}_q^{*}\) defined by \(\psi (\beta )=\zeta _{2p_1}\). By Lemma 2, we have
where h is the class number of \(\mathbb {Q}(\sqrt{-p_1})\), and b, c are integers determined by \(4p^{h}=b^2+p_1c^2\) and \(bp^{\frac{f-h}{2}}\equiv -2 \pmod {p_1}\). By the same argument as in Theorem 5.1 of [8] we have
where \(0< s<p_1\) and \((\frac{\cdot }{p_1})\) is the Legendre symbol.
Let \(\tau =\varphi ^{2n}\) in (8). Since \(l=2\) and \(N=2p_1\), by (8) the Hamming weight of codeword \(\mathbf{c}_x\) equals
By (10) it is followed that
By Lemma 7 and Lemma 8, we have
Hence, we obtain
Frequency of each Hamming weight is derived from (14) directly. So we get the weight enumerator of \( {\mathcal C}_D\) as in (9). \(\square \)
Remark 3
When \(b,c\in \{-1,1\}\), the obtained codes are two-weighted.
Example 2
Let \(p=11\), \(p_1=7\) and \(N=14\). Then \(f=3\) and \(q=11^{3}\). The class number h of \(\mathbb {Q}(\sqrt{-7})\) is equal to 1 (see [19]). Since \(4p^{h}=b^2+p_1c^2\) and \(bp^{\frac{f-h}{2}}\equiv -2 \pmod {p_1}\), we have \(c^2=4\) and \(b=-4\). By Theorem 2, the weight enumerator of the irreducible cyclic code \( {\mathcal C}_D\) defined by (5) is
This is confirmed by Magma.
Example 3
Let \(p=3\), \(p_1=11\) and \(N=22\). Then \(f=5\) and \(q=3^{5}\). The class number h of \(\mathbb {Q}(\sqrt{-11})\) is equal to 1 (see [19]). Since \(4p^{h}=b^2+p_1c^2\) and \(bp^{\frac{f-h}{2}}\equiv -2 \pmod {p_1}\), we have \(c^2=1\) and \(b=1\). By Theorem 2, the weight enumerator of the irreducible cyclic code \( {\mathcal C}_D\) defined by (5) is
This is confirmed by Magma.
Theorem 3
Let \(N=p_1p_2\), where \(p_1, p_2\) are primes such that \(p_1\equiv 3 \pmod 4\) and \(p_2 \equiv 1 \pmod 4\). Assume that p is a prime such that \([\mathbb {Z}_N^{*}:\langle p\rangle ]=2\), ord\(_{p_1}(p)=\phi (p_1)\) and ord\(_{p_2}(p)=\phi (p_2)\). Let \(f=\phi (N)/2, q=p^f\). Let \(h_{12}\) be the class number of \(\mathbb {Q}(\sqrt{-p_1p_2})\), and let b, c be integers determined by \(b,c\not \equiv 0 \pmod {p}\), \(4p^{h_{12}}=b^2+p_1p_2c^2\) and \(b\equiv 2p^{\frac{1}{2}h_{12}} \pmod {p_1}\). Let \(h=\frac{1}{2}(f-h_{12})\) and \( {\mathcal C}_D\) be a linear code defined in (5) and (6), then the weight enumerator of the linear code \( {\mathcal C}_D\) is as follows:
Proof
Since \(p_1,p_2\) are primes, ord\(_{p_1}(p)=\phi (p_1)\) and ord\(_{p_2}(p)=\phi (p_2)\), we have \(p\not \equiv 1 \pmod {p_1}\) and \(p\not \equiv 1 \pmod {p_2}\). Since \(N=p_1p_2\,|\,(q-1)\), we have \(p_1p_2|\frac{q-1}{p-1}\) and \(l=\frac{p-1}{\gcd (n, p-1)}=\frac{(p-1)p_1p_2}{\gcd (q-1, (p-1)p_1p_2)}=\frac{p_1p_2}{\gcd (\frac{q-1}{p-1}, p_1p_2)}=1\).
Let \(\tau _1\) be a multiplicative character of \(\mathbb {F}_q^{*}\) defined by \(\tau _1(\beta )=\zeta _{p_1}\) and let \(\tau _2\) be a multiplicative character of \(\mathbb {F}_q^{*}\) defined by \(\tau _2(\beta )=\zeta _{p_2}\). By Lemma 3, we have
where \(h_{12}\) is the class number of \(\mathbb {Q}(\sqrt{-p_1p_2})\), \(h=\frac{1}{2}(f-h_{12})\) and b, c are integers determined by \(b,c\not \equiv 0 \pmod {p}\), \(4p^{h_{12}}=b^2+p_1p_2c^2\) and \(b\equiv 2p^{\frac{1}{2}h_{12}} \pmod {p_1}\). Every multiplicative character of \( {\mathbb F}_{q}^{*}\) with order \(p_1p_2\) is of the form \(\tau _{1}^{s} \tau _2^t\), where \(s\in \mathbb {Z}_{p_1}^{*}\) and \(t\in \mathbb {Z}_{p_2}^{*}\). By the same argument as in Theorem 5.1 in [8], we have
where \((\frac{.}{p_1})\) is the Legendre symbol.
Let \(\tau =\varphi ^{n}\) in (8). Since \(l=1\) and \(N=p_1p_2\), from (8) we have
Since \(\tau \) is a character with order N, we get
Below we will compute each sum individually. By (16) and Lemma 7 and Lemma 8,
and
Combing (17), (18), (19), (20) and (21) we obtain
Frequency of each Hamming weight is derived from equation (22) directly. So we get the weight enumerator of \( {\mathcal C}_D\) as in (15). \(\square \)
Remark 4
When \(c^2=1,b=\frac{p_2-p_1}{2}\) and \(p^{\frac{h_{12}}{2}}=\frac{p_1+p_2}{4}\), the obtained codes are three-weighted.
Example 4
Let \(p=2\), \(p_1=3\), \(p_2=13\) and \(N=39\). Then \(f=12\) and \(q=2^{12}\). The class number \(h_{12}\) of \(\mathbb {Q}(\sqrt{-39})\) is equal to 4 (see [1]). Since \(b^2+p_1p_2c^2=4p^{h_{12}}\) and \(b\equiv 2p^{\frac{h_{12}}{2}}\pmod {p_1}\), we have \(c^2=1\) and \(b=5\). By Theorem 3, the weight enumerator of the irreducible cyclic code \( {\mathcal C}_D\) defined by (5) is
This weight enumerator coincides with that computed by Magma.
Example 5
Let \(p=2\), \(p_1=11\), \(p_2=5\) and \(N=55\). Then \(f=20\) and \(q=2^{20}\). The class number \(h_{12}\) of \(\mathbb {Q}(\sqrt{-55})\) is equal to 4 ([1]). Since \(b^2+p_1p_2c^2=4p^h\) and \(b\equiv 2p^{\frac{h_{12}}{2}} \pmod {p_1}\), we have \(c^2=1\) and \(b=-3\). By Theorem 3, the complete weight enumerator of the irreducible cyclic code \( {\mathcal C}_D\) defined by (5) is
This weight enumerator coincides with that computed by Magma.
Theorem 4
Let \(N=4p_1\), where \(p_1\) is prime such that \(p_1\equiv 1 \pmod 4\). Assume that p is a prime such that \(p\equiv 3\pmod 4\), \([\mathbb {Z}_N^{*}:\langle p \rangle ]=2\) and ord\(_{p_1}(p)=\phi (p_1)\). Let \(f=\phi (N)/2,\ q=p^f\), and b, c be integers determined by \(p^{\frac{f}{2}}=b^2+p_1c^2\) and \(b\equiv -p^{\frac{f}{4}} \pmod {p_1}\). Let \( {\mathcal C}_D\) be a linear code defined in (5) and (6), then the weight enumerator of \(\mathcal{C}_D\) is as follows:
Proof
Since \(p_1\) is a prime, and ord\(_{p_1}(p)=\phi (p_1)\), we have \(p\not \equiv 1 \pmod {p_1}\). Since \( 4\,|\,f=p_1-1\) and \(p\equiv 3\pmod 4\), it follows that \(\frac{q-1}{p-1}=p^{f-1}+p^{f-2}+\cdots +1\equiv 0\pmod 4\). Since \(N=4p_1\,| \,(q-1)\), we imply that \(4p_1|\frac{q-1}{p-1}\) and \(l=\frac{p-1}{\gcd (n, p-1)}=\frac{(p-1)4p_1}{\gcd (q-1, (p-1)4p_1)}=\frac{4p_1}{\gcd (\frac{q-1}{p-1}, 4p_1)}=1\).
Let \(\tau _1\) be the multiplicative character of \(\mathbb {F}_q^{*}\) defined by \(\tau _1(\beta )=\zeta _{p_1}\) and let \(\tau _2\) be the character of \(\mathbb {F}_q^{*}\) defined by \(\tau _2(\beta )=\zeta _{4}\). By Lemma 4, we know that
where b, c are integers determined by \(p^{\frac{f}{2}}=b^2+p_1c^2\) and \(b\equiv -p^{\frac{f}{4}} \pmod {p_1}\). Every multiplicative character of \(\mathbb {F}_q^{*}\) with order \(4p_1\) is of the form \(\tau _{1}^{s}\tau _2^t\), where \(s\in \mathbb {Z}_{p_1}^{*}\) and \(t\in \mathbb {Z}_{4}^{*}\). It follows that for any \(s\in \mathbb {Z}_{p_1}^{*}\) and \(t\in \mathbb {Z}_{4}^{*}\),
where \(\left( \frac{.}{p_1}\right) \) is the Legendre symbol.
Let \(\tau =\varphi ^{n}\) in (8). Since \(l=1\) and \(N=4p_1\), by (8) the Hamming weight of codeword \(\mathbf{c}_x\) equals
Since \(\tau \) is a character with order N, it follows that every multiplicative character of \(\mathbb {F}_q^{*}\) with order \(4p_1\) is of the form \(\tau _{1}^{s}\tau _2^{t}\), where \(s\in \mathbb {Z}_{p_1}^{*}\) and \(t\in \mathbb {Z}_4^{*}\). By (24) we have
where \(o(\tau )\) denotes the order of the character \(\tau \). Next we evaluate above sum according to x.
If \(x\in C_0^{(p_1, q)}\) and \(x\in C_0^{(4, q)}\) from (26) we have
If \(x\in C_0^{(p_1, q)}\) and \(x\in C_1^{(4, q)}\) from (26) we get
If \(x\in C_0^{(p_1, q)}\) and \(x\in C_2^{(4, q)}\) from (26) we obtain
If \(x\in C_0^{(p_1, q)}\) and \(x\in C_3^{(4, q)}\) from (26) we imply
If \(x\in C_i^{(p_1, q)}, i\ne 0\) and \(x\in C_0^{(4, q)}\) from (26) we have
If \(x\in C_i^{(p_1, q)}, i\ne 0\) and \(x\in C_1^{(4, q)}\) from (26) we get
If \(x\in C_i^{(p_1, q)}, i\ne 0\) and \(x\in C_2^{(4, q)}\) from (26) we obtain
If \(x\in C_i^{(p_1, q)}, i\ne 0\) and \(x\in C_3^{(4, q)}\) from (26) we imply
Combing (25), (26) and above discussions, we obtain
Frequency of each Hamming weight is derived from (27) directly. So we get the weight enumerator of \( {\mathcal C}_D\) as in (23).
Example 6
Let \(p=3\), \(p_1=5\) and \(N=20\). Then \(f=4\) and \(q=3^{4}\). Since \(b^2+p_1c^2=p^{\frac{f}{2}}\) and \(b\equiv -p^{\frac{f}{4}} \pmod {p_1}\), we have \(c^2=1\) and \(b=2\). By Theorem 4, the weight enumerator of \( {\mathcal C}_D\) defined by (5) is
This result is confirmed by Magma, and shows that \( {\mathcal C}_D\) has dimension 2. In fact, the dimension of the vector space generated by \(\{1, \alpha ^{20}, \alpha ^{40}, \alpha ^{60}\}\) is 2 for some primitive element \(\alpha \in {\mathbb F}_{3^4}\), which is equal to the dimension of the code \( {\mathcal C}_D\) by Theorem 6 in [5].
Example 7
Let \(p=3\), \(p_1=17\) and \(N=68\). Then \(f=16\) and \(q=3^{16}\). Since \(b^2+p_1c^2=p^{\frac{f}{2}}\) and \(b\equiv -p^{\frac{f}{4}} \pmod {p_1}\), we have \(c^2=81\) and \(b=72\). By Theorem 4, the weight enumerator of the irreducible cyclic code \( {\mathcal C}_D\) defined by (5) is
This weight enumerator coincides with that computed by Magma.
5 Concluding remark
In this paper we present four classes of linear codes from coset decomposition of subgroups and cyclotomic coset families of certain finite field, and determine their weight distributions by Gauss sums with index 2 cases. Many other similar linear codes maybe constructed and their corresponding weight distributions maybe determined by Gauss sums with other index 2 cases.
References
Arno S.: The imaginary quadratic fields of class number 4. Acta Arith. 60, 321–334 (1992).
Ding C.: Linear codes from some 2-designs. IEEE Trans. Inf. Theory 61(6), 3265–3275 (2015).
Ding C.: A construction of binary linear codes from Boolean functions. Discret. Math. 339(9), 2288–2303 (2016).
Ding K., Ding C.: Binary linear codes with three weights. IEEE Commun. Lett. 18, 1879–1882 (2014).
Ding C., Niederreiter H.: Cyclotomic linear codes of order 3. IEEE Trans. Inf. Theory 53(6), 2274–2277 (2007).
Ding C., Yang J.: Hamming weights in Irreducible cyclic codes. Discret. Math. 313, 434–446 (2013).
Ding C., Luo J., Niederreiter H.: Two weight codes punctured from irreducible cyclic codes. In: Li Y., Ling S., Niederreiter H., Wang H., Xing C., Zhang S (Eds.) Proceedings of the First International Workshop on Coding Theory and Cryptography, pp. 119–124. World Scientific, Singapore (2008)
Feng T., Xiang Q.: Strongly regular graphs from unions of cyclotomic classes. J. Comb. Theory (B) 102, 982–995 (2012).
Heng Z., Yue Q.: A class of binary linear codes with at most three weights. IEEE Commun. Lett. 19, 1488–1491 (2015).
Heng Z., Yue Q.: Evaluation of the Hamming weights of a classes of linear codes based on Gauss sums. Des. Codes Cryptogr. (2016). doi:10.1007/s10623-016-0222-7.
Heng Z., Yue Q.: Optimal linear codes, constant-weight codes and constant-composition codes over \({\mathbb{F}}_{q}\). arXiv:1605.04063v1.
Kløve T.: Codes for Error Detection. World Scientific, Hackensack (2007).
Langevin P.: Calcus de certaines sommes de Gauss. J. Number Theory 63, 59–64 (1997).
Li C., Bae S., Ahn J., et al.: Complete weight enumerartors of some linear codes and their applications. Des. Codes Cryptogr. 81(1), 153–168 (2016).
Li F., Wang Q., Lin D.: A class of three-weight and five-wiehgt linear codes. arXiv:1509.06242.
Lidl R., Niederreiter H.: Finite Fields. Cambridge University Press, Cambridge (1997).
Mbodj O.D.: Quadratic Gauss Sums. Finite Fields Appl. 4, 347–361 (1998).
Meijer P., van der Vlugt M.: The evaluation of Gauss sums for characters of 2-power order. J. Number Theory 100, 381–395 (2003).
Neukirch J.: Algebraic Number Theory. Springer, Berlin (1999).
Wang Q., Ding K., Xue R.: Binary linear codes with two weight. IEEE Commun. Lett. 19, 1097–1100 (2015).
Xiang C.: Linear codes from a generic construction. Cryptogr. Commun. 8, 525–539 (2016).
Yang J., Xia L.: Complete solving of explicit evaluation of Gauss sums in the index 2 case. Sci. China Ser. A 53, 2525–2542 (2010).
Yuan J., Ding C.: Secret sharing schemes from three classes of linear codes. IEEE Trans. Inf. Theory 52(1), 206–212 (2006).
Zhou Z., Li N., Fan C., Helleseth T.: Linear codes with two or three weight from quafratic bent functions. Des. Codes Cryptogr. 81(2), 283–295 (2016).
Acknowledgements
The authors wish to thank prof. Qing Xiang for his helpful comments. The work was partially supported by National Natural Science Foundation of China (NSFC) under Grant 11101131.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Q. Xiang.
Rights and permissions
About this article
Cite this article
Zheng, D., Bao, J. Four classes of linear codes from cyclotomic cosets. Des. Codes Cryptogr. 86, 1007–1022 (2018). https://doi.org/10.1007/s10623-017-0374-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-017-0374-0