Construction and decoding of BCH codes over chain of commutative rings

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.

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 xⁿ − 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 η = (α₁α₂,⋯,α_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 = b^t, where b is a prime and t is a positive integer, there exist corresponding Galois ring extensions , where 0 ≤ i ≤ t and h_i = bⁱ (respectively, their residue fields , where 0 ≤ i ≤ t and h_i = bⁱ) of unitary local ring with p^m 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 n_i (divides ) relatively prime to p (it extends Theorem 2 of [6]). Furthermore, if generates a cyclic subgroup of order n_i in , then βⁱ generates a cyclic subgroup of order n_id_i in , where d_i 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: h_i = bⁱ for i = 2 or h_i = bⁱ 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.

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) = a₁(x)a₂(x), then either a₁(x) is a unit or a₂(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. 〈a₁,a₂,⋯,a_n〉 = A.

3.a_iis 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 A_j be a finite local ring with characteristic p_j, for each j such that 1 ≤ j ≤ s. Let be the residue fields of local rings R_j = A_j[x]/〈f_j(x) 〉, where f_j(x) is a basic irreducible polynomial over A_j of degree h, for each j such that 1 ≤ j ≤ s.

Theorem 5

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

The following theorem indicates the condition under which x^s − 1 can be factored over :

Theorem 6

(Theorem 3.4 of [ [7]]) The polynomialsx^s − 1 can be factored over the multiplicative groupasx^s − 1 = (x−α)(x−α²) ⋯ (x−α^s) if and only ifhas ordersin, wheregcd(sp_j) = 1 andα corresponds to β = (β₁β₂,⋯,β_s), forj = 1,2,3,⋯,s.

Theorem 7

(Theorem 3.5 of [ [7]]) For any positive integer l, let M_l(x) be the minimal polynomial of α^l over, where α generates. Then, , where B_l 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 = {e₁,e₂,e₃,⋯,e_n−k}.

Sequences of BCH codes

Let (A,M) be a unitary finite local commutative ring with residue field having p^m 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 = b^t, 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(p^kh) is a Galois ring of the form GR(p^kh^′), where h^′ divides h. Conversely, if h^′ divides h, then GR(p^kh) contains a unique copy of GR(p^kh^′).

Since 1,b,b²,⋯,b^t−1,b^t are divisors of h, so take h₀ = 1,h₁ = b,h₂ = b²,⋯,h_t = b^t = h, and by Lemma 9, it follows that there exist basic irreducible polynomials f₁(x),f₂(x),⋯,f_t(x)∈A[x] with degrees h₁,h₂,⋯,h_t, 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 h_i divides h_{i + 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(n_i,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 n_i in , for 0 ≤ i ≤ t. Conversely, suppose that has order n_i 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 xⁿ − 1 can be factored over the multiplicative groupas xⁿ − 1 = (x−α)(x−α²) ⋯ (x−αⁿ) 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 C_i over . To construct the cyclic BCH codes over , we need to choose certain elements of as the roots of generator polynomials g_i(x) of the codes, so are all the roots of g_i(x) in . We construct g_i(x) as

where are the minimal polynomials of , for l_i = 1,2,⋯,n_i−k_i, 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 l_i = 1,2,⋯,n_i−k_i. 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 ≤ l_i ≤ n_i − k_i. We can verify that each (the projection of ) is divisible by (minimal polynomials of ), for each i such that 0 ≤ i ≤ t and 1 ≤ l_i ≤ n_i − k_i. So, among its roots, it has distinct elements of the sequence , for each i such that 0 ≤ i ≤ t and 1 ≤ l_i ≤ n_i − k_i. Consequently, has, among its roots, distinct elements of the sequence , for 0 ≤ i ≤ t and 1 ≤ l_i ≤ n_i − k_i. Thus, any element of the above sequence is a root of , for 0 ≤ i ≤ t, 0 ≤ q_i ≤ h_i − 1 and 1 ≤ l_i ≤ n_i − k_i. 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, ifg_i(x) is the generator polynomial of BCH codeoverwith length n_isuch thatare the roots of g_i(x) in, where α_ihas order n_i, then the minimum Hamming distance ofis greater than the largest number of consecutive integers modulo n_i in.

Proof

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

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

is zero, then clearly no linear combination of d_i − 1 columns of each M_i is zero, and by the extended form of Corollary 3.1 of [10], it follows that each code has a minimum distance d_i or greater. This can be seen by examining the determinants of any d_i − 1 columns of the matrices . Let be the matrix where the entries is a collection of any set of d_i − 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 d_i − 1 or fewer columns of each M_i is linearly dependent. So, by Corollary 3.1 of [10], it follows that each code has a minimum distance d_i 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 = {e₁,e₂,e₃,⋯,e_n−k}.

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 f_i(x) over of degree h_i = bⁱ, 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 d_in_i in for some integers d_i and put . Thus, α_i = (β_i,β_i,β_i,⋯,β_i) has order n_i in and generates . Assume that for each i, where 0 ≤ i ≤ t, α_i be any element of .

4. Let be the roots of g_i(x). Find the minimal polynomials of , for l_i = 1,2,⋯,n_i−k_i, where each . Thus, g_i(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 n_i 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 n_i generated by the polynomials g_i(x) with minimum degree whose distinct roots are, for some b_i ≥ 0, and t_i ≥ 1, i.e.,, where, for 1 ≤ l_i ≤ 2t_i, are minimal polynomials of.

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

Thus, v_i(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{2t_i + 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))=x⁴ + x + 1 is an irreducible polynomial with degree h = 2²over. By Theorem 4, it follows that f(x) = x⁴ + x + 1 is irreducible over A. Letbe the Galois ring andbe the corresponding Galois field. The numbers 1, 2, and 2²are the only divisors of 4, and therefore, say, h₁ = 1, h₂ = 2, and h₃ = 2². Then, there exist irreducible polynomials f₁(x) = x² − x + 1 and f₂(x) = f(x) inwith degrees h₂ = 2 and h₃ = 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 β₂ = u²and get α₂ = (β₂,β₂) which generates. The elements ofare given by

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

Put β₀ = 1 and get α₀ = (β₀,β₀) which generates . Choose α₂, , α₁, and α₀ to be the roots of the generator polynomials g_i(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 a₁ = (1,1), a₂ = (2,2), and a₃ = (3,3). If we take 1, 2, and 3 instead of a₁, a₂, and a₃ in the above polynomial, then we get the generator polynomials of the codes C_i and over and , respectively.

Decoding procedure of BCH codes

In this section, we turn to the problem of decoding BCH codes of length n_i, contrived to correct up to r^′t_i 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 ≤ k_i ≤ n_i, is again a sequence of transmitted codewords from the sequence of codes C_i over the chain of Galois rings . Let be the sequence of received vectors, where each , for 1 ≤ k_i ≤ n_i and 1 ≤ i ≤ t. Thus, the error vector is given by , where , for 1 ≤ k_i ≤ n_i 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 ≤ w_i ≤ 2t_i and 1 ≤ i ≤ t.

2. Calculation of sequences of ‘elementary symmetric functions’ from s_i, where each , for 1 ≤ u_i ≤ v_i and 1 ≤ i ≤ t.

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

4. Calculation of the sequences of the error magnitudes from s_i,j, where each , for 1 ≤ u_i ≤ v_i 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 v_i 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

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 v_i, to the following sets of linear recurrent equations over each

where the coefficients of , for 1 ≤ u_i ≤ v_i, 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 n_i,jth power sums be defined as

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 n_i,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 n_i,jth stage. The n_i,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 n_i,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 n_i,j power sums and has next discrepancy . Let

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

have solutions in y. Then, the polynomials

are solutions to the first n_i,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 n_i,j power sums, it follows that each system of equations in Equation 4 holds, i.e.,

Similarly, is a solution to the first M_i power sums

If

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

This sum has the form

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

(or in another way, as ). Note that for j_i = n_i + 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 a_iis a unit inand. Therefore, each polynomialis a polynomial solution to the firstequations of Equation 4 and has next discrepancy satisfyingand.

Proof

By hypothesis,

and

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

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

Letting , Equation 13 can be rewritten as

Finally, define the polynomial by

Thus,

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 n_ith stage and letbe one of the prior minimal solutions, for 1 ≤ m_i < n_i, such thathas solutions in y andhas the largest value. Further, suppose eachis updated in the following way:

1. If, then

2. If, then

and

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 (n_i + 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 n_i + 1.

• On the other hand, if , then

Let us analyze when are still minimal solutions. Assume that there exist polynomials with degree d_isuch 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., d_i > d_i, 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 (n_i + 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 n_i stages and are any solution at (n_i + 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 (n_i + 1)) over the chain of rings , for 1 ≤ i ≤ t.

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

are solutions for the first M_i 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 v_i. 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 s_i,1 is the first nonzero component of the corresponding syndrome vectors s_i, for each i, for 1 ≤ i ≤ t. Now, we want to do the following steps:

1. Each n_i ← 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 m_k ≤ n_k − 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 l_k in the range such that defined by

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

5. If all n_i < 2t_i − 1, then

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

6. n_i ← n_i + 1; if n_i < 2t_i, then go to (2); else, stop.

7. In this way, we compute in the nth iteration procedure, where n = max{n_i : 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{n_i : 1 ≤ i ≤ t}, and in each iteration, it deals t codewords of codes C_i 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 C_i 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 (n_i + 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 M_i 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

where ( are integers in the range that indicate the position of the u_ith errors in the sequence of codewords) are the correct error location numbers and v_i 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 v_idistinct roots over, namely, that is,

(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 ≤ u_i ≤ v_i and 1 ≤ i ≤ t.

Proof

From Equation 19, it follows that

for 1 ≤ u_i ≤ v_i, 1 ≤ j_i ≤ 2t_i − v_i and 1 ≤ i ≤ t. Substituting X for in Equation 21 and summing the right-hand side for 1 ≤ j_i ≤ 2t_i − v_i, we get

Note that Equation 23 vanishes for very j_isuch that 1 ≤ j_i ≤ 2t_i − v_i(since the ’s form solutions to the linear system in Equation 3). Consequently,

for 1 ≤ j_i ≤ 2t_i − v_i(the left-hand side of Equation 24 is the collection of sums of the right-hand side of Equation 21 for 1 ≤ u_i ≤ v_i). In a matrix form, the sets of equations in Equation 24 can be written as

where

Equation 25 can be viewed as homogeneous linear systems over the chain of rings in the unknowns . The values 2t_i − v_i are always greater than or equal to v_i(since v_i ≤ t_i), and the McCoy rank of the matrices that appears in Equation 25 is v_i, 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 ≤ u_i ≤ v_i. □

Thus, from Proposition 23, we concluded that each product is necessarily a zero divisor in . Thus, , where 1 ≤ u_i ≤ v_i, has at least th factors which are zero divisors in . Moreover, if some (l_i,1)th factors of are zero divisors, say , and some other (l_i,2)th factors of are also zero divisors, say , then l_i,1 ≠ l_i,2 for u_i ≠ k_i and 1 ≤ i ≤ t. It can be solved in the following way: Suppose that l_i,1 = l_i,2 for u_i ≠ k_i. Thus, and . Therefore, are zero divisors in , which is a contradiction for u_i ≠ k_i. Hence, there are unique error location numbers in corresponding to each , where 1 ≤ u_i ≤ v_i, 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

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 α₁ = (x + 3,x + 3) and α₂ = (x²,x²) be the primitive elements of and , respectively. Both codes and have an error-correcting capability equal to t₁ = 1 and t₂ = 2 errors. So, and have an error-correcting capability equal to t₁ = 1 and t₂ = 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 s₁ and s₂, obtaining Table 1, where s_1,3 = (x,2x + 2), s_1,4 = (x + 1,2x), and s_1,5 = (x,x + 1), and Table 2, where

and

based on a four- and six-iteration process.

The roots of ρ₁(X) = X + s_1,5 and ρ₂(X) = X² + s_2,10X + s_2,11 are Z_1,1 = −s_1,5 and Z_2,1 = (2x + 1,x²), Z_2,2 = (x³ + 3x² + x,x³ + 3x² + 1). Among the elements of G₃ and G₁₅, it follows that X_1,1 = (0,β₁), , X_2,1 = (1,0), X_2,2 = (0,β), X_2,3 = (β¹³,0), and X_2,4 = (0,β¹⁴) are such that X_1,1−Z_1,1, X_1,2 − Z_1,2 are zero divisors in and X_2,1 − Z_2,1, X_2,2 − Z_2,2 are zero divisors in . Therefore, X_1,1, X_1,2, X_2,1, X_2,2, X_2,3, and X_2,2are the correct error location numbers and indicate that two errors have occurred in c₁, one at position 2 and the other at position 3, while four errors have occurred in c₂, 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 s_i, and we get the error magnitudes Y_1,1 = 3, Y_1,2 = 6, Y_2,1 = 6, and Y_2,2 = 3. Therefore, the error pattern is given by

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 C₀,C₁,⋯,C_t−1,C. In this process, step 2 contains n iterations, where n = max{n_i : 0 ≤ i ≤ t}, and in each iteration, it deals t codewords of codes C_i 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 C_i over the chain of Galois rings , for each i, where 0 ≤ i ≤ t, at once.

The authors declare that they have no competing interests.

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.

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).

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