Error Locating Codes Dealing with Repeated Low-Density Burst Errors B. K. Dass Department of Mathematics University of Delhi Delhi-110 007, India e-mail: dassbk@rediffmail.com Ritu Arora∗ Department of Mathematics JDM College (University of Delhi) Sir Ganga Ram Hospital Marg New Delhi-110 060, India e-mail: rituaroraind@gmail.com Abstract. This paper presents a study of linear codes which are capable to detect and locate errors which are repeated low-density bursts of length b(fixed) with weight w or less. An illustration for such a kind of code has also been provided. Keywords: Error locating codes, burst errors, burst errors of length of b(fixed), repeated low-density burst errors of length b(fixed). AMS Subject Classification: 94B20, 94B65, 94B25. ∗Corresponding author. Ratio Mathematica, 20, 2010 67 1 Introduction Burst errors are the type of errors that occur quite frequently in several communication channels. Codes developed to detect and correct such errors have been studied extensively by many authors. Abramson [1959] developed codes which dealt with the correction of single and double adjacent errors, which was extended by Fire [1959] as a more general concept called ‘burst errors’. A burst of length b is defined as follows: Definition 1. A burst of length b is a vector whose only non-zero components are among some b consecutive components, the first and the last of which is non-zero. The nature of burst errors differs from channel to channel depending upon the kind of channel. Chien and Tang [1965] proposed a modification in the definition of a burst and they defined a burst of length b, which shall be called as CT-burst of length b, as follows: Definition 2. A CT-burst of length b is a vector whose only non-zero components are confined to some b consecutive positions, the first of which is non-zero. Channels due to Alexander, Gryb and Nast [1960] fall in this category. This definition was further modified by Dass [1980] as follows: Definition 3. A burst of length b(fixed) is an n-tuple whose only non-zero components are confined to b consecutive positions, the first of which is non-zero and the number of its starting positions is among the first n−b+1 components. Ratio Mathematica, 20, 2010 68 This definition is useful for channels not producing errors near the end of a code word. In very busy communication channels errors repeat themselves. So is a situation when errors occur in the form of bursts. Dass, Garg and Zannetti [2008] studied this kind of repeated burst errors. They termed such errors as m-repeated burst errors of length b(fixed) which has been defined as follows: Definition 4. An m-repeated bursts of length b(fixed) is an n-tuple whose only non-zero components are confined to m distinct sets of b consecutive digits, the first component of each set is non-zero and the number of its starting positions is among the first n − mb + 1 components. In particular a 2-repeated bursts of length b(fixed) has been defined by Dass and Garg [2009(a)] as follows: Definition 5. A 2-repeated bursts of length b(fixed) is an n-tuple whose only non-zero components are confined to 2 distinct sets of b consecutive digits, the first component of each set is non-zero and the number of its starting positions is among the first n − 2b + 1 components. During the process of transmission some disturbances cause occur- rence of burst errors in such a way that over a given length, some digits are received correctly while others get corrupted i.e. not all the digits inside a burst are in error. Such bursts are termed as low-density bursts [Wyner (1963)]. A low-density burst of length b(fixed) with weight w or less has been defined as follows: Ratio Mathematica, 20, 2010 69 Definition 6. A low-density burst of length b(fixed) with weight w or less is an n-tuple whose only non-zero components are confined to some b consecutive positions, the first of which is non-zero with at most w (w ≤ b) non-zero components within such b consecutive digits and the number of starting positions of the burst is among the first n − b + 1 components. Dass and Garg [2009(b)] studied codes which are capable to detect and/or correct m-repeated low-density bursts of length b(fixed) with weight w or less. They defined such codes as follows: Definition 7. An m-repeated low-density burst of length b(fixed) with weight w or less is an n-tuple whose only non-zero components are confined to m distinct sets of b consecutive positions, the first component of each set is non-zero where each set can have at most w non-zero components (w ≤ b), and the number of its starting positions in an n-tuple is among the first n − mb + 1 positions. In particular, a 2-repeated low-density burst of length b(fixed) with weight w or less has been defined as follows: Definition 8. A 2-repeated low-density burst of length b(fixed) with weight w or less is an n-tuple whose only non-zero components are confined to two distinct sets of b consecutive positions, the first component of each set is non-zero where each set can have at most w non-zero components (w ≤ b), and the number of its starting positions in an n-tuple is among the first n − 2b + 1 positions. Ratio Mathematica, 20, 2010 70 As an illustration, (21010000102000) is a 2-repeated low-density burst of length up to 6(fixed) with weight 3 or less over GF(3) whereas (001000011110) is a 2-repeated low-density burst of length at most 5(fixed) with weight 4 or less over GF(2). In this paper we have presented a study of codes dealing with the location of such kind of errors occurring within a sub-block. The concept of error-locating codes, lying midway between error detection and error correction, was introduced by Wolf and Elspas [1963]. In this technique the block of received digits is to be regarded as subdivided into mutually exclusive sub-blocks and while decoding it is possible to detect the error and in addition the receiver is able to identify which particular sub-block contains error. Such codes are referred to as Error-Locating codes (EL- codes). Wolf and Elspas [1963] studied binary codes which are capable of detecting and locating a single sub-block containing random errors. A study of codes locating burst errors of length b(fixed) has been made by Dass and Kishanchand [1986]. Dass and Arora [2010] obtained bounds for codes capable of locating repeated burst errors of length b(fixed) occurring within a sub-block. In this paper we have obtained bounds on the number of check digits required to locate 2-repeated low-density bursts of length b(fixed), and m-repeated low-density bursts of length b(fixed). An illustration of such a code has also been given. Development of such codes will economize in the number of parity-check digits required in comparison to the usual low- density burst error locating codes while considering such repeated bursts as single bursts. Ratio Mathematica, 20, 2010 71 The paper has been organized as follows. In section 2 the necessary condition for the detection and location of 2-repeated low-density burst of length b(fixed) with weight w or less has been derived. This is followed by a sufficient condition for the existence of such a code. An illustration of 2-repeated low-density burst of length b(fixed) with weight w or less over GF(2) has also been given. In section 3 a necessary condition for the detection and location of m-repeated low-density burst of length b(fixed) with weight w or less has been given followed by a sufficient condition for the existence of such a code. In what follows we shall consider a linear code to be a subspace of n- tuples over GF(q). The block of n digits, consisting of r check digits and k = n − r information digits, is considered to be divided into s mutually exclusive sub-blocks. Each sub-block contains t = n/s digits. 2 2-Repeated Low-density Burst Error Locating Codes In this section, we consider (n, k) linear codes over GF(q) that are capable of detecting and locating all 2-repeated low-density burst of length b(fixed) with weight w or less within a single sub-block. It may be noted that an EL-code capable of detecting and locating a single sub-block containing an error which is in the form of a 2-repeated low-density bursts of length b(fixed) with weight w or less must satisfy the following conditions: (a) The syndrome resulting from the occurrence of a 2-repeated low- density burst of length b(fixed) with weight w or less within any one 6 Ratio Mathematica, 20, 2010 72 sub-block must be distinct from the all zero syndrome. (b) The syndrome resulting from the occurrence of any 2-repeated low- density burst of length b(fixed) with weight w or less within a single sub-block must be distinct from the syndrome resulting likewise from any 2-repeated low-density burst of length b(fixed) with weight w or less within any other sub-block. In this section we shall derive two results. The first result derives a lower bound on the number of check digits required for the existence of a linear code over GF(q) capable of detecting and locating a single sub-block containing errors that are 2-repeated low-density burst of length b(fixed) with weight w or less. In the second result, an upper bound on the number of check digits which ensures the existence of such a code has been derived. As the code is divided into several blocks of length t each and we wish to detect a 2-repeated low-density burst of length b(fixed) with weight w or less, we may come across with a situation when the difference between 2b and t (b + w and t) becomes narrow. We note that if t−b + 1 < b + w and if we consider any two 2-repeated low-density bursts x1 and x2 of length b(fixed) with weight w or less such that their non-zero components are confined to first t − b + 1 positions with w components confining to some fixed w positions out of first b consecutive positions then their difference x1 - x2 is again a 2-repeated low-density burst of length b(fixed) with weight w or less. However if we do not restrict ourselves to first t − b + 1 positions then we may not get a 2-repeated burst of length b(fixed) with weight w or less. This may be better understood with the help of the following examples: Ratio Mathematica, 20, 2010 73 Example 1. Let t = 9, b = 4, w = 3 and q = 2. So that t − b + 1 = 6 < b + w(= 7). Let x1 = (101101001) and x2 = (100101011). Then x1 and x2 are 2-repeated low-density burst of length 4(fixed) with weight 3 or less whereas x1 − x2 = (001000010) is not a 2-repeated burst of length 4(fixed). Example 2. Let t = 11, b = 5, w = 3 and q = 2. Let x1 = (10101010010) and x2 = (10101010001) Then x1 and x2 are 2-repeated low-density burst of length 5(fixed) with weight 3 or less whereas x1 − x2 = (00000000011) which is not even a 2-repeated burst of length 4(fixed) what to talk of its weight. So, accordingly we discuss the following cases: Case 1: When t − b + 1 ≥ 2b. Let X be the collection of all those vectors in which all the non- zero components are confined to some fixed w positions out of two sets of b consecutive positions each i.e. l -th to (l + b)-th position and j -th to (j + b)-th position where j > l + b. We observe that the syndromes of all the elements of X should be different; else for any x1, x2 belonging to X having the same syndrome would imply that the syndrome of x1 − x2 which is also an element of X and hence a 2-repeated low density burst of length b(fixed) with weight w or less within the same sub-block becomes zero; in violation of condition (a). Also, since the error locates a single sub-block containing errors that are 2-repeated low-density bursts of length b(fixed) of weight w or less, Ratio Mathematica, 20, 2010 74 the syndromes produced by similar vectors in different sub-blocks must be distinct by condition (b). Thus the syndromes of vectors which are 2-repeated low-density burst of length b(fixed) with weight w or less in fixed positions, whether in the same sub-block or in different sub-blocks, must be distinct. (It may be noted that the choice of different fixed components in different sub-blocks will also yield the same result). As there are (q2w − 1) distinct non-zero syndromes corresponding to the vectors in any one sub-block and there are s sub-blocks in all, so we must have atleast (1 + s(q2w −1)) distinct syndromes counting the all zero syndrome. As maximum number of distinct syndromes available using r check bits is qr , so there are qr distinct syndromes in all, therefore we must have qr ≥ {1 + s(q2w − 1)} (1) where t − b + 1 ≥ 2b. Case 2: When b + w ≤ t − b + 1 < 2b. Let X be the collection of all those vectors in which all the non- zero components are confined to some w fixed positions out of first b components i.e first and b-th position and another set of w fixed positions out of (b + 1)-th to (t − b + 1)-th positions. As discussed in case 1 the syndromes of all the elements of X is different. In this case also, there are (q2w − 1) distinct non-zero syndromes corresponding to the vectors in any one sub-block and there are s sub- Ratio Mathematica, 20, 2010 75 blocks in all, so we must have atleast (1 + s(q2w − 1)) distinct syndromes counting the all zero syndrome. So, in this case also, we must have qr ≥ {1 + s(q2w − 1)} (2) where b + w ≤ t − b + 1 < 2b. Case 3: When t − b + 1 < b + w . In this case consider X to be collection of all those vectors in which all the non-zero components are confined to some w fixed positions out of first b positions and t − 2b + 1 components from (b + 1)-th to (t − b + 1)- th positions. In this case there are (qw+(t−2b+1) − 1) distinct non-zero syndromes corresponding to the vectors in any one sub-block. As and there are s sub-blocks in all, so we must have atleast (1+s(qw+(t−2b+1)−1)) distinct syndromes counting the all zero syndrome. Therefore in this case, we must have qr ≥ {1 + s(qw+(t−2b+1) − 1)} (3) where t − b + 1 < b + w . From (1), (2), and (3) we have r ≥    logq{1 + s(q2w − 1)} where t − b + 1 ≥ 2b and b + w ≤ t − b + 1 < 2b logq{1 + s(qw+(t−2b+1) − 1)} where t − b + 1 < b + w. Thus we have proved: Theorem 1. The number of parity check digits r in an (n, k) linear code subdivided into s sub-blocks of length t each, that locates a single corrupted Ratio Mathematica, 20, 2010 76 sub-block containing errors that are 2-repeated low density burst of length b(fixed) with weight w or less is at least    logq{1 + s(q2w − 1)} where t − b + 1 ≥ 2b and b + w ≤ t − b + 1 < 2b logq{1 + s(qw+(t−2b+1) − 1)} where t − b + 1 < b + w . Remark 1. For w = b, the weight consideration over the burst becomes redundant and the result coincides with Theorem 1[Dass and Arora [2010]], when the bursts considered are 2-repeated bursts of length b(fixed). In the following result we derive another bound on the number of check digits required for the existence of such a code. The proof is based on the technique used to establish Varshomov-Gilbert Sacks bound by constructing a parity check matrix for such a code [refer Sacks[1958], also Theorem 4.7 Peterson and Weldon[1972]]. This technique not only ensures the existence of such a code but also gives a method for the construction of such a code. Theorem 2. An (n, k) linear EL-code over GF(q) capable of detecting a 2-repeated low density burst of length b(fixed) with weight w or less (w ≤ b) within a single sub-block and of locating that sub-block can always be constructed provided that qn−k > [1 + (q − 1)](b−1,w−1){1 + (q − 1)(t − 2b + 1)[1 + (q − 1)](b−1,w−1)} · { 1 + (s − 1) 2∑ i=1 ( t − ib + i i ) (q − 1)i{[1 + (q − 1)](b−1,w−1)}i } (4) where [1 + x](m,r) denotes the incomplete binomial expansion of (1 + x)m up to the term xr in ascending power of x, viz. [1 + x](m,r) = 1 + ( m 1 ) x + ( m 2 ) x2 + . . . + ( m r ) xr. Ratio Mathematica, 20, 2010 77 Proof. The existence of such a code will be shown by constructing an appropriate (n − k × n) parity check matrix H by a synthesis procedure. For that we first construct a matrix H1 from which the requisite parity check matrix H shall be obtained by reversing the order of the columns of each sub-block. After adding (s−1)t columns appropriately corresponding to the first (s − 1) sub-blocks, suppose that we have added the first j − 1 columns h1, h2, . . . , hj−1 of the s-th sub-block also, out of which the first b − 1 columns h1, h2, . . . , hb−1 may be chosen arbitrarily (non-zero). We now lay down the condition to add the j -th column hj to H1 as follows: According to condition (a), for the detection of 2-repeated low- density burst of length b(fixed) with weight w or less in the s-th sub-block hj should not be a linear combination of any w−1 or fewer columns among the immediately preceding b − 1 columns hj−b+1, hj−b+2, . . . hj−1 together with any w or fewer columns from amongst some b consecutive columns from the first j − b columns of the s-th sub-block. i.e. hj 6= (αj1 hj1 +αj2 hj2 + . . . +αjw−1 hjw−1 ) +(βl1 hl1 +βl2 hl2 + . . . +βlw hlw ) (5) where hj1 , hj2 , . . . , hjw−1 are any w−1 columns among hj−b+1, hj−b+2, . . . hj−1 and hl ’s are any w columns from a set of b consecutive columns among the first j−b columns of the s-th sub-block such that either all the coefficients βli ’s are zero or if the p-th coefficient βlp is the last non-zero coefficients then b ≤ p ≤ j − b; αji ’s, βli ’s ∈ GF(q). Ratio Mathematica, 20, 2010 78 The number of ways in which the coefficients αi ’s can be selected is [1 + (q − 1)](b−1,w−1) . To enumerate the coefficients βi ’s is equivalent to enumerate the number of bursts of length b(fixed) with weight w or less in a vector of length j − b. This number including the vector of all zeros [refer Theorem 1, Dass [1983]] is 1 + (j − 2b + 1)(q − 1)[1 + (q − 1)](b−1,w−1) So, the number of linear combinations on the right hand side of (5) is [1 + (q − 1)](b−1,w−1)[1 + (j − 2b + 1)(q − 1)[1 + (q − 1)](b−1,w−1)] (6) According to condition (b), for the location of 2-repeated low-density bursts of length b(fixed) with weight w or less, hj should not be a linear combination of any w − 1 or fewer columns among the immediately preceding the b−1 columns and any w columns from a set of b consecutive columns from the remaining j − b columns of the s-th sub-block along with any w or less columns each from any of the two sets of b consecutive columns out of any one of the previously chosen s − 1 sub-blocks, the coefficient of the last column of either both or one of the sets being non- zero. The number of 2-repeated low-density bursts of length b(fixed) with weight w or less in a sub-block of length t [refer Dass and Garg [2009(b)]] is 2∑ i=1 ( t − ib + i i ) (q − 1)i{[1 + (q − 1)](b−1,w−1)}i (7) Since there are (s−1) previous sub-blocks, therefore number of such linear Ratio Mathematica, 20, 2010 79 combinations becomes (s − 1) 2∑ i=1 ( t − ib + i i ) (q − 1)i{[1 + (q − 1)](b−1,w−1)}i (8) So, for the location of 2-repeated low-density burst of length b(fixed) with weight w or less the number of linear combinations to which hj can not be equal to is the product of expr.(6) and expr.(8) i.e. expr.(6) × expr.(8) (9) Thus the total number of linear combinations to which hi can not be equal to is the sum of exp.(6) and exp.(9) At worst all these combinations might yield distinct sum. Therefore hi can be added to the s-th sub-block provided that qn−k > [1 + (q − 1)](b−1,w−1){1 + (q − 1)(j − 2b + 1)[1 + (q − 1)](b−1,w−1)} · { 1 + (s − 1) 2∑ i=1 ( t − ib + i i ) (q − 1)i{[1 + (q − 1)](b−1,w−1)}i } To obtain the length of the block as t we replace j by t in the above expression. The required parity-check matrix H can be obtained from H1 by reversing the order of the columns in each sub-block. Remark 2. For w = b, the weight consideration over the burst becomes redundant and the inequality in Theorem 2 reduces to qn−k > qb−1{1 + (q − 1)(t − 2b + 1)qb−1} × { 1 + (s − 1) 2∑ i=1 ( t − ib + i i ) (q − 1)iqi(b−1) } Ratio Mathematica, 20, 2010 80 which coincides with the condition for the location of 2-repeated burst of length b(fixed) [refer Theorem 2, Dass and Arora [2010]]. We conclude this section with the following example: Example 3. For an (27,15) linear code over GF(2) consider the following 12 × 27 matrix H which has been constructed by the synthesis procedure given in the proof of theorem 2 by taking s = 3, t = 9, b = 3, w = 2. H =   0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 1   The null space of this matrix can be used as a code to locate a sub- block of length t = 9 containing 2-repeated burst of length 3(fixed). From the error pattern syndrome Table 1 we observe that: The syndromes of 2-repeated burst of length 3(fixed) within any sub- block are all non-zero showing thereby that the code detects all 2-repeated low-density bursts of length 3(fixed) with weight 2 or less occurring within a sub-block. Ratio Mathematica, 20, 2010 81 It has been verified through MS-Excel program that the syndromes of the 2-repeated bursts of length 3(fixed) with weight 2 or less in any sub-block is different from the syndrome of a 2-repeated burst of length 3(fixed) with weight 2 or less within any other sub-block. Table 1 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 1 1 100100000 000000000 000000000 0000 0100 1000 2 100101000 000000000 000000000 0001 0100 1000 3 100110000 000000000 000000000 0000 1100 1000 4 101100000 000000000 000000000 0000 0110 1000 5 101101000 000000000 000000000 0001 0110 1000 6 101110000 000000000 000000000 0000 1110 1000 7 110100000 000000000 000000000 0000 0101 1000 8 110101000 000000000 000000000 0001 0101 1000 9 110110000 000000000 000000000 0000 1101 1000 10 100010000 000000000 000000000 0000 1000 1000 11 100010100 000000000 000000000 0010 1000 1000 12 100011000 000000000 000000000 0001 1000 1000 13 101010000 000000000 000000000 0000 1010 1000 14 101010100 000000000 000000000 0010 1010 1000 15 101011000 000000000 000000000 0001 1010 1000 16 110010000 000000000 000000000 0000 1001 1000 17 110010100 000000000 000000000 0010 1001 1000 18 110011000 000000000 000000000 0001 1001 1000 19 100001000 000000000 000000000 0001 0000 1000 20 100001010 000000000 000000000 0101 0000 1000 21 100001100 000000000 000000000 0011 0000 1000 22 101001000 000000000 000000000 0001 0010 1000 23 101001010 000000000 000000000 0101 0010 1000 24 101001100 000000000 000000000 0011 0010 1000 25 110001000 000000000 000000000 0001 0001 1000 26 110001010 000000000 000000000 0101 0001 1000 27 110001100 000000000 000000000 0011 0001 1000 28 100000100 000000000 000000000 0010 0000 1000 29 100000101 000000000 000000000 1010 0000 1000 Ratio Mathematica, 20, 2010 82 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 1 30 100000110 000000000 000000000 0110 0000 1000 31 101000100 000000000 000000000 0010 0010 1000 32 101000101 000000000 000000000 1010 0010 1000 33 101000110 000000000 000000000 0110 0010 1000 34 110000100 000000000 000000000 0010 0001 1000 35 110000101 000000000 000000000 1010 0001 1000 36 110000110 000000000 000000000 0110 0001 1000 37 010010000 000000000 000000000 0000 1001 0000 38 010010100 000000000 000000000 0010 1001 0000 39 010011000 000000000 000000000 0001 1001 0000 40 010110000 000000000 000000000 0000 1101 0000 41 010110100 000000000 000000000 0010 1101 0000 42 010111000 000000000 000000000 0001 1101 0000 43 011010000 000000000 000000000 0000 1011 0000 44 011010100 000000000 000000000 0010 1011 0000 45 011011000 000000000 000000000 0001 1011 0000 46 010001000 000000000 000000000 0001 0001 0000 47 010001010 000000000 000000000 0101 0001 0000 48 010001100 000000000 000000000 0011 0001 0000 49 010101000 000000000 000000000 0001 0101 0000 50 010101010 000000000 000000000 0101 0101 0000 51 010101100 000000000 000000000 0011 0101 0000 52 011001000 000000000 000000000 0001 0011 0000 53 011001010 000000000 000000000 0101 0011 0000 54 011001100 000000000 000000000 0011 0011 0000 55 010000100 000000000 000000000 0010 0001 0000 56 010000101 000000000 000000000 1010 0001 0000 57 010000110 000000000 000000000 0110 0001 0000 58 010100100 000000000 000000000 0010 0101 0000 59 010100101 000000000 000000000 1010 0101 0000 60 010100110 000000000 000000000 0110 0101 0000 61 011000100 000000000 000000000 0010 0011 0000 62 011000101 000000000 000000000 1010 0011 0000 63 011000110 000000000 000000000 0110 0011 0000 64 001001000 000000000 000000000 0001 0010 0000 65 001001010 000000000 000000000 0101 0010 0000 66 001001100 000000000 000000000 0011 0010 0000 Ratio Mathematica, 20, 2010 83 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 1 67 001011000 000000000 000000000 0001 1010 0000 68 001011010 000000000 000000000 0101 1010 0000 69 001011100 000000000 000000000 0011 1010 0000 70 001101000 000000000 000000000 0001 0110 0000 71 001101010 000000000 000000000 0101 0110 0000 72 001101100 000000000 000000000 0011 0110 0000 73 001000100 000000000 000000000 0010 0010 0000 74 001000101 000000000 000000000 1010 0010 0000 75 001000110 000000000 000000000 0110 0010 0000 76 001010100 000000000 000000000 0010 1010 0000 77 001010101 000000000 000000000 1010 1010 0000 78 001010110 000000000 000000000 0110 1010 0000 79 001100100 000000000 000000000 0010 0110 0000 80 001100101 000000000 000000000 1010 0110 0000 81 001100110 000000000 000000000 0110 0110 0000 82 000100100 000000000 000000000 0010 0100 0000 83 000100101 000000000 000000000 1010 0100 0000 84 000100110 000000000 000000000 0110 0100 0000 85 000101100 000000000 000000000 0011 0100 0000 86 000101101 000000000 000000000 1011 0100 0000 87 000101110 000000000 000000000 0111 0100 0000 88 000110100 000000000 000000000 0010 1100 0000 89 000110101 000000000 000000000 1010 1100 0000 90 000110110 000000000 000000000 0110 1100 0000 91 100000000 000000000 000000000 0000 0000 1000 92 101000000 000000000 000000000 0000 0010 1000 93 110000000 000000000 000000000 0000 0001 1000 94 010000000 000000000 000000000 0000 0001 0000 95 010100000 000000000 000000000 0000 0101 0000 96 011000000 000000000 000000000 0000 0011 0000 97 001000000 000000000 000000000 0000 0010 0000 98 001010000 000000000 000000000 0000 1010 0000 99 001100000 000000000 000000000 0000 0110 0000 100 000100000 000000000 000000000 0000 0100 0000 101 000101000 000000000 000000000 0001 0100 0000 102 000110000 000000000 000000000 0000 1100 0000 Ratio Mathematica, 20, 2010 84 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 1 103 000010000 000000000 000000000 0000 1000 0000 104 000010100 000000000 000000000 0010 1000 0000 105 000011000 000000000 000000000 0001 1000 0000 106 000001000 000000000 000000000 0001 0000 0000 107 000001010 000000000 000000000 0101 0000 0000 108 000001100 000000000 000000000 0011 0000 0000 109 000000100 000000000 000000000 0010 0000 0000 110 000000101 000000000 000000000 1010 0000 0000 111 000000110 000000000 000000000 0110 0000 0000 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 2 112 000000000 100100000 000000000 0011 0000 1100 113 000000000 100101000 000000000 1111 0000 1100 114 000000000 100110000 000000000 1111 0000 1111 115 000000000 101100000 000000000 1001 1010 0110 116 000000000 101101000 000000000 0101 1010 0110 117 000000000 101110000 000000000 0101 1010 0101 118 000000000 110100000 000000000 1101 1110 0010 119 000000000 110101000 000000000 0001 1110 0010 120 000000000 110110000 000000000 0001 1110 0001 121 000000000 100010000 000000000 0011 1100 0011 122 000000000 100010100 000000000 0011 1100 0010 123 000000000 100011000 000000000 1111 1100 0011 124 000000000 101010000 000000000 1001 0110 1001 125 000000000 101010100 000000000 1001 0110 1000 126 000000000 101011000 000000000 0101 0110 1001 127 000000000 110010000 000000000 1101 0010 1101 128 000000000 110010100 000000000 1101 0010 1100 129 000000000 110011000 000000000 0001 0010 1101 130 000000000 100001000 000000000 0011 1100 0000 131 000000000 100001010 000000000 0011 1100 0010 132 000000000 100001100 000000000 0011 1100 0001 133 000000000 101001000 000000000 1001 0110 1010 134 000000000 101001010 000000000 1001 0110 1000 135 000000000 101001100 000000000 1001 0110 1011 136 000000000 110001000 000000000 1101 0010 1110 Ratio Mathematica, 20, 2010 85 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 2 137 000000000 110001010 000000000 1101 0010 1100 138 000000000 110001100 000000000 1101 0010 1111 139 000000000 100000100 000000000 1111 1100 0001 140 000000000 100000101 000000000 1111 1100 0101 141 000000000 100000110 000000000 1111 1100 0011 142 000000000 101000100 000000000 0101 0110 1011 143 000000000 101000101 000000000 0101 0110 1111 144 000000000 101000110 000000000 0101 0110 1001 145 000000000 110000100 000000000 0001 0010 1111 146 000000000 110000101 000000000 0001 0010 1011 147 000000000 110000110 000000000 0001 0010 1101 148 000000000 010010000 000000000 0010 1110 1101 149 000000000 010010100 000000000 0010 1110 1100 150 000000000 010011000 000000000 1110 1110 1101 151 000000000 010110000 000000000 1110 0010 0001 152 000000000 010110100 000000000 1110 0010 0000 153 000000000 010111000 000000000 0010 0010 0001 154 000000000 011010000 000000000 1000 0100 0111 155 000000000 011010100 000000000 1000 0100 0110 156 000000000 011011000 000000000 0100 0100 0111 157 000000000 010001000 000000000 0010 1110 1110 158 000000000 010001010 000000000 0010 1110 1100 159 000000000 010001100 000000000 0010 1110 1111 160 000000000 010101000 000000000 1110 0010 0010 161 000000000 010101010 000000000 1110 0010 0000 162 000000000 010101100 000000000 1110 0010 0011 163 000000000 011001000 000000000 1000 0100 0100 164 000000000 011001010 000000000 1000 0100 0110 165 000000000 011001100 000000000 1000 0100 0101 166 000000000 010000100 000000000 1110 1110 1111 167 000000000 010000101 000000000 1110 1110 1011 168 000000000 010000110 000000000 1110 1110 1101 169 000000000 010100100 000000000 0010 0010 0011 170 000000000 010100101 000000000 0010 0010 0111 171 000000000 010100110 000000000 0010 0010 0001 172 000000000 011000100 000000000 0100 0100 0101 173 000000000 011000101 000000000 0100 0100 0001 Ratio Mathematica, 20, 2010 86 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 2 174 000000000 011000110 000000000 0100 0100 0111 175 000000000 001001000 000000000 0110 1010 1010 176 000000000 001001010 000000000 0110 1010 1000 177 000000000 001001100 000000000 0110 1010 1011 178 000000000 001011000 000000000 1010 1010 1001 179 000000000 001011010 000000000 1010 1010 1011 180 000000000 001011100 000000000 1010 1010 1000 181 000000000 001101000 000000000 1010 0110 0110 182 000000000 001101010 000000000 1010 0110 0100 183 000000000 001101100 000000000 1010 0110 0111 184 000000000 001000100 000000000 1010 1010 1011 185 000000000 001000101 000000000 1010 1010 1111 186 000000000 001000110 000000000 1010 1010 1001 187 000000000 001010100 000000000 0110 1010 1000 188 000000000 001010101 000000000 0110 1010 1100 189 000000000 001010110 000000000 0110 1010 1010 190 000000000 001100100 000000000 0110 0110 0111 191 000000000 001100101 000000000 0110 0110 0011 192 000000000 001100110 000000000 0110 0110 0101 193 000000000 000100100 000000000 1100 1100 1101 194 000000000 000100101 000000000 1100 1100 1001 195 000000000 000100110 000000000 1100 1100 1111 196 000000000 000101100 000000000 0000 1100 1101 197 000000000 000101101 000000000 0000 1100 1001 198 000000000 000101110 000000000 0000 1100 1111 199 000000000 000110100 000000000 0000 1100 1110 200 000000000 000110101 000000000 0000 1100 1010 201 000000000 000110110 000000000 0000 1100 1100 202 000000000 100000000 000000000 1111 1100 0000 203 000000000 101000000 000000000 0101 0110 1010 204 000000000 110000000 000000000 0001 0010 1110 205 000000000 010000000 000000000 1110 1110 1110 206 000000000 010100000 000000000 0010 0010 0010 207 000000000 011000000 000000000 0100 0100 0100 208 000000000 001000000 000000000 1010 1010 1010 209 000000000 001010000 000000000 0110 1010 1001 210 000000000 001100000 000000000 0110 0110 0110 211 000000000 000100000 000000000 1100 1100 1100 Ratio Mathematica, 20, 2010 87 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 2 212 000000000 000101000 000000000 0000 1100 1100 213 000000000 000110000 000000000 0000 1100 1111 214 000000000 000010000 000000000 1100 0000 0011 215 000000000 000010100 000000000 1100 0000 0010 216 000000000 000011000 000000000 0000 0000 0011 217 000000000 000001000 000000000 1100 0000 0000 218 000000000 000001010 000000000 1100 0000 0010 219 000000000 000001100 000000000 1100 0000 0001 220 000000000 000000100 000000000 0000 0000 0001 221 000000000 000000101 000000000 0000 0000 0101 222 000000000 000000110 000000000 0000 0000 0011 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 3 223 000000000 000000000 100100000 1111 1110 0111 224 000000000 000000000 100101000 1101 0111 0011 225 000000000 000000000 100110000 1000 1110 1001 226 000000000 000000000 101100000 0111 0111 1000 227 000000000 000000000 101101000 0101 1110 1100 228 000000000 000000000 101110000 0000 0111 0110 229 000000000 000000000 110100000 1111 1110 1101 230 000000000 000000000 110101000 1101 0111 1001 231 000000000 000000000 110110000 1000 1110 0011 232 000000000 000000000 100010000 1000 1111 0110 233 000000000 000000000 100010100 0110 0000 0001 234 000000000 000000000 100011000 1010 0110 0010 235 000000000 000000000 101010000 0000 0110 1001 236 000000000 000000000 101010100 1110 1001 1110 237 000000000 000000000 101011000 0010 1111 1101 238 000000000 000000000 110010000 1000 1111 1100 239 000000000 000000000 110010100 0110 0000 1011 240 000000000 000000000 110011000 1010 0110 1000 241 000000000 000000000 100001000 1101 0110 1100 242 000000000 000000000 100001010 0011 0110 1011 243 000000000 000000000 100001100 0011 1001 1011 244 000000000 000000000 101001000 0101 1111 0011 Ratio Mathematica, 20, 2010 88 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 3 245 000000000 000000000 101001010 1011 1111 0100 246 000000000 000000000 101001100 1011 0000 0100 247 000000000 000000000 110001000 1101 0110 0110 248 000000000 000000000 110001010 0011 0110 0001 249 000000000 000000000 110001100 0011 1001 0001 250 000000000 000000000 100000100 0001 0000 1111 251 000000000 000000000 100000101 1001 0000 1110 252 000000000 000000000 100000110 1111 0000 1000 253 000000000 000000000 101000100 1001 1001 0000 254 000000000 000000000 101000101 0001 1001 0001 255 000000000 000000000 101000110 0111 1001 0111 256 000000000 000000000 110000100 0001 0000 0101 257 000000000 000000000 110000101 1001 0000 0100 258 000000000 000000000 110000110 1111 0000 0010 259 000000000 000000000 010010000 0111 0000 0100 260 000000000 000000000 010010100 1001 1111 0011 261 000000000 000000000 010011000 0101 1001 0000 262 000000000 000000000 010110000 0111 0001 1011 263 000000000 000000000 010110100 1001 1110 1100 264 000000000 000000000 010111000 0101 1000 1111 265 000000000 000000000 011010000 1111 1001 1011 266 000000000 000000000 011010100 0001 0110 1100 267 000000000 000000000 011011000 1101 0000 1111 268 000000000 000000000 010001000 0010 1001 1110 269 000000000 000000000 010001010 1100 1001 1001 270 000000000 000000000 010001100 1100 0110 1001 271 000000000 000000000 010101000 0010 1000 0001 272 000000000 000000000 010101010 1100 1000 0110 273 000000000 000000000 010101100 1100 0111 0110 274 000000000 000000000 011001000 1010 0000 0001 275 000000000 000000000 011001010 0100 0000 0110 276 000000000 000000000 011001100 0100 1111 0110 277 000000000 000000000 010000100 1110 1111 1101 278 000000000 000000000 010000101 0110 1111 1100 279 000000000 000000000 010000110 0000 1111 1010 280 000000000 000000000 010100100 1110 1110 0010 281 000000000 000000000 010100101 0110 1110 0011 Ratio Mathematica, 20, 2010 89 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 3 282 000000000 000000000 010100110 0000 1110 0101 283 000000000 000000000 011000100 0110 0110 0010 284 000000000 000000000 011000101 1110 0110 0011 285 000000000 000000000 011000110 1000 0110 0101 286 000000000 000000000 001001000 1010 0000 1011 287 000000000 000000000 001001010 0100 0000 1100 288 000000000 000000000 001001100 0100 1111 1100 289 000000000 000000000 001011000 1101 0000 0101 290 000000000 000000000 001011010 0011 0000 0010 291 000000000 000000000 001011100 0011 1111 0010 292 000000000 000000000 001101000 1010 0001 0100 293 000000000 000000000 001101010 0100 0001 0011 294 000000000 000000000 001101100 0100 1110 0011 295 000000000 000000000 001000100 0110 0110 1000 296 000000000 000000000 001000101 1110 0110 1001 297 000000000 000000000 001000110 1000 0110 1111 298 000000000 000000000 001010100 0001 0110 0110 299 000000000 000000000 001010101 1001 0110 0111 300 000000000 000000000 001010110 1111 0110 0001 301 000000000 000000000 001100100 0110 0111 0111 302 000000000 000000000 001100101 1110 0111 0110 303 000000000 000000000 001100110 1000 0111 0000 304 000000000 000000000 000100100 1110 1110 1000 305 000000000 000000000 000100101 0110 1110 1001 306 000000000 000000000 000100110 0000 1110 1111 307 000000000 000000000 000101100 1100 0111 1100 308 000000000 000000000 000101101 0100 0111 1101 309 000000000 000000000 000101110 0010 0111 1011 310 000000000 000000000 000110100 1001 1110 0110 311 000000000 000000000 000110101 0001 1110 0111 312 000000000 000000000 000110110 0111 1110 0001 313 000000000 000000000 100000000 1111 1111 1000 314 000000000 000000000 101000000 0111 0110 0111 315 000000000 000000000 110000000 1111 1111 0010 316 000000000 000000000 010000000 0000 0000 1010 317 000000000 000000000 010100000 0000 0001 0101 318 000000000 000000000 011000000 1000 1001 0101 Ratio Mathematica, 20, 2010 90 Low density 2-repeated bursts of length 3(fixed) Syndromes Sub-block - 3 319 000000000 000000000 001000000 1000 1001 1111 320 000000000 000000000 001010000 1111 1001 0001 321 000000000 000000000 001100000 1000 1000 0000 322 000000000 000000000 000100000 0000 0001 1111 323 000000000 000000000 000101000 0010 1000 1011 324 000000000 000000000 000110000 0111 0001 0001 325 000000000 000000000 000010000 0111 0000 1110 326 000000000 000000000 000010100 1001 1111 1001 327 000000000 000000000 000011000 0101 1001 1010 328 000000000 000000000 000001000 0010 1001 0100 329 000000000 000000000 000001010 1100 1001 0011 330 000000000 000000000 000001100 1100 0110 0011 331 000000000 000000000 000000100 1110 1111 0111 332 000000000 000000000 000000101 0110 1111 0110 333 000000000 000000000 000000110 0000 1111 0000 Remark 3. The space visible between vectors in the first column in Table 1 has been given to distinguish between different sub-blocks whereas the space given in the syndrome vector is for convenience. Observation. Syndromes of some of the 2-repeated bursts of length 3(fixed) occurring within the second sub-block are same. For coding efficiency it is desired that the syndromes of the error patterns within any sub-block is identical whenever possible. 3 Location of m-Repeated Low-density burst of length b(fixed) In this section a necessary and sufficient condition for the location of an m-repeated low-density burst of length b(fixed) with weight w or less has been given. Ratio Mathematica, 20, 2010 91 It may be noted that an EL-code capable of detecting and locating a single sub-block containing an error which is in the form of an m-repeated low-density burst of length b(fixed) with weight w or less (w ≤ b) must satisfy the following conditions: (c) The syndrome resulting from the occurrence of an m-repeated low- density burst of length b(fixed) with weight w or less within any one sub-block must be distinct from the all zero syndrome. (d) The syndrome resulting from the occurrence of any m-repeated low- density burst of length b(fixed) with weight w or less within a single sub-block must be distinct from the syndrome resulting likewise from any m-repeated low-density burst of length b(fixed) with weight w or less within any other sub-block. In this section we shall derive two results. The first result gives a lower bound on the number of check digits required for the existence of a linear code over GF(q) capable of detecting and locating a single sub-block containing errors that are m-repeated low-density bursts of length b(fixed) with weight w or less. In the second result, we derive an upper bound on the number of check digits which ensures the existence of such a code. Theorem 3. The number of parity check digits r in an (n, k) linear code subdivided into s sub-blocks of length t each, that locates a single corrupted sub-block containing errors that are 2-repeated low density bursts of length b(fixed) with weight w or less is at least    logq{1 + s(qmw − 1)} where t − b + 1 ≥ mb and (m−1)b+w≤t−b+1 < mb logq{1 + s(q(m−1)w+(t−mb+1) − 1)} where t − b + 1 < (m − 1)b + w. (10) Ratio Mathematica, 20, 2010 92 The proof of this result is on the similar lines as that of proof of Theorem 1 so we omit the proof. Remark 4. For m = 2 the result coincides with that of Theorem 1 when 2-repeated low-density bursts of length b(fixed) with weight w or less are considered. Remark 5. For m = 1, the result obtained in (10) reduces to    logq{1 + s(qw − 1)} where t − b + 1 ≥ b and w ≤ t − b + 1 < b logq{1 + s(q(t−b+1) − 1)} where t − b + 1 < w . which is a case of detecting and locating a sub-block containing errors which are usual low-density bursts of length b(fixed) with weight w or less. Remark 6. For w = b, the result obtained in (10) reduces to r ≥ { logq{1 + s(qmb − 1)} where t − b + 1 ≥ mb logq{1 + s(q(t−b+1) − 1)} where t − b + 1 < mb which coincides with the result due to Dass and Arora [Theorem 3, 2010]. In the following result we derive another bound on the number of check digits required for the existence of such a code. As earlier the proof is based on the technique used to establish Varshomov-Gilbert Sacks bound by constructing a parity check matrix for such a code (refer Sacks, Theorem 4.7 Peterson and Weldon(1972)). Theorem 4. An (n, k) linear EL-code over GF(q) capable of detecting an m-repeated low density burst of length b(fixed) with weight w or less Ratio Mathematica, 20, 2010 93 (w ≤ b) within a single sub-block and of locating that sub-block can always be constructed provided that qn−k > [1 + (q − 1)](b−1,w−1) · { m−1∑ i=0 ( t − (i + 1)b + i i ) (q − 1)i[1 + (q − 1)](b−1,w−1) } · { 1 + (s − 1) m∑ i=1 ( t − ib + i i ) (q − 1)i{[1 + (q−1)](b−1,w−1)}i } (11) where [1 + x](m,r) denotes the incomplete binomial expansion of (1 + x)m up to the term xr in ascending power of x, viz. [1 + x](m,r) = 1 + ( m 1 ) x + ( m 2 ) x2 + . . . + ( m r ) xr. As in theorem 3 we omit the proof because proof of this result is on the similar lines as that of proof of Theorem 2. Remark 7. For m = 2 the result coincides with that of Theorem 2 when 2-repeated low-density bursts of length b(fixed) with weight w or less are considered. Remark 8. For m = 1, the result obtained in (11) reduces to qn−k>[1 + (q − 1)](b−1,w−1){1 + (s − 1)(t − b + 1)(q − 1)[1 + (q − 1)](b−1,w−1)} which is a necessary condition for detecting and locating a sub-block containing errors which are usual low-density bursts of length b(fixed) with weight w or less. Ratio Mathematica, 20, 2010 94 Remark 9. For w = b, the result obtained in (11) reduces to qn−k > qb−1 { m−1∑ i=0 ( j − (i + 1)b + i i ) (q − 1)iqi(b−1) } · { 1 + (s − 1) m∑ i=1 ( j − (i + 1)b + i i ) (q − 1)iqi(b−1) } which coincides with the result due to Dass and Arora [Theorem 4, 2010]. References [1] Abramson, N.M. [1959] A class of systematic codes for non- independent errors, IRE Trans. on Information Theory, IT-5 (4), 150– 157. [2] Alexander, A.A., Gryb, R.M. and Nast, D.W. [1960] Capabilities of the telephone network for data transmission, Bell System Tech J., 39(3), 431-476. [3] Chien, R.T. and Tang, D.T. [1965] On definitions of a burst, IBM Journal of Research and Development, 9(4), 292–293. [4] Dass, B.K. [1980] On a Burst- Error Correcting Codes, J. Inf. Optimization Sciences, 1(3), 291–295. [5] Dass, B.K. [1983] Low-density burst error correcting linear codes, Advances in Management Studies, 2(4), 375–385. [6] Dass, B.K. and Arora, Ritu [2010] Error Locating Codes Dealing with Repeated Burst Errors, accepted for publication in Italian Journal of Pure and Applied Mathematics, No. 30. Ratio Mathematica, 20, 2010 95 [7] Dass, B.K. and Chand, Kishan [1986] Linear codes locating/correcting burst errors, DEI Journal of Science and Engineering Research, 4(2), 41–46. [8] Dass, B.K., Garg, Poonam and Zannetti, M. [2008] Some combina- torial aspects of m-repeated burst error detecting codes, Journal of Statistical Theory and Practice, 2(4), 707–711. [9] Dass, B.K. and Garg, Poonam [2009(a)] On 2-repeated burst codes, Ratio Mathematica - Journal of Applied Mathematics, 19, 11–24. [10] Dass, B.K. and Garg, Poonam [2009(b)] Bounds for codes correct- ing/detecting repeated low-density burst errors, communicated. [11] Dass, B.K. and Garg, Poonam [2010], On repeated low-density burst error detecting linear codes, communicated. [12] Fire, P. [1959] A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Report RSL-E-2, Sylvania Recon- naissance Systems Laboratory, Mountain View, Calif. [13] Hamming, R.W. [1950] Error-detecting and error-correcting codes, Bell System Tech. J., 29, 147- 160. [14] Peterson, W.W., Weldon, E.J., Jr. [1972] Error-Correcting Codes, 2nd edition, The MIT Press, Mass. [15] Sacks, G.E. [1958] Multiple error correction by means of parity-checks, IRE Trans. Inform. Theory IT, 4(December), 145–147. [16] Wyner, A.D. [1963] Low-density-burst-correcting codes, IEEE Trans. Informatiom Theory, (April), 124. [17] Wolf, J., Elspas, B. [1963] Error-locating codes A new concept in error control, IEEE Transactions on Information Theory, 9(2), 113–117. Ratio Mathematica, 20, 2010 96