i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 369 — #1 i
i

i
i

i
i

Tema
Tendências em Matemática Aplicada e Computacional, 19, N. 2 (2018), 369-389
© 2018 Sociedade Brasileira de Matemática Aplicada e Computacional
www.scielo.br/tema
doi: 10.5540/tema.2018.019.02.0369

Sequences of Primitive and Non-primitive BCH Codes

A.S. ANSARI1, T. SHAH1, ZIA-UR-RAHMAN1 and A.A. ANDRADE2

Received on March 27, 2017 / Accepted on March 21, 2018

ABSTRACT. In this work, we introduce a method by which it is established that how a sequence of
non-primitive BCH codes can be obtained by a given primitive BCH code. For this, we rush to the out of
routine assembling technique of BCH codes and use the structure of monoid rings instead of polynomial
rings. Accordingly, it is gotten that there is a sequence {Cb jn}1≤ j≤m, where b jn is the length of Cb jn, of
non-primitive binary BCH codes against a given binary BCH code Cn of length n. Matlab based simulated
algorithms for encoding and decoding for these type of codes are introduced. Matlab provides in routines for
construction of a primitive BCH code, but impose several constraints, like degree s of primitive irreducible
polynomial should be less than 16. This work focuses on non-primitive irreducible polynomials having
degree bs, which go far more than 16.

Keywords: Monoid ring, BCH codes, primitive polynomial, non-primitive polynomial.

1 INTRODUCTION

Introducing more general algebraic structures lead to various gains in coding applications and the
generality of the algebraic structures helps to find more efficient encoding and decoding algo-
rithms for known codes. This has motivated special attention of many researchers in considering
ideals of certain rings [1], [5], [6], [9] and [10]. The extension of a BCH code embedded in a
semigroup ring was considered by Cazaran in [4]. More information regarding ring constructions
and its corresponding polynomial codes were given by Kelarev [5]. In [1], the authors elaborated
cyclic, BCH, Alternant, Goppa and Srivastava codes over finite rings, which are constructed
through a polynomial ring in one indeterminate. Several classes of cyclic codes constructed using
the monoid rings are discussed in [2], [14], [13], [12], [11] and [15]. These constructions address
the error correction and the code rate in a good way. In [16], Shah et al., showed the existence
of a binary cyclic code of length (n+ 1)n such that a binary BCH code of length n is embed-
ded in it. Though they were not succeeded to show the existence of binary BCH code of length

*Corresponding author: Antonio A. Andrade – E-mail: antonio.andrade@unesp.br
1Department of Mathematics, Quaid-i-Azam University, Islamabad, Pakistan. E-mail: asia ansari@hotmail.com;
stariqshah@gmail.com; ziaagikian@gmail.com
2Departamento de Matematica, Universidade Estadual Paulista – São José do Rio Preto, SP, Brazil. E-mail:
andrade@ibilce.unesp.br



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 370 — #2 i
i

i
i

i
i

370 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

(n+1)n corresponding to a given binary BCH code of length n. In [17], a construction method
is given by which cyclic codes are ideals in F2[x;aZ0]n, F2[x]an, F2[x; a

bZ0]bn and F2[x; 1
bZ0]abn,

where Z0 is the set of non-negative integers, a,b ∈ Z and a,b > 1. These codes are capable of
correcting random as well as burst errors. Moreover, a link between all these codes are also been
developed. Furthermore, in [3], the work of [16] is improved and an association between primi-
tive and non-primitive binary BCH codes is obtained by using the monoid ring F2[x; a

bZ0], where
a,b > 1. It is noticed that the monoid ring F2[x; a

bZ0] does not contain the polynomial ring F2[x]
for a > 1. To handle this situation, a BCH code in the monoid ring F2[x;aZ0] is constructed and
then the existence of a non-primitive BCH code in the monoid ring F2[x; a

bZ0] is showed. The
non-primitive BCH code Cbn in the monoid ring F2[x; a

bZ0] is of length bn and generated by a
generalized polynomial g(x

a
b ) ∈ F2[x; a

bZ0] of degree br. In this line, corresponding to a binary
BCH code Cn of length n generated by a generalized polynomial g(xa) ∈ F2[x;aZ0] of degree r
it is constructed a code Cbn such that Cn is embedded in Cbn.

This work extends the work of [3], where the monoid ring F2[x; a
b j Z0], with b= a+ i, 1≤ i, j≤m,

where m is a positive integer, is used. Corresponding to the sequence {F2[x; a
b j Z0]} j≥1 of monoid

rings, we obtain a sequence of non-primitive binary BCH codes {C j
b jn} j≥1, based on a primitive

BCH code Cn of length n. The non-primitive BCH code C j
b jn in the monoid ring F2[x; a

b j Z0] is

of length b jn and generated by a generalized polynomial g(x
a

b j ) ∈ F2[x; a
b j Z0] of degree b jr.

Similarly, corresponding to a given binary BCH code Cn of length n generated by a polynomial
g(xa) ∈ F2[x;aZ0] of degree r it is constructed a code C j

b jn such that Cn is embedded in C j
b jn,

where the length of the binary BCH code C j
b jn is well controlled with better error correction

capability. Along with the construction of a sequence {C j
b jn} j≥1 of non-primitive binary BCH

codes our focus is on its simulation as well, where the simulation is carried out using Matlab.
It provides built in routines only for primitive BCH codes with degree of primitive polynomial
less than 16. Whereas in constructing non-primitive BCH codes, the degree of non-primitive
polynomial goes beyond 16, where to overcome this situation Generic Algorithm is developed in
Matlab. The whole method of the algorithm is carried out in two major steps: I) Generating non-
primitive polynomial and II) Error correction in received polynomial. In Table 5, some examples
are listed. The non-primitive BCH codes with same code rate and error corrections are found
to be interleaved codes. By interleaving a t random error correcting (n,k) code to degree β , we
obtain a (βn,βk) code which is capable of correcting any combination of t bursts of length β

or less [7, Section 9.4], where the non-primitive BCH codes C j
b jn have burst error correction

capability along with the random error correction.

2 BCH CODES IN F2[X ; A
BJ Z0]BJN , WHERE 1≤ J ≤M.

The set of all finitely nonzero functions f from a commutative monoid (S,∗) into the binary
field F2 is denoted by F2(S). This set F2(S) is a ring with respect to binary operations addition
and multiplication defined as: ( f + g)(s) = f (s) + g(s) and ( f g)(s) = ∑t∗u=s f (t)g(u), where
the symbol ∑t∗u=s indicates that the sum is taken over all pairs (t,u) of elements of S such that

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 371 — #3 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 371

t ∗ u = s and it is understood that in the situation where s is not expressible in the form t ∗ u for
any t,u ∈ S, then ( f g)(s) = 0. The ring F2(S) is known as the monoid ring of S over F2 and it
is represented by F2[x;S] whenever S is an additive monoid. A nonzero element f of F2[x;S] is
uniquely represented in the canonical form ∑

n
i=1 f (si)xsi = ∑

n
i=1 fixsi , where fi 6= 0 and si 6= s j

for i 6= j. The monoid ring F2[x;S] is a polynomial ring in one indeterminate if S = Z0.

The indeterminate of generalized polynomials in monoid rings F2[x;aZ0] and F2[x; a
b j Z0] are

given by xa and x
a

b j for each 1 ≤ j ≤ m, where m is a fix positive integer, and they behave
like an indeterminate x in F2[x]. The arbitrary elements in F2[x;aZ0] and F2[x; a

b j Z0] are written,

