EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 14, No. 3, 2021, 685-694
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Cyclic Codes from A Sequence over Finite Fields

Nopendri1,3,∗, Intan Muchtadi Alamsyah1, Djoko Suprijanto2, Aleams Barra1

1 Algebra Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi
Bandung, Bandung, Indonesia
2 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural
Sciences, Institut Teknologi Bandung, Bandung, Indonesia
3 Cybernetics Research Group, School of Industrial and System Engineering,
Telkom University, Bandung, Indonesia

Abstract. A cyclic code has been one of the most active research topics in coding theory due to its
applications in many areas, such as data storage systems and communication, as they have efficient
encoding and decoding algorithms. This paper explains the construction of a family of cyclic codes
from sequences generated by a trace of a monomial over finite fields of odd characteristics. The
parameter and some examples of the codes are presented in this paper.

2020 Mathematics Subject Classifications: 94B15, 94B65, 94A55

Key Words and Phrases: Cyclic codes, sequences, linear span, cyclotomic coset, minimal poly-
nomials

1. Introduction

Let GF (q) be finite fields with q = pm elements, where p is prime and m ≥ 1. Consider
(GF (q))n as a vector space over GF (q). A q-ary [n, k, d]-linear code C is a k-dimensional
subspace of (GF (q))n with the minimum nonzero weight d. A linear code C over the finite
field GF (q) is said to be cyclic if any (c0, c1, . . . , cn−1) ∈ C implies (cn−1, c0, . . . , cn−2) ∈ C.
A word c = (c0, c1, ..., cn−1) in C can be represented as a polynomial c(x) = c0 + c1x +
... + cn−1x

n−1 in ring Rn = GF (q)[x]/〈xn − 1〉. So that C ⊆ (GF (q))n can be identified
by a subset of Rn, in this case the cyclic code is an ideal of Rn. Any ideal of Rn is
principal, so that it is generated by a polynomial g(x), where g(x) is a divisor of xn − 1.
The polynomial g is called generator of the cyclic code C. The dimension of cyclic code C
can be determined from degree of generator polynomial g.

The error-correcting capability of cyclic codes may not be as good as some other linear
codes in general. However, cyclic codes are widely used in many fields such as data storage

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v14i3.3907

Email addresses: nopendri301@s.itb.ac.id (Nopendri), ntan@math.itb.ac.id (I.M.Alamsyah),
djoko@math.itb.ac.id (D.Suprijanto),barra@math.itb.ac.id (A. Barra)

http://www.ejpam.com 685 © 2021 EJPAM All rights reserved.



Nopendri et al. / Eur. J. Pure Appl. Math, 14 (3) (2021), 685-694 686

and communication systems because they have attractive algebraic properties and have
efficient algorithms for encoding and decoding [2, 7, 11]. This code is also used to construct
impressive structures such as quantum codes [18], frequency hopping sequences [5] and so
on.

One of the main problems in coding theory research is finding the optimal code, which
is the code that has the largest minimum distance d related to the ability to correct
errors in the information transfer or meets some bounds from the best known linear code
according to the tables [8].

The cyclic code can be constructed from a periodic sequence s [3, 6]. These sequences
are generated from a function over a finite field. For simplicity, we call this cyclic code
as Cs. The results of Ding and Zhou’s constructions in papers [3] and [6] are interesting,
showing that the codes obtained are optimal.

Several open problems are presented in these papers [3, 6]. Some researchers have
solved the problems, see [12, 14, 16, 17]. Finding the dimension and the generator poly-
nomial of cyclic codes Cs from monomial f(x) = xq

m−2 ∈ GF (qm)[x] appear as an open
problem in [3], and solved by [17] then. However, differing sequences provide some different
results. In this paper, we discuss the construction of the cyclic code with the new sequence,
and we say that “sequence š”, from the monomial f(x). This construction will generate a
new cyclic code related to the code from the sequence s. We also add information about
the minimum distance of the code.

This paper is organized as follows. Section 2 introduces some basic notation and results
about q-cyclotomic cosets and sequences that will frequently be used to prove our main
results in the following sections. The dimension and the generator polynomial of a class
of cyclic codes defined by a sequence are determined in Section 3. The minimum distance
of this cyclic code is also provided in that section. In Section 4, we conclude this paper.

2. Preliminaries

In this section, some basic notations and results on q-cyclotomic cosets modulo n and
sequences used to prove the main result are introduced.

