4_xxx_siap.dvi EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 3, No. 4, 2010, 653-669 ISSN 1307-5543 – www.ejpam.com Burst Error Enumeration of m-Array Codes over Rings and Its Applications İrfan Şiap Department of Mathematics, Yildiz Technical University, Istanbul, Turkey Abstract. Enumerating burst errors enables to obtain bounds on parameters of codes. Recently, Jain in [5] established a Reiger’s type bound for burst error correcting matrix codes over finite fields with respect to a non Hamming metric. Here, we extend these results to array codes over finite rings. Further, we also introduce a new constructive method for counting burst errors that avoids solving Diophantine inequalities in order to compute burst errors for each given weight. Finally, we apply our results on establishing some bounds for array codes over finite rings. 2000 Mathematics Subject Classifications: 94B05, 94B20,94B25. Key Words and Phrases: Matrix Array Codes, Non Hamming Metric, Burst Errors, Burst Weight enu- merator. 1. Introduction The RT (non Hamming) metric for m-array codes has gained quite interest recently. On the other hand, burst error correction of array codes is also another important topic investi- gated by several researchers lately [1, 11, 2]. In [5], the author emphasizes the importance of considering burst errors by giving an application of array codes with respect to the RT met- ric. By enumerating burst errors of particular weights, a Rigger’s Type bound is established. Recently, an alternative approach that relies on generating type of multivariable polynomials in order of computing the number of a class of burst errors is presented in [10]. Here, we generalize these results to array codes over finite rings. In [5], counting of burst errors over fields relies on solving Diophantine inequalities 2. Further, this computation needs to be car- ried out for each particular weight when the question is to compute the number of burst errors of a particular weight or less which is the case. Here, we also introduce a new constructive method for counting burst errors that avoids solving Diophantine inequalities in order to com- pute burst errors for each given weight. Moreover, we introduce a multivariable polynomial whose coefficients enumerate the number of burst errors of particular weight and hence this Email address: isiap�yildiz.edu.tr (̇I. Siap) http://www.ejpam.com 653 c© 2010 EJPAM All rights reserved. İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 654 method avoids recalculations. Finally, we apply our results on establishing some bounds for array codes over finite rings. The RT (non Hamming) metric for array (matrix) codes over fields is defined in [7] and some bounds for the minimum distance are established. Some applications of this metric to uniform distributions are given in [8]. A MacWilliams type identity for codes over matrices with respect to the RT metric is proven in [3]. Further, a MacWilliams type identity for complete weight enumerators of codes over matrices with respect to the RT metric is proven in [9]. R be a commutative finite ring with unity. Throughout the paper we assume that the cardinality of R equals to q. Definition 1. Let M = Mm×s(R) be the set of m× s matrices with components from R . A subset C of M is called an m-array code. If C is a linear R-submodule, then C is called a linear m-array code. In this paper we will always refer to linear array codes. Definition 2 (Non Hamming-RT weight). Let x = (x1, x2, . . . , xs) ∈ Rs. The RT weight (or ρ-weight) of x is defined by wN(x ) = � max{i|x i 6= 0}, x 6= 0 0, x = 0. Let A ∈ Mm×s(R) and Ai be the ith row of the matrix A. Then the RT weight of the matrix A is the sum of the RT weights of its rows, in other words wN (A) = ∑m i=1 wN (Ai). The RT metric (ρ distance) is defined by ρ(x , y) = wN (x − y) where x , y ∈ M . Note the difference between the weight and distance notations of Hamming and RT (Non Hamming) metrics. The letter "N" for RT metric is used to emphasize the non Hamming case. Definition 3. Let C be an R-linear code. The minimum nonzero ρ distance between the code- words of C is denoted by dN (C). The minimum nonzero ρ weight among all codewords of C is denoted by wN (C). In linear case, dN (C) = wN (C), and dN (C) is called the minimum distance of C with respect to the RT metric. The concept of burst errors for codes in a classical setup is introduced in [4]. Recently, in [5], the notion of burst errors for matrix codes with respect to RT metric has been introduced and some formulas on enumeration of burst errors has been obtained and by use of this enu- meration Reiger’s type bounds are stated and proved. We extend the definitions introduced by Jain in [5] from finite field case to finite commutative ring case. Work on linear codes over rings is an interesting and ongoing topic in coding theory. Mostly, the work is done over finite rings such as Zm, Galois rings, chain rings and etc. In this paper, all this well known rings are covered. In the introduction, the basics and definitions are covered. In Section 2, generic burst errors are defined. An equivalence relation on the set of burst errors is introduced. The equivalence classes are shown to be the generic burst errors. Later, a generic multi variable polynomial that represents all generic burst errors is introduced. By substituting suitable İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 655 variables in a generic multivariable polynomial, we show how to obtain a new polynomial that gives the number of burst errors and their weights. Finally, applying a final substitution, we obtain a new polynomial called the burst weight enumerator polynomial with coefficients being the number of burst errors that correspond to the powers which gives the RT weights. Thus, the new computation method of burst errors of order p× r in the space Mp×r(R) (the set of matrices of order p× r with entries from a finite commutative ring with q elements R) is given. In Section 3, the computation method of burst errors of order p × r in the space Mm×s(R) where 1 ≤ p ≤ m, 1 ≤ r ≤ s is presented by making use of the results obtained in Section 2. In Section 4, some applications for obtaining bounds are presented. Finally, the paper is concluded by some remarks. Definition 4. A burst of order pr or (p× r) (1≤ p ≤ m, 1 ≤ r ≤ s) in the space Mm×s(R) is an m×s matrix in which all the nonzero entries are confined to some p× r submatrix which has non zero first and last rows as well as nonzero first and last columns. B p×r m×s(R) denotes the number of burst errors of order p× r. The number B p×r m×s(Fq) that is used in establishing some bounds for array codes over a finite field Fq is presented by Jain in [5] with the following theorem: Theorem 1 ([5]). Let B p×r m×s(Fq) denote the number of bursts of order pr in Mm×s(Fq). Then, B p×r m×s(Fq) =        ms(q− 1), p = 1, r = 1, m(s− r + 1)(q− 1)2qr−2, p = 1, r ≥ 2 (m− p+ 1)s(q− 1)2qp−2, p ≥ 2, r = 1, (m− p+ 1)(s− r + 1)qr(p−2)[(qr − 1)2 −2(qr−1− 1)2q2−p + (qr−2 − 1)2q4−2p], p ≥ 2, r ≥ 2. Further, in [5] a formula for the number of bursts of a particular order and not exceeding a given ρ-weight is stated and proved in the following theorem: Theorem 2 ([5]). The number of bursts of order pr (1≤ p ≤ m, 1 ≤ r ≤ s) in Mm×s(Fq) having ρ-weight w or less (1≤ w ≤ ms) is given by B p×r m×s(Fq, w) =    m(q− 1)min(w, s), p = 1, r = 1, mmin(w − r + 1, s− r + 1)(q− 1)2qr−2, p = 1, r ≥ 2, (m− p+ 1)B3, p ≥ 2, r = 1, (m− p+ 1)B4, p ≥ 2, r ≥ 2. where B3 = min([w/2],s) ∑ j=1 p−1 ∑ η=0:η j≤w−2 j (q− 1)2 � p− 2 η � (q− 1)η, B4 = (m− p+ 1) min(w−r+1,s−r+1) ∑ j=1 (L p j − 2L p−1 j + L p−2 j ), İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 656 and L p j = ∑ k j ,...,k j+r−1 p! ∏r−1 l=0 k j+1! � p− ∑r−1 l=0 k j+l � ! � q− 1 q � ∑r−1 l=0 k j+l q ∑r−1 l=0 (l+1)k j+l (1) where k j , k j+1, . . . , k j+r−1 being nonnegative integers such that k j > 0, k j+1, k j+2, . . . , k j+r−2 ≥ 0, k j+r−1 > 0, r−1 ∑ l=0 k j+l ≤ p r−1 ∑ l=0 ( j+ l)k j+l ≤ w. (2) In Theorem 2, computing the number of burst errors of a particular order is still a chal- lenging task. In Equation 2, the two Diophantine inequalities are first to be solved in the set of natural numbers. Then, the L p j numbers are computed by using the ki solutions. In [5], some examples using this approach are worked out explicitly. In the next sections, we first extend the results obtained by Jain in [5] to array codes over R by introducing a new constructive method that gives the number of burst errors. This new method, it does not only give the number of a particular burst error weight but it also gives all spectra of the weights in a single computation. The spectra of the number of burst errors shall be called the burst error weight enumerator. Finally, we apply our results to obtain new bounds for array codes over rings. 2. Enumerating Burst Errors In this section, we shall work on the space Mp×r(R) and consider only burst errors of order p× r. In the next section, we shall consider burst errors of order p× r in the space Mm×s(R) where 1≤ p ≤ m, 1≤ r ≤ s. In order to introduce the new approach for computing burst error matrices we need to state some definitions and introduce some new concepts. Definition 5. If A ∈ Mm×s(Fq) and wN (Ai) = αi, then the matrix A is said to have a weight distribution of type (α1,α2, . . . ,αm). If A j is the jth row of an A ∈ Mp×r matrix, then the index of A j denoted by (k j , l j) where 1 ≤ k j ≤ l j ≤ r is defined by a ji = 0 for all 1 ≤ i ≤ k j − 1 and a jk j 6= 0 and l j = wN (A j). The index of a matrix with rows A1,A2, . . . Ap is defined by ((k1, l1), (k2, l2), . . . , (kp, lp)). Let A=       a11 · · · a1r a21 · · · a2r ... ... ... ap1 · · · apr       . The first row and column, and the last row and column of the matrix A are shown in the following rectangle which is called the frame of matrix A. İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 657 a11 a12 · · · a1r−1 a1r a21 · · · · · · · · · a2r ... ... ... ... ... ap1 ap2 · · · apr−1 apr The restrictions on the first and last rows together with the first and last columns determine whether a matrix is a burst error or not. Hence, we focus on the frame of the matrix and introduce some new definitions in order to control these entries and transform the problem of computing the number of these errors into an algebraic problem. Further, the four entries a11, a1r , ap1 and apr of A shall be referred as the corners of the matrix. Definition 6. A generic burst error A ∈ Mp×r of order p× r is a burst error of order p× r such that the first and the last rows have exactly two or one nonzero entries, and the submatrix of size p− 2× r − 2 that is obtained by removing first and last rows and first and last columns (i.e. the borders) has all entries equal to zeroes, i.e, the entries that fall out off the frame are all equal to zeroes. Example 1. B1 =      0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0      4×4 B2 =      1 0 1 0 0 0 0 0 0 0 0 1      4×3 B3 = � 1 0 1 0 1 0 � 2×3 . The matrices B1, B2 and B3 are generic burst errors. Note that the matrices E = � 1 0 1 1 1 1 � 2×3 and D =    1 0 1 0 1 0 1 0 1    3×3 are burst errors but they are not generic burst errors. However, the matrix    1 0 1 0 0 0 1 0 1    3×3 is a generic burst error. In order to determine the generic burst errors, we need to classify matrices according to their corners. Let A = (ai j) ∈ Mp×r(R) be a generic burst error and the jth row A j = (a j1, a j2, . . . , a jr). By definition, the jth row has at most two nonzero entries. Let (k j, l j) be the index of A j. We İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 658 associate a multi variable term to the jth row of A in the following way: µ(A j) =                    z j, 1= k j = l j x k j j , 1< k j = l j < r y j, 1< k j = l j = r x k j j X l j j , k j < l j < r x k j j y j, 1< k j < l j = r z jX l j j , 1= k j < l j < r z j y j , 1= k j < l j = r. We associate z j and y j variables for the first and last column entries respectively. If there exist two nonzero entries in the first or last row which are different from the corner entries, then we associate x k j X l j where the small letter indicates the beginning and capital X j indicates the end of the nonzero entries. We use x i j , when the jth row has only one nonzero entry on the i-th entry, 1< i < r. In a natural way, we extend this representation to the matrix A by taking the product of all terms µ(A j) corresponding to the rows of A. The terms that correspond to the rows different from the first and last contain only the terms composed by z and y variables. For example, the representations of the following matrices are given below: Example 2. Generic errors A=    0 1 0 1 0 0 0 0 1    B =    1 0 1 0 0 0 0 1 0    C = � 0 1 0 1 0 1 0 0 0 1 � . The terms x2 1z2 y3 z1 y1 x2 3 x2 1X 4 1z2 y2 Given a p multi variable representation of a generic burst error, it is possible to list all burst errors by using it. In general, we have G = a11 · · · a1r ... ... ... ap1 · · · apr ↔ z1 · · · x j 1, xk1 X l1, X l1 · · · y1 ...zi ... ... ...yi ... zp · · · x j p, xkp X lp , X lp · · · yp and the term ∏p j=1 µ(A j) corresponds to the term of the matrix A. We classify generic burst errors by considering their corners. There are 24 = 16 possible cases for these corners and corresponding multi variable terms. We list them in Table 1. In order to solve the problem of representing burst array errors in terms, we need to split it into cases. First, we need to split it to two main cases as p ≥ 3 and r ≥ 3 and otherwise. We work out these cases by the following theorems. Let z̃ = (z1, . . . , zp), x̃ = (x1, . . . , xp), ỹ = (y1, . . . , yp) and X̃ = (X1, . . . , X p). Definition 7. Let Kp×r be the set of all generic burst errors of size p × r. Let G(z̃, x̃ , X̃ , ỹ) = ∑ A∈K ∏p j=1µ(A j) be the multivariable polynomial whose terms represent generic burst errors. İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 659 (a11, a1r , ap1, apl) term (a11, a1r , ap1, apl) term (0,0,0,0) 1 (0,1,1,0) y1zp (1,0,0,0) z1 (0,1,0,1) y1 yp (0,1,0,0) y1 (0,0,1,1) zp yp (0,0,1,0) zp (1,1,1,0) z1 y1zp (0,0,0,1) yp (1,1,0,1) z1 y1 yp (1,1,0,0) z1 y1 (1,0,1,1) z1zp yp (1,0,1,0) z1zp (0,1,1,1) y1zp yp (1,0,0,1) z1 yp (1,1,1,1) z1 y1zp ypTable 1: Terms with respe t to the orners In the following theorem we first determine multivariable polynomial G that gives the terms of generic burst errors of size p ≤ 2 and r ≤ 2. The remaining case is treated separately in the next theorem. Theorem 3. 1. Let p = 1 and r ≥ 2. Then, G(z̃, x̃ , X̃ , ỹ) = z1 y1. 2. Let p ≥ 2 and r = 1. Then, G(z̃) = z1zp. 3. Let p = 2 and r ≥ 2. Let S = {(i, j, k, l) ∈ Z4 2 |(i, k) 6= (0,0), ( j, l) 6= (0,0)}. Then, G(z̃, x̃ , X̃ , ỹ) = ∑ (i, j,k,l)∈S z i 1 y j 1zk 2 y l 2γi j(X1)γkl(X p). 4. Let p ≥ 2 and r = 2. Let T = {(i, j, k, l) ∈ {0,1}4|(i, j) 6= (0,0), (k, l) 6= (0,0)}. Then, G(z̃, x̃ , X̃ , ỹ) = ∑ (i, j,k,l)∈T z i 1 y j 1zk p y l pZ ikY jl . where Z st = ¨ −1+ ∏p−1 i=2 (1+ zi), (s, t) = (0,0) ∏p−1 i=2 (1+ zi), otherwise Y st = ¨ −1+ ∏p−1 i=2 (1+ yi), (s, t) = (0,0) ∏p−1 i=2 (1+ yi), otherwise γst(Xk) =        ∑r−2 i=2 x i k � 1+ ∑r−1 j=i+1 X j k � + x r−1 k , (s, t) = (0,0) 1+ ∑r−1 i=2 x i k , (s, t) = (0,1) 1+ ∑r−1 i=2 X i k , (s, t) = (1,0) 1, (s, t) = (1,1). İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 660 Proof. The cases 1 and 2 follow directly from the definitions. We give the proof of case 3 and the proof of the case 4 also can be shown by using similar arguments. Let p = 2 and r ≥ 2 and A= (ai j) ∈ M2×r (R) be a generic burst error. Hence the matrix A has only two rows and r ≥ 2 columns. There are 24 = 16 possible values (as zero and none zero) for the corners of A. Since the matrix A is a burst error, the first and last column must be nonzero. The first column is equal to zero if (i, k) = (0,0) and the last column is equal to zero if ( j, l) = (0,0). Excluding these seven cases the possible values for the corners are all values of the set S. If both corners of the first row are equal to zero, then the term that corresponds to A must consist of β = x2 1(X 2 1 + · · ·+ X r−1 1 ) + x3 1(X 4 1 + · · ·+ X r−1 1 ) + · · ·+ x r−1. Otherwise, the term that corresponds to A must consist of 1+ β . These two cases are represented by the multiple γi j(X1). In a similar way we can argue for the last row. Example 3. The following generic multivariable polynomial G gives the term representation of A∈ M2×3(F2) generic burst errors of order 2× 3. By Theorem 3 part 3, we have G(z̃, x̃ , X̃ , ỹ) = ∑ (i, j,k,l)∈S z i 1 y j 1 zk 2 y l 2γi j(X1)γkl(X2) = z1 y1X 2 2 + z2 y2X 2 1 + z1 y2(1+ X 2 1)(1+ x2 2) + z2 y1(1+ x2 1)(1+ X 2 2) + z1 y1 y2(1+ x2 2) + y1z2 y2(1+ X 2 1) + z1z2 y1(1+ X 2 2) + z1z2 y2(1+ X 2 1) + z1 y1z2 y2 = z1 y1X 2 2 + z2 y2 x2 1 + z1 y2 + z1 y2 x2 2 + z1 y2X 2 1 + z1 y2X 2 1 x2 2 + z2 y1 + z2 y1 x2 2 + z2 y1X 2 1 + z2 y1X 2 1 x2 2 + z1 y1 y2 + z1 y1 y2X 2 2 + y1z2 y2 + y1z2 y2 x2 1 + z1z2 y1 + z1z2 y1X 2 2 + z1z2 y2 + z1z2 y2X 2 1 + z1 y1z2 y2. Using the generic multivariable polynomial, we can list all generic burst errors of size 2× 3. � 1 0 1 0 1 0 � , � 0 1 0 1 0 1 � , � 1 0 0 0 0 1 � , � 1 0 0 0 1 1 � , � 1 1 0 0 0 1 � , � 1 1 0 0 1 1 � , � 0 0 1 1 0 0 � , � 0 0 1 1 1 0 � , � 0 1 1 1 0 0 � , � 0 1 1 1 1 0 � , � 1 0 1 0 0 1 � , � 1 0 1 0 1 1 � , � 0 0 1 1 0 1 � , � 0 1 1 1 0 1 � , � 1 0 1 1 0 0 � , � 1 0 1 1 1 0 � , � 1 0 0 1 0 1 � , � 1 1 0 1 0 1 � , � 1 0 1 1 0 1 � . Theorem 4. All generic bursts of order p × r (p, r ≥ 3) are obtained as terms of the following multi variable polynomial, say generic multivariable polynomial: G( x̃ , z̃, X̃ , ỹ) = ∑ (i, j,k,l)∈Z4 2 z i 1 y j 1zk p y l pZ ikY jlγi j(X1)γkl(X p). İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 661 Proof. Let A= (ai j) ∈ Mp×r(R) be a generic burst error. A= a11 · · · a1r ... zero submatrix ... ap1 · · · apr . We consider the corners of A. There are 16 cases depending on the corner’s values as whether they are equal to one or zero. If any pair of adjacent corners corresponding to the first row, column or last row or column both equal to zero, then at least one of the entries between the corners must equal to one. As argued in the proof of Theorem 3, γi j(X1) represents the term that corresponds to the first row. Similarly, γkl(X p) represents the term that corresponds to the last row. Again, if the first and the last entry of the first column both equal to zero, then the term corresponding to the matrix has to include the factor −1+ ∏p−1 i=2 (1+zi) since at least one of the entries must equal to one excluding the zero column. In other cases, ∏p−1 i=2 (1+ zi) represents the first column. Arguing similarly for the last column, we get the result. Example 4. The following generic multivariable polynomial G gives the term representation of A∈ M3×3(F2) generic burst errors of order 3× 3 : G(z̃, x̃ , X̃ , ỹ) = ∑ (i, j,k,l)∈{0,1}4 z i 1 y j 1 x k 3 y l 3Y jl(α)γi j(X1)γkl(X3). Now, we shall make use of generic burst errors to determine all burst errors especially the number of burst errors. First, we introduce a relation on burst errors that is based on the frames of matrices. Definition 8. Let B be the set of all burst errors of order p× r. Let A, B ∈ B⊂ Mp×r(R). It is said that the matrix A is related to the matrix B, i.e At B, in the set B if and only if µ(A j) = µ(B j) for j = 1, p and µ(A j)|x j=X j=1 = µ(B j)|x j=X j=1 for j 6= 1, p. The proof of the following Lemma follows from the definitions. Lemma 1. The relation “≈” defined on the set B is an equivalence relation. Now we have a partition of the space of burst errors into disjoint classes which are generic burst errors. Let CA represent the set of equivalence class of matrix A. We determine the representative set CA in the following way: Let A1 be the first row of a generic burst error matrix A. If the weight of the row is two (the term consists of z1 y1, z1X l1 1 , x k1 1 X l1 1 or x k1 1 y1), then these two entries are nonzero and the choices for the entries in between run through all nonzero elements of the ring R. If the weight is equal to one (the term consists of y1, z1 or x k1 1 only), then a nonzero choice for this entry from R\{0}. In a similar way we can argue for the last row of the matrix. Also we note that the entries that fall out off the frame can take any value without any restriction. İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 662 Now we use generic burst error matrices in Example 3, to find all burst errors of size 2×3 over F2. We list the equivalency classes with respect to the relation: ¨� 1 0 1 0 1 0 � , � 1 1 1 0 1 0 �« , ¨� 0 1 0 1 0 1 � , � 0 1 0 1 1 1 �« , ¨� 1 0 0 0 0 1 �« , ¨� 1 0 0 0 1 1 �« , ¨� 1 1 0 0 0 1 �« , ¨� 1 1 0 0 1 1 �« , ¨� 0 0 1 1 0 0 �« , ¨� 0 0 1 1 1 0 �« , ¨� 0 1 1 1 0 0 �« , ¨� 0 1 1 1 1 0 �« , ¨� 1 0 1 0 0 1 � , � 1 1 1 0 0 1 �« , ¨� 1 0 1 0 1 1 � , � 1 1 1 0 1 1 �« , ¨� 0 0 1 1 0 1 � , � 0 0 1 1 1 1 �« , ¨� 0 1 1 1 0 1 � , � 0 1 1 1 1 1 �« , ¨� 1 0 1 1 0 0 � , � 1 1 1 1 0 0 �« , ¨� 1 0 1 1 1 0 � , � 1 1 1 1 1 0 �« , ¨� 1 0 0 1 0 1 � , � 1 0 0 1 1 1 �« , ¨� 1 1 0 1 0 1 � , � 1 1 0 1 1 1 �« , ¨� 1 0 1 1 0 1 � , � 1 1 1 1 0 1 � , � 1 0 1 1 1 1 � , � 1 1 1 1 1 1 �« . The sets are classes that correspond to a generic burst error. Altogether, they add up to 32 burst errors of order 2× 3 over F2. If we were working over the field F3, then, for example, the generic burst error class that correspond to the generic matrix Z = � 1 0 1 0 1 0 � would be; CZ = ¨� a b c 0 d 0 � |a, c, d ∈ F3\{0} and b ∈ F3 « and |CZ | = 23 · 3 = 24. In general, over a ring R, the generic matrix Z ∈ M2×3(R) represented by the term x1 y1X 2 2 will have a burst error class of size (q− 1)3q. İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 663 Corollary 1. The number of terms of generic polynomial G, gives the number of equivalence classes of equivalence relation “≈” which are generic burst errors. Under this observation, we can make use of generic burst terms and hence generic multi variable polynomial to obtain the number of burst errors. Definition 9. Let A∈ B ⊂ Mp×r(R). Assume that A has a weight distribution of type (α1,α2, . . . ,αp). We associate a term X α1 1 X α2 2 · · ·X αp p to the matrix A. Then, the p-variable polynomial Hp×r(X̃ ) = ∑ A∈B X α1 1 X α2 2 · · ·X αp p is said to be the weight spectra polynomial of the burst errors in Mp×r(R). Now we shall make use of generic polynomial in order to compute the weight spectra polynomial of burst errors. Here, we point out that the frame of the arrays hence generic bursts lead to construction of burst errors. So, if we have for instance a term z a1 1 x b1 1 X c1 1 y d1 1 for the first row, then the first and the last if any nonzero entry will lead to (q− 1)2 choices and there is no restriction in between with q choices for each entry. However, if this row consists of a single nonzero entry then the total number of choices is equal to q− 1. In order to accommodate all cases we will invent the following compact substitution. Assume that the term z a1 1 x b1 1 X c1 1 y d1 1 is related to the first row of a generic burst error with the convention that the powers may equal to zero in generic polynomial. The term z a1 1 x b1 1 X c1 1 y d1 1 that corresponds to the first row of the generic matrix leads to (q− 1)2[w(a1d1)+w(a1c1)+w(b1d1)]+w(b1)qw(a1d1)(r−2)+w(a1 c1)(c1−2)+w(b1d1)(r−b1−1) number of possibilities for the first row of burst error that falls into the generic class where w(a) = 0 if a = 0 and otherwise w(a) = 1. The same argument is still valid for the last row. Thus, for j = 1 and j = p, if γ(X j) = (q− 1)2[w(a1d1)+w(a1c1)+w(b1d1)]+w(b1)· qw(a1d1)(r−2)+w(a1 c1)(c1−2)+w(b1d1)(r−b1−1) · X max{rd j ,c j,b j ,a j} j is substituted for the term z a j j x b j j X c j j y d j j in the generic polynomial, then the new term expres- sion gives all possible weight distributions for the jth row. For j = 2, . . . p − 1, there are four cases to be considered. If the term z j y j exists then, we substitute (q− 1)2qr−2X r j . If the term y j exists only, then we substitute (q− 1)qr−2X r j . If the term z j exists only, then we substitute (q − 1)X j + ∑r−1 i=2 qi−2(q − 1)2X i j . Finally, if none of z j or y j exist, then we substitute the term 1+ ∑r−1 i=2 qi−1(q − 1)X i j . Hence, we obtain the multivariable polynomial Hp×r which is the spectra weight enumerator of burst error arrays of order p× r in Mp×r(R). Thus we obtain the following theorem: İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 664 Theorem 5. Let G(z̃, x̃ , X̃ , ỹ) be the generic polynomial. Then, for j = 1 and j = p, by sub- stituting γ(X j) for z a j j x b j j X c j j y d j j in G, and further substituting (q− 1)2qr−2X r j , (q− 1)qr−2X r j , and (q− 1)X j + ∑r−1 i=2 qi−2(q− 1)2X i j for z j y j , y j , and z j and multiplying the terms that do not include the factors z j and y j by 1+ ∑r−1 i=2 qi−1(q−1)X i j for j 6= 1 and j 6= p, we obtain the spectra weight enumerator polynomial Hp×r(X̃ ) in the space of burst errors of order p× r. Example 5. Let G be given as in Example 3. For instance, for z1 y1X 2 2 and z2 y2X 2 1 we substitute 2X 3 2 X 2 1 respectively. Hence, by applying the necessary substitutions, we have H(X1, X2) =4X 3 1 X2+ 6X 3 1 X 2 2 + 12X 3 2X 3 1 + 6X 3 2 X 2 1 + 4X 3 2 X1. Now, we can compare the terms of H(X1, X2) with the list in the Example 3. For instance, the term 12X 3 2 X 3 1 indicates that there are 12 burst errors of weight distribution (3,3). Example 6. Let G be given as in Example 4. By applying Theorem 5, we get H(X1, X2, X3) =28X 2 1X 3 2 X 3 3 + 6X 2 1 X 3 3 + 12X 3 1X 3 3 + 14X 2 1 X 2 2 X 3 3 + 28X 3 1X 2 2 X 3 3 + 8X 2 1 X2X 3 3 + 4X1X2X 3 3 + 8X1X 2 2 X 3 3 + 16X1X 3 2 X 3 3 + 4X1X 3 3 + 56X 3 1 X 3 2 X 3 3 + 16X 3 1X2X 3 3 + 14X 2 1X 2 3 X 3 2 + 28X 3 1 X 2 3 X 3 2 + 8X 3 1 X 2 3 X2+ 14X 3 1X 2 3 X 2 2 + 8X1X 2 3 X 3 2 + 6X 3 1 X 2 3 + 4X1X 3 2 X3+ 4X 3 1 X2X3+ 4X 3 1 X3 + 8X 2 1 X 3 2 X3+ 8X 3 1 X 2 2 X3+ 16X 3 1 X 3 2 X3. Definition 10. The polynomial, Bp×r (t) = ∑ A∈B twN (A) = ∑p·r i=1 bi t i is said to be the weight enumerator of bursts of order p× r in the space Mp×r(R). Corollary 2. By substituting X i = t in H(X̃ ), we obtain Bp×r(t) which is the weight enumerator of bursts of order p × r. Further, the Bp×r(R, w) numbers formulated in Theorem 2 by [5] are reobtained as follows: Bp×r(R, w) = w ∑ i=1 bi where bi ’s are coefficients of Bp×r(t). We would like to emphasize that by applying Corollary 2, we are able to compute Bp×r(R, w) quite easily. In [5], for each weight w where 1 ≤ w ≤ pr, the computation of Bp×r(R, w) has to be carried out separately by solving the necessary Diophantine inequalities (see Eq.(2)) and then applying the formula (see Eq. (1)). Example 7. The following generic polynomial G gives the term representation of A ∈ M4×4(F2) generic burst errors of order 4× 4 : G(z̃, x̃ , X̃ , ỹ) = ∑ (i, j,k,l)∈{0,1}4 z i 1 y j 1zk 4 y l 4Z ik(α)Y jl(α)γi j(X1)γkl(X4). İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 665 Applying necessary substitutions given in Corollary 2, we obtain the weight enumerator of burst errors: B4×4(t) =3840t16 + 7680t15+ 9600t14+ 9728t13 + 8288t12+ 5856t11 + 3504t10+ 1824t9+ 792t8+ 272t7 + 72t6 + 16t5. Letting t = 1, in B4×4(t) we have B4×4(1) = 51472. Further, B4×4(F2, 7) = 16+72+272= 360 which is the number of burst errors of type 4× 4 of weight 7 or less. 3. Enumerating Bursts in Larger Space In this section we consider burst of errors of order p × r in the space Mm×s(R) where 1≤ p < m and 1≤ r < s. Example 8. We list two burst errors of order 3× 3 in the space M4×4(F2). A=      0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1      , B =      0 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0      . Lemma 2. Let A be a burst of order p× r in the space Mm×s(R) where 1≤ p < m and 1≤ r < s. If T p×r p×r (R) is the number of burst errors of order p× r in the space Mp×r(R), then T p×r m×s (R) = (s− r + 1)(m− p+ 1)T p×r p×r (R) gives the number of burst of order p× r in the space Mm×s(R). Proof. By definition, a burst of order p× r in the space Mm×s(R) is a matrix of order m× s that includes a submatrix A which is a burst error of order p× r itself in the space Mp×r(R) and the entries that fall out of this submatrix are all zeroes. Hence, placing A as a submatrix of a matrix of size m× s is possible in s− r+1 ways moving from the left to the right starting from the position (1,1) for both the matrix and the submatrix. Also, for a given possible position obtained above, there exist also m− p+ 1 movements downwards for obtaining submatrices. Thus, there exist (s− r+1)(m− p+1) ways that give raise to new submatrices for each burst error of order p × r in the space Mm×s(R). Therefore, the number of burst of order p × r in the space Mm×s(R) is (s− r + 1)(m− p+ 1)T p×r p×r (R). Hence, it is possible to construct all burst errors of size p× r in Mm×s(R) knowing all burst errors of size p × r in Mp×r(R). This can be done easily by positioning the matrices of size p× r as sub matrices of matrices of size m× s. Since after repositioning, the RT weights will change, the main problem is to control the weights of burst errors when repositioning is done. If we know the weight spectra polynomial H(X ) of burst errors of size p× r in Mp×r(R), then by multiplying H(X ) with suitable variables or in other words applying a translation map, we can obtain the weight spectra of burst errors of size p× r in Mp×r(R) as explained below. İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 666 Definition 11. Let H(X1, X2, . . . , X p) = ∑ (i1,i2,...,ip)∈Np h(i1, i2, . . . , ip)X i1 1 X i2 2 · · ·X ip p be the weight spectra polynomial where h(i1, i2, . . . , ip) ∈ N and N is the set of natural numbers. Then, we define a translation map T (H) = ∑ (i1,i2,...,ip)∈Np h(i1, i2, . . . , ip)X w(i1)(i1+1) 1 X w(i2)(i2+1) 2 · · ·X w(ip)(ip+1) p . Lemma 3. Let H(X ) be the weight spectra polynomial of burst of errors of order p×r in the space Mp×r(R). The weight spectra polynomial of burst of errors of order p× r in the space Mm×s(R) is given by W (X̃ ) = (m− p+ 1) s−r+1 ∑ i=0 T i(H). Proof. Polynomial H gives the terms that correspond to burst errors of order p× r whose (1,1) entry position is located at (1,1). The polynomial T (H) gives the terms that correspond to burst errors whose (1,1) entry position is located at (1,2). There are s− r + 1 translations possible for a submatrix of order p× r in the space of matrices of order m× s. The sum of all these give all possible submatrices as burst errors of order p× r whose first rows are situated as first rows of burst error of order m× s. For each submatrix obtained above, we can move it downwards to obtain all possible burst errors. This is possible in m− p + 1 ways for each case. Definition 12. W p×r m×s (t) = ms ∑ i=0 wi t i is called the burst weight enumerator of burst errors of order p× r in the space Mm×s(R). Now, it is clear that by setting X1 = X2 = · · ·= X p = t in W (X̃ ) we obtain the burst weight enumerator W p×r m×s (t) = ∑ms i=0 wi t i . Example 9. The weight spectra polynomial of burst errors of order 2×3 in the space of matrices M3×5(F2) is computed in the following way. First, the weight spectra polynomial of burst of errors of order 2× 3 in the space of matrices M2×3(F2) is already computed in Example 3. Next, by Lemma 3 by applying T (H) and T 2(H), we get all possible weight distributions of the terms that correspond to burst errors. H + T (H) + T 2(H) = 3X 3 1 X 5 2 + 4X 5 1 X 4 2 + 12X 5 1X 5 2 + 5X 4 1 X 5 2 + 6X 5 1 X 3 2 + X 3 1 X 7 2 + 2X 7 1 X 5 2 + X 4 1 X 7 2 + 3X 2 1 X 4 2 + 4X 4 1 X 3 2 + 12X 4 1 X 4 2 + 5X 3 1 X 4 2 + 4X 4 1 X 2 2 + X 2 1 X 6 2 + 2X 6 1 X 4 2 İ. Siap / Eur. J. Pure Appl. Math, 3 (2010), 653-669 667 + X 3 1 X 6 2 + 3X1X 3 2 + 4X 2 2 X 3 1 + 12X 3 1 X 3 2 + 5X 3 2 X 2 1 + 4X2X 3 1 + X1X 5 2 + X 5 2 X 2 1 . Setting X = Y = t and multiplying by p− r + 1 in W (X̃ ) = 2(H + T (H) + T 2(H)), we obtain W 2×3 3×5 (t) = 4t12 + 2t11 + 30t10 + 20t9 + 44t8 + 20t7+ 40t6 + 18t5 + 14t4. Hence, the number of burst errors of ρ-weight 3 or less is equal to T 2×2 3×3 (F2, 3) = 10+ 6+ 2. Corollary 3. By substituting X i = t in W (X̃ ), we obtain W p×r m×s (t) which is the weight enumerator of bursts of order p× r in Mm×s(R). Further, B p×r m×s(R, w) = w ∑ i=1 wi where wi ’s are the coefficients of W p×r m×s (t). 4. Some Applications From previous sections we have presented a constructive method for computing B p×r m×s(R) and B p×r m×s(R, w). By making use of these results we have the following theorems: Theorem 6. Let C be an array code over R. If C corrects all burst errors of type p× r, then |R|ms |C | ≥ 1+ B p×r m×s(R) (3) where “| · |” stands for the cardinality of the set. Proof. C is an abelian additive group. If C corrects all burst errors of type p× r, then all these bursts must fall into different cosets. So the number of cosets including C itself should be larger or equal to the number of burst errors plus one which stands for zero codeword. A similar argument that depends on syndrome decoding leads to the following theorem: Theorem 7. Let C be an array code over R. If C corrects all burst errors of type p × r and RT-weight equal to w or less, then |R|ms |C | ≥ 1+ p ∑ i=1 r ∑ j=1 B i× j m×s(R, w). (4) Burst error correction is based on assumption of errors occurring nearby and sometimes in particular predesigned places. Reiger [6] proved an inequality by assuming predesigned burst errors (burst errors occurring in the last consecutive digits) for block codes over fields. Later, Jain in [5] extended these results for array codes over finite fields. Here, we extend them further for array codes over finite commutative rings. REFERENCES 668 Theorem 8 ((A Reiger’s Type Bound)). Let C be an array code over R with no burst errors of type p× r or smaller in a predesigned place of size p× r. Then, |R|ms |C | ≥ qpr . (5) Proof. Without loss of generality, we may assume that the predesigned place is the first p rows and the first r columns of size p× r. In other words we assume that the burst errors of size may appear only in this place. Two different bursts of this type does not fall into the same coset. Otherwise, If two different burst errors of this type fall into the same coset, then their the difference will be a codeword in the code. This will lead to a contradiction since the array code does not contain such burst errors. Hence, the number of cosets must be larger or equal to the number of all possible burst errors of type p× r which equals to qpr . 5. Conclusion A new approach that avoids solving integer inequalities on enumerating burst errors of arrays is presented. This method is applied to array codes over finite rings which is a general- ization of previous results. Finally, some applications of the results are presented . ACKNOWLEDGEMENTS The author is thankful to the referee(s) for their valuable remarks that helped on improving the presentation of the paper. References [1] K.A.S. Abdel-Ghaffar, R.J. McEliece, and H.C.A. van Tilborg, Two Dimensional Burst Iden- tification Codes and their Use in Burst Correction, IEEE Trans. Inf. Theory, vol. 34, No. 3, pp. 494-504, May 1998. [2] M. Blaum and P.G. Farell, Array Codes For Cluster Error Correction, Elec. Letters, vol. 30, No. 21, pp.1752-1753, oct. 1994. [3] Steven T. Dougherty and Maxim M. Skriganov, MacWilliams Duality and the Rosenbloom- Tsfasman Metric, Moscow Mathematical Journal, Vol. 2 Number 1, p. 83-89, 2002. [4] P. Fire, A class of Multiple Error Correcting Binary Codes for Non-independent Errors, Sylvania Reports RSL-E-2, Sylvania Reconnaissance Systems, Mountain View, California, 1959. [5] Sapna Jain, Bursts in m- Metric Array Codes, Linear Algebra and Its Applications, Vol. 418, p.130-141, 2006. [6] S.H. Reiger, Codes for the Correction of Clustered Errors, IRE Transc. On Information Theory, Vol. 6, pp. 16-21, 1960. REFERENCES 669 [7] M. Yu Rosenbloom and M. A. Tsfasman, Codes for the m-metric, Problems of Information Transmission, Vol. 33. No. 1, pp. 45-52, 1997. [8] M.M. Skriganov, Coding Theory and Uniform Distributions, St. Petersburg Math. J. Vol 143, No. 2, 2002. [9] Irfan Siap, The Complete Weight Enumerator for Codes overM n×s(Fq), Lecture Notes on Computer Sciences 2260, pp. 20-26, 2001. [10] Irfan Siap, CT Burst Error Weight Enumerator Of Array Codes, Albanian Journal of Math- ematics, Vol. 2, No. 3, pp. 171-178, 2008. [11] Moshe Shwartz and Tuvi Etzion, Two Dimensional Cluster-Correcting Codes, IEEE Trans. on Info. Theory, Vol. 51, No. 6, pp. 2121-2132 June 2005.