respectively, as f (xa)= 1+(xa)+(xa)2+ · · ·+(xa)n and f (x
a

b j )= 1+(x
a

b j )+(x
a

b j )2+ · · ·(x
a

b j )n.
The monoids aZ0 and a

b j Z0 are totally ordered, so degree and order of elements of F2[x;aZ0] and
F2[x; a

b j Z0] are defined.

As F2[x;aZ0]⊂ F2[x], it follows that the construction of BCH code in the factor ring F2[x;aZ0]n
is similar to the construction of a BCH code in F2[x]n. Whereas the construction of BCH codes
in F2[x; a

b j Z0]/((x
a

b j )b jn−1) ≡ F2[x; a
b j Z0]b jn is based on the values of b. BCH codes of length

b jn in F2[x; a
b j Z0]b jn, corresponding to a BCH code Cn of length n don’t exist for all values of b,

where b = a+ i, such that 1 ≤ i ≤ m, and a, m are positive integers. For that, consider the fol-
lowing map p(xa) = p0 + p1xa + · · ·+ pn−1(xa)n−1 7→ p0 + p1(x

a
b j )b j

+ · · ·+ pn−1(x
a

b j )b j(n−1) =

p(x
a

b j ), which convert a primitive polynomial p(xa) of degree s in F2[x;aZ0] to a polynomial
p(x

a
b j ) of degree b js in F2[x; a

b j Z0]. This converted polynomial is found to be non-primitive, but
is irreducible for some values of b. Therefore, for the construction of a non-primitive BCH code
in F2[x; a

b j Z0]b jn, only this specific value of b is selected for which there is an irreducible poly-

nomial p(x
a

b j ) in F2[x; a
b j Z0]. Thus, for positive integers c j, d j and b jn such that 2 ≤ d j ≤ b jn

with b jn is relatively prime to 2, there exists a non-primitive binary BCH code Cb jn of length
b jn, where b jn is order of an element α ∈ F

2b js .

In Table 1, we present a list of irreducible polynomials of degree b js in F2[x; a
b j Z0] correspond-

ing to primitive irreducible polynomial of degree s in F2[x;aZ0], where for p(xa) ∈ F2[x;aZ0],
p(x

a
b ) ∈ F2[x; a

bZ0], p(x
a

b2 ) ∈ F2[x; a
bZ0], replace xa,x

a
b and x

a
b2 by x,y and z, respectively.

Proposition 1. [3, Proposition 2] If p(xa) ∈ F2[x;aZ0] is a primitive irreducible polynomial of
degree s∈ {2l,3l,4l,6l}, where l ∈Z0, then the corresponding generalized polynomial p(x

a
b j ) of

degree b js in F2[x; a
b j Z0] is non-primitive irreducible for b ∈ {3,7,{3,5},{3,7}}, respectively.

Theorem 2. [3, Theorem 3] Let n = 2s− 1 be the length of a primitive BCH code Cn, where
p(xa)∈F2[x;aZ0] is a primitive irreducible polynomial of degree s such that p(x

a
b j )∈F2[x; a

b j Z0]

is a non-primitive irreducible polynomial of degree b js.

1. For positive integers c j,d j,b jn such that 2 ≤ d j ≤ b jn and b jn are relatively prime to 2,
there exist a non-primitive binary BCH code Cb jn of length b jn, where b jn is the order of
an element α ∈ F

2b js .

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 372 — #4 i
i

i
i

i
i

372 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

Table 1: Irreducible polynomials of degree b js in F2[x; a
b j Z0] corresponding to

primitive irreducible polynomial of degree s in F2[x;aZ0].

p(xa) ∈ F2[x;aZ0] p(x
a
b ) ∈ F2[x; a

bZ0] p(x
a

b2 ) ∈ F2[x; a
bZ0]

1+(xa)+(xa)3 1+(x
a
7 )7 +(x

a
7 )21 1+(x

a
49 )49 +(x

a
49 )147

1+(x
a
3 )3 +(x

a
3 )12

1+(x
a
5 )5 +(x

a
5 )20

1+(x
a
9 )9 +(x

a
9 )36

1+(x
a

25 )25 +(x
a
25 )100

1+(xa)3 +(xa)4 1+(x
a
3 )9 +(x

a
3 )12

1+(x
a
5 )15 +(x

a
5 )20

1+(x
a
9 )27 +(x

a
9 )36

1+(x
a
25 )75 +(x

a
25 )100

1+(xa)+(xa)6 1+(x
a
3 )3 +(x

a
3 )18

1+(x
a
7 )7 +(x

a
7 )42

1+(x
a
9 )9 +(x

a
9 )54

1+(x
a
49 )49 +(x

a
49 )294

1+(xa)+(xa)3

+(xa)5 +(xa)8

1+(x
a
3 )3 +(x

a
3 )9+

(x
a
3 )15 +(x

a
3 )24

1+(x
a
5 )5 +(x

a
5 )15+

(x
a
5 )25 +(x

a
5 )40

1+(x
a
9 )9 +(x

a
9 )27+

(x
a
9 )45 +(x

a
9 )72

1+(x
a
25 )25 +(x

a
25 )75+

(x
a

25 )125 +(x
a
25 )200

1+(xa)4 +(xa)9 1+(x
a
7 )28 +(x

a
7 )63

1+(x
a

49 )196 +(x
a
49 )441

...
...

...

2. The non-primitive BCH code Cb jn of length b jn is defined as

Cb jn = {v(x
a

b j ) ∈ F2[x;
a
b j Z0]b jn : v(α i) = 0 for all i = c j,c j +1, · · · ,c j +d j−2.

Equivalently, Cb jn is the null space of the matrix

H =


1 αc j α2c j · · · α(bn−1)c j

1 αc j+1 α2(c j+1) · · · α(bn−1)(c j+1)

...
...

...
. . .

...
1 αc j+d j−2 α2(c j+d j−2) · · · α(bn−1)(c j+d j−2)

 .

The following example illustrates the construction of a non-primitive BCH code of length 32n
through F2[x; 2

32 Z0].

Example 2.1. Corresponding to a primitive polynomial p(x2) = 1+(x2)+ (x2)4 in F2[x;2Z0]

there is a non-primitive irreducible polynomial p(x
2

32 ) = 1+(x
2
9 )9+(x

2
9 )36 in F2[x; 2

32 Z0] (Table

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 373 — #5 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 373

1). Let α ∈ GF(236) such that α satisfies the relation α36 +α9 + 1 = 0. Using this relation, in
the Table 2, we obtain the distinct elements of GF(236).

By Table 2, it follows that b2n = 32× 15 = 135. Now, to calculate the generating polynomial
g(x

2
9 ), first calculate the minimal polynomials. By [8, Theorem 4.4.2], the following roots

α,α2,α4,α8,α16,α32,α64,α128,α121,α107,α79,α23,α46,α92,α49,α98,α61,α122,

α109,α83,α31,α62,α124,α113,α91,α47,α94,α53,α106,α77,α19α38,α76,α17,α34,α68

have same minimal polynomial m1(x
2
9 ) = p(x

2
9 ) = 1+(x

2
9 )9+(x

2
9 )36. It m3(x

2
9 ) is the minimal

polynomial for α3, then α3,α6,α12,α24,α48,α96,α57,α114,α93,α51,α102 and α69 all are roots
for m3(x

2
9 ). Therefore, it follows that m3(x

2
9 ) = (x

2
9 )12+(x

2
9 )3+1. Similarly,

m5(x
2
9 ) = (x

2
9 )

18
+(x

2
9 )9+1,m7(x

2
9 ) = (x

2
9 )36+(x

2
9 )27+1

m9(x
2
9 ) = (x

2
9 )

4
+(x

2
9 )+1, m15(x

2
9 ) = (x

2
9 )6+(x

2
9 )3+1

m21(x
2
9 ) = (x

2
9 )

12
+(x

2
9 )9+1

m27(x
2
9 ) = (x

2
9 )

4
+(x

2
9 )3+(x

2
9 )2+(x

2
9 )+1

m45(x
2
9 ) = (x

2
9 )

2
+(x

2
9 )+1, m63(x

2
9 ) = (x

2
9 )4+(x

2
9 )3+1.

The BCH code with d2 = 3 has generator polynomial g(x
2
9 ) = 1+(x

2
9 )9+(x

2
9 )36. It corrects up

to 1 error and its code rate is 99
135 = 0.733. The BCH code with d2 = 5 has generator polynomial

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 )) = ((x

2
9 )36+(x

2
9 )9+1)((x

2
9 )12+(x

2
9 )3+1)

