RATIO MATHEMATICA 27 (2014) 61-68 ISSN:1592-7415 On weights of 2-repeated bursts Barkha Rohtagia, Bhu Dev Sharmab aDepartment of Applied Sciences, KIET, NH-58, P.Box-02, Ghaziabad-201206, India barkha.rohtagi@gmail.com bDepartment of Mathematics, JIIT (Deemed University), A-10, Sector-62, Noida-201301, India bhudev\_sharma@yahoo.com Abstract It is generally seen that the behavior of the bursts depend upon the nature of the channel. In a very busy communication channel bursts repeat themselves. In this communication we are exploring the idea of weight consideration of 2-repeated bursts of length b(fixed). Some results on weights of 2-repeated bursts of length b(fixed) are derived and some combinatorial results with weight constraint for 2-repeated bursts of length b(fixed) are also given. Key words: repeated burst errors, weight of bursts, burst error correcting codes. 2000 AMS: 94B20, 94B25, 94B75. 1 Introduction In most of the communication channels disturbances due to lightning, break downs and loose connections affect successive digits for some length of the word, causing errors in bursts. Abramson (1959) initiated the idea of such errors and developed a class of error correcting codes which correct all double adjacent errors. Later, a systematic study in this direction was made by Fire (1959), Regier (1960) and Elspas (1960). These studies were based on the assumption that if errors occur in the form of bursts then all digits within a burst may not be corrupted. Easy implementation and efficient functioning 61 B. Rohtagi and B. D. Sharma are the added advantages with burst error correcting codes. Stone (1961) and Bridwell and Wolf (1970) considered multiple bursts. It was noted by Chien and Tang (1965) hat in several channels errors occur in the form of a burst but not in the end digit of the burst. Channels due to Alexander, Gryb and Nast (1960) belong to this category. In the view of this Chien and Tang modified the definition of a burst which in literature is known as CT burst. Although, this definition was further modified by Dass (1980). In general communication the messages are long and the strings of bursts may be short repeating in a vector itself. The notion of repeated burst was introduced by Berardi, Dass and Verma (2009). They defined 2-repeated bursts and obtained results for correction and detection of such type of errors. Dass, Garg and Zannetti (2008) introduced a different type of repeated burst, termed as repeated burst of length b(fixed). Later on Dass and Garg (2009) defined 2-repeated burst of length b(fixed) and gave codes for correcting and detecting such type of errors. Sharma and Dass (1976) were first to study bursts in terms of weight. The area of 2-repeated burst of length b(fixed) with weight w was explored by Dass and Garg (2011). In this paper, we obtain results regarding the weight of all vectors having 2-repeated bursts of length b(fixed). The paper has been organized as follows: In section 2 basic definitions are stated with some examples. In section 3 some results on weights of 2-repeated bursts of length b(fixed) are derived. In this correspondence, we shall consider the space of all n-tuples whose nonzero components are taken from the field of q code characters with elements 0, 1, 2, . . . , q − 1. The weight of a vector is considered in Hamming sense as the number of non-zero entries. 2 Preliminaries We give definition of a burst, defined by Fire (1959): Definition 2.1. A burst of length b is a vector all of whose nonzero components are confined to some b consecutive components, the first and the last of which is nonzero. A vector may have not just one cluster of errors, but more than one. Lumping them into one burst, amounts to neglecting the nature of communication and unnecessarily considering longer burst which may have a part, which is not of cluster in-between. For example in a very busy communication channel, sometimes, bursts repeat themselves. Berardi, Dass and Verma (2009) introduced the idea of repeated bursts. In particular they defined ‘2-repeated burst ’. 62 On weights of 2-repeated bursts A 2-repeated burst of length b may be defined as follows: Definition 2.2. A 2-repeated burst of length b is a vector of length n whose only nonzero components are confined to two distinct sets of b consecutive components, the first and the last component of each set being nonzero. Example 2.1. (0001204100300) is a 2-repeated burst of length 4 over GF(5). Chien and Tang (1965) defined a burst of length b which is called as CT burst of length b and may be defined as follows: Definition 2.3. 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. This definition was further modified by Dass (1980) as follows: Definition 2.4. 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 in an n-tuple is among the first n − b + 1 components. Following is the definition of a 2-repeated burst of length b(fixed) as given by Dass and Garg (2009): Definition 2.5. A 2-repeated burst of length b(fixed ) is an n-tuple whose only non-zero components are confined to two distinct sets of b consecutive digits, the first component of each set is non-zero and the number of its starting positions is amongst the first n − 2b + 1 components. For example, (10000010000) is a 2-repeated burst of length up to 5(fixed) whereas (0000100100) is a 2-repeated burst of length at most 3 (fixed). Dass and Garg (2011) defined a 2-repeated burst of length b(fixed) with weight w as follows: Definition 2.6. A 2-repeated 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 components 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 is among the first n − 2b + 1 components. For example, (001111000000100000) is a 2-repeated burst of length up to 6(fixed) with weight 4 or less. Weight structure being of quite some interest, in the next section, we present some results on weights of 2-repeated bursts of length b(fixed). 63 B. Rohtagi and B. D. Sharma 3 Results on Weights of 2-repeated bursts Let W2b denotes the total weight of all vectors having 2-repeated bursts of length b in the space of all n-tuples. Before obtaining W2b in terms of n and b we give two results in the lemmas below, on counting the 2-repeated bursts. Lemma 3.1. The total number of 2-repeated bursts length b > 1(fixed ), in the space of all n-tuple over GF(q), is (n − 2b + 1)(n − 2b + 2) 2 (q − 1)2q2(b−1) . (1) Proof. Total number of 2-repeated bursts of length b(fixed) in the space of all n-tuples over GF (q) is, refer Theorem 1 of Dass, Garg and Zannetti (2008), 1+ ( b 1 ) (q−1)qb−1 + n−2b+1∑ i=1 (q−1)qb−1 [ 1 + ( n−2b−i+2 1 ) (q−1)qb−1 ] . (2) Eqn. (2) includes the cases when all vectors are zero and when in the last 2b − 1 position there remains only a single burst of length b(fixed). As we are counting the number of 2-repeated bursts of length b(fixed) only, eqn. (2) reduces to the following form n−2b+1∑ i=1 (q − 1)qb−1 [ 1 + ( n − 2b − i + 2 1 ) (q − 1)qb−1 ] or (n − 2b + 1)(n − 2b + 2) 2 (q − 1)2q2(b−1). This proves the result. Next we impose weight restriction on 2-repeated bursts and count their numbers. The results are given in the lemma below. Lemma 3.2. The total number of vectors having 2-repeated bursts of length b(fixed ) with weight w (1 ≤ w ≤ b) in the space of all n-tuples is: (n − 2b + 1)(n − 2b + 2) 2 [Lb−1w,q ] 2, (3) where [ w∑ s=1 ( b − 1 s − 1 ) (q − 1)s ] = Lb−1w,q (4) is the incomplete binomial expansion of [1 + (q − 1)]b−1 up to the (q − 1)w in the ascending powers of (q − 1), w ≤ b. 64 On weights of 2-repeated bursts Proof. Let us consider a vector having 2-repeated bursts of length b(fixed) with weight w. Its only nonzero components are confined to two distinct sets of consecutive components, the first component of each set is nonzero, where each set can have at most w non-zero components (w ≤ b), and the number of its starting positions is among the first n − 2b + 1 components. Now, each of these, the first component of each set may be any of the q − 1 nonzero field elements. As we are considering only 2-repeated bursts of length b(fixed) with weight w, in a vector of length n, this will have non-zero positions as follows: (i) First position of first burst. (ii) First position of second burst. (iii) Some r − 1 amongst the b − 1 in-between positions of first burst (1 ≤ r ≤ w) and then some s − 1 in the in-between b − 1 positions of the second burst (1 ≤ s ≤ w). (iv) Other positions have the value 0. Thus analyzing in combinatorial ways, in the earlier counting factor [(q − 1)qb−1]2 replacing one factor qb−1 by ( b−1 r−1 ) (q − 1)r−1 and the other by ( b−1 s−1 ) (q − 1)s−1 each 2-repeated burst will give its number by: (q − 1)(q − 1) w∑ r=1 ( b − 1 r − 1 ) (q − 1)r−1 w∑ s=1 ( b − 1 s − 1 ) (q − 1)s−1 = w∑ r=1 ( b − 1 r − 1 ) (q − 1)r [ w∑ s=1 ( b − 1 s − 1 ) (q − 1)s ] . Then from eqn. (4) the number of each 2-repeated burst of length b(fixed) with weight w is given by, [Lb−1w,q ] 2. Therefore, the total number of 2-repeated bursts of length b(fixed) and weight w, with sum of their starting position (n − 2b + 1)(n − 2b + 2) 2 is (n − 2b + 1)(n − 2b + 2) 2 [Lb−1w,q ] 2 . This proves the lemma. Now we return to finding an expression for W2b, the total weight of all vectors having 2-repeated bursts of length b(fixed) in the space of all n-tuples. 65 B. Rohtagi and B. D. Sharma Theorem 3.1. For n ≥ b W2 = n(n − 1) 2 (q − 1)2 (5) and W2b = (n − 2b + 1)(n − 2b + 2) 2 w2[Lb−1w,q ] 2 . (6) Proof. The value of W2 follows simply by considering all vectors having any two non-zero entries out of n. Their number clearly is given by( n 2 ) (q − 1)2 = n(n − 1) 2 (q − 1)2 . This gives the value of W2 as stated. Next, for b > 1, using the Lemma 3.2, the total weight of all vectors having 2-repeated bursts of length b(fixed) each with weight of each burst at most w, is given by w∑ i=1 w∑ j=1 (n − 2b + 1)(n − 2b + 2) 2 i[Lb−1w,q ] · j[L b−1 w,q ] = (n − 2b + 1)(n − 2b + 2) 2 w2[Lb−1w,q ] 2 . This completes the proof of the theorem. Further, in coding theory, an important criterion is to look for minimum weight in a group of vectors. Our following theorem is a result in that direction. Theorem 3.2. The minimum weight of a vector having 2-repeated burst of length b > 1(fixed ) in the space of all n-tuples is at most[ wLb−1w,q (q − 1)qb−1 ]2 . (7) Proof. From Lemma 3.1, it is clear that the number of 2-repeated bursts of length b(fixed) in the space of all n-tuples with symbols taken from the field of q elements is [q(b−1)(q − 1)]2 (n − 2b + 1)(n − 2b + 2) 2 . 66 On weights of 2-repeated bursts Also from Theorem 3.1, their total weight is (n − 2b + 1)(n − 2b + 2) 2 w2[Lb−1w,q ] 2 . Since the minimum weight element can at most be equal to the average weight, an upper bound on minimum weight of a 2-repeated burst of length b(fixed) is given by (n − 2b + 1)(n − 2b + 2) 2 w2[Lb−1w,q ] 2 · 2 (n − 2b + 1)(n − 2b + 2)(q − 1)2q2(b−1) = [ wLb−1w,q (q − 1) q(b−1) ]2 . This proves the result. 4 Concluding remarks Here we have considered vectors having two bursts of equal lengths b(fixed), with or without weight constraints. Studies generalizing these considerations have also attracted our attention that will be reported separately. With these bursts as error patterns in block-wise manner will be a part of later study as codes capable of correcting such type of error patterns will improve the communication rate. References [1] N. M. Abramson, A class of systematic codes for non-independent errors, IRE Trans. on Information Theory IT-5 (4) (1959), 150-157. [2] A. A. Alexander, R. M. Gryb and D. W. Nast, Capabilities of the telephone network for data transmission, Bell System Tech. J. 39 (3) (1960), 431-476. [3] L. Berardi, B. K. Dass and R. Verma, On 2-repeated burst error detecting codes, Journal of Statistical Theory and Practice 3 (2009), 381-391. [4] J. D. Bridwell and J. K. Wolf, Burst distance and multiple-burst correction, Bell System Tech. J. 49 (1970), 889-909. [5] R. T. Chien and D. T. Tang, On definitions of a burst, IBM Journal of Research and Development 9 (4) (1965), 229-293. 67 B. Rohtagi and B. D. Sharma [6] B. K. Dass, On a burst-error correcting code, Journal of Information and Optimization Sciences 1 (3) (1980), 291-295. [7] B. K. Dass, P. Garg and M. Zanneti, On repeated burst error detecting and correcting codes, in special volume of East-West J. of Mathematics: Contributed in General Algebra II (eds. Nguyen Van Sanh and Nittiya Pabhapote) (2008), 79-98. [8] B. K. Dass and P. Garg, On repeated low-density burst error detecting linear codes, Mathematical Communications 16 (2011), 37-47. [9] B. K. Dass and P. Garg, On 2-repeatted burst codes, Ratio Mathematica 19 (2009), 11-24. [10] B. Elspas, A note on p-nary adjacent error correcting codes, IRE Trans. IT-6 (1960), 13-15. [11] P. Fire, A class of multiple-error-correcting binary codes for non- independent errors, Sylvania Report RSL-E-2, Sylvania Reconnaissance System Laboratory, Mountain View, Calif., (1959). [12] W. W. Peterson and E. J. Weldon, Jr., Error-cCorrecting Codes, 2nd edition, The MIT Press, Mass. (1972). [13] S. H. Reiger, Codes for the correction of clustered errors, IRE Trans. Inform. Theory, IT-6 (1960), 16-21. [14] B. D. Sharma and B. K. Dass (1972), On weight of bursts, presented at 38th Annul. Conf. of IMS, Bhopal, India. [15] J. J. Stone, Multiple burst error correction, Information and Control 4 (1961), 324-331. 68