Definition 1. Let n = qm−1 and Zn = {0, 1, 2, . . . , n−1}. For any integer s, 0 ≤ s ≤ n−1,
the q-cyclotomic coset modulo n containing s is defined by

Cs = {s, qs, q2s, . . . , qls−1s} ⊂ Zn

where ls is the least positive integer such that qls ≡ s( mod n) and ls is called the size of
Cs.

Lemma 1. [9] Let q be a power of a prime p and n = qm− 1. For any 1 ≤ s ≤ n− 1 with
gcd(s, n) = 1 the length ls of the q-cyclotomic coset Cs is equal to m.

Definition 2. Let s∞ = (st)
∞
t=0 be a sequence over GF (q). A sequence s∞ is called

periodic with period N if there is positive integer N such that st = st+lN for every t, l ≥ 0.



Nopendri et al. / Eur. J. Pure Appl. Math, 14 (3) (2021), 685-694 687

Definition 3. The polynomial c(x) = akx
k +ak−1x

k−1 +ak−2x
k−2 + · · ·+a0 over GF (q),

with ak = 1, is called characteristic polynomial of s∞ if

aksn+k + ak−1sn+k−1 + ak−2sn+k−2 + ...+ a0sn = 0

for every n = 0, 1, 2, . . . . Furthermore, the polynomial characteristic of the smallest degree
of s∞ is called minimal polynomial of s∞, and denoted by Ms(x).

The minimal polynomial Ms(x) of the sequence s∞ is unique and divides c(x). The
degree of Ms(x) is called linear span or linear complexity of s∞ and is denoted by Ls.

For any sequence s∞, we can determine the linear span and minimal polynomial of s∞

from the following lemma [4, Theorem 5.3].

Lemma 2. Let s∞ = (st)
∞
t=0 be a sequence with period L over GF (q). Defined SL(x) =∑L−1

t=0 stx
t ∈ GF (q)[x]. Then the minimial polynomial Ms(x) of s∞ is given by

xL − 1

gcd(SL(x), xL − 1)

and the linear span Ls is given by L− deg( gcd(SL(x), xL − 1)).

Another way is given in the following lemma [1], which is very important for proof of
our main result.

Lemma 3. Any sequence s∞ over GF (q) of period qm − 1 has a unique powers-of-α
representation of the form

st =

qm−2∑
i=0

ciα
it, for all t ≥ 0,

where ci ∈ GF (qm) and α is a primitive element in GF (qm). Suppose that I = {i|ci 6= 0},
then the minimal polynomial of s∞ is

Ms(x) =
∏
i∈I

(x− αi), (1)

and the linear span of s∞ is Ls = |I|.

It should be noticed that in some references, the reciprocal of Ms(x) is the minimal
polynomial of the sequence s∞.

3. Cyclic codes from the monomial f(x) = xqm−2

In this section, we study a particular type of sequences š∞ defined by

št = Trm1 (f(αt + 1)− f(αt)), t ≥ 0, (2)



Nopendri et al. / Eur. J. Pure Appl. Math, 14 (3) (2021), 685-694 688

where
f(x) = xq

m−2, (3)

is a function in GF (qm)[x], m is a positive integer, Trm1 is the trace function from GF (qm)
to GF (q) and α is a primitive element of GF (qm)∗.

The objective of this part is to construct a class of cyclic code from this sequence with
explicit monomial f . We call the cyclic code Cš with the generator polynomial from the
minimal polynomial of the sequence š∞ = (št)

∞
t=0. Let n = qm − 1 and e = qm − 2. By

Lemma 3 and (2), to get the parameters of the corresponding cyclic codes is to compute
the powers-of-α representation of Trm1 (f(αt + 1)− f(αt)) as follows:

št = Trm1 (f(αt + 1)− f(αt))

= Trm1 ((αt + 1)e − (αt)e)

= Trm1

(
e∑

i=0

(
e
i

)
αit − αet

)

=

qm−2∑
i=0

(
e
i

)m−1∑
j=0

αqjit −
m−1∑
j=0

αqjet

=

qm−2∑
i=0,
i 6∈Ce

(
e
i

)m−1∑
j=0

αqjit

=

qm−2∑
i=0,
i 6∈Ce

m−1∑
j=0

(
e

qji mod n

)
mod p

αit

=

qm−2∑
i=0,
i 6∈Ce

Ke,q,m(i)αit,

(4)

where Ke,q,m(i) =
m−1∑
j=0

(
e

qji mod n

)
mod p and Ce is the q-cyclotomic coset containing

e modulo n.
From (4), define

