##### Mathematical Sciences
Original research

# Construction and decoding of BCH codes over chain of commutative rings

Tariq Shah1, Attiq Qamar1 and Antonio Aparecido de Andrade2*

Author Affiliations

1 Department of Mathematics, Quaid-i-Azam University, Islamabad, 45320, Pakistan

2 Department of Mathematics, São Paulo State University, São José do Rio Preto, São Paulo, 15054-000, Brazil

For all author emails, please log on.

Mathematical Sciences 2012, 6:51 doi:10.1186/2251-7456-6-51

The electronic version of this article is the complete one and can be found online at: http://www.iaumath.com/content/6/1/51

 Received: 22 May 2012 Accepted: 4 September 2012 Published: 12 October 2012

© 2012 Shah et al.; licensee Springer.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License( http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

### Abstract

In this paper, we present a new construction and decoding of BCH codes over certain rings. Thus, for a nonnegative integer t, let be a chain of unitary commutative rings, where each is constructed by the direct product of appropriate Galois rings, and its projection to the fields is (another chain of unitary commutative rings), where each is made by the direct product of corresponding residue fields of given Galois rings. Also, and are the groups of units of and , respectively. This correspondence presents a construction technique of generator polynomials of the sequence of Bose, Chaudhuri, and Hocquenghem (BCH) codes possessing entries from and for each i, where 0 ≤ i t. By the construction of BCH codes, we are confined to get the best code rate and error correction capability; however, the proposed contribution offers a choice to opt a worthy BCH code concerning code rate and error correction capability. In the second phase, we extend the modified Berlekamp-Massey algorithm for the above chains of unitary commutative local rings in such a way that the error will be corrected of the sequences of codewords from the sequences of BCH codes at once. This process is not much different than the original one, but it deals a sequence of codewords from the sequence of codes over the chain of Galois rings.

##### Keywords:
Units of a Galois ring; BCH code; McCoy rank; Direct product of Galois rings; 11T71; 94A15; 14G50

### Introduction

Linear codes over finite rings have been hashed out in a series of papers introduced by Blake [1,2], Spiegel [3,4], and Forney [5]. Recently, a keen interest about the structure of the multiplicative group of units of certain finite local commutative rings has been developed in coding theory owing to its wondrous application, especially in the construction of Bose, Chaudhuri, and Hocquenghem (BCH) codes. Using the multiplicative group of unit elements of a Galois ring extension of , Shankar [6] has constructed BCH codes over . However, Andrade and Palazzo [7] have further extended this construction of BCH codes over finite commutative rings with identity. Both construction techniques of [6] and [7] have been addressed from the approach of specifying a cyclic subgroup of the group of units of an extension ring of finite commutative rings. The complexity of this study is to get the factorization of xn − 1 over the group of units of the appropriate extension ring of the given local ring and then construct the generator polynomial for BCH codes.

Let be a finite commutative ring with identity. The ring , with , being a free -module that preserves the concept of linear independence among its elements, is similar to a vector space over a field. Though it has the constraint that an r × r submatrix of r × n generator matrix M over is non-singular or, equivalently, has a determinant unit in , the existence of non-singular matrices having no obligatory unit elements is, in fact, the primary obstacle in working over a local ring instead of a field. The notion of elementary row operations in a matrix, and its consequences, also carries over with the understanding that only multiplication of a row by a unit element in is allowed, which is in contrast to the multiplication by any nonzero element in the case of a field. The structure of the multiplicative group of units of is the main motivation to calculate the McCoy rank [8] of a matrix M, that is, the largest integer r such that the r × r submatrix of M has a determinant unit in .

Andrade and Palazzo [9] describe a construction technique of a matrix

based on the vector η = (α1α2,⋯,αn), where αi, for 1 ≤ i n, are distinct units in the unitary local ring such that 1−αj, for 1 ≤ j l, are units. By this, one can obtain the McCoy rank of the matrix M, whereas the findings of these types of units are linked with the multiplicative group of units of the ring .

For h = bt, where b is a prime and t is a positive integer, there exist corresponding Galois ring extensions , where 0 ≤ i t and hi = bi (respectively, their residue fields , where 0 ≤ i t and hi = bi) of unitary local ring with pm elements (respectively, p elements of residue field ). For each i, where 0 ≤ i t, it follows that has one and only one cyclic subgroup of order ni (divides ) relatively prime to p (it extends Theorem 2 of [6]). Furthermore, if generates a cyclic subgroup of order ni in , then βi generates a cyclic subgroup of order nidi in , where di is an integer greater than or equal to 1, and generates the cyclic subgroup in for each i (an extension of Lemma 1 of [6]). Consequently, by extending the given algorithm of [6] for constructing a BCH type of codes with symbols from the local ring for each member in chains of Galois rings and residue fields, respectively, there are two situations: hi = bi for i = 2 or hi = bi for i ≥ 2. By these motivations, in this paper, for any , let be a chain of unitary commutative rings, whereas for each i such that 0 ≤ i t, it follows that is a direct product of Galois rings, i.e.,

whereas is the chain of Galois rings. Corresponding to the chain , there is the chain of rings constituted through the direct product of their residue fields, i.e.,

whereas is the chain of corresponding residue fields. Also, and for each i, where 0 ≤ i t, are multiplicative groups of units of and , respectively.

In this work, we present a construction technique of generator polynomials of BCH codes having entries from and for each i, where 0 ≤ i t. Thus, this paper is organized as follows: the ‘Preliminaries’ section 2 contains a brief introduction of the basics of polynomial rings and some results from [7]. In the ‘Sequences of BCH codes’ section, we describe the construction technique of the sequence of BCH codes over the chain of commutative rings constructed by the direct product of appropriate chains of Galois rings. In the ‘Decoding procedure of BCH codes’ section, we present the decoding procedure for the constructed BCH codes. The ‘Conclusions’ section concludes the whole discussion.

### Methods

#### Preliminaries

Assume that (A,M) is a finite unitary local commutative ring with residue field , where p is a prime integer and m is a positive integer. The natural projection is defined by , where for i = 0,⋯,n. Thus, the natural ring morphism is simply the restriction of Π to the constant polynomials. In the following, we recall some definitions and results from [8] for the sake of quick reference.

#### Definition 1

Let a(x) be a polynomial in A[x]. We say that

1. a(x) is a unit if there exists a polynomial b(x) ∈ A[x] such that a(x)b(x) = 1.

2. a(x) ≠ 0 is a zero divisor if there exists a polynomial b(x) ∈ A[x]∖{0} such that a(x)b(x) = 0.

3. a(x) is regular if a(x) is not a zero divisor.

4. a(x) is irreducible if a(x) is not a unit, and if a(x) = a1(x)a2(x), then either a1(x) is a unit or a2(x) is a unit.

#### Theorem 2

(Theorem XIII.2 of [ [8]]) Let (AM) be a local ring and. The following assertions are equivalent:

1.a(x) is regular.

2.a1,a2,⋯,an〉 = A.

3.aiis a unit for some i, for 0 ≤ i n.

4.Π(a(x)) ≠ 0.

#### Theorem 3

(Theorem XV.1 of [ [8]]) Let (AM) be a local ring anda(x) be a regular polynomial inA[x] such thatΠ(a(x)) has a simple (i.e., non-multiple) zero in . Then, a(x) has one and only one zeroα with.

#### Theorem 4

(Theorem XIII.7 of [ [8]]) Let (AM) be a local ring anda(x) be a regular polynomial inA[x] such thatΠ(a(x)) is irreducible in. Then, a(x) is irreducible inA[x].

Let Aj be a finite local ring with characteristic pj, for each j such that 1 ≤ j s. Let be the residue fields of local rings Rj = Aj[x]/〈fj(x) 〉, where fj(x) is a basic irreducible polynomial over Aj of degree h, for each j such that 1 ≤ j s.

#### Theorem 5

(Theorem 3.3 of [ [7]]) Let, where eachRj is a local finite commutative (Galois) ring. Then, .

The following theorem indicates the condition under which xs − 1 can be factored over :

#### Theorem 6

(Theorem 3.4 of [ [7]]) The polynomialsxs − 1 can be factored over the multiplicative groupasxs − 1 = (xα)(xα2) ⋯ (xαs) if and only ifhas ordersin, wheregcd(spj) = 1 andα corresponds to β = (β1β2,⋯,βs), forj = 1,2,3,⋯,s.

#### Theorem 7

(Theorem 3.5 of [ [7]]) For any positive integer l, let Ml(x) be the minimal polynomial of αl over, where α generates. Then, , where Bl are all distinct elements of the sequence.

#### Theorem 8

(Theorem 2.5 of [ [7]]) Let g(x) be the generator polynomial of BCH code over A with length n = s such thatare the roots of g(x) in Hα,n, where α has order n, then the minimum Hamming distance of the code is greater than the largest number of consecutive integers modulo n in E = {e1,e2,e3,⋯,enk}.

#### Sequences of BCH codes

Let (A,M) be a unitary finite local commutative ring with residue field having pm elements. The natural projection Π : A[x] → K[x] is defined by , where for i = 0,1,⋯,n. Thus, the natural ring morphism is simply the restriction of Π to the constant polynomials. Now, if f(x) ∈ A[x] is a basic irreducible polynomial with degree h = bt, where b is a prime and t is a positive integer, then is the Galois ring extension of A and is the residue field of , where is the maximal ideal of .

For the construction of a chain of Galois rings, the following lemma is of central importance:

#### Lemma 9

(Lemma VII of [ [8]]) Every subring of GR(pkh) is a Galois ring of the form GR(pkh), where hdivides h. Conversely, if hdivides h, then GR(pkh) contains a unique copy of GR(pkh).

Since 1,b,b2,⋯,bt−1,bt are divisors of h, so take h0 = 1,h1 = b,h2 = b2,⋯,ht = bt = h, and by Lemma 9, it follows that there exist basic irreducible polynomials f1(x),f2(x),⋯,ft(x)∈A[x] with degrees h1,h2,⋯,ht, respectively, such that we can constitute the Galois subrings , for each i, where 1 ≤ i t, of with the maximal ideals , for 1 ≤ i t. Thus, the residue fields of each becomes

As hi divides hi + 1 for all 0 ≤ i t, so by Lemma 9, it follows that there is a chain

of Galois rings with corresponding chain of residue fields

If for 0 ≤ i t, then we obtain a chain of another unitary commutative rings, i.e.,

with a corresponding chain of rings

where for 0 ≤ i t.

Let and be the multiplicative group of units of and , respectively, for 0 ≤ i t. The next corollary of Theorem XVIII.1 of [8] plays a fundamental role in the decomposition of the polynomial into linear factors over the rings . This theorem asserts that for each element , there exist unique elements , for 0 ≤ i t, such that αi = (βiβi,⋯,βi) are ordered r-tuples.

#### Corollary 10

Let, for 0 ≤ i t, where eachis a local finite commutative ring. Then, .

The following theorem indicates the condition under which can be factored over , for 0 ≤ i t:

#### Theorem 11

For 0 ≤ i t, the polynomialscan be factored over the multiplicative groupsasif and only ifhas orderin, where gcd(ni,p) = 1 and αi = (βi,βi,⋯,βi).

#### Proof

Suppose that the polynomials can be factored over as . Then, can be factored over as , for 0 ≤ i t. Now, it follows from the extension of Theorem 3 of [6] that has order ni in , for 0 ≤ i t. Conversely, suppose that has order ni in , for 0 ≤ i t. Again, it follows from the extension of Theorem 3 of [6] that the polynomials can be factored over as , for 0 ≤ i t. Since αi = (βi,βi,⋯,βi), for 0 ≤ i t, it follows that over , for 0 ≤ i t. □

#### Corollary 12

(Theorem 3.4 of [ [7]]) The polynomials xn − 1 can be factored over the multiplicative groupas xn − 1 = (xα)(xα2) ⋯ (xαn) if and only ifhas order n in, where gcd(n,p) = 1.

Let denote the cyclic subgroup of generated by αi, for each i, where 0 ≤ i t, i.e., contains all the roots of provided that the conditions of Theorem 11 are met. The BCH codes over can be obtained as the direct product of BCH codes Ci over . To construct the cyclic BCH codes over , we need to choose certain elements of as the roots of generator polynomials gi(x) of the codes, so are all the roots of gi(x) in . We construct gi(x) as

where are the minimal polynomials of , for li = 1,2,⋯,niki, where each . The following theorem extended Lemma 3 of [6] and provides a method for the construction of , the minimal polynomials of over the ring .

#### Theorem 13

For each i, where 0 ≤ i t, letbe the minimal polynomials ofover, wheregenerates, for li = 1,2,⋯,niki. Then, , where.

#### Proof

Let be the projection of over the fields and be the minimal polynomial of over , for each i such that 0 ≤ i t and 1 ≤ li ni ki. We can verify that each (the projection of ) is divisible by (minimal polynomials of ), for each i such that 0 ≤ i t and 1 ≤ li ni ki. So, among its roots, it has distinct elements of the sequence , for each i such that 0 ≤ i t and 1 ≤ li ni ki. Consequently, has, among its roots, distinct elements of the sequence , for 0 ≤ i t and 1 ≤ li ni ki. Thus, any element of the above sequence is a root of , for 0 ≤ i t, 0 ≤ qi hi − 1 and 1 ≤ li ni ki. Hence, . □

#### Remark 14

Since, for each i such that 0 ≤ i t, is the projection of(minimal polynomial of) over the fields, it follows thatgenerates the sequence of codes over the special chain of rings.

The lower bound on the minimum distances derived in the following theorem applies to any cyclic code. The BCH codes are a class of cyclic codes whose generator polynomials are chosen so that the minimum distances are guaranteed by this bound. In this sense, the following theorem generalizes Theorem 2.5 of [7]:

#### Theorem 15

Letbe the chain. For each i such that 0 ≤ i t, ifgi(x) is the generator polynomial of BCH codeoverwith length nisuch thatare the roots of gi(x) in, where αihas order ni, then the minimum Hamming distance ofis greater than the largest number of consecutive integers modulo ni in.

#### Proof

For each i, where 0 ≤ i t, let {ki,ki + 1,ki + 2,⋯,ki + di−2} be the largest set of consecutive integers modulo ni in the set Ei. A sequence of cyclic code with roots is the null space of the matrix

Now, if no linear combination of di − 1 columns of the matrix

is zero, then clearly no linear combination of di − 1 columns of each Mi is zero, and by the extended form of Corollary 3.1 of [10], it follows that each code has a minimum distance di or greater. This can be seen by examining the determinants of any di − 1 columns of the matrices . Let be the matrix where the entries is a collection of any set of di − 1 columns of matrix . Thus,

Now, we want to show that the determinants of matrices are non-singular, i.e., it is a unit in each . Note that the determinant of each matrix is given by

where the matrix is given by

The determinant of each is Vandermonde and each having a unit determinant in each ring . Hence, no combination of di − 1 or fewer columns of each Mi is linearly dependent. So, by Corollary 3.1 of [10], it follows that each code has a minimum distance di or greater. □

#### Corollary 16

(Theorem 2.5 of [ [7]]) Let g(x) be the generator polynomial of BCH code over A with length n such thatare the roots of g(x) in , where α has order n. Then, the minimum Hamming distance of the code is greater than the largest number of consecutive integers modulo n in E = {e1,e2,e3,⋯,enk}.

We can also use the extension of Theorem 4 of [6] for the BCH bound of these codes.

#### Algorithm

The algorithm for constructing a BCH type of cyclic codes over the chain of rings is then as follows:

1. Choose irreducible polynomials fi(x) over of degree hi = bi, for 1 ≤ i t, which are also irreducible over GF(p) and form the chain of Galois rings

and its corresponding chain of residue fields is

where each , for 1 ≤ i t.

2. Now, put , for 0 ≤ i t, and get a chain of rings

with another chain of rings

where each , for 0 ≤ i t.

3. Let be the primitive element in , for 0 ≤ i t. Then, ηi has order dini in for some integers di and put . Thus, αi = (βi,βi,βi,⋯,βi) has order ni in and generates . Assume that for each i, where 0 ≤ i t, αi be any element of .

4. Let be the roots of gi(x). Find the minimal polynomials of , for li = 1,2,⋯,niki, where each . Thus, gi(x) are given by

The length of each code in the chain is the least common multiple of the orders of , and the minimum distance of the code is greater than the largest number of consecutive integers modulo ni in the set for each i, where 0 ≤ i t.

Now, we give the following definition of the sequence of the BCH codes over the chain of Galois rings as in [11].

#### Definition 17

Let αi be a primitive element of. A sequence of BCH-type codes over the chain of Galois ringsis a sequence of cyclic codes of length ni generated by the polynomials gi(x) with minimum degree whose distinct roots are, for some bi ≥ 0, and ti ≥ 1, i.e.,, where, for 1 ≤ li ≤ 2ti, are minimal polynomials of.

From Definition 17, it turns out that is a collection of codewords if and only if , for 1 ≤ li ≤ 2ti and 0 ≤ i t. Therefore, a collection of parity-check matrices Hi for the sequence of BCH-type codes having gi(x) as the generator polynomial is given by

(1)

Thus, vi(x) is a collection of codewords if and only if . From the previous discussion, we have the following theorem which is an extension of Theorem 5 of [11]:

#### Theorem 18

The minimum Hamming distance of the sequence of BCH codes defined by the matrices in Equation 1 is greater than or equal to min{2ti + 1, for 0 ≤ i t}.

Now, we end this section by the following example:

#### Example 19

We initiate by constructing a chain of codes of lengths 1, 3, and 15 over the ring. Since M = {0,2}, it follows that. The regular polynomialis such that Π(f(x))=x4 + x + 1 is an irreducible polynomial with degree h = 22over. By Theorem 4, it follows that f(x) = x4 + x + 1 is irreducible over A. Letbe the Galois ring andbe the corresponding Galois field. The numbers 1, 2, and 22are the only divisors of 4, and therefore, say, h1 = 1, h2 = 2, and h3 = 22. Then, there exist irreducible polynomials f1(x) = x2 x + 1 and f2(x) = f(x) inwith degrees h2 = 2 and h3 = 4 such that we can constitute the Galois rings, where 1 ≤ i ≤ 2. So, . Again, by the same argument, it follows that, where 1 ≤ i ≤ 2, that is, , , and, with. If r= 2, thensuch that. Let u = {X} insuch that. Then, has order 15 in, and therefore, . However, u has order 30 in, so put β2 = u2and get α2 = (β2,β2) which generates. The elements ofare given by

Also, has order 3 in , so . However, u has order 6 in , so β1 = u2 and get α1 = (β1,β1) which generates . The elements of are given by

Put β0 = 1 and get α0 = (β0,β0) which generates . Choose α2, , α1, and α0 to be the roots of the generator polynomials gi(x) of the BCH codes over the chain . Thus, , , and have, as roots, all distinct elements in the sets , , and , respectively. So,

and, similarly,

Thus, the generator polynomials are given by

which generate the cyclic BCH codes , , and of lengths 1, 3, and 15 over the direct product of A(r)times with minimum hamming distances at least 2, 4, and 5, respectively. Also,

generate the cyclic BCH codes , , and of lengths 1, 3, and 15 over with minimum hamming distances at least 2, 4, and 5, respectively, for each i such that 0 ≤ i ≤ 2. Note that here a1 = (1,1), a2 = (2,2), and a3 = (3,3). If we take 1, 2, and 3 instead of a1, a2, and a3 in the above polynomial, then we get the generator polynomials of the codes Ci and over and , respectively.

### Results and discussion

#### Decoding procedure of BCH codes

In this section, we turn to the problem of decoding BCH codes of length ni, contrived to correct up to rti errors. In [11], a decoding procedure is proposed based on the modified Berlekamp-Massey algorithm for BCH codes defined over the integer residue ring . We have observed that even with almost evident analogous proofs, this decoding procedure is applied to the BCH codes over the chains of arbitrary finite local commutative rings with identity and also to the BCH codes over the direct product of the chain of local commutative rings with identity.

Let be a chain of rings and βi be a collection of primitive elements of , for 1 ≤ i t. Similarly, let be the chain of corresponding Galois fields. Since , for 0 ≤ i t, it follows that the new chain of rings is given by

with its projection over the chain of fields given by

i.e., each , for 1 ≤ i t. Let be the sequence of transmitted codewords from the sequence of codes . So, each , for 1 ≤ ki ni, is again a sequence of transmitted codewords from the sequence of codes Ci over the chain of Galois rings . Let be the sequence of received vectors, where each , for 1 ≤ ki ni and 1 ≤ i t. Thus, the error vector is given by , where , for 1 ≤ ki ni and 1 ≤ i t. The proposed decoding procedure consists of four major steps like in [11], for 1 ≤ i t:

1. Calculation of sequences of the syndrome such that , where each , for 1 ≤ wi ≤ 2ti and 1 ≤ i t.

2. Calculation of sequences of ‘elementary symmetric functions’ from si, where each , for 1 ≤ ui vi and 1 ≤ i t.

3. Calculation of the sequences of the error location numbers from , where each , for 1 ≤ ui vi and 1 ≤ i t.

4. Calculation of the sequences of the error magnitudes from si,j, where each , for 1 ≤ ui vi and 1 ≤ i t.

5. Without loss of generality, we can assume that the set of consecutive roots of the generator polynomials of the sequence of BCH codes is given by , for 1 ≤ i t. We can also define the sets of error location numbers, i.e., it consists of the elements , where ϵi,j are any positive integers, for 1 ≤ i t and 1 ≤ j r. Let vi be the number of errors introduced by the channel in each code . Thus, the elementary symmetric functions of the error location numbers are defined as the coefficients of the polynomials

and also, the relation of syndromes to the error location numbers and to the magnitudes of the errors are given by the equation

(2)

In the following, each step of the decoding process is analyzed. Since the syndrome calculation is so simple, there is no need to annotate on step 1.

In step 2, we want to calculate the elementary symmetric functions. It is equivalent to finding the sequences of solution sets , with minimum possible vi, to the following sets of linear recurrent equations over each

(3)

where the coefficients of , for 1 ≤ ui vi, are the components of the syndrome vectors. A quick solution to Equation 3 is made available by the following extension of the modified Berlekamp-Massey algorithm that holds for the chain of commutative rings with identity. We concentrate on the fact that in rings, we want to take care about zero divisors, multiple solutions of the systems of linear equations, and also with an inversionless implementation of the extension of the original Berlekamp-Massey algorithm. In [11], it is shown that the solution of each system to Equation 3 is unique if and only if all the error magnitudes are units in . Let the ni,jth power sums be defined as

(4)

where are the sequences of the components of the syndrome vectors and are the sequences of elementary symmetric functions. The proposed algorithm is also an iterative method. In this method, at the ni,jth step, the decoder seeks to determine the collection of sets of values such that the systems of equations, given in Equation 4, are satisfied with as small as possible, for 1 ≤ i t and 1 ≤ j r, where , for 1 ≤ i t and 1 ≤ j r. The polynomials

represent the solutions at the ni,jth stage. The ni,jth discrepancy will be denoted by and defined by

Next, we give two lemmas as extensions of Lemmas 1 and 2 of [11], concerning the determination of from , that is, we update the solution polynomial at each ni,jth step, although it is not necessary to have the lowest values of .

The following lemma extended Lemma 1 of [11]:

#### Lemma 20

Suppose that , for each i with 1 ≤ i t and each j with 1 ≤ j r, are solutions to the first ni,j power sums and has next discrepancy . Let

be a polynomial solution to the first mi,j power sums, for each i and j, where 1 ≤ mi,j < ni,j, such that the linear equations in given by

have solutions in y. Then, the polynomials

are solutions to the first ni,j + 1 power sums. Moreover, .

#### Proof

Since , for each i with 1 ≤ i t and each j with 1 ≤ j r, are solutions to the first ni,j power sums, it follows that each system of equations in Equation 4 holds, i.e.,

(5)

Similarly, is a solution to the first Mi power sums

(6)

If

is a solution to the first ni + 1 power sums, then we must have

(7)

This sum has the form

(8)

Since , for ui < 0 and , and , for ui < 0 and , it follows that Equation 8 can be written as

(9)

(or in another way, as ). Note that for ji = ni + 1, the first sum in Equation 9 has the value and the second has the value . Thus, Equation 9 reduces to and is true. By Equation 5, it follows that the first sum in Equation 9 is zero, provided that . By Equation 6, it follows that the second sum in Equation 9 is zero, provided that or, equivalently, provided that . Therefore, Equation 9 is satisfied, provided that

Since equations in Equation 4 are satisfied by , it follows that their degree is formally given by

Finally, note that the coefficients of the higher powers of the indeterminate X in may be zero, and therefore, the additional equations in Equation 4 may be further satisfied. □

The following lemma extended Lemma 2 of [11]:

#### Lemma 21

For each i, where 1 ≤ i t, letandbe defined as in Lemma 20. Suppose thatis any polynomial solution satisfyingpower sums. Then,

where each aiis a unit inand. Therefore, each polynomialis a polynomial solution to the firstequations of Equation 4 and has next discrepancy satisfyingand.

#### Proof

By hypothesis,

(10)

and

(11)

Since is a minimal solution, for , it follows that subtracting Equation 11 from Equation 10 for , we get

(12)

Now, suppose that the first ni mi coefficients of are zero (note that since , it follows that ni mi > 0, i.e., ni > mi). Thus, Equation 12 reduces to

(13)

Letting , Equation 13 can be rewritten as

(14)

Finally, define the polynomial by

Thus,

(15)

By Equation 15, it follows that each is a solution to the first equations in Equation 4 and each has next discrepancy such that . The degree of is given formally by . Note that the coefficients of the higher powers of the indeterminate X in may be zero; thus, some additional equations in Equation 4 may be satisfied, i.e., may not be minimal. □

Now, based on these two lemmas, we show that the following theorem is an extension of Theorem 6 of [11]:

#### Theorem 22

For each i with 1 ≤ i t, letbe a solution polynomial at the nith stage and letbe one of the prior minimal solutions, for 1 ≤ mi < ni, such thathas solutions in y andhas the largest value. Further, suppose eachis updated in the following way:

1. If, then

(16)

2. If, then

and

(17)

If there is no solutionwith degree less thanand such that the coefficient of the lowest power of the indeterminate X inis a zero divisor in, then eachis a minimal polynomial solution at the (ni + 1)th stage.

#### Proof

If , then are minimal solutions since are also minimal solutions. Now, consider the case where . Since each and are known, it follows that also are known by Equation 17. By Lemma 20, it follows that are polynomial solutions with degree given by

We will now show that these are minimal solutions.

• If , then by Lemma 20 and are minimal solutions at stages ni + 1.

• On the other hand, if , then

Let us analyze when are still minimal solutions. Assume that there exist polynomials with degree disuch that and the coefficients of the lowest power of the indeterminate X in are units in . There are two cases to consider:

1. If , then by Lemma 21, it follows that there are solutions with , i.e., with . By hypothesis, it follows that , and thus, . However, was chosen to be the largest of the values for the previous solutions, which is a contradiction.

2. If , then by Lemma 2, it follows that . However, since , it follows that

i.e., di > di, which is a contradiction.

Thus, if the coefficients of the lower power of X in are units in , then are minimal solutions. □

Note that the solution provided by Theorem 22 need not be answered because the theorem does not guarantee minimality when in case (2), the coefficients of the lowest power of the indeterminate X in are not units in . However, in many cases, it indicates the minimal solutions at the (ni + 1)th stages.

By extension of the lemma [12], we can verify that if satisfies equations in Equation 4, but not equations, then the solutions will satisfy equations in Equation 4, where

Now, by using the arguments of ‘section III’ of [12], it is straightforward to show that if the linear equation over the chain of the Galois ring , , always have solutions in y for , then the above inequalities become equalities, i.e.,

In contrast, if there are such that does not have solutions in y for any , with , then the solutions , for , given by Theorem 22, i.e., by Equations 16 and 17, are not necessarily minimal solutions. In this case, let us suppose that are minimal solutions at ni stages and are any solution at (ni + 1) stages (obtained from Equations 16 and 17 of Theorem 22). We analyze it in the following:

1. If , then are already the minimal solutions (at stages (ni + 1)) over the chain of rings , for 1 ≤ i t.

2. If , then it is possible that there are minimal solutions with degree li, where . Any collection of polynomials with minimum degree li (in the range ) will be minimal solutions (at stages (ni + 1)) if and only if the polynomials defined by

are solutions for the first Mi power sums, where and are zero divisors in . Evidence of this emerged in Lemmas 20 and 21 and from Theorem 22.

We can now collect these results and extend the modified Berlekamp-Massey algorithm.

#### Extension of the modified Berlekamp-Massey algorithm for commutative rings with identity

The collection of syndromes is used as the input for the algorithm. The output of the algorithm will be sets of values such that the equations in Equation 3 hold with minimum vi. We want to have some initial conditions for starting the algorithm as in [10], given by

for each i such that 1 ≤ i t, where 1 is the unity of and each si,1 is the first nonzero component of the corresponding syndrome vectors si, for each i, for 1 ≤ i t. Now, we want to do the following steps:

1. Each ni ← 0.

2. Now, each ; if any , for some j, 1 ≤ j t, then for that j,

and go to (5).

3. If any , then find an mk nk − 1 such that has a solution in y and has the largest value. Then,

and

where the solution of the equation , can be obtained by any of the algorithms presented in [13].

4. If , then go to (5); else, search for solution with minimum degree lk in the range such that defined by

is a solution for the first mk power sums, , with as a zero divisor in corresponding . If such a solution is found, then

5. If all ni < 2ti − 1, then

else, there is no need to find the values of .

6. ni ni + 1; if ni < 2ti, then go to (2); else, stop.

7. In this way, we compute in the nth iteration procedure, where n = max{ni : 1 ≤ i t}.

The coefficients of satisfy Equation 3, for each i, where 1 ≤ i t. This concludes step 2. This process contains n iterations, where n = max{ni : 1 ≤ i t}, and in each iteration, it deals t codewords of codes Ci at once, for each i, where 1 ≤ i t. By this procedure, we compute t elementary symmetric functions in the chain of rings with less computation. This process is not much different than the original one, but it deals a sequence of t codewords from the sequence of codes Ci over the chain of Galois rings , for each i, where 1 ≤ i t, at a time. Also, this process does not necessarily lead to a minimal solution (at the (ni + 1)th stages). As in [11], step 4 had to be introduced in the original algorithm so that the new solutions , calculated at step 3, are checked to be minimal solutions. If these are not so, then a search is necessary to be carried out to find minimal solutions, which consists of finding the polynomials , which are solutions for the first Mi power sums, and satisfying certain conditions. Step 4 does not essentially increase the complexity due to less number of polynomials.

In step 3, the calculation of error location numbers over the chain of rings requires one more step than that over the chain of fields because in , the solutions to Equation 3 are generally not unique and the reciprocals of polynomials , namely ρi(X), may not be the correct error locator polynomial

(18)

where ( are integers in the range that indicate the position of the uith errors in the sequence of codewords) are the correct error location numbers and vi are the numbers of errors in the sequence of codewords and are defined earlier.

Now, we describe how to convert the roots of ρi(X) into the correct error location numbers. The following proposition extends Proposition 3 of [11]:

#### Proposition 23

Suppose that ρi(X) has at least vidistinct roots over, namely, that is,

(19)

(20)

(note that at least one sequence of ρi(X) produced by the extension of the modified Berlekamp-Massey algorithm will have this property), where are the elementary symmetric functions found in step 2). Further, suppose that the error magnitudes are . Then, , where , for 1 ≤ ui vi and 1 ≤ i t.