= (x
2
9 )48+(x

2
9 )39+(x

2
9 )36+(x

2
9 )21+(x

2
9 )9+(x

2
9 )3+1.

It corrects up to 3 errors and its code rate is 87
135 = 0.644. Similarly, the BCH codes with d2 =

7,9,15,21,27,45,63 and 135 have generator polynomials

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))

= (x
2
9 )66+(x

2
9 )54+(x

2
9 )45+(x

2
9 )36+(x

2
9 )30+(x

2
9 )27+(x

2
9 )12+(x

2
9 )3+1.

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))(m7(x

2
9 ))

= (x
2
9 )102+(x

2
9 )93+(x

2
9 )90+(x

2
9 )57+(x

2
9 )48+(x

2
9 )45+(x

2
9 )12+(x

2
9 )3+1.

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))(m7(x

2
9 ))(m9(x

2
9 ))

= (x
2
9 )106+(x

2
9 )103+(x

2
9 )102+(x

2
9 )97+(x

2
9 )93+(x

2
9 )91+(x

2
9 )90+(x

2
9 )61

+(x
2
9 )58+(x

2
9 )57+(x

2
9 )52+(x

2
9 )48+(x

2
9 )46+(x

2
9 )45+(x

2
9 )16+(x

2
9 )13

+(x
2
9 )12+(x

2
9 )7+(x

2
9 )3+(x

2
9 )+1.

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))(m7(x

2
9 ))(m9(x

2
9 ))(m15(x

2
9 ))

= (x
2
9 )112+(x

2
9 )108+(x

2
9 )105+(x

2
9 )102+(x

2
9 )100+(x

2
9 )99+(x

2
9 )94+(x

2
9 )91

+(x
2
9 )90+(x

2
9 )67+(x

2
9 )63+ (x

2
9 )60+(x

2
9 )57+(x

2
9 )55+(x

2
9 )54+(x

2
9 )49

+(x
2
9 )46+(x

2
9 )45+(x

2
9 )22+(x

2
9 )18+(x

2
9 )15+(x

2
9 )12+(x

2
9 )10+(x

2
9 )9

+(x
2
9 )4+(x

2
9 )+1.

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 374 — #6 i
i

i
i

i
i

374 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

Table 2: Distinct elements of GF(236).

α36= 1+α
9

α62= α26+α35 α88= α16+α34 α114= α6+α15+α24+α33

α37= α +α10 α63= 1+α
9+α27 α89= α17+α35 α115= α7+α16+α25+α34

α38= α2+α11 α64= α +α10+α28 α90= 1+α
9+α18 α116= α8+α17+α26+α35

α39= α3+α12 α65= α2+α11+α29 α91= α +α10+α19 α117= 1+α
18+α27

α40= α4+α13 α66= α3+α12+α30 α92= α2+α11+α20 α118= α +α19+α28

α41= α5+α14 α67= α4+α13+α31 α93= α3+α12+α21 α119= α2+α20+α29

α42= α6+α15 α68= α5+α14+α32 α94= α4+α13+α22 α120= α3+α21+α30

α43= α7+α16 α69= α6+α15+α33 α95= α5+α14+α23 α121= α4+α22+α31

α44= α8+α17 α70= α7+α16+α34 α96= α6+α15+α24 α122= α5+α23+α32

α45= α9+α18 α71= α8+α17+α35 α97= α7+α16+α25 α123= α6+α24+α33

α46= α10+α19 α72= 1+α
18

α98= α8+α17+α26 α124= α7+α25+α34

α47= α11+α20 α73= α +α19 α99= α9+α18+α27 α125= α8+α26+α35

α48= α12+α21 α74= α2+α20 α100= α10+α19+α28 α126= 1+α
27

α49= α13+α22 α75= α3+α21 α101= α11+α20+α29 α127= α +α28

α50= α14+α23 α76= α4+α22 α102= α12+α21+α30 α128= α2+α29

α51= α15+α24 α77= α5+α23 α103= α13+α22+α31 α129= α3+α30

α52= α16+α25 α78= α6+α24 α104= α14+α23+α32 α130= α4+α31

α53= α17+α26 α79= α7+α25 α105= α15+α24+α33 α131= α5+α32

α54= α18+α27 α80= α8+α26 α106= α16+α25+α34 α132= α6+α33

α55= α19+α28 α81= α9+α27 α107= α17+α26+α35 α133= α7+α34

α56= α20+α29 α82= α10+α28 α108= 1+α
9+α18+α27 α134= α8+α35

α57= α21+α30 α83= α11+α29 α109= α +α10+α19+α28 α135= 1

α58= α22+α31 α84= α12+α30 α110= α2+α11+α20+α29

α59= α23+α32 α85= α13+α31 α111= α3+α12+α21+α30

α60= α24+α33 α86= α14+α32 α112= α4+α13+α22+α31

α61= α25+α34 α87= α15+α33 α113= α5+α14+α23+α32

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 375 — #7 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 375

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))(m7(x

2
9 ))(m9(x

2
9 ))(m15(x

2
9 ))(m21(x

2
9 ))

= (x
2
9 )124+(x

2
9 )121+(x

2
9 )120+(x

2
9 )109+(x

2
9 )106+(x

2
9 )105+(x

2
9 )94+(x

2
9 )91

+(x
2
9 )90+(x

2
9 )79+(x

2
9 )76+(x

2
9 )75+(x

2
9 )64+(x

2
9 )61+(x

2
9 )60+(x

2
9 )49

+(x
2
9 )46+(x

2
9 )45+(x

2
9 )34+(x

2
9 )31+(x

2
9 )30+(x

2
9 )19+(x

2
9 )16+(x

2
9 )15

+(x
2
9 )4+(x

2
9 )+1.

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))(m7(x

2
9 ))(m9(x

2
9 ))(m15(x

2
9 ))(m21(x

2
9 ))(m27(x

2
9 ))

= (x
2
9 )128+(x

2
9 )127+(x

2
9 )126+(x

2
9 )124+(x

2
9 )120+(x

2
9 )113+(x

2
9 )112+(x

2
9 )111

+(x
2
9 )109+(x

2
9 )105+(x

2
9 )98+(x

2
9 )97+(x

2
9 )96+(x

2
9 )94+(x

2
9 )90+(x

2
9 )83+(x

2
9 )82

+(x
2
9 )81+(x

2
9 )79+(x

2
9 )75+(x

2
9 )68+(x

2
9 )67+(x

2
9 )66+(x

2
9 )64+(x

2
9 )60+(x

2
9 )53

+(x
2
9 )52+(x

2
9 )51+(x

2
9 )49+(x

2
9 )45+(x

2
9 )38+(x

2
9 )37+(x

2
9 )36+(x

2
9 )34+(x

2
9 )30