Supp(Ke,q,m) = {i ∈ Zn : Ke,q,m(i) 6= 0, i 6∈ Ce}. (5)

Now, we need to count the Supp(Ke,q,m). To do this, we have to simplify (4). Note that
the following lemma is well-known.

Lemma 4. [15] Let N > M > 0, then(
N − 1
M

)
=
N −M
N

(
N
M

)
.



Nopendri et al. / Eur. J. Pure Appl. Math, 14 (3) (2021), 685-694 689

Let kij = qji mod n, from the Lemma 4 and note that the multiplicative inverse of
e+ 1 is p− 1 in modulo p, then

Ke,q,m(i) ≡
m−1∑
j=0

(
e
kij

)

≡
m−1∑
j=0

e+ 1− kij
e+ 1

(
e+ 1
kij

)

≡
m−1∑
j=0

(1 + kij)

(
e+ 1
kij

)
mod p.

(6)

The last part of (6) always has the same form for any j as the following lemma.

Lemma 5. For any i ∈ Zn, (
e+ 1

qi mod n

)
=

(
e+ 1

i mod n

)
.

Proof. Let i =
∑m−1

j=0 ijq
j , then qi mod n = im−1 + i0q+ · · ·+ im−2q

m−1. Combaining

the fact e+ 1 =
∑m−1

j=0 (q − 1)qj and Lucas’s theorem [13] we have(
e+ 1

qi mod n

)
≡
(
q − 1
im−2

)
. . .

(
q − 1
i0

)(
q − 1
im−1

)
≡
(
q − 1
im−1

)
. . .

(
q − 1
i1

)(
q − 1
i0

)
≡
(
e+ 1
i

)
mod p.

This yields, for kij = qji mod n, (where j ∈ Zm),

(
e+ 1
kij

)
≡
(
e+ 1
i

)
mod p. Hence,

the equation (6) equivalent to

Ke,q,m(i) ≡
(
e+ 1
i

)m−1∑
j=0

(1 + kij)

≡
(
e+ 1
i

)m+

m−1∑
j=0

kij

 mod p.

The following lemma assures that the

(
e+ 1
i

)
is not divided by p.



Nopendri et al. / Eur. J. Pure Appl. Math, 14 (3) (2021), 685-694 690

Lemma 6. Let a be a positive integer and k be a nonnegative integer. For p prime then(
pa − 1
k

)
6≡ 0 mod p.

Proof. (
pa − 1
k

)
≡ (pa − 1)!

k!(pa − 1− k)!

≡ (pa − 1)(pa − 2) · · · (pa − k)

k!

≡
pak −

(
k∑

i=1
i

)
p(k−1)a

k!

+

( ∑
i 6=j,i,j∈[k]

i.j

)
p(k−2)a − · · ·+ (−1)kk!

k!

≡ (−1)k mod p.

Let sq(i) =
m−1∑
j=0

kij , then (5) becomes

Supp(Ke,q,m) = {i ∈ Zn : sq(i) +m 6≡ 0 mod p}\{i ∈ Ce}. (7)

Let A = {i ∈ Zn : sq(i) +m 6≡ 0 mod p} and B = {i ∈ Ce}. So, (7) becomes

Supp(Ke,q,m) = A\B.

To get the cardinality of A we need to prove the following lemmas. Let λ1 = n
q−1 and

λ2 = q − 1, then λ1 = 1 + q + q2 + · · ·+ qm−1 and λ1λ2 = n.

Lemma 7. Let a ∈ Zn and j ∈ {0, 1, 2, . . . ,m − 1} such that aqj ≥ n and aqj = γn + δ,
for some δ ∈ Zn. Then

aqj ≡ aqj − γλ2(1 + q + q2 + · · ·+ qm−1) mod n,

for some γ ≥ 0.

Proof. Consider δ ∈ Zn, that is δ = aqj − γn = aqj − γλ1λ2, so that

δ ≡ aqj − γλ2(1 + q + q2 + · · ·+ qm−1) mod n,

for some γ ≥ 0.



Nopendri et al. / Eur. J. Pure Appl. Math, 14 (3) (2021), 685-694 691

Lemma 8. Let b ∈ Zn, b 6= 0. Then

sq(b) = (bq0 mod n) + (bq1 mod n) + · · ·
+ (bqm−1 mod n)

= (b− γ′)(1 + q + q2 + · · ·+ qm−1)

= (b− γ′) n

q − 1
,

for some γ′ < b.