#### Proof

From Equation 19, it follows that

(21)

(22)

for 1 ≤ ui vi, 1 ≤ ji ≤ 2ti vi and 1 ≤ i t. Substituting X for in Equation 21 and summing the right-hand side for 1 ≤ ji ≤ 2ti vi, we get

(23)

Note that Equation 23 vanishes for very jisuch that 1 ≤ ji ≤ 2ti vi(since the ’s form solutions to the linear system in Equation 3). Consequently,

(24)

for 1 ≤ ji ≤ 2ti vi(the left-hand side of Equation 24 is the collection of sums of the right-hand side of Equation 21 for 1 ≤ ui vi). In a matrix form, the sets of equations in Equation 24 can be written as

(25)

where

Equation 25 can be viewed as homogeneous linear systems over the chain of rings in the unknowns . The values 2ti vi are always greater than or equal to vi(since vi ti), and the McCoy rank of the matrices that appears in Equation 25 is vi, which is exactly the number of unknowns. By Theorem 5.3 of [14], this implies that the only solutions to Equation 25 are the trivial one, i.e., for 1 ≤ ui vi. □

Thus, from Proposition 23, we concluded that each product is necessarily a zero divisor in . Thus, , where 1 ≤ ui vi, has at least th factors which are zero divisors in . Moreover, if some (li,1)th factors of are zero divisors, say , and some other (li,2)th factors of are also zero divisors, say , then li,1 li,2 for ui ki and 1 ≤ i t. It can be solved in the following way: Suppose that li,1 = li,2 for ui ki. Thus, and . Therefore, are zero divisors in , which is a contradiction for ui ki. Hence, there are unique error location numbers in corresponding to each , where 1 ≤ ui vi, for 0 ≤ i t.