+(x
2
9 )23+(x

2
9 )22+(x

2
9 )21+(x

2
9 )19+(x

2
9 )15+(x

2
9 )8+(x

2
9 )7+(x

2
9 )6+(x

2
9 )4+1.

g(x
2
9 ) = (m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))(m7(x

2
9 ))(m9(x

2
9 ))(m15(x

2
9 ))(m21(x

2
9

))(m27(x
2
9 ))(m45(x

2
9 ))=(x

2
9 )130+(x

2
9 )128+(x

2
9 )125+(x

2
9 )124+(x

2
9 )122

+(x
2
9 )121+(x

2
9 )120+(x

2
9 )115+(x

2
9 )113+(x

2
9 )110+(x

2
9 )109+(x

2
9 )107

+(x
2
9 )106+(x

2
9 )105+(x

2
9 )100+(x

2
9 )98+(x

2
9 )95+(x

2
9 )94+(x

2
9 )92

+(x
2
9 )91+(x

2
9 )90+(x

2
9 )85+(x

2
9 )83+(x

2
9 )80+(x

2
9 )79+(x

2
9 )77+(x

2
9 )76

+(x
2
9 )75+(x

2
9 )70+(x

2
9 )68+(x

2
9 )65+(x

2
9 )64+(x

2
9 )62+(x

2
9 )61+(x

2
9 )60

+(x
2
9 )55+(x

2
9 )53+(x

2
9 )50+(x

2
9 )49+(x

2
9 )47+(x

2
9 )46+(x

2
9 )45+(x

2
9 )40

+(x
2
9 )38+(x

2
9 )35+(x

2
9 )34+(x

2
9 )32+(x

2
9 )31+(x

2
9 )30+(x

2
9 )25

+(x
2
9 )23+(x

2
9 )20+(x

2
9 )19+(x

2
9 )17+(x

2
9 )16+(x

2
9 )15+(x

2
9 )10+(x

2
9 )8

+(x
2
9 )5+(x

2
9 )4+(x

2
9 )2+(x

2
9 )+1.

g(x
2
9 ) = m1(x

2
9 ))(m3(x

2
9 ))(m5(x

2
9 ))(m7(x

2
9 ))(m9(x

2
9 ))(m15(x

2
9 ))

(m21(x
2
9 ))(m27(x

2
9 ))(m45(x

2
9 ))(m63(x

2
9 ))

= (x
2
9 )134+(x

2
9 )133+ · · ·+(x

2
9 )2+(x

2
9 )+1.

Finally, errors like 3,4,7,10,13,22,31 and 67 are corrected.

From Example 2.1 and [3, Example 1], it follows that the code generated through F2[x; a
b j Z0]

corrects more errors and has better code rate than the code generated through F2[x;aZ0]. Now,
we are in position to develop a link between a primitive (n,n−r) binary BCH code Cn and a non-
primitive (b jn,b jn− r j) binary BCH code Cb jn, where r and r j are, respectively, the degrees of

their generating polynomials g(xa) and g(x
a

b j ). From Theorem 2, it follows that the generalized
polynomial g(x

a
b j ) in F2[x; a

b j Z0] divides (x
a

b j )b jn−1 in F2[x; a
b j Z0]. So, there is a non-primitive

BCH code Cb jn generated by g(x
a

b j ) in F2[x; a
b j Z0]b jn. By the same argument, as b jn divides

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 376 — #8 i
i

i
i

i
i

376 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

n j = 2b js−1, it follows that (x
a

b j )b jn−1 divides (x
a

b j )n j−1 in F2[x; a
b j Z0]. Therefore, ((x

a
b j )n j−

1)⊂ ((x
a

b j )b jn−1). Consequently, from third isomorphism theorem for rings, it follows that

F2[x; a
b j Z0]/((x

a
b j )n j −1)

((x
a

b j )b jn−1)/((x
a

b j )n j −1)
'

F2[x; a
b j Z0]

((x
a

b j )b jn−1)
' F2[x;aZ0]

((xa)n−1)
.

Thus, there are embeddings Cn ↪→ Cb jn ↪→ Cn j of codes, whereas Cn,Cb jn,Cn j are, respec-
tively, primitive BCH, non-primitive BCH and primitive BCH codes. Whereas the embeddings
Cn ↪→ Cb jn are defined as a(xa) = a0 + a1(xa) + · · ·+ an−1(xa)n−1 7→ a0 + a1(x

a
b j )b j

+ · · ·+
an−1(x

a
b j )b j(n−1) = a(x

a
b j ), where a(xa)∈Cn and a(x

a
b j )∈Cb jn. Also, if g(x

a
b j−1 ) is the generator

polynomial of a binary non-primitive BCH code C j−1
b j−1n in F2[x; a

b j−1 Z0]b j−1n, then g(x
a

b j ) is the
generator polynomial of a binary non-primitive BCH code Cb jn in the monoid ring F2[x; a

b j Z0]b jn.
Thus, a non-primitive BCH code Cb j−1n is embedded in a non-primitive BCH code Cb jn under

the monomorphism defined as a(x
a

b j−1 ) 7→ a(x
a

b j ).

With the above discussion it follows the following theorem.

Theorem 3. [3, Theorem 6] Let Cn be a primitive binary BCH code of length n= 2s−1 generated
by a polynomial g(xa) of degree r in F2[x;aZ0].

1. There exists a binary non-primitive BCH code Cb jn of length b jn generated by a polynomial
g(x

a
b j ) of degree b jr in F2[x; a

b j Z0].

2. The binary primitive BCH code Cn is embedded in a binary non-primitive BCH code Cb jn,
for each j ≥ 1.

3. The binary BCH codes of the sequence {Cb jn} j≥1 have the following embedding

Cbn ↪→Cb2n ↪→ ··· ↪→Cb jn ↪→ ···

Hence,

F2[x;aZ0] ⊂ F2[x; a
bZ0] ⊂ F2[x; a

b2 Z0] ⊂ ·· · F2[x; a
b j Z0]

F2[x;aZ0]
((xa)n−1) w

F2[x; a
bZ0]

((x
a
b )bn−1)

w
F2[x; a

b2 Z0]

((x
a

b2 )b2n−1)
w · · ·

F2[x; a
b2 Z0]

((x
a

b j )b jn−1)

∪ ∪ ∪ ·· · ∪
Cn ↪→ Cbn ↪→ Cb2n ↪→ ·· · Cb jn

and a non-primitive BCH code Cb j−1n is embedded in a non-primitive BCH code Cb jn under

the monomorphism defined by a(x
a

b j−1 ) 7→ a(x
a

b j ).

Remark 4. The polynomial g(x
a
b ) can be obtained from g(x

a
b j ) by substituting x

a
b j = y and

replacing y by yb j−1 = x
a
b .

Example 2.2. By [3, Example 2] and Example 2.1, it follows that the BCH codes with designed
distance d = 2,3, · · · ,9 have generator polynomials g(x

2
3 ), g(x

2
9 ) with the same minimum dis-

tance, error correction capability and code rate, where the differences are degree, data bits, code

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 377 — #9 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 377

length and check sum of the code C135 which is three times that of code C45 and nine times of the
code C15. Similarly, on letting (x

2
9 ) = y, that is x

2
3 = y3, we get

g(x
2
9 ) = (x

2
9 )106 +(x

2
9 )103 +(x

2
9 )102 +(x

2
9 )97 +(x

2
9 )93 +(x

2
9 )91 +(x

2
9 )90 +

(x
2
9 )61 +(x

2
9 )58 +(x

2
9 )57 +(x

2
9 )52 +(x

2
9 )48 +(x

2
9 )46 +(x

2
9 )45 +(x

2
9 )16 +

