JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

1

Two new families of two-weight codes∗

arXiv:1612.00967v2 [] 15 Sep 2017

Minjia Shi, Yue Guan, and Patrick Solé

Abstract—We construct two new infinite families of
trace codes of dimension 2m, over the ring Fp + uFp ,
with u2 = u, when p is an odd prime. They have the
algebraic structure of abelian codes. Their Lee weight
distribution is computed by using Gauss sums. By Gray
mapping, we obtain two infinite families of linear p-ary
codes of respective lengths (pm − 1)2 and 2(pm − 1)2 .
When m is singly-even, the first family gives five-weight
codes. When m is odd, and p ≡ 3 (mod 4), the first
family yields p-ary two-weight codes, which are shown
to be optimal by application of the Griesmer bound. The
second family consists of two-weight codes that are shown
to be optimal, by the Griesmer bound, whenever p = 3
and m ≥ 3, or p ≥ 5 and m ≥ 4. Applications to secret
sharing schemes are given.

on two different defining sets. These codes are visibly
abelian, but possibly not cyclic. The field image of the
first family has two or five weights, depending on the
choice of parameters. The second family only contains
two-weight codes. Note that abelian codes over rings
have been studied already in [11]. The alphabet ring
we consider here is Fp +uFp , with u2 = u. It is a semilocal ring, which is ring isomorphic to Fp × Fp (Cf.
§2.1 for a proof). It is an odd characteristic analogue
of F2r + vF2r , with v 2 = v. The latter ring has been
employed recently to construct convolutional codes
over fields [9]. Some bounds on codes over Fp + uFp ,
with u2 = u can be found in [10].

Index Terms—Two-weight codes; Gauss sums; Griesmer bound; Secret sharing schemes.

The defining set of our abelian code is not a cyclic
group, but it is an abelian group. The defining set of
the first family is related to quadratic residues in an
extension of degree m of Fp , which makes quadratic
Gauss sums appear naturally in the weight distribution
analysis, and requires p to be an odd prime. When m is
odd, and p ≡ 3 (mod 4), we obtain an infinite family
of linear p-ary two-weight codes, which are shown to
be optimal by application of the Griesmer bound. The
codes in the second family are also shown to be optimal
by the same technique up to finitely many exceptions.
We show that, both in the five-weight and in the twoweight cases, the first family has a very nice support
inclusion structure which makes it suitable for use in a
Massey secret sharing scheme [7], [8], [19]. Indeed, we
can show that all nonzero codewords are minimal for
the poset of codewords ordered by support inclusion. A
similar result holds for the second family. To the best
of our knowledge, the weight distributions of the codes
obtained here are different from the classical families
of [4] and from the those of the codes in [14], [15],
[16]. Our codes are therefore new.

I. I NTRODUCTION

T

Wo-weight codes over fields have been studied since the 1970s due to their connections to
strongly regular graphs, finite geometries and difference sets [5]. However, most constructions, have used
cyclic codes over finite fields [3], [4]. In the present
paper, we use trace codes over a semi-local ring which
is a quadratic extension of a finite field, and obtain
codes over a finite field by Gray mapping. Trace codes
are naturally low-rate codes, and not necessarily cyclic.
This is part of a general research program where a
variety of few weight codes are obtained by varying the
alphabet ring and the defining set [14], [15], [16]. Here
we consider an alphabet ring of odd characteristic, in
contrast with [14], [15], and over a non local ring, in
contrast with [16]. We consider two families depending
MinJia Shi is with Key Laboratory of Intelligent Computing &
Signal Processing, Ministry of Education, Anhui University No. 3
Feixi Road, Hefei Anhui Province 230039, P. R. China, National
Mobile Communications Research Laboratory, Southeast University, 210096, Nanjing, P. R. China and School of Mathematical
Sciences of Anhui University, Anhui, 230601, P. R. China (Email:smjwcl.good@163.com).
Yue Guan is with School of Mathematical Sciences of Anhui
University, Anhui, 230601, P. R. China.
Patrick Solé is with CNRS/ LAGA, University Paris 8, 93 526
Saint-Denis, France
Manuscript received November 11, 2016; revised May 14, 2017.
M. Shi was supported in part by the National Natural Science
Foundation of China under Grant 61672036, in part by the Technology Foundation for Selected Overseas Chinese Scholar, Ministry
of Personnel, China, under Grant 05015133, in part by the Open
Research Fund of National Mobile Communications Research Laboratory, Southeast University, under Grant 2015D11, and in part by
the Key Projects of Support Program for Outstanding Young Talents
in Colleges and Universities under Grant gxyqZD2016008.

The paper is organized as follows. Section II collects
the notions and notations needed in the rest of the
article. Section III shows that the trace codes are
abelian. Section IV recalls and reproves some results
on Gaussian periods. Section V computes the weight
distribution of our codes, building on the character
sum evaluation of the preceding section. Section VI
discusses the optimality of the p-image from trace
codes over R. Section VII determines the minimum
distance of the dual codes. Section VIII determines
the support structure of the p-ary image and describes
an application to secret sharing schemes.

JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

II. D EFINITIONS

2

AND NOTATIONS

A. Rings
Consider the ring R = Fp +uFp where u2 = u and p
is a odd prime. It is semi-local with maximal ideals (u)
and (u − 1). For any integer m ≥ 1, we construct an
extension of degree m as R = Fpm + uFpm with again
u2 = u. There is a Frobenius operator F which maps
a + ub onto ap + ubp . The Trace function, denoted
m−1
P j
F . It follows from
by T r, is defined as T r =
j=0