Based on these given facts, we can obtain the following procedure for the calculation of the correct error location numbers:

1. Compute the roots of each ρi(X), say, .

2. Among , select those such that are zero divisors in . The selected elements give the correct error location numbers.

This concludes step 3.

In step 4, the calculation of error magnitudes is based on Forney’s method [5], where the error magnitudes are given by

(26)

and the coefficients are defined by

Starting with , here, from [11, p. 1018], the denominator of Equation 26 is always a unit in .

Next, we give an example on this four-step decoding procedure.

#### Example 24

Letandbe a collection of (3,1) and (15,7) BCH codes, respectively, over the chain of Galois rings, referring to Example 19, with generator polynomials

We know that α1 = (x + 3,x + 3) and α2 = (x2,x2) be the primitive elements of and , respectively. Both codes and have an error-correcting capability equal to t1 = 1 and t2 = 2 errors. So, and have an error-correcting capability equal to t1 = 1 and t2 = 2 errors. Parity-check matrices of and are given by

Assume that the all zero codewords

are transmitted through the channel and the error pattern is

The received vectors are then given by

Applying the decoding procedure, first, we get syndromes

where

The extension of the modified Berlekamp-Massey algorithm is applied to s1 and s2, obtaining Table 1, where s1,3 = (x,2x + 2), s1,4 = (x + 1,2x), and s1,5 = (x,x + 1), and Table 2, where

