MODERATE-DENSITY BURST ERROR CORRECTING LINEAR CODES MODERATE-DENSITY BURST ERROR CORRECTING LINEAR CODES Bal Kishan Dass and Gangmei Sobha* Department of Mathematics, University of Delhi, Delhi-110007, India ABSTRACT Lower and upper bounds for the existence of linear codes which correct burst of length b (fixed) and whose weight lies between certain limits have been presented. Keywords : Error detecting codes, error correcting codes, burst errors, moderate- density burst, lower and upper bounds. 1. INTRODUCTION It is well known that during the process of transmission errors occur predominantly in the form of a burst. However, it does not generally happen that all the digits inside any burst length get corrupted. Also when burst length is large then the actual number of errors inside the burst length is also not very less. Keeping this in view, we study codes which detect/correct moderate-density burst errors. In the literature, various kinds of burst errors have been studied, viz. open loop bursts (c.f. Peterson and Weldon, Jr. (1972), p.109), closed-loop bursts [Campopiono, 1962], C.T. bursts [Chien and Tang, (1965)], low-density bursts [Dass, 1975], etc. One important kind of bursts errors which has not drawn much attention is burst of specified length (fixed) [Dass, 1982]. In this paper, we derive lower and upper bounds for linear codes that detect/correct Moderate-density bursts of length b (fixed) for some positive integer b. In what follows we shall consider a linear code to be a subspace of n-tuples over GF(q). The weight of a vector shall be considered in the Hamming's sense [Hamming, 1950] and we shall mean by a burst of length b (fixed), is an n-tuple whose only nonzero components are confined to b consecutive positions, the first of which is nonzero and the number of its starting positions is the first (n-b+1) components. * On Study leave from Department of Mathematics and Statistics, College of Agriculture, Central Agricultural University, Imphal-795001, India. 47 2. BOUNDS FOR CODES CORRECTING MODERATE-DENSITY BURSTS In this section, we consider codes correcting moderate-density burst errors. We first obtain a lower bound on the number of check digits which is a necessary conditions for the existence of codes capable of correcting bursts of length b (fixed) with weight lying between w1 and w2 (0 ≤ w1 ≤ w2 ≤ b). Before this we prove the following Lemma. Lemma 1. If J (n, b, w1, w2) denotes the number of n-tuples over GF(q) which form bursts of length b (fixed) with weight lying w1 and w2 (0 ≤ w1 ≤ w2 ≤ b) then (1) ( ) ( ) ( 1i 1w 0w 1wi 21 1qi 1b 1bnw,w,b,nJ 2 1 1 + − ≠ −= −      − +−= ∑ ) ) Proof. The Lemma follows immediately from the fact that the number of bursts of length b (fixed) with weight i is . ( ) ( .1bn1q 1 i 1b i +−−      − − Theorem 1. The number of parity check symbols in an (n, k) linear code that corrects all bursts of length b (fixed) of weight lying between w1 and w2 (0 ≤ w1 ≤ w2 ≤ b) is at least. logq [1 + J (n, b, w1, w2)]. (2) Proof. Since the code has qn-k cosets in all, and all the error patterns are to be in different cosets of the standard array, therefore, in view of Lemma 1, we must have qn-k ≥ 1 + J (n, b, w1, w2). (3) The result now follows by taking logarithm on both sides. Remarks. If we put w1 = 0 and w2 = b in the above result then weight constraints imposed on the burst becomes redundant and we get qn-k ≥ 1 + [(n–b+1] (q–1)] qb-1, which gives the number of parity check digits in an (n, k) linear code over GF(q) that corrects all bursts of length b (fixed), a result due to Dass [1980]. Now, if we take, w1 = 0 and w2 = w in (3) we get qn-k ≥ 1 + (n-b+1) (q-1) [1+(q-1)](b-1, w-1), 48 which gives the number of check digits required for linear codes correcting bursts of length b (fixed) with weight w or less (w ≤ b) a result which is again due to Dass [1983]. Moreover, when w1 = w and w2 = b we obtain qn-k ≥ 1 + (n–b+1) , ( ) 1i 1b 0w 1wi 1q i 1b +− ≠ −= −      − ∑ which gives the number of check digits required in an (n, k) linear code that corrects all bursts of length b (fixed) with weight w or more (w ≤ b) which coincides with the result due to the authors [2000]. Now, we first obtain a sufficient condition giving an upper bound for the existence of a code capable of detecting moderate-density burst errors, and then in the theorem following this result we shall obtain an upper bound for codes correcting such errors. Theorem 2. Given non-negative integers, w1, w2 and b such that 0 ≤ w1 ≤ w2 ≤ b, a sufficient condition that there exists an (n, k) linear code that has no burst of length b (fixed) whose weight lies between w1 and w2, as a code word is qn-k > 1 + . (4) ( i 1w 0w 1wi 1q i 1b2 1 1 −      − ∑ − ≠ −= ) Proof. The existence of such a code will be proved by constructing a suitable (n–k) x n parity check matrix H for the desired code. For this we first construct an (n–k) x n matrix H′ and then H will be obtained by reversing altogether the columns of H′. We select any non-zero (n–k)-tuple as the first column of H′. Subsequent columns are added to H′ in such a way that after having selected j–1 columns h1, h2,…,hj-1 suitably a nonzero (n–k)-tuple is chosen as the j-th column such that it is not a linear combination of any p columns (w1–1 ≤ p ≤ w2–1) from the immediately preceding b–1 columns hj-b+1, hj-b+2, … , hj-1. Such a condition will ensure that a burst of length b (fixed) with weight lying between w1, w2 cannot be a code word in the code whose parity-check matrix is H to be obtained from H′ as prescribed earlier. In other words, hj ≠ a1hj-b+1 + a2hj-b+2 + … + ab-1hj-1, (5) where number of nonzero ai's lies between w1–1 and w2–2. Since ai∈GF(q), the possible number of linear combinations on the R.H.S. of (5) including the case when all the αi's are zero is . ( )i 1w 0w 1wi 1q i 1b 1 2 1 1 −      − + ∑ − ≠ −= 49 Therefore, a column hj can be added to H′ provided that this number is less than the total number of (n–k)-tuples. At worst, all these linear combinations might yield a distinct sum, therefore, hj can always be added to H′ provided that qn-k > 1 + . (6) ( i 1w 0w 1wi 1q i 1b2 1 1 −      − ∑ − ≠ −= ) It is important note that this relation is independent of j, therefore we can go on adding the columns as long as we wish but for the code of length j we shall stop after choosing j columns. So for j = n we shall added upto n columns. By reversing the order of columns of the matrix H′ = [h1,h2, …, hn], we get the required parity check matrix H = [H1,H2,…, Hn] where hI = Hn-i+1 (i.e. hn = H1, Hn-1 = H2, …, h1 = Hn]. Thus we obtain the inequality as stated in (4). Examples 1. Consider the following 5x7 matrix of a (7, 2) code over GF (2).                 = 0100001 1100010 1100100 1101000 1010000 H This matrix has been constructed by the synthesis procedure outlined in the proof of theorem 2 by taking b = 4, w1 = 2 and w2 = 3. The code words of this code are 0000000, 0111101, 1000111, 1111010 which are not bursts of length 4 with weight lying between w1 = 2, w2 = 3. Next we derive sufficient condition for codes correcting moderate-density bursts of length b (fixed). Theorem 3. A sufficient condition for the existence of an (n, k) linear code over GF(q) which corrects all burst of length b (fixed) with weight lying between w1 and w2 (0 ≤ w1 ≤ w2 ≤ b) is 50 ( ) ( ) ( ) ( ) ( ) ( ) ( )∑ ∑ ∑ ∑∑ ∑∑∑ − = +++ −≤≤−− −≤++ = −≥+ + − ≠ −= + = + − ≠ −= − ≠ −= −                 −      −−       −       − +           −      −−       − −      − +         −      − +           −      − +−           −      − +> 1b 1k 1rrr 32 2wr1kw 2w2rrr :r,r,r 1 1-b 1k 2wrr :r,r rr 32 1w 0w 1wr 1r 1 i p 0i 1i 1w 0w 1wi i 1w 0w 1wi kn 321 111 2321 322 132 32 32 2 1 11 1 2 1 1 2 1 1 1q r 1kb r 1k r kb 1q r 1kb r 1k 1q r kb 1q i 1b 1q i 1b 1b2n1q i 1b 1q (7) where p = 2w2–1, when b ≥ 2w1, q=2 = 2b – 2w1–1 when b < 2w1, q = 2 and w1–k ≤ r1 ≤ w2–1, w1–k–1 ≤ w2–1, 0 ≤ r2 ≤ 2w2–3, r1 + r2 + r3 ≤ 2w2 –2. Proof. The existence of such a code shall be proved as in the previous theorem. A nonzero (n-k)-tuple is chosen as the first column of H′. Subsequent columns are added such that after having selected j–1 columns, h1, h2, …, hj–1 suitably a column hj is added provided that it is not a linear combination of any number of columns lying between w1–1 and w2–1 among the immediately preceding b–1 columns hj–b+1, hj–b+2, …, hj–1 together with any number of columns lying between w1 and w2 among any b consecutive columns out of all the j–1 columns selected so far. In other words, hj can be added provided that hj ≠ (α1hj-b+1 + α2hj-b+2 + … + αb-1hj-1) + (βihi +βi+1hi+1 + … + βi+bhi+b-1) (8) where hj's are any b consecutive columns from all the j–1 previously chosen columns and the number of nonzero βi's lies between w1 and w2 whereas the number of nonzero αi's lies between w1–1 and w2–1 along with the case when all the αi's are zero. To compute the number of all possible linear combinations corresponding to R.H.S. of (8) for all possible choices of αj and βi we analyse three different cases as follows. Case 1. When hj's are completely confined to the first j–b columns. The number of ways that the coefficients αj's can be selected is . (9) ( i 1w 0w 1wi 1q i 1b2 1 1 −      − ∑ − ≠ −= ) 51 Further the number of ways that the coefficients of βi's which form a burst of length b (fixed) with weight lying between w1 and w2 in a vector of length j-b can be selected is (refer Lemma 1). J(j–b, b, w1, w2) = (j–2b+1) . (10) ( ) 1i 1w 0w 1wi 1q i 1b2 1 1 + − ≠ −= −      − ∑ Therefore, the total number of choices of coefficients in this case is . (11) ( ) ( ) ( )           −      − +−           −      − +− ≠ −= − ≠ −= ∑∑ 1i 1w 0w 1wi i 1w 0w 1wi 1q i 1b 1b2j1q i 1b 2 1 1 2 1 1 Case II. When hj's are completely confined to the immediately preceding b–1 columns. In this case the number of linear combinations corresponding to R.H.S. of (8) is , (12) ( i p 0i 1q i 1b −      − ∑ = ) where p = 2w2–1, when b ≥ 2w1, q=2 = 2b–2w1–1 when b < 2w1, q=2 Case III. When hj's are neither completely confined to the first (j–b) columns nor to the last b–1 columns. j–2b+2 j–2b+1+k j–b j–b+1 j–b+k–1 j–b+k j–b+k+1 j–1 b-1 b r3 r2 r1 Let the burst starts from (j–2b+1+k)-th position which can continue upto (j–b+k)-th position, (1 ≤ k ≤ b –1). We select at least w1–1 and at the most w2–1 nonzero components corresponding to j–2b+1+k, j–2b+2+k, …, j–b+k–1 columns together with nonzero components lying between w1–1 and w2–1 corresponding to j–b+1, j–b+2, …, j–1 columns. Let r1, r2 and r3 be the number of nonzero components corresponding to columns lying between (j–2b+1+k)-th to (j–b)-th, (j–b+1)-th to (j–b+k–1)-th and (j–b+k+1)-th to (j–1)-th column respectively, such that 52 w1–k ≤ r1 ≤ w2–1, w1–k–1 ≤ r3 ≤w2–1, 0≤r2 ≤ 2w2–3, r1 + r2 + r3 ≤ 2w2–2 (13) Therefore total possible number of distinct choices of coefficients is ( ) ( ) ( )∑ ∑ ∑ ∑∑ − = +++ −≤≤−− −≤++ − = − −≥+ ++ − ≠ −=                 −      −−       −       − +           −      −−       − −      − + 1b 1k 1rrr 32 2wr1kw 2w2rrr :r,r,r 1 1b 1k 1w 2wrr :r,r rr 32 1r 1w 0w 1wr 1 321 111 2321 322 2 132 32 32i 2 1 11 1q r 1kb r 1k r kb 1q r 1kb r 1k 1q r kb (14) Thus total possible number of distinct linear combinations corresponding to (8), which cannot be equal to hj including zero vector is ( ) ( ) ( ) ( ) ( ) ( ) ( )∑ ∑ ∑ ∑∑ ∑∑∑ − = +++ −≤≤−− −≤++ − = + −≥+ + − ≠ −= = + − ≠ −= − ≠ −=                 −      −−       −       − +           −      −−       − −      − +         −      − +           −      − +−           −      − + 1b 1k 1rrr 32 2wr1kw 2w2rrr :r,r,r 1 1b 1k rr 3 2wrr :r,r 2 1r 1w 0w 1wr 1 i p 0i 1i 1w 0w 1wi i 1w 0w 1wi 321 111 2321 321 32 132 32 1 2 1 11 2 1 1 2 1 1 1q r 1kb r 1k r kb 1q r 1kb r 1k 1q r kb 1q i 1b 1q i 1b 1b2n1q i 1b 1 (15) Therefore, the j-th column can be added to H′ provided that qn-k > M, (16) where M denotes expression (15). For the existence of an (n, k) desired code relation (16) should hold for j = n so that it is possible to add upto nth column to form an (n–k) x n matrix. Thus we have constructed the matrix H′ = [hi], (hi denotes the i-th column from which we obtain the required parity check matrix H = [Hi], (Hi denotes the i-th column) by reversing its column altogether, i.e. hi → Hn-i+1. This proves the result. 53 Remarks 1. If we take w1 = 0, w2 = b in (16) the weight constraints becomes redundant. Hence the bound gives qn-k > qb-1 [qb-1 (n–2b+1) (q–1)+1] which is a result due to Dass [1980]. 2. If we put w1 = 0, w2 = w, in (16) we get the bound obtained by Dass [1982], which is a sufficient condition for the existence of low-density burst correcting code that corrects all bursts of length b (fixed). Example 2. Consider the following matrix 6x9 of a (9,3) code over GF(2) which can correct all bursts of length 4 (fixed) with weight 2 or 3.                     = 011000001 101000010 001000100 101001000 001010000 001100000 H This matrix is constructed by the synthesis procedure outline in the proof of theorem 3. It can be seen from the table 1 that syndromes of all the correctable error patterns are distinct and therefore the null space of this matrix gives the desired code. 54 Table 1 Error Pattern Syndrome Error Pattern Syndrome 110000000 000011 111000000 000111 011000000 000110 011100000 001110 001100000 001100 001110000 011100 000110000 011000 000111000 111000 000011000 110000 000011100 001111 000001100 011111 000001110 011110 101000000 000101 110100000 001101 010100000 001010 011010000 011010 001010000 010100 001101000 110100 000101000 101000 000110100 100111 000010100 101111 000011010 110001 000001010 100001 000001101 010101 100100000 001001 101100000 001011 010010000 010010 010110000 010110 001001000 100100 001011000 101100 000100100 110111 000101100 010111 000010010 010001 000010110 101110 000001001 101010 000001011 101011 REFERENCES 1. CHIEN, R.T. and D.T. TANG (1965) : On definition of a Burst, IBM J. Research & Develop., 9(4), 292-293. 2. DASS, B.K. (1975) : A sufficient Bound for Codes Correcting Bursts with Weight Constraints, Journal of the Association for Computing Machinery (J. ACM), Vol.22, No.4, 501-503. 3. DASS, B.K. (1980) : On a Burst-Error Correcting Linear Codes, J. Infor. & Opt. Sciences, Vol.1, No.3, 291-295. 55 4. DASS, B.K. (1983) : Low Density Burst-Error Correcting Linear Codes, Adv. in Mngt. Studies, Vol.2, pp.375-385. 5. DASS, B.K. and G. SOBHA (2000) : High-Density Burst Error Correcting Linear Codes, unpublished. 6. HAMMING, R.W. (1950) : Error Detecting and Error Correcting Codes, Bell System Tec. J., 29, 147-160. 7. PETERSON, W.W. and E.J. WELDON, Jr. (1972) : Error-Correcting Codes, Cambridge, Mass : The M.I.T. Press. 8. SHARMA, B.D. and S.N. GUPTA (1975) : On the existence of Moderate- Density Burst Codes, Journal of Mathematical Sciences, Vol.10, 8-12. 56