these definitions that T r(a + ub) = tr(a) + utr(b),
for a, b ∈ Fpm . Here tr() denotes the absolute trace of
Fpm , given by
p

tr(z) = z + z + · · · + z

pm−1

, z ∈ Fpm .

The ring R is semi-local with maximal ideals (u)
and (u − 1), and respective quotients R/(u) and
R/(u − 1) are both isomorphic to Fpm . The Chinese
Remainder Theorem shows that uFpm + (1 − u)Fpm is
isomorphic to the product ring Fpm × Fpm . Similarly,
the group of units R∗ is uF∗pm + (1 − u)F∗pm which
is isomorphic to F∗pm × F∗pm . Here F∗pm denotes the
multiplicative group of Fpm . Denote the squares and
the non-squares of Fpm by Q and N , respectively.
Thus
Q = {x2 | x ∈ F∗pm }, N = F∗pm \ Q.

We write L = uQ + (1 − u)F∗pm and let L′ = R∗
for simplicity. Thus L is a subgroup of R∗ of index 2.
B. Gray map
As a preparation for the image code from trace codes
over R, we shall take a closer look at the Gray map
φ from R to F2p , which is defined by φ(a + ub) =
(−b, 2a + b) for a, b ∈ Fp . It is a one to one map from
R to F2p , which extends naturally into a map from Rn
n
to F2n
p . Denote the Hamming weight on Fp by wH (.),
2n
and the Hamming distance on Fp by dH (., .). The
Lee weight is defined as the Hamming weight of the
Gray image wL (a + ub) = wH (−b) + wH (2a + b) for
a, b ∈ Fnp . The Lee distance of x, y ∈ Rn is defined as
dL (x, y) = wL (x − y). Thus the Gray map is a linear
isometry from (Rn , dL ) to (F2n
p , dH ). For convenience,
we write N = 2n in the rest of the paper.
C. Codes
A linear code C over R of length n is an Rsubmodule of Rn . If x = (x1 , x2 , · · · , xn ) and
y = (y1 , y2 , · · · , yn ) are two elements of Rn , their
n
P
xi yi ,
standard inner product is defined by hx, yi =
i=1

where the operation is performed in R. The dual
code of C is denoted by C ⊥ and defined as C ⊥ =
{y ∈ Rn |hx, yi = 0, ∀x ∈ C}. By definition, C ⊥

is also a linear code over R. Given a finite abelian
group G, a code over R is said to be abelian [2],
if it is an ideal of the group ring R[G]. Recall that
the ring R[G] is defined on functions from G to R
with pointwise addition as addition, and convolution
product as multiplication.
P Concretely, it is the set of
all formal sums f = h∈G fh X h , with addition and
multiplication defined as follows. If f, g ∈ R[G], we
write
X
f +g =
(fh + gh )X h ,
g∈G

and
fg =

X X
(
fr gs )X h .

h∈G r+s=h

In other words, the coordinates of C are indexed by
elements of G and G acts regularly on this set. For
more details on abelian codes see [18]. In the special
case when G is cyclic, the code is a cyclic code in the
usual sense [12].
III. S YMMETRY
For a ∈ R, define the vector ev(a) by the following
evaluation map ev(a) = (T r(ax))x∈L . Define the code
C(m, p) by the formula C(m, p) = {ev(a)|a ∈ R}.
m
2
Thus C(m, p) is a code of length |L| = (p 2−1) and
size |R|m over R. Similarly, define the vector ev ′ (a) by
the following evaluation map ev ′ (a) = (T r(ax))x∈L′ ,
and the code C ′ (m, p) by the formula C ′ (m, p) =
{ev ′ (a)|a ∈ R}. Thus C ′ (m, p) is a code of length
|L′ | = (pm − 1)2 and size |R|m over R.
Proposition 3.1 The group L (resp. L′ ) acts regularly on the coordinates of C(m, p) (resp. C ′ (m, p)
).
Proof For any w, v ∈ L the change of variables x 7→
(v/w)x maps w to v. This transformation defines thus
a transitive action of L on itself. Given an ordered pair
(w, v) this transformation is unique, hence the action
is regular. A similar argument holds for C ′ (m, p) and
L′ .
The code C(m, p) is thus an abelian code with
respect to the group R∗ . In other words, it is an ideal
of the group ring R[R∗ ]. As observed in the previous
section R∗ is not a cyclic group, hence C(m, p) may
be not cyclic.
IV. C HARACTER

SUMS

In this section we give some background material on
character sums. Let χ denote an arbitrary multiplicative
character of Fq . Assume q is odd. Denoted by η
the quadratic multiplicative character is defined by
η(x) = 1, if x is a square and η(x) = −1, if not.
Let ψ denote the standard canonical additive character
of Fq . The squares and the non-squares of Fq are

JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

denoted, extending the notation of §2.1, by Q and N ,
respectively. Thus,
Q = {x2 | x ∈ F∗q }, N = F∗q \ Q.
The
P classical Gauss sum can be defined as G(χ) =
ψ(x)χ(x).
x∈F∗
q

We define the following character sums
X
X
Q=
ψ(x), N =
ψ(x).
x∈Q