and

based on a four- and six-iteration process.

Table 1. Calculation of the polynomial

Table 2. Calculation of the polynomial

The roots of ρ1(X) = X + s1,5 and ρ2(X) = X2 + s2,10X + s2,11 are Z1,1 = −s1,5 and Z2,1 = (2x + 1,x2), Z2,2 = (x3 + 3x2 + x,x3 + 3x2 + 1). Among the elements of G3 and G15, it follows that X1,1 = (0,β1), , X2,1 = (1,0), X2,2 = (0,β), X2,3 = (β13,0), and X2,4 = (0,β14) are such that X1,1Z1,1, X1,2 Z1,2 are zero divisors in and X2,1 Z2,1, X2,2 Z2,2 are zero divisors in . Therefore, X1,1, X1,2, X2,1, X2,2, X2,3, and X2,2are the correct error location numbers and indicate that two errors have occurred in c1, one at position 2 and the other at position 3, while four errors have occurred in c2, respectively, at positions 1, 2, 14, and 15. The correct elementary symmetric functions σ1,1, σ2,1, and σ2,2 are obtained from

Finally, Forney’s procedure is applied to si, and we get the error magnitudes Y1,1 = 3, Y1,2 = 6, Y2,1 = 6, and Y2,2 = 3. Therefore, the error pattern is given by