(x
2
9 )13 +(x

2
9 )12 +(x

2
9 )7 +(x

2
9 )3 +(x

2
9 )+1,

g(y) = (y)106 +(y)103 +(y)102 +(y)97 +(y)93 +(y)91 +(y)90 +(y)61 +(y)58 +

(y)57 +(y)52 +(y)48 +(y)46 +(y)45 +(y)16 +(y)13 +(y)12 +(y)7 +

(y)3 + y+1,

g(y3) = (y3)106 +(y3)103 +(y3)102 +(y3)97 +(y3)93 +(y3)91 +(y3)90 +(y3)61 +

(y3)58 +(y3)57 +(y3)52 +(y3)48 +(y3)46 +(y3)45 +(y3)16 +(y3)13 +

(y3)12 +(y3)7 +(y3)3 +(y3)+1,

g(x
2
3 ) = (x

2
3 )106 +(x

2
3 )103 +(x

2
3 )102 +(x

2
3 )97 +(x

2
3 )93 +(x

2
3 )91 +(x

2
3 )90 +(x

2
3 )61

+(x
2
3 )58 +(x

2
3 )57 +(x

2
3 )52 +(x

2
3 )48 +(x

2
3 )46 +(x

2
3 )45 +(x

2
3 )16 +(x

2
3 )13

+(x
2
3 )12 +(x

2
3 )7 +(x

2
3 )3 +(x

2
3 )+1

= (x
2
3 )16 +(x

2
3 )13 +(x

2
3 )12 +(x

2
3 )7 +(x

2
3 )3 +(x

2
3 )+1 ∈ F2[x;

2
3
Z0]45.

Similarly, for

g(x
2
9 ) = (x

2
9 )112 +(x

2
9 )108 +(x

2
9 )105 +(x

2
9 )102 +(x

2
9 )100 +(x

2
9 )99 +(x

2
9 )94 +

(x
2
9 )91 +(x

2
9 )90 +(x

2
9 )67 +(x

2
9 )63 +(x

2
9 )60 +(x

2
9 )57 +(x

2
9 )55 +

(x
2
9 )54 +(x

2
9 )49 +(x

2
9 )46 +(x

2
9 )45 +(x

2
9 )22 +(x

2
9 )18 +(x

2
9 )15 +

(x
2
9 )12 +(x

2
9 )10 +(x

2
9 )9 +(x

2
9 )4 +(x

2
9 )+1,

it follows that

g(x
2
3 ) = (x

2
3 )22 +(x

2
3 )18 +(x

2
3 )15 +(x

2
3 )12 +(x

2
3 )10 +(x

2
3 )9 +(x

2
3 )4 +(x

2
3 )+1,

which is the generating polynomial of a BCH code (45,23) having design distance d2 = 6,7. In
this way. we can obtain a non-primitive binary BCH code C15 from a non-primitive binary BCH
code C45. On writing the corresponding code vectors of the generating polynomials

g(x
2
3 ) = (x

2
3 )16 +(x

2
3 )13 +(x

2
3 )12 +(x

2
3 )7 +(x

2
3 )3 +(x

2
3 )+1

g(x
2
9 ) = (x

2
9 )106 +(x

2
9 )103 +(x

2
9 )102 +(x

2
9 )97 +(x

2
9 )93 +(x

2
9 )91 +

(x
2
9 )90 +(x

2
9 )61 +(x

2
9 )58 +(x

2
9 )57 +(x

2
9 )52 +(x

2
9 )48 +(x

2
9 )46 +

(x
2
9 )45 +(x

2
9 )16 +(x

2
9 )13 +(x

2
9 )12 +(x

2
9 )7 +(x

2
9 )3 +(x

2
9 )+1,

it follows that

v1 = (11010001000011001)

v2 = (11010001000011001000000000000000000000000000011010001

000011001000000000000000000000000000011010001000011001)

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 378 — #10 i
i

i
i

i
i

378 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

The binary bits of v1 are properly overlapped on the bits of v2, in fact, they are repeated
three times after a particular pattern. Hence, the generating matrix G2 of g(x

2
9 ) contains the

generating matrix G1 of g(x
2
3 ) such that G2 =⊕3

1G1.

3 ALGORITHM

In this section, we propose an algorithm to calculate a non-primitive BCH code of length b jn
using a primitive BCH code of length n, where the encoding and decoding of the code are carried
out in Matlab. The process of developing algorithm is divided into two major steps, i.e., encoding
and decoding of a non-primitive BCH code of length b jn.

3.1 Encoding of a non-primitive BCH code of length b jn.

In encoding, we first calculate a primitive polynomial of degree s by invoking Matlab’s built in
command “bchgenpoly”. After this operation, a non-primitive polynomial of degree bs is calcu-
lated. With the help of a root, say α ′, the elements of the Galois field GF(2bn) are calculated
such that (α ′)b jn = 1 and after we obtain the minimal polynomials of these elements. Finally, we
get a non-primitive polynomial with the help of these minimal polynomials. Thus, these design
distances are calculated through which the number of errors that can be corrected in each BCH
code are determined. Some methods are developed in order to achieve a specified result. In Table
3, we show a list of these methods and its description.

Table 3: Encoding modulation description.

Module Input Output

a Elements of Galois Field b∗n α ′[i]
b Bchgenpoly n,k g[i]
c Cyclotomic cosets α ′[i], b, k c[i]
d Design distance c[i] d
e error d t

The steps of the algorithm are explained as follows:

a. Elements of Galois field (alpha array) α ′[i]).

This step calculates all the elements of the Galois field GF(2bn) using a root, say α ′, of a non-
primitive polynomial of degree bs such that (α ′)bn = 1. The element α ′ is called of alpha array
and denoted by α ′[i]. Now, denote the index array by A[index]. For a given input b∗n, the non-
primitive polynomial of degree bs gives the first element of the array α ′[i]. By increasing its
power, each element of the array α ′[i] is calculated in outer loop. Then in nested while loop their
corresponding values are determined in such a way that if the value of any element in the array
exceed bs, we take the remainder rem(index,bs) (step 9 of the algorithm). The loop breaks when
the condition for identity is met.

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 379 — #11 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 379

Algorithm 1:

1 begin
2 INPUT b and n
3 bn← b∗n
4 Initialize A[index] from 1 to bn−1
5 Initialize α ′[i]↼ 0
6 Initialize index ↼ 1
7 WHILE index 6= 0
8 mark A[index]↼ 0
9 Initialize v ↼ index

10 Calculate next candidate, pi, by rem(index,bs)
11 α ′[i]↼ v
12 WHILE current position of A[index] = 0
13 IF current position < A[index] size
14 i++
15 ELSEIF
16 i← 0
17 BREAK
18 ENDIF
19 ENDWHILE
20 ENDWHILE

21 end

b. BCH generator polynomial (g[i]).

The Matlab builds a function and its complete documentation is found under
http://www.mathworks.com/help/comm/ref/bchgenpoly.html. In this module, we get the
generator polynomial of primitive BCH code of length n.

1 INPUT n and k

2 OUTPUT g[i]

c. Cyclotomic cosets (c[i]).

Given α ′[i], dimension of code k and positive integer b, cyclotomic cosets c[i] are calculated.
Length of c[i] is initialized to at max b ∗ k, in short all elements should not exceed the max
length. Loop start from 2 to max length and calculate unique values in given α ′[i]. The process
stops when we get sum of two elements = 2. Once cyclotomic cosets are calculated, we can
calculate the minimal polynomials for BCH codes.

d. Non-primitive generating polynomial g′[i].