x∈N

On the basis of orthogonality of characters [12, Lemma
9, p. 143] it is evident that Q + N = −1. Noting that
the characteristic function of Q is 1+η
2 , we get then
G(η) − 1
−G(η) − 1
, N=
.
2
2
It is well known [6] that if q = pm , the quadratic
Gauss sums can be evaluated as
√
(1)
G(η) = (−1)m−1 q , p ≡ 1 (mod 4),
√
G(η) = (−1)m−1 im q, p ≡ 3 (mod 4). (2)
Q=

Particularly, if m is singly-even, these formulas
√
can be simplified to G(η) = ǫ(p) q, with ǫ(p) =
(p+1)
(−1) 2 , yielding
√
√
ǫ(p) q − 1
ǫ(p) q + 1
Q=
,N = −
.
2
2
In fact Q and N are examples of Gaussian periods,
and these relations could have been deduced from [6,
Lemma 11].
V. W EIGHT

DISTRIBUTIONS OF TRACE CODES

Let ω = exp( 2πi
p ) be a complex root of unity of
order p. If y = (y1 , y2 , · · · , yN ) ∈ FN
p , let Θ(y) =
N
P
ω yj . For simplicity, we let θ(a) = Θ(φ(ev(a))).
j=1

By linearity of the Gray map, and of the evaluation
map, we see that θ(sa) = Θ(φ(ev(sa))), for any s ∈
F∗p . For our purpose, let us begin with the following
correlation lemma.
Lemma 5.1 [15] For all y = (y1 , y2 , · · · , yN ) ∈
p−1
P
FN
Θ(sy) = (p − 1)N − pwH (y).
p , we have
s=1

In connection with the proceding discussion, we now
distinguish two cases of weight distributions depending
on the defining set.
A. The case of L = Q × F∗pm

1) m is singly-even: Theorem 5.2 Assume m is
singly-even. For a ∈ R, the Lee weight of codewords
of C(m, p) is given below.
(a) If a = 0, then wL (ev(a)) = 0;
(b) If a = uα, α ∈ F∗pm , then if

3

α ∈ Q then wL (ev(a)) = (p − 1) p2m−1 − pm−1 −
ǫ(p)p3m/2−1 + ǫ(p)pm/2−1 ,
α ∈ N then wL (ev(a)) = (p − 1) p2m−1 − pm−1 +
ǫ(p)p3m/2−1 − ǫ(p)pm/2−1 ;
(c) If a = (1 − u)β, β ∈ F∗pm , then wL (ev(a)) =
(p − 1)(p2m−1 − pm−1 );
(d) If a = uα + (1 − u)β ∈ R∗ , then if
α ∈ Q then wL (ev(a))
= (p − 1) p2m−1 − 2pm−1 +

m/2−1
ǫ(p)p
,
α ∈ N then wL (ev(a))
= (p − 1) p2m−1 − 2pm−1 −

m/2−1
ǫ(p)p
.
Proof
(a) If a = 0, then T r(ax) = 0. So wL (ev(a)) = 0.
(b) If a = uα, x = ut + (1 − u)t′ with α ∈ F∗pm ,
then ax = uαt, and T r(ax) = T r(uαt) =
utr(αt). Taking Gray map yields φ(ev(a)) =
(−tr(αt), tr(αt))t,t′ . Taking character sums
X X
X X
θ(a) =
ω −tr(αt) +
ω tr(αt)
t∈Q t′ ∈F∗
pm

= 2

t∈Q t′ ∈F∗
pm

X X

t∈Q

ω −tr(αt)

t′ ∈F∗
pm

= 2(pm − 1)

X

ω tr(αt) .

t∈Q