### Conclusions

For a nonnegative integer t, let be a chain of unitary commutative rings, where each is constructed by the direct product of suitable Galois rings with multiplicative group of units, and let be the corresponding chain of unitary commutative rings, where each is constructed by the direct product of corresponding residue fields of given Galois rings, with multiplicative groups of units. Despite [7], the construction of BCH codes with symbols from the commutative ring , the direct product of local commutative rings , where 0 ≤ i t and 1 ≤ j r, has residue fields , where 0 ≤ i t and 1 ≤ j r. For each member in the chain of the direct product of Galois rings and residue fields, respectively, we obtain the sequence of BCH codes over the direct product of local commutative rings with different lengths and sequences of BCH codes over the direct product of residue fields with proper lengths, i.e.,

and

In fact, this technique provides a choice to select the most suitable BCH code (respectively, BCH code ), where 0 ≤ i t, with required error-correcting capabilities and code rate but with compromising length. We extend the modified Berlekamp-Massey algorithm for the chain of unitary commutative local rings in such a way that the error will be corrected by a sequence of codewords from the sequence of BCH codes C0,C1,⋯,Ct−1,C. In this process, step 2 contains n iterations, where n = max{ni : 0 ≤ i t}, and in each iteration, it deals t codewords of codes Ci for each i, where 0 ≤ i t at once. By the algorithm of step 2, we compute t elementary symmetric functions in the chain of rings with less computation. This process is not much different than the original one, but it deals a sequence of t codewords from the sequence of codes Ci over the chain of Galois rings , for each i, where 0 ≤ i t, at once.