Given primitive polynomial p[i] and b. First find the highest degree of p[i] i.e., s and initial
degree of non-primitive polynomial p′[i] i.e., bs. Initialize each element of p′[i] of length bs to 0.
Iterate loop from 2 to bs in order to initialize coefficient array to 1. Finally, iterate each element
if coeft array and modify the value if p′[i] at position i to the value of coeft array at i. Finally
insert 1 at position 0 of p′[i], i.e., when its first element becomes 0. The output of this module

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 380 — #12 i
i

i
i

i
i

380 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

Algorithm 2:

1 begin
2 INPUT α ′[i], b, k
3 Initialize cal coset ↼ 0
4 Initialize len cal coset ↼ 0
5 Initialize code length ↼ b∗ k
6 Initialize len coset ↼ length of c[i]
7 Initialize code ↼ b∗ k
8 FOR i ↼ 2 to len coset
9 cal coset ↼ c[i] at position i

10 IF i 6= 2 THEN
11 code length ↼ bk cal coset
12 ENDIF
13 PRINT c[i]
14 END FOR

15 end

play an integral role for calculating non-primitive BCH generating polynomial. It is denoted by
g′ in our algorithm. We are interested in rows of obtained matrix. Using the matrix we obtained,
the code for non-primitive generating polynomial of length b. Finally these values are printed out
and saved in file for further usage.

Algorithm 3:

1 begin
2 INPUT p[i], b
3 Initialize len ↼ length of p[i]
4 Initialize size array ↼ len × b
5 Initialize p′[i] of length size array i.e. p′[i]↼ 0
6 Initialize index ↼ 1
7 Initialize len coef array ↼ 0
8 FOR i taking values from 2 to len
9 IF p′[i] at i 6= 0 THEN

10 Initialize coef array ↼ b∗ (i−1)
11 increment index
12 ENDIF
13 ENDFOR
14 len coef array ↼ length of coef array
15 FOR j taking values from 1 to len coef array
16 g′(i) at position j of coef array ↼ 1
17 ENDFOR
18 g′[i]↼ 1 to p′[i]
19 PRINT g′[i]

20 end

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 381 — #13 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 381

e. Designed distance (d).

Here design distance is calculated from g′[i]. The length of coset array cl is determined and then
iterate index from 2 to cl, calculate next index ni by increment current index. If ni≤ cl, then next
element of coset is calculated to the value of coset array at position of next index. Otherwise the
bn is assigned to next coset. The whole process iterates to lencoset coset and finally stops at the
last coset. Design distance d is calculated from the last value of coset array at position 1.

Algorithm 4:

1 begin
2 INPUT c[i]
3 Initialize lencoset ↼ cl
4 Initialize ni ↼ 0
5 Initialize next coset ↼ 0
6 FOR index from 2 to cl
7 ni ↼ increment index
8 IF ni ≤ cl THEN
9 next coset ↼ c[i] at position ni

10 ELSEIF
11 next coset ↼ bn
12 ENDIF
13 ENDFOR
14 d ↼ next coset at position 1.
15 end

f. Error correction capability.

For given designed distance d, the error correction capability of a code t is calculated.

Algorithm 5:

1 begin
2 INPUT d.
3 error t ↼ (d−1)/2.
4 end

3.2 Error correction in received polynomial (decoding)

In decoding step for a received polynomial, we first calculate the syndrome matrix S[i]. Then the
D−matrix is calculated that should be invertible. After this error locator polynomial is determined
whose roots give the exact position of errors in the received polynomial. Finally the received
polynomial is corrected. To find the error vector and obtain the corrected codeword following
scheme is used. Table 4 shows list of the following steps for error correction.

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 382 — #14 i
i

i
i

i
i

382 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

Table 4: Encoding modulation description.

Module Input Output

a Syndrome Matrix d, bn, bk, α ′, r[i] S′[i]
b Calculate D matrix t, S′[i] D matrix
c Is D invertible t, D matrix | D |6= 0
d error locator poly t, D matrix,S′[i] f [i]
e error position f [i] e[i]
f error values t, S[i], D matrix, e[i], bn, pm[i] ev[i]
h Correct recieved t, bn, e[i], ev[i], r[i], α ′ v[i]

polynomial

a. Syndrome matrix S(′[i]).

Given design distance d, bn, message length bk and received polynomial r[i], syndrome matrix
S′[i] can be calculated. The length of S′[i] is initialize to the difference of bn and bk, i.e., bn−bk.
Furthermore, S′[i] is initialized by element of Galois field at position i i.e. GF [i]. Nested loop are
used to calculate S′[i]. Upper loop is limited to the length of bn+d−2, where S′[i] equalizes to
power of α ′ and in nested loop S′[i] equalize to power of S′[i] and the iterator. Once the values of
S′[i] are filled with the above values of S′[i], it follows that these S′[i] can be calculated as product
of r[i] and (S′[i])t .

Algorithm 6:

1 begin
2 INPUT d, bn, bk, α and r[i]
3 Initialize lenSyndrome ↼ bn−bk
4 Initialize S′[i]↼ GF [i] of len Syndrome
5 Initialize valueSynd ↼ 0
6 Initialize valueSynd ↼ GF [i] length bn
7 Initialize loopLimit ↼ bn+d−2
8 FOR i ↼ bn to loop limit
9 valueSynd ↼ α i

10 FOR j ↼ 1 to bn
11 evalSynd ↼ valueSynd powers j
12 ENDFOR
13 S′[i]↼ received poly ∗ transpose of evalSynd
14 ENDFOR
15 PRINT S′[i]
16 end

b. D matrix (D[i]).

Given error t and S′[i], D matrix is calculated and then double loops operation on syndrome
matrix is carried out and suitable values from syndrome matrix is scanned out. The process is as

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 383 — #15 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 383

follows: calculate GF [i] of length t and D-matrix is initialized to that value. D[i] in nested loop
for loops. Both loops iterates from 1 to t. D[i] values are S′[i] values at position i of sum of loops
iterators to 1.

Algorithm 7:

1 begin
2 INPUT t, S′[i]
3 Calculate GF [i] of length t
4 Initialize D matrix ↼ GF [i]
5 FOR index i1 taking from 1 to t
6 FOR index i2 taking from 1 to t
7 D matrix ↼ S′[i] at position i1+ i2−1
8 ENDFOR
9 ENDFOR

10 end

c. Is D invertible.

This module check if D[i] is invertible. If D[i] is invertible, then the algorithm works, otherwise
error t is decremented and D matrix is again calculated. These operations are carried out till error
t becomes 0. If t becomes 0, then algorithm will exit i.e panic condition occurs as in step 10.

Algorithm 8:

1 begin
2 INPUT t and D[i]
3 IF D[i] is invertible THEN
4 continue algo // goto step 5.
5 ELSEIF
6 decrement t;
7 IF t equals 0
8 goto STEP 3
9 ENDIF

10 ENDIF
11 // Panic Condition
12 IF t equals 0
13 Print ERROR cannot be corrected.
14 EXIT algo
15 ENDIF
16 end

d. Error locator polynomial (f[i]).

Given input t, D[i] and S′[i], error locator polynomial f [i] is calculated. First, initialize product
matrix pm[i] and f [i] to α ′t [i]. Then, iterate the loop from 1 to t, pm[i] is filled with the value of
S′[i] at t + i. After the loops ends, the value of (S′[i] ∗ pm[i])−1 get equals to temporary matrix

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 384 — #16 i
i

i
i

i
i

384 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

T ′′[i]. Once the temporary matrix T ′′[i] is achieved f [i] is taken as the transpose of that temporary
matrix (T ′′[i])t discuss in step 10.