Replaced αt by t, it is easy to check that the last
character sum is Q or N depending on α ∈ Q
or α ∈ N . Since m is even, s ∈ F∗p is a
square in Fpm . Thus θ(sa) = θ(a), for any
s ∈ F∗p . The statement follows from Lemma 5.1.
m
− 1)Q), or
Thus wL (ev(a)) = p−1
p (N − 2(p
p−1
m
wL (ev(a)) = p (N − 2(p − 1)N ), according
to the value of η(α).
(c) If a = (1 − u)β, x = ut + (1 − u)t′ with
β ∈ F∗pm , then ax = βt′ − uβt′ , and T r(ax) =
tr(βt′ ) − utr(βt′ ). Taking Gray map yields
′
′ . Taking characφ(ev(a)) = (tr(βt′P
), tr(βt
P ))t,ttr(βt
′
)
ω
= 1 − pm .
ter sums θ(a) = 2
t∈Q t′ ∈F∗
pm
2m−1

Thus wL (ev(a)) = (p − 1)(p
− pm−1 ).
∗
(d) Let a = uα + (1 − u)β ∈ R , x = ut +
(1 − u)t′ . So T r(ax) = tr(βt′ ) + utr(αt −
βt′ ). Thus φ(ev(a)) = (−tr(αt − βt′ ), tr(αt +
map. Taking
character
βt′ ))t,t′ by the Gray
P
P −tr(αt)
tr(βt′ )
ω
+
ω
sums θ(a) =
P

t∈Q

ω

tr(αt)

P

t′ ∈F∗
pm

t∈Q
tr(βt′ )

ω

t′ ∈F∗
pm

= −2

P

ω tr(αt) . By

t∈Q

a change of variable t = αt, we see that the last
character sum is Q or N depending on α ∈ Q
or α ∈ N . Thus wL (ev(a)) = p−1
p (N + 2Q),
p−1
or wL (ev(a)) = p (N + 2N ), considering the
value of η(α).
Therefore, we have constructed a p-ary code of
length N = (pm − 1)2 , dimension 2m, with five

JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

weights. The weight distribution is given in Table I.
Table I.

weight distribution of C(m, p) in
Theorem 5.2
Weight
Frequency
0
1
pm −1
m−1
m/2−1
m
(p − 1)(p
−p
)(p − 1)
2
(pm −1)2
(p − 1)(p2m−1 − 2pm−1 − pm/2−1 )
2
(pm −1)2
(p − 1)(p2m−1 − 2pm−1 + pm/2−1 )
2
(p − 1)(p2m−1 − pm−1 )
pm − 1
m
p −1
(p − 1)(pm−1 + pm/2−1 )(pm − 1)
2
(Note that taking ǫ(p) = 1, or −1, leads to the same
values.)
2) m is odd and p ≡ 3 (mod 4): Note that in that
case by (2) in Section IV we see that G(η) is imaginary. This implies that ℜ(Q) = ℜ(N ) = − 12 , where
ℜ(z) denotes the real part of the complex number z.
We need first to refine the following correlation lemma.
Lemma 5.3 [15] If p ≡ 3 (mod 4), then we have
p−1
P
θ(sa) = (p − 1)ℜ(θ(a)).
s=1

Theorem 5.4 Assume m is odd and p ≡ 3 (mod 4).
For a ∈ R, the Lee weight of codewords of C(m, p)
is given below.
(a) If a = 0, then wL (ev(a)) = 0;
(b) If a = uβ with β ∈ F∗pm , then wL (ev(a)) =
(p − 1)(p2m−1 − pm−1 );
(c) If a = (1 − u)β with β ∈ F∗pm , then wL (ev(a)) =
(p − 1)(p2m−1 − pm−1 );
(d) If a ∈ R∗ , then wL (ev(a)) = (p − 1)(p2m−1 −
2pm−1 ).
Proof The proof of the case (a) is like that of
Theorem 5.2. The case (b) follows from Lemma 5.3
applied to the correlation lemma. Thus ℜ(θ(a)) =
1 − pm , and pwL (ev(a)) = (p − 1)(N − ℜ(θ(a))),
yielding wL (ev(a)) = (p − 1)(p2m−1 − pm−1 ). The
result follows. The proof of case (c) is the same as
that of case (b). In the case (d), ℜ(θ(a)) = 1, then
wL (ev(a)) = (p − 1)(p2m−1 − 2pm−1 ).
Thus we obtain a family of p-ary two-weight codes
of parameters [p2m − 2pm + 1, 2m], with weight
distribution as given in Table II. The parameters are
different from those in [4], [14], [15] and [16].
Table II.

weight distribution of C(m, p) in
Theorem 5.4
Weight
Frequency
0
1
(pm − 1)2
(p − 1)(p2m−1 − 2pm−1 )
(p − 1)(p2m−1 − pm−1 )
2(pm − 1)
B. The case of L′ = F∗pm × F∗pm

Theorem 5.5 For a ∈ R, the Lee weight of
codewords of C ′ (m, p) is

4

(a) If a = 0, then wL (ev ′ (a)) = 0;
(b) If a = uα, α ∈ F∗pm , then wL (ev ′ (a)) = 2(p −
1)(p2m−1 − pm−1 );
(c) If a = (1 − u)β, β ∈ F∗pm , then wL (ev ′ (a)) =
2(p − 1)(p2m−1 − pm−1 );
(d) If a ∈ R∗ , then wL (ev ′ (a)) = 2(p − 1)(p2m−1 −
2pm−1 ).
Proof
(a) If a = 0, then T r(ax) = 0. So wL (ev ′ (a)) = 0.
(b) If a = uα, x = ut + (1 − u)t′ with
α ∈ F∗pm , then ax = uαt, and T r(ax) =
T r(uαt) = utr(αt). Taking Gray map yields
′ . Taking charφ(ev ′ (a)) = (−tr(αt), tr(αt))
P t,tP
ω −tr(αt) +
acter sums θ(a) =
′ ∈F∗
t
t∈F∗
m
m
p
Pp
P
P
P
ω −tr(αt) =
ω tr(αt) = 2
t′ ∈F∗
t∈F∗
pm
pm
′
wL (ev (a)) =

t′ ∈F∗
t∈F∗
pm
pm
m

−2(p − 1). Thus
2(p −
1)(p2m−1 − pm−1 ).
(c) If a = (1 − u)β, x = ut + (1 − u)t′
with β ∈ F∗pm , then ax = βt′ − uβt′ , and
T r(ax) = tr(βt′ ) − utr(βt′ ). Taking Gray map
′
′ . Taking
yields φ(ev ′ (a)) = (tr(βt′P
), tr(βt
P))t,t tr(βt
′
)
ω
=
character sums θ(a) = 2
t′ ∈F∗
t∈F∗
pm
pm

′

m

2 − 2p . Thus wL (ev (a)) = 2(p − 1)(p2m−1 −
pm−1 ).
(d) Let a = uα + (1 − u)β), x = ut + (1 − u)t′ .
So ax
=
βt′ + u(αt − βt′ ), and
T r(ax)
=
tr(βt′ ) + utr(αt − βt′ ).
Taking Gray map yields
φ(ev ′ (a))
=