Proof. Suppose j1, j2, · · · , jt ∈ {0, 1, 2, · · · ,m − 1} such that bqji ≥ n, for every i =
1, 2, · · · , t. Then by Lemma 7, we have

bqji ≡ bqji − γiλ2(1 + q + · · ·+ qm−1) mod n,

for some γi ≥ 0 and for all i = 1, 2, · · · , t. Hence

sq(b) = (bq0 mod n) + (bq1 mod n) + · · ·
+ (bqm−1 mod n)

= b(q0 + q1 + q2 + · · ·+ qm−1)

− (λ2

t∑
i=0

γi(q
0 + q1 + q2 + · · ·+ qm−1))

=

(
b− λ2

t∑
i=0

γi

)
(q0 + q1 + q2 + · · ·+ qm−1).

Put γ′ = λ2
∑t

i=1 γi.

Lemma 9. If (b− γ′) 6= 0 mod p, then

(b− γ′)λ1 = (b− γ′) n

q − 1
6= 0 mod p.

Proof. Since λ1|n = qm − 1, then gcd(λ1, p) = 1 so that λ1 mod p is a unit in Zp.
Consequently, if (b− γ′) 6≡ 0 mod p, then (b− γ′)λ1 ≡ (b− γ′) n

q−1 6≡ 0 mod p.

In order to determine i ∈ Zn such that sq(i) 6= 0 mod p, it is equivalent to find i such
that i − γ′ 6≡ 0 mod p (based on Lemma 8 and Lemma 9) and i − γ′ 6≡ 0 mod p if and
only if gcd(i− γ′, qm) = 1. Hence, from Phi Euler function we have

#A = qm(1− 1

p
). (8)

The biggest element in Zn, that is e = qm − 2, contained in A. It can be shown by the
following lemma.



Nopendri et al. / Eur. J. Pure Appl. Math, 14 (3) (2021), 685-694 692

Lemma 10. Let q be a prime power of p. Defined sq(i) =
m−1∑
j=0

kij ,, where kij = qji mod n

and n = qm − 1. Then
sq(e) +m 6≡ 0 mod p,

where e = qm − 2.

Proof.

sq(e) +m ≡ (e mod n) + (qe mod n) + · · ·
+ (qm−1e mod n) +m

≡ (n− 1) + (n− q) + · · ·+ (n− qm−1) +m

≡ mn+m− (1 + q + q2 + · · ·+ qm−1)

≡ −1 mod p.

From Lemma 1 and gcd(e, n) = 1 we have |B| = |Ce| = m. Thus, from (8), we have

#Supp(Ke,q,m) = qm(1− 1

p
)−m. (9)

The following theorem gives the minimal polynomial of the sequence š∞ in (2) with func-
tion (3).

Theorem 1. Let š∞ be the sequence of (2), where f(x) = xq
m−2, then the minimal

polynomial of š∞ is given by

Mš(x) =
∏
i∈Zn,

sq(i)+m6≡0 mod p,
i 6∈Ce

(x− αi), (10)

and the linier span Lš of š∞ is

Lš = qm(1− 1

p
)−m.

Proof. This theorem follows from Lemma 3, Lemma 10, Eq. (7) and Eq. (9).

The polynomial (10) in Theorem 1 can be used to construct a class of cyclic codes as
the following.

Theorem 2. The cyclic code Cš defined by sequence of Theorem 1 has parameters [qm −
1, q

m

p − 1 +m, d] where d ≥ q(p−1)
p and generator polynomial Mš(x) of (10).

Proof. The dimension of Cš follows from Theorem 1. Therefore we consider the lower
bound of minimum weight d. Note that the weight distribution of the cyclic code gen-
erated by Mš(x) is the same as that generated by the reciprocal polynomial of Mš(x).



REFERENCES 693

Furthermore, the reciprocal polynomial of Mš(x) has zeros αi where i ∈ H = {pj+1 : j =

1, 2, . . . , q(p−1)
p − 1}. Thus, from the Hartmann-Tzeng bound [10, Theorem 1], we have

d ≥ q(p−1)
p .

Example 1. Let q = 3, m = 2, and irreducible polynomial for GF (32) is x2 + 2x+ 2 = 0.
Then Cš is a [8, 4, 2] cyclic code over GF (3) with the generator polynomial Mš(x) = x4 +2.
It is known that for optimal linear codes of length 8 and dimension 4 over GF (3), the
minimal distance is d = 4.Its dual is a [8, 4, 2] cyclic code.