### Competing interests

The authors declare that they have no competing interests.

### Authors’ contributions

TS carried out the construction of the BCH codes, participated in the construction, and drafted the manuscript. AQ carried out the decoding procedure, participated in the design of the study, and performed the examples. AAA conceived of the study, participated in its design and coordination, and helped to draft the manuscript. All authors read and approved the final manuscript.

### Acknowledgements

The authors would like to thank the anonymous reviewers for their intuitive commentary that significantly improved the worth of this work and the FAPESP for the financial support (2007/56052-8 and 2011/03441-2).

### References

1. Blake, IF: Codes over certain rings. In: Inform. Contr. 20, 396–404

2. Blake, IF: Codes over integer residue rings. In: Inform. Contr. 29, 295–300

3. Spiegel, E: Codes over . In: Inform. Control. 35, 48–51

4. Spiegel, E: Codes over , revisited. In: Inform. Control. 37, 100–104

5. Forney, GDJr: On decoding BCH codes. In: IEEE Trans. Inform. Theory. IT-11, 549–557

6. Shankar, P: On BCH codes over arbitrary integer rings. In: IEEE Trans. Inform. Theory. IT-25(4), 480–483

7. Andrade, AA, Palazzo, RJr: Construction and decoding of BCH codes over finite rings. In: Linear Algebra Applic. 286, 69–85

8. McDonlad, BR: Finite Rings with Identity, Marcel Dekker, New York

9. Andrade, AA, Palazzo, RJr: A note on units of finite local rings. In: Rev. Mat. Estat., São Paulo. 18(2), 213–222

10. Peterson, WW, Weldon, EJJr: Error Correcting Codes, MIT, Cambridge

11. Interlando, JC, Palazzo, RJr, Elia, M: On the decoding of Reed-Solomon and BCH codes over integer residue rings. In: IEEE Trans. Inform. Theory. IT-43, 1013–1021

12. Massey, JL: Shift-register synthesis and BCH decoding. In: IEEE Trans. Inform. Theory. IT-15, 122–127

13. Elia, M, Interlando, JC, Palazzo, RJr: Computational of units in Galois rings. In: J. Discrete Mathematica Sci. and Criptography. 3(1-3), 41–55

14. Interlando, IC, Palazzo, RJr: A note on cyclic codes over . In: Latin Amer. Appl. Res. 25/S. 83–85