′
′
−tr(αt−βt ), tr(αt+βt ) t,t′ . Taking character
P −tr(αt) P
′
ω tr(βt ) +
ω
sums θ(a) =
P

ω

tr(αt)

t∈F∗
pm

t∈F∗
pm
tr(βt′ )

P

ω

t′ ∈F∗
pm

=

2.

Thus

t′ ∈F∗
pm

p−1
′
wL (ev ′ (a))
=
− 2),
or
p (N
′
2m−1
wL (ev (a)) = 2(p − 1)(p
− 2pm−1 ).
Thus we have constructed a p-ary code of length
N ′ = 2(pm − 1)2 , dimension 2m, with two weights.
The weight distribution is given in Table III. Note that
the parameters are different from those in [4], [14],
[15] and [16].

weight distribution of C ′ (m, p) in
Theorem 5.5
Weight
Frequency
0
1
2(p − 1)(p2m−1 − 2pm−1 )
p2m − 2pm + 1
2(p − 1)(p2m−1 − pm−1 )
2pm − 2
Table III.

VI. O PTIMALITY OF

THE

p- ARY

IMAGE

A central question of coding theory is to decide
whether the constructed codes are optimal or not. In
this section, we will investigate the optimality of the pary image of the trace codes we constructed in Section

JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

V. Recall the p-ary version of the Griesmer bound. If
[N, K, d] are the parameters of a linear p-ary code,
then
K−1
Xd
≤ N.
pj
j=0
A. L = uQ + (1 − u)F∗pm , m is odd and p ≡ 3
(mod 4)
Theorem 6.1 Assume m is odd and m ≥ 3, and
p ≡ 3 (mod 4). The code φ(C(m, p)) is optimal.
Proof Firstly, N = p2m − 2pm + 1, K = 2m, d =
(p − 1)(p2m−1 − 2pm−1 ) on account of Theorem
K−1
P  d+1 
5.4. We claim that
> N, contradicting
pj
j=0

the Griesmer bound. The ceiling function takes three
values depending on j.
d+1
2m−j
• 0 ≤ j ≤ m − 1 ⇒ ⌈ pj ⌉ = p
− 2pm−j −
2m−j−1
m−j−1
p
+ 2p
+ 1;
d+1
m
m−1
− 1;
• j = m ⇒ ⌈ pj ⌉ = p − p
d+1
2m−j
• m < j ≤ 2m − 1 ⇒ ⌈ pj ⌉ = p
− p2m−j−1 .
K−1
P  d+1 
= p2m − 2pm + m. Note that
Thus
pj
j=0

K−1
P
j=0

⌈ d+1
pj ⌉

− N = m − 1 > 0.

Example 6.2 Let p = 3 and m = 3, we obtain a
ternary code of parameters [676, 6, 450]. The weights
of this code are 450 and 468 with frequencies 676 and
52, respectively.
B. L′ = R∗ , m is an arbitrary integer and p is odd
prime

Theorem 6.3 Assume m ≥ 3 and p = 3 or m ≥ 4
and the odd prime p ≥ 5. The code φ(C ′ (m, p)) is
optimal.
Proof It follows from Theorem 5.5 that N ′ =
2(p2m − 2pm + 1), K = 2m, d = 2(p − 1)(p2m−1 −
K−1
P  d+1 
2pm−1 ). We claim that
> N ′ , violating
pj
j=0

the Griesmer bound. The ceiling function takes the
following values depending on the position of j.
(a) when p = 3, the ceiling function takes three
values depending on j.
d+1
2m−j
− 4pm−j −
• 0 ≤ j ≤ m− 1 ⇒ ⌈ pj ⌉ = 2p
2m−j−1
m−j−1
2p
+ 4p
+ 1;
d+1
m
m−1
• j = m ⇒ ⌈ pj ⌉ = 2p − 2p
− 2;
d+1
2m−j
−
• m < j ≤ 2m − 1 ⇒ ⌈ pj ⌉ = 2p
2m−j−1
2p
.
K−1
P  d+1 
= 2p2m − 4pm + m. Note that
Thus
pj
j=0

K−1
P 
j=0

d+1
pj



− N ′ = m − 2 > 0.

(b) when p ≥ 5 and p is odd prime, the ceiling
function takes three values depending on j.

5

2m−j
− 4pm−j −
0 ≤ j ≤ m− 1 ⇒ ⌈ d+1
pj ⌉ = 2p
2m−j−1
m−j−1
2p
+ 4p
+ 1;
d+1
m
m−1
• j = m ⇒ ⌈ pj ⌉ = 2p − 2p
− 3;
d+1
2m−j
−
• m < j ≤ 2m − 1 ⇒ ⌈ pj ⌉ = 2p
2m−j−1
2p
.
K−1
P  d+1 
Thus
= 2p2m − 4pm + m − 1. Note
pj
•

that

j=0
K−1
P 
j=0

d+1
pj



− N ′ = m − 3 > 0.

Hence the theorem is proved.
Example 6.4 Let p = 3 and m = 3, we obtain a
ternary code of parameters [1352, 6, 900]. The weights
of this code are 900 and 936 with frequencies 676 and
52, respectively.
VII. T HE MINIMUM

DISTANCE OF THE DUAL CODE

We
compute
the
dual
distance
of
φ(C(m, p))(resp. φ(C ′ (m, p))). In connection
with the discussion in [14], we mention without proof
the following lemma.
Lemma 7.1 If for all a ∈ R, we have that T r(ax) =
0, then x = 0.
Theorem 7.2 For all odd primes p and all m ≥ 2,
the dual Lee distance d′ of C(m, p) is 2.
Proof First, we check that d′ ≥ 2 by showing that
C(m, p)⊥ does not contain a word of Lee weight
one. If it does, let us assume first that it has value
γ 6= 0 at some x ∈ L. This implies that ∀a ∈
R, γT r(ax) = 0 or T r(aγx) = 0, and by Lemma
7.1 γx = 0. Contradiction with γ 6= 0. If that word
takes the value γ(1 − 2u) at some x ∈ L, then writing
x = ut + (1 − u)t′ and a = uα + (1 − u)β, with
α, β in Fpm , with t ∈ Q, t′ ∈ F∗pm yields, after
reduction modulo M the equation valid ∀α, β ∈ Fpm ,
γtr(βt′ ) = 0 and tr(γαt) = 0, and we conclude, by
the nondegenerate character of tr(), that γt = γt′ = 0.
Contradiction with x 6= 0.
Next, we shall show that d′ < 3. If not, we can apply
the sphere-packing bound to φ(C(m, p))⊥ , to obtain
p2m ≥ 1 + N (p − 1) = 1 + (p2m − 2pm + 1)(p − 1), or,
after expansion 2p2m + 2pm+1 ≥ p + pm (pm+1 + 2).
Dropping the p in the RHS, and dividing both sides
by pm , we find that this inequality would imply pm <
2
f (p), with f (x) = 2x−2
x−2 = 2 + x−2 . But the function
f is decreasing for x ≥ 3, and f (3) = 4, while pm ≥
p2 ≥ 9. Contradiction.
We now consider codes from the second family.
Theorem 7.3 For all odd prime p and all m ≥ 2,
the dual Lee distance d′ of C ′ (m, p) is 2.
Proof First, we check that d′ ≥ 2. The proof of
′
d ≥ 2 is like that in Theorem 7.2. Next, we show that
d′ < 3. Otherwise, we can apply the sphere-packing
bound to φ(C ′ (m, p)⊥ ), to obtain
p2m ≥ 1 + N ′ (p − 1) = 1 + 2(p2m − 2pm + 1)(p − 1).

JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

It is shown by a straightforward argument that 1 +
N ′ (p − 1) > 1 + N ′ where p is an odd prime. Then we
check p2m > 1 + N ′ . We obtain the inequality (pm −
3)(pm − 1) < 0 after calculation which is contradict
pm ≥ 3. Hence p2m ≤ 1 + N ′ (p − 1) = 1 + 2(p2m −
2pm + 1)(p − 1).
VIII. A PPLICATIONS

TO SECRET SHARING
SCHEMES

To illustrate an application of our constructed codes
in secret sharing, we review the fundamentals of this
cryptographic protocol. The concept of secret sharing
schemes was first proposed by Blakley and Shamir in
1979. We present some basic definitions concerning
secret sharing schemes and refer the interested reader
to the survey [17] for details.
The sets of participants which are capable of recovering the secret S are called access sets. The set
of all access sets is called the access structure of the
scheme. An access set is called minimal if its members
can recover the secret S but the members of any of
its proper subsets cannot recover S. Furthermore, if a
participant is contained in every minimal access set in
the scheme, then it is a dictatorial participant.
The support s(x) of a vector x in FN
p is defined
as the set of indices where it is nonzero. We say
that a vector x covers a vector y if s(x) contains
s(y). A minimal codeword of a linear code C is
a nonzero codeword that does not cover any other
nonzero codeword.
Next, we recall the secret sharing scheme based on
linear codes which is constructed by Massey. Let C
be an [n, k] linear code over the given finite field Fp
and G = [g0 , g1 , · · · , gn−1 ] be a generator matrix of
C where the column vectors are nonzero. The dealer
chooses a random vector u = (u0 , u1 , · · · , uk−1 ) ∈
Fkp and encodes the chosen vector as c = uG =
(c0 , c1 , · · · , cn−1 ). Then the dealer keeps the value of
u at the first coordinate S = c0 = ug0 as a secret, and
distributes the values at the remaining coordinates of c
to the participants as shares. Note that S = c0 = ug0 ,
the set of shares {vi1 = ci1 , · · · , vit = cit } can recover
the secret S if and only if the vectors g0 , gi1 , · · · , git
are linearly independent. Hence, we can write the
secret as a linear combination
S = ug0 =

t
X

xj cij .

j=1

From this equation, it is clear that if we P
have shares
t
cij , 1 ≤ j ≤ t and find xj by g0 =
j=1 xj gij ,
we can recover the secret S. In fact, we can use
the participants that correspond to the nonzero coordinates of the minimal codewords v ∈ C ⊥ , because
cv = c0 + ci1 vi1 + · · · + cit vit which implies that
S = c0 = −(ci1 vi1 + · · · + cit vit ).

6

In general, it is a tough task to determine the
minimal codewords of a given linear code. However,
there is a numerical condition, derived in [1], bearing
on the weights of the code, that is easy to check.
Lemma 8.1 (Ashikmin-Barg) Let w0 and w∞ denote the minimum and maximum nonzero weights, re0
> p−1
spectively. If ww∞
p , then every nonzero codeword
of C is minimal.
In the special case when all nonzero codewords are
minimal, it was shown in [7] that there is the following
alternative, depending on d′ .
Lemma 8.2 ([7]) Let C be an [n, k] code over Fp
and G = [g0 , g1 , · · · , gn−1 ] be a generator matrix of C.
If every codeword of C is minimal vector, then there
are pk−1 minimal access sets and the total number of
participants is n−1 in the secret sharing scheme based
on C ⊥ . Let d′ denote the minimal distance of C ⊥ . We
have the following results:
′
′
• If d ≥ 3, then for any fixed 1 ≤ t ≤ min{k −
′
′
1, d −2}, every group of t participants is involved
′
′
in (p − 1)t pk−(t +1) out of pk−1 minimal access
sets. We call such participants dictators.
′
• When d = 2, if gi is a multiple of g0 , 1 ≤ i ≤
n − 1, then the participant Pi must be in every
minimal access set and such a participant is called
a dictatorial participant. If gi is not a multiple of
g0 , then the participant Pi must be in (p − 1)pk−2
out of pk−1 minimal access sets.
Theorem 8.3 Let G = [g0 , g1 , ..., g(pm −1)2 −1 ] be a
generator matrix of φ(C(m, p)) where m(≥ 3) is odd
and p ≡ 3 (mod 4), then there are p2m−1 minimal
access sets and the total number of participants is
(pm − 1)2 − 1 in the secret sharing scheme based on
φ(C(m, p)⊥ ). We have the following results:
m
2
• if gi is a multiple of g0 , 1 ≤ i ≤ (p − 1) − 1,
then the participant Pi must be in every minimal
access set and such a participant is called a
dictatorial participant.
• If gi is not a multiple of g0 , then the participant
Pi must be in (p−1)p2m−2 out of p2m−1 minimal
access sets.
Proof By the preceding lemma with w0 = (p −
1)(p2m−1 −2pm−1 ) and w∞ = (p−1)(p2m−1 −pm−1 )
in Table II. Rewriting the inequality of the lemma
as
pm
pw0 > (p−1)w∞ , and dividing both sides by p−1
, we
obtain p(pm −2) > (p−1)(pm −1), or pm −p−1 > 0,
which is true for m ≥ 3. Substitute n = (pm − 1)2
into Lemma 8.2, and then the conclusion is obtained.
Remark 8.4 By the similar method in the proof of
Theorem 8.3, we find that all the nonzero codewords of
φ(C(m, p)) (m(≥ 6) is singly-even) and φ(C ′ (m, p))
(m ≥ 2, p is odd prime) are minimal. Thus, when
m(≥ 6) is singly-even, the secret sharing scheme based
on φ(C(m, p)⊥ ) has a similar structure as that in the
case when m ≥ 3 is odd and p ≡ 3 (mod 4). Let

JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

G′ = [g0 , g1 , ..., g2(pm −1)2 −1 ] be a generator matrix of
φ(C ′ (m, p)), then there are p2m−1 minimal access sets
and the total number of participants is 2(pm − 1)2 − 1
in the secret sharing scheme based on φ(C ′ (m, p)⊥ ).
If gj is a multiple of g0 , 1 ≤ j ≤ 2(pm − 1)2 − 1, then
the participant Pj must be in every minimal access set
and such a participant is called a dictatorial participant.
If gj is not a multiple of g0 , then the participant Pj
must be in (p − 1)p2m−2 out of p2m−1 minimal access
sets.
IX. C ONCLUSION
In the present paper, we have studied two infinite
families of trace codes defined over a finite ring.
Because the defining sets of these codes have the
structure of abelian multiplicative groups, they inherit
the structure of abelian codes. It is an open problem
to determine if they are cyclic codes or not. More
importantly, it is worthwhile to study other defining
sets that are subgroups of the group of units of R.
In particular, it would be interesting to replace our
Gaussian periods Q, N by other character sums that
are amenable to exact evaluation, in the vein of the
sums which appear in the study of irreducible cyclic
codes [6], [13]. This would lead to other enumerative
results of codes with a few weights.
Compared to the codes we constructed by similar
techniques in [14], [15] and [16], the obtained codes
in this paper have different weight distributions. They
are also different from the weight distributions in the
classical families in [4]. Hence, the p-ary linear codes
constructed from trace codes over rings in this paper
are new.
Biographies of all authors
Minjia Shi, he received the B.S. degree in Mathematics from Anqing Normal College of China in 2004; the
M.S. degree in Mathematics from Hefei University of
Technology of China in 2007, and the Ph.D degree in
the Institute of Computer Network Systems from Hefei
University of Technology of China in 2010. He has
been teaching at the School of Mathematical Sciences
of Anhui University since 2007. Since April 2012, he
has been the Associate Professor with the School of
Mathematical Sciences, Anhui University of China.
His research interests include algebraic coding theory and cryptography. He is the author of more than 60
journal articles and of one book. He has been the Area
Editor of Journal of Algebra Combinatorics Discrete
Structure and Application since 2014.
He has held visiting positions in School of Physical
& Mathematical Sciences, Nanyang Technological
University, Singapore, from August 2012 to August
2013, Telecom ParisTech, Paris, from July 2016
to August 2016, Chern Institute of Mathematics in
Nankai University since 2013.

7

Yue Guan, she has been an undergraduate student
at the School of Mathematical Sciences of Anhui
University since 2013. She won Honorable Mention
of Mathematical Contest in Modeling Certificate of
Achievement in 2016 and gained scholarships several
times during school years. She will become a graduate
student at School of Mathematical Sciences of Anhui
University in 2017. Her research direction includes
coding theory and cryptography.
Patrick Solé received the Ingénieur and DocteurIngénieur degrees both from Ecole Nationale
Supérieure des Télécommunications, Paris, France,
in 1984 and 1987, respectively, and the habilitation
diriger des recherches from Université de Nice-Sophia
Antipolis, Sophia Antipolis, France, in 1993.
He has held visiting positions in Syracuse University, Syracuse, NY, from 1987 to 1989, Macquarie
University, Sydney, Australia, from 1994 to 1996, and
Lille University, Lille, France, from 1999 to 2000.
Since 1989, he has been a permanent member of the
CNRS and became Directeur de Recherche in 1996.
He is currently member of the CNRS lab LAGA, from
University of Paris 13.
His research interests include coding theory (codes
over rings, quasi-cyclic codes), interconnection networks (graph spectra, expanders), vector quantization
(lattices), and cryptography (boolean functions, pseudo
random sequences).
He is the author of more than 150 journal articles
and of three books.
He was the associate editor of the IEEE Information
Theory Transactions from 1996 till 1999. He has
been associate editor of Advances in Mathematics of
Communication since 2007.
ACKNOWLEDGMENT
It is the authors’ pleasure to thank the anonymous
referees for their helpful comments which led to improvements of the paper.
R EFERENCES
[1] A. Ashikmin, A. Barg, “Minimal vectors in linear codes”, IEEE
Trans. Inform. Theory, vol. 44, no. 5, pp. 2010–2017, Sep. 1998.
[2] D. Berman, “Semisimple cyclic and Abelian codes. II”, Cybernetics & Systems Analysis, vol. 3, no. 3, pp. 17–23, 1967.
[3] A.E. Brouwer, W.H. Haemers, Spectra of Graphs, Springer,
2012.
[4] R. Calderbank, W.M. Kantor, “The geometry of two-weight
codes”, Bull. London Math. Soc., vol. 18, no. 2, pp. 97-122,
1986.
[5] P. Delsarte, “Weights of linear codes and strongly regular
normed spaces”, Disc. Math., vol. 3, no. 1-3, pp. 47–64, 1972.
[6] C. Ding, J. Yang, “Hamming weights in irreducible cyclic
codes”, Disc. Math., vol. 313, issue 4, pp. 434–446, Feb. 2013.
[7] C. Ding, J. Yuan, “Covering and secret sharing with linear
codes”, Springer LNCS, vol. 2731, pp. 11-25, Jun. 2003.

JOURNAL OF LATEX CLASS FILES, VOL. , NO. , 2017

[8] K.L. Ding, and C. Ding, “A Class of Two-Weight and ThreeWeight Codes and Their Applications in Secret Sharing”, IEEE
Trans. Inform. Theory, vol. 61, issue 11, pp. 5835–5842, Nov.
2015.
[9] J.M. Lampos, V. Sison, “Systematic Unit-Memory Binary Convolutional Codes from Linear Block Codes over F2r + vF2r ”,
WASET, issue 71, pp. 384-387, Nov. 2012.
[10] J.M. Lampos, V. Sison, “Bounds on (..) linear block codes over
finite semi-local Frobenius ring Fpr + vFpr ”, Southeast-Asian
J. of Sc., Vol. 1, No 1 (2012), pp.76–98.
[11] S. Ling, P. Solé, “Duadic codes over F2 + uF2 ”, AAECC, vol.
12, no. 5, pp. 365-379, Oct. 2001.
[12] F.J. MacWilliams, N.J.A. Sloane, The theory of errorcorrecting codes, North-Holland Math. Library, vol. 16, 1977.
[13] R.J. McEliece, H.Jr. Rumsey, “Euler products, cyclotomy, and
coding”, J. Number Theory, vol. 4, no. 3, pp. 302–311, Jun.
1972.
[14] M.J. Shi, Y. Liu, P. Solé, “Optimal two weight codes from
trace codes over F2 +uF2 ”, IEEE Commun. Letters, 20 ( 2016),
2346–2349.
[15] M.J. Shi, Y. Liu, P. Solé, “ Optimal two weight codes from
trace codes over a non-chain ring”, Discrete Applied Mathematics, 219 (2017) 171–181.
[16] M.J. Shi, R.S. Wu, Y. Liu, P. Solé, “Two and three weight
codes over Fp + uFp ”, Cryptogr. Commun., 9 (2017) 637–646.
[17] D.R. Stinson, “An explication of secret sharing schemes”,
Designs, Codes and Cryptography, vol. 2, no. 4, pp. 357-390,
Dec. 1992.
[18] H.N. Ward, “Quadratic residue codes an divisibility”, in Handbook of Coding Theory, W.C. Hufman and V. Pless eds, North
Holland, 827–870, 1998.
[19] J. Yuan, C. Ding, “Secret sharing schemes from three classes
of linear codes”, IEEE Trans. Inform. Theory, vol. 52, no.1, pp.
206-212, Jan. 2006.

8