Example 2. Let q = 3,m = 3, and α be a generator of GF (33)∗ with α3 + 2α + 1 = 0.
Then Cš is a [26, 11, 6] cyclic code over GF (3) with the generator polynomial Mš(x) =
x15 + x14 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + 1. It is known that
for optimal linear codes of length 26 and dimension 11 over GF (3), the minimal distance
satisfies 9 ≤ d ≤ 11. Its dual is a [26, 15,4] cyclic code.

Example 3. Let q = 3,m = 3, and α be a generator of GF (33)∗ with α3 + 2α2 + 1 = 0.
Then Cš is a [26, 11, 6] cyclic code over GF (3) with the generator polynomial Mš(x) =
x15 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x+ 1. Its dual is a [26, 15,4]
cyclic code.

4. Conclusion

We have given the construction of a family of cyclic code from periodic sequence š
from a monomial f(x) = xq

m−2 in GF (qm). The lower bound of the code is presented in

Theorem 2. In general, the code Cš has parameter [qm− 1, q
m

p − 1 +m, d] with d ≥ q(p−1)
p .

Three examples are presented. Numerical examples show that for the same length and
distance, the dual of cyclic codes presented in this paper has a lower dimension than in
[3, 1983] and [17, page 27].

Acknowledgements

The authors are very grateful to the editors and the reviewers for their comments and
suggestions to improve this paper’s quality. The authors also thank Irwansyah for the
valuable discussions. This work was supported by HIBAH RISET DASAR DIKTI 2019.

References

[1] M Antweiler and L Bömer. Complex sequences over GF (pm) with a two-level autocor-
relation function and a large linear span. IEEE Trans. Inform. Theory, 38(1):120–130,
1992.

[2] R T Chien. Cyclic decoding procedures for bose-chaudhuri-hocquenghem codes. IEEE
Trans. Inform. Theory, 10(4):357–363, 1964.



REFERENCES 694

[3] C Ding. Cyclic codes from some monomials and trinomials. SIAM Journal on Discrete
Mathematics, 27(4):1977–1994, 2013.

[4] C Ding, G Xiao, and W Shan. The Stability Theory of Stream Ciphers, volume 561 of
Lecture Notes in Computer Science. Springer-Verlag Berlin Heidelberg, 1st edition,
1991.

[5] C Ding, Y Yang, and X Tang. Optimal sets of frequency hopping sequences from
linear cyclic codes. IEEE Trans. Inform. Theory, 56(7):3605–3612, 2010.

[6] C Ding and Z Zhou. Binary cyclic codes from explicit polynomials over GF (2m).
Discrete Mathematics, 321:76–89, 2014.

[7] G D Forney. On decoding BCH codes. IEEE Trans. Inform. Theory, 11(4):549–557,
1965.

[8] M Grassl. Bounds on the minimum distance of linear codes and quantum codes.
Online available at http://www.codetables.de, 2007. Accessed on 2020-12-20.

[9] K C Gupta and S Maitra. Primitive polynomials over GF (2) - A cryptologic ap-
proach. In Information and Communications Security, Third International Confer-
ence, ICICS 2001, Xian, China, November 13-16, 2001, pages 23–34, 2001.

[10] C R P Hartmann and K K Tzeng. Generalizations of the BCH bound. Information
and Control, 20(5):489–498, 1972.

[11] W C Huffman and V Pless. Fundamentals of Error-Correcting Codes. Cambridge
University Press, 2010.

[12] L Li, S Zhu, L Liu, and X Kai. Some q-ary cyclic codes from explicit monomials over
Fm
q . Problems of Information Transmission, 55(3):254–274, 2019.

[13] E Lucas. Théorie des fonctions numériques simplement périodiques. Am. J. Math,
1:229–231, 1878.

[14] Z Rajabi and K Khashyarmanesh. Some cyclic codes from some monomials. Appl.
Algebra Eng., Commun. Comput., 28(6):469–495, 2017.

[15] K H Rosen. Discrete mathematics and its applications. McGraw-Hill, 8th edition,
2019.

[16] A Syarifuddin and I Muchtadi-Alamsyah. Construction of cyclic codes over ternary
field from periodic sequences. Southeast Asian Bulletin of Mathematics, 42(5):773–
780, 2018.

[17] C Tang, Y Qi, and M Xu. A note on cyclic codes from APN functions. Appl. Algebra
Eng., Commun. Comput., 25(1):21–37, 2014.

[18] A Thangaraj and S W McLaughlin. Quantum codes from cyclic codes over GF(4m).
IEEE Trans. Inform. Theory, 47(3):1176–1178, 2001.