Algorithm 9:

1 begin
2 INPUT t, D[i] and S[i]
3 Create α ′t [i]
4 Initialize pm[i]↼ α ′t [i]
5 Initialize f [i]↼ α ′t [i]
6 Initialize temporary matrix T ′′[i] of size t ↼ 0
7 FOR index i taking values from 1 to t
8 pm[i]↼ S[i] at position t + i
9 ENDFOR

10 T ′′[i]↼ (S[i])−1 ∗ pm[i]
11 f [i]↼ (T ′′[i])t

12 f [t +1]↼ 1 // coefficient of f [t +1] = 1
13 end

e. Error position matrix (e[i]).

Based on f [i] we can determine error position. First, the roots of f [i] is calculated and then we
take its inverse. The values we obtain are in matrix form and these manifest error position.

Algorithm 10:

1 begin
2 INPUT f [i]
3 Initialize error pos matrix e[i]↼ 0
4 Initialize root matrix ↼ 0
5 root matrix ↼ roots of f [i]
6 e[i]↼ inverse of roots of f [i]
7 PRINT e[i]
8 end

f. Error values (ev[i]).

Once error position e[i] is determined we can easily calculate their respective values. The nested
for loops are used to determine error values. Both of the loops iterate from 1 to t, in the first loop
values from D matrix can be taken while in the next loop value of product matrix pm[i] can be
taken along with S′[i]. Finally, ev[i] get equated to (D matrix∗pm[i])−1 as discusses on line 9.

g. Correct received polynomial r[i].

Once we have calculated error positions e[i] and error values ev[i] the received polynomial r[i]
can be corrected. Here input parameters are e[i],ev[i], r[i] and bn. First estimated codeword de-
noted by est code is calculated using various operations i.e., taking loops to t,bn and power of

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 385 — #17 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 385

Algorithm 11:

1 begin
2 INPUT t, S[i], D[i], e[i], bn and pm[i]
3 Initialize ev[i]↼ 0
4 FOR 1≤ i1≤ t
5 FOR 1≤ i2≤ t
6 D[i] at i1 and i2 ↼ e[i] at i2∗ (i1+bn−1)
7 ENDFOR
8 pm[i] at i1 ↼ S[i1]
9 ENDFOR

10 ev[i]↼ (D matrix ∗pm[i])−1

11 PRINT ev[i]
12 end

Galois field. The received polynomial is corrected by subtracting error polynomial and we get
the corrected codeword v[i].

Algorithm 12:

1 begin
2 INPUT t, bn, e[i], ev[i], r[i] and α ′

3 calculate GF [i] of length bn.
4 Initialize est error ↼ GF [i]
5 Initialize est code ↼ GF [i]
6 Initialize alpha val ↼ 0
7 FOR 1≤ i≤ t
8 FOR 1≤ j ≤ bn
9 alpha val ↼ (α ′) j−1

10 IF alpha val = element e[i] at i THEN
11 est error position j ↼ est error at position j+ ev[i] at i
12 ENDIF
13 ENDFOR
14 est code ↼ r[i]+ est error
15 PRINT est code
16 elements of pm[i] at i1 ↼ S′[i] elements at i1
17 ENDFOR
18 ev[i]↼ D matrix ∗pm[i]
19 PRINT ev[i]
20 end

Example 3.1. For the code of length 45 simulation is carried out as follows: in this case b = 3
and n = 15. Using n = 15 and k = 11, Matlab’s build in function genpoly is invoked in order to
find primitive polynomial, i.e., p(i) = x4 + x+ 1, as explain in Table 3. With b = 3 and p(i) =
x4 + x + 1, non primitive poly function is invoked, as described in Table 3 step 4, here non-
primitive polynomial named as p′(i) is obtained. Output for p′(i) is x12 + x9 + 1. Cyclotomic
cosets, i.e., coset array values are also calculated. First elements of Galois field in step 1 of

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 386 — #18 i
i

i
i

i
i

386 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

Table 1, is invoked to find the power of alpha till α45 = 1. With coset array in hand, the designed
distance d can be calculated, which is the first element of next coset array. Last but not the least
error t is calculated against the given designed distance d. Code rate R is also calculated against
each k1 and bn but is not mentioned in previous section. The output are as follows: Cyclotomic
cosets for (45,33) = [1 2 4 8 16 32 19 38 31 17 34 23], t1 = 1 and R1 = (0.73333). Cyclotomic
cosets for (45,29) = [3 6 12 24], t1 = 2 and R1 = (0.64444). Cyclotomic cosets for (45,23) = [5
10 20 40 35 25], t1 = 3 and R1 =(0.51111). Cyclotomic cosets for (45,11)= [7 14 28 11 22 44 43
41 37 29 13 26], t1 = 4 and R1 = (0.24444). Cyclotomic cosets for (45,5) = [15 30], t1 = 10 and
R1 = (0.11111). Now comes error correction in received polynomial. In this the code (45,29) is
taken under consideration, with designed distance d1 = 5 and t1 = 2. Let the received polynomial
be

x44 + x16 + x13 + x12 + x11 + x7 + x3 + x+1.

With the given values d1, k1, and received polynomial, syndrome matrix is calculated. The output
for syndromes are S1 = α2, S2 = α4, S3 = α30, S4 = α8. Next, we arrange syndrome values
in linear equation form that is Ax = B. Where A = [S1, S2; S2, S3] and B = [S3, S4]. Matrix
A is named as t matrix of t × t dimension. Thus, we find the whether the t matrix is singular
or not. If the determinant of t matrix is nonzero then error locator polynomial is calculated.
Next error position is calculated from sigma matrix which is obtained from the coefficients of
error locator polynomial. For the given values, error positions are 44 and 11. Hence the error
polynomial is x44+x11. On subtracting error polynomial from received polynomial the following
code polynomial

x16 + x13 + x12 + x7 + x3 + x+1

is obtained. All of the above equations are obtained by using Matlab symbolic toolbox.

With the help of the above discussed algorithm many examples on non-primitive BCH codes
of length bn, b2n, b3n are constructed corresponding to primitive BCH code of length n. The
parameters for all binary non-primitive BCH codes of length bn, b2n, b3n, where n≤ 26−1 and
b is either 3 or 7 are given in Table 5.

Table 5 manifests the error and code rate values against some selected codes which we have
obtained after simulating our algorithm. These codes are of length bn, b2n and b3n, where n ≤
26−1, and b = 3, 7. k1,k2 and k3 are dimensions of the codes Cbn,Cb2n and Cb3n, respectively.

Interleaved Codes

From Table 5, it is observed that corresponding to a primitive (n,k) code there are (bn,bk),
(b2n,b2k2), (b3n, b3k) codes with same error correction capability and code rate. These codes
are found to be interleaved codes (Interleaving is a periodic and reversible reordering of codes
of L transmitted bits) of depth b, b2 and b3. Hence along with random error correction capability
these codes can correct burst of error of length b, b2 and b3, respectively. The term burst of error
means that two or more bits in the received word has changed from 1 to 0 or from 0 to 1. The
length of the burst is measured from the first corrupted bit to the last corrupted bit. Similarly, for
the code (bn,bk) the codes (b2n,b2k) and (b3n,b3k) are interleaved codes of depth b2 and b3,

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 387 — #19 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 387

Table 5: Parameters of binary non-primitive BCH codes.

n bn k1 t1 R1 b2n k2 t2 R2 b3n k3 t3 R3

15 45 33 1 0.733 135 99 1 0.733 405 297 1 0.733
29 2 0.644 87 2 0.644 261 2 0.644
23 3 0.511 69 3 0.511 207 3 0.511
11 4 0.244 33 4 0.244 99 4 0.244
7 7 0.155 29 7 0.214 87 7 0.214
5 10 0.111 23 10 0.170 69 10 0.170
1 22 0.022 11 13 0.081 33 13 0.081

7 22 0.051 29 22 0.071
5 31 0.037 23 31 0.056
1 67 0.007 11 40 0.027

7 67 0.017
5 94 0.012
1 202 0.002

63 189 171 1 0.904 567 513 1 0.904 1701 1539 1 0.904
165 2 0.873 495 2 0.873 1485 2 0.873
147 3 0.777 441 3 0.777 1323 3 0.777
129 4 0.682 387 4 0.682 1161 4 0.682
123 5 0.650 381 5 0.672 1143 5 0.671
105 6 0.555 327 6 0.576 981 6 0.576
87 7 0.460 273 7 0.481 819 7 0.481
81 10 0.428 255 10 0.449 765 10 0.449

63 189 75 11 0.3968 567 237 11 0.4179 1701 711 11 0.417
57 13 0.3015 183 13 0.3227 549 13 0.322
54 15 0.2857 177 15 0.3121 543 15 0.319
36 16 0.1904 123 16 0.2169 381 16 0.224
30 19 0.1587 105 19 0.1851 327 19 0.192
24 22 0.1269 87 22 0.1534 273 22 0.160
18 31 0.0952 81 31 0.1428 255 31 0.149
16 34 0.0846 75 34 0.1322 237 34 0.1393
10 40 0.0529 57 40 0.1005 183 40 0.1075
7 46 0.0370 54 46 0.0952 177 46 0.1040
1 94 0.0053 36 49 0.0634 123 49 0.0723

30 58 0.0529 105 58 0.0617
24 67 0.0423 87 67 0.0511
18 94 0.0317 81 94 0.0476
16 103 0.0282 75 103 0.0440
10 121 0.0176 57 121 0.0335
7 139 0.0123 54 139 0.0317
1 283 0.0017 36 148 0.0211

30 175 0.0176
10 364 0.0058
1 850 0.0005

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 388 — #20 i
i

i
i

i
i

388 SEQUENCES OF PRIMITIVE AND NON-PRIMITIVE BCH CODES

respectively. The code (49,28) is interleaved code of depth 7, which is formed by interleaving the
following 7 codewords from (7,4) code that is (0000000), (1101000), (0000000), (0000000),
(0000000), (0000000) and (0000000). on writing them column by column it gives

v1 = (01000000100000000000001000000000000000000000000000) ∈C49.

In a similar way, codeword of (343,196) and (2401,1372) are obtained by writing column by
column 7 codeword of C49 and C343. Therefore, for decoding a received polynomial in C343 one
can easily reverse the process and correct errors in the codeword of either C49 or C7.

ACKNOWLEDMENT

Acknowledgment to FAPESP by financial support 2013/25977-7. The authors would like to thank
the anonymous reviewers for their intuitive commentary that signicantly improved the worth of
this work.

RESUMO. Neste trabalho, apresentamos um método que estabelece como uma sequência
de códigos BCH não primitivos pode ser obtida através de um dado código BCH primitivo.
Para isso, utilizamos uma técnica de construção diferente da técnica rotineira de códigos
BCH e usamos a estrutura de anéis monoidais em vez de anéis de polinômios. Conse-
quentemente, mostramos que existe uma sequência {Cb jn}1≤ j≤m, onde b jn é o compri-
mento do código Cb jn, de códigos BCH binários não primitivos em vez de um dado código
binário BCH Cn de comprimento n. Algoritmos simulados via Mathlab para codificação e
decodificação para este tipo de códigos são introduzidos. O algoritmo via o Matlab fornece
rotinas para a construção de um código BCH primitivo, mas impõe várias restrições, como
por exemplo, o grau s de um polinômio irredutı́vel primitivo deve ser menor que 16. Este
trabalho trata-se de polinômios não-primitivos irredutı́veis com grau bs, que são maiores do
que 16.

Palavras-chave: Anel monoidal, códigos BCH, polinômio primitivo, polinômio
não-primitivo.

REFERENCES

[1] A.A. Andrade & P. Jr. Linear codes over finite rings. TEMA – Trends in Applied and Computational
Mathematics, 6(2) (2005), 207–217.

[2] A.A. Andrade, T. Shah & A. Khan. A note on linear codes over semigroup rings. TEMA – Trends in
Applied and Computational Mathematics, 12(2) (2011), 79–89.

[3] A.S. Ansari & T. Shah. An association between primitive and non-primitive BCH codes using monoid
rings. EURASIP - Journal on Wireless Communications and Networking, 38 (2016).

[4] J. Cazaran, A.V. Kelarev, S.J. Quinn & D. Vertigan. An algorithm for computing the minimum dis-
tances of extensions of BCH codes embedded in semigroup rings. Semigroup Forum, 73(3) (2006),
317–329.

Tend. Mat. Apl. Comput., 19, N. 2 (2018)



i
i

“A12-1078-5889-1-LE” — 2018/8/15 — 11:02 — page 389 — #21 i
i

i
i

i
i

ANSARI, SHAH, RAHMAN and ANDRADE 389

[5] A.V. Kelarev. “Ring constructions and applications”. World Scientific Publishing Co. Inc., New York
(2002).

[6] A.V. Kelarev & P. Solé. Error-correcting codes as ideals in group rings. Contemporary Mathematics,
273 (2001), 11–18.

[7] S. Lin & J. D. J. Costello. “Error control coding: fundamentals and applications”. Prentice Hall
Professional Technical Reference, New York (1994).

[8] S.R. Nagpaul & S.K. Jain. “Topics in applied abstract algebra”, The Brooks/Cole Series in Advanced
Mathematics. New York (2005).

[9] V.S. Pless, W.C. Huffman & R.A. Brualdi. “Handbook of coding theory”. Elsevier, New York (1998).

[10] A. Poli & L. Huguet. “Error-correcting codes: theory and applications”. Prentice-Hall, New York
(1992).

[11] T. Shah, Amanullah & A.A. de Andrade. A decoding procedure which improves code rate and error
corrections. Journal of Advanced Research in Applied Mathematics, 4(4) (2012), 37–50.

[12] T. Shah, Amanullah & A.A. de Andrade. A method for improving the code rate and error correction
capability of a cyclic code. Computational and Applied Mathematics, 32(2) (2013), 261–274.

[13] T. Shah & A.A. de Andrade. Cyclic codes through B[X ], B[X ; 1
kp Z0] and B[X ; 1

pk Z0]: a comparison.
Journal of Algebra and its Applications, 11(4) (2012), 1250078, 19.

[14] T. Shah & A.A. de Andrade. Cyclic codes through B[X ; a
bZ0], with a

b ∈ Q+ and b = a + 1, and
encoding. Discrete Mathematics, Algorithms and Applications, 4(4) (2012), 1250059, 14.

[15] T. Shah, A. Khan & A.A. Andrade. Encoding through generalized polynomial codes. Comp. Appl.
Math., 30(2) (2011), 349–366.

[16] T. Shah, M. Khan & A.A. de Andrade. A decoding method of an n length binary BCH code through
(n+1)n length binary cyclic code. Anais da Academia Brasileira de Ciências, 85(3) (2013), 863–872.

[17] T. Shah & A. Shaheen. Cyclic codes as ideals in F2[x;aN0]n, F2[x]an, and F2[x; 1
b N0]abn : a linkage.

U.P.B. Sci. Bull., Series A, 78(3) (2016), 205–220.

Tend. Mat. Apl. Comput., 19, N. 2 (2018)