On 2-Repeated Burst Codes B. K. Dass Department of Mathematics University of Delhi Delhi - 110 007, India e-mail: dassbk@rediffmail.com Poonam Garg∗ Department of Mathematics Deen Dayal Upadhyaya College (University of Delhi) Shivaji Marg, Karam Pura New Delhi - 110 015, India e-mail: poonamgarg 68@yahoo.co.in Abstract. There are several kinds of burst errors for which error detecting and error correcting codes have been constructed. In this paper, we consider a new kind of burst error which will be termed as ‘2-repeated burst error of length b(fixed)’. Linear codes capable of detecting such errors have been studied. Further, codes capable of detecting and simultaneously correcting such errors have also been dealt with. The paper obtains lower and upper bounds on the number of parity-check digits required for such codes. An example of such a code has also been provided. ∗Corresponding author. Ratio Mathematica, 19, pp. 11-24 11 1. Introduction Investigations in coding theory have been made in several directions but one of the most important aspects considered has been the detection and correction of errors. The beginning was made with the detection and correction of random errors [refer Hamming (1950)] and thereafter the advent of BCH codes for multiple error correction was taken up. Though there is a long history concerning the growth of the subject and many of the codes developed have found applications in numerous areas of practical interest, one of the areas of practical importance in which a parallel growth of the subject took place is that of burst error detecting and correcting codes. It has also been observed that in many communication channels the likelihood of the occurrence of errors is more in adjacent digits rather than their occurrence in a random manner. Extending the work of Hamming (1950), Abramson (1959) developed codes which dealt with the correction of single and double adjacent errors. The work due to Fire (1959) depicted a more general concept of clustered errors which in the literature are known as ‘burst errors’. A burst of length b may be 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. Fire (1959) considered two kinds of bursts viz. open-loop burst which are popularly refered to simply a burst (as in Definition 1) and the other is called as ‘closed-loop burst’ defined as follows: Ratio Mathematica, 19, pp. 11-24 12 Definition 2. Let b be an integer and x = (ξ1, . . . ,ξn) be a vector in V n(q) , a vector space of n-tuples over GF(q) . If 2 6 b 6 n + 1 2 , then x is called a ‘closed-loop burst vector of length b’ whenever there is an i such that 1 6 i 6 b− 1 , ξi · ξn−b+i+1 6= 0 , ξi+1 = ξi+2 = · · · = ξn−b+i = 0 . Stone (1961), and Bridwell and Wolf (1970) considered multiple bursts. It was noted by Chien and Tang (1965) that in several channels errors occur in the form of a burst but not in the end digits of the burst. Channels due to Alexander, Gryb and Nast (1960) fall in this category. This prompted Chien and Tang to propose 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 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 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. It is clear that the nature of burst errors differ from channel to channel depending upon the behaviour of channels or the kind of errors which occur during the process of transmission. Also, in very busy communication channels, errors repeat themselves. So is a situation when Ratio Mathematica, 19, pp. 11-24 13 errors occur in the form of a burst. In a way, we need to consider repeated bursts. Codes that detect and correct repeated open-loop bursts have been studied by Berardi, Dass and Verma (2009). In this paper, a 2-repeated burst (open-loop) of length b has been defined as follows: Definition 5. A 2-repeated burst of length b is an n-tuple whose only non-zero components are confined to two distinct sets of b consecutive digits, the first and the last component of each set being non-zero. The development of codes detecting and correcting repeated burst errors will economize in the number of parity-check digits required not only in comparison with codes dealing with detection and correction of the same number of random errors but also in comparison to the usual burst error detecting and correcting codes while considering such repeated bursts as single bursts. In this paper, we introduce yet another kind of a repeated burst and define a ‘2-repeated burst of length b(fixed)’ as follows: Definition 6. 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 among the first n− 2b + 1 components. For example, (1000001000) is a 2-repeated burst of length up to 4 (fixed) whereas (0000100100) is a 2-repeated burst of length at most 3 (fixed). Ratio Mathematica, 19, pp. 11-24 14 These 2-repeated burst patterns of length b(fixed) include several 2- repeated bursts of length b or less in an obvious manner. Moreover, these are four times in number than the 2-repeated burst patterns of the same length in the binary case, and in the q-nary case these are q2 (q − 1)2 -times the number of 2-repeated bursts. It is clear from the fact that the number of 2-repeated burst vectors of length b is (q−1)4(q)2(b−2) and the number of 2-repeated burst vectors of length b(fixed) is (q−1)2(q)2(b−1) giving the ratio as q2 (q − 1)2 . In section 2, we obtain bounds for codes detecting 2-repeated bursts of length b(fixed). Section 3 presents a bound for codes which can detect and simultaneously correct such 2-repeated bursts. In what follows a linear code will be considered as a subspace of the space of all n-tuples over GF(q) . The distance between two vectors shall be considered in the Hamming sense. 2. 2-repeated burst error detecting codes In this section, we consider linear codes that are capable of detecting any 2-repeated burst of length b(fixed). Clearly, the patterns to be detected should not be code words. In other words we consider codes that have no 2-repeated burst of length b(fixed) as a code word. Firstly, we obtain a lower bound over the number of parity-check digits required for such a code. Theorem 1. Any (n,k) linear code over GF(q) that detects any 2-repeated burst of length b(fixed) must have at least 2b parity-check digits. Ratio Mathematica, 19, pp. 11-24 15 Proof. The result will be proved on the basis that no detectable error vector can be a code word. Let V be an (n,k) linear code over GF(q) . Consider a set X that has all those vectors which have their non-zero components confined to some two fixed distinct b consecutive components in the first n − b + 1 components. We claim that no two vectors of the set X can belong to the same coset of the standard array, else a code word shall be expressible as a sum or difference of two error vectors. Assume on the contrary that there is a pair, say x1,x2 in X belonging to the same coset of the standard array. Their difference viz. x1−x2 must be a code vector. But x1−x2 is a vector all of whose non-zero components are confined to the same two fixed b consecutive components and so is a member of X , i.e., x1−x2 is a 2-repeated burst of length b(fixed), which is a contradiction. Thus all the vectors in X must belong to distinct cosets of the standard array. The number of such vectors over GF(q) is clearly q2b . The theorem follows since there must be at least this number of cosets. Remark 1. Incidentally, this result coincides with [Theorem 1, Berardi, Dass and Verma (2009)] when bursts considered are open-loop bursts. An upper bound on the number of check digits required for the construction of a linear code is provided in the following theorem. This bound assures the existence of a linear code that can detect all 2- repeated bursts of length b(fixed). The bound has been obtained by first constructing a matrix under certain constraints and then by reversing the Ratio Mathematica, 19, pp. 11-24 16 order of its columns altogether giving rise to a parity-check matrix for the requisite code, a technique given by Dass (1980). Theorem 2. There exists an (n,k) linear code that has no 2-repeated burst of length b(fixed) as a code word provided that qn−k > qb−1[1 + (n− 2b + 1)(q − 1)qb−1] . (1) Proof. The existence of such a code will be shown by constructing an appropriate (n − k) × n parity-check matrix H . Firstly, we construct a matrix H′ from which the requisite parity-check matrix H shall be obtained by reversing the order of its columns altogether. Any non-zero (n−k) -tuple is chosen as the first column h1 of H′. Subsequent columns are added to H′ such that after having selected the first j − 1 columns h1,h2, . . . ,hj−1 , j -th column hj is added provided that hj 6= (αj−b+1hj−b+1 + αj−b+2hj−b+2 + · · · + αj−1hj−1) + (βihi + βi+1hi+1 + · · · + βi+b−1hi+b−1) (2) where either all βi are zero or if βt is the last nonzero coefficient then b 6 t 6 j − b, αj ’s and βi ’s in GF(q) . This condition ensures that no 2- repeated burst of length b(fixed) will be a code word. The number of ways in which the coefficients αj can be selected is clearly q b−1 . To enumerate the coefficients βi is equivalent to enumerate the number of bursts of length b(fixed) amongst the first j − b components. This number, including the vector of all zeros, is [Theorem 1, Dass (1980)] 1 + (j − 2b + 1)(q − 1)qb−1 . Ratio Mathematica, 19, pp. 11-24 17 Thus, the total number of possible combinations that hj can not be equal to, is qb−1[1 + (j − 2b + 1)(q − 1)qb−1] . (3) At worst, all these linear combinations might yield a distinct sum. Therefore a column hj can be added to H ′ provided that qn−k > (3) . The required parity-check matrix H = [H1H2 . . .Hn] can be obtained from H′ by reversing the order of its columns altogether (hi → Hn−i+1 ). For a code of length n, replacing j by n gives the result. Remark 2. In view of the fact that the result obtained in Theorem 2 is the same as the result for the correction of bursts of length b(fixed), such a code can serve dual purpose viz. it can either be used to correct bursts of length b(fixed) or can be used to detect 2-repeated bursts of length b(fixed). 3. Simultaneous detection and correction of repeated burst errors In this section we determine extended Reiger’s bound [Reiger (1960); also refer Theorem 4.15, Peterson and Weldon (1972)] for simultaneous detection and correction of 2-repeated bursts of length b(fixed). The following theorem gives a bound on the number of parity-check digits for Ratio Mathematica, 19, pp. 11-24 18 a linear code that simultaneously detects and corrects 2-repeated bursts of length b(fixed). Theorem 3. An (n,k) linear code over GF(q) that corrects all 2- repeated bursts of length b(fixed) must have at least 4b parity-check digits. Further, if the code corrects all 2-repeated bursts of length b(fixed) and simultaneously detects 2-repeated bursts of length d(fixed) (d > b) then the code must have at least 2(b + d) parity-check digits. Proof. We first prove the first part. Consider a burst of length 4b(fixed) in the first n − b + 1 components. Such a vector is expressible as a sum or difference of two vectors, each of which is a 2-repeated burst of length b(fixed). These component vectors must belong to different cosets of the standard array because both such errors are correctable errors. Accordingly, such a vector viz. burst of length 4b(fixed) can not be a code vector. In view of Theorem 1, such a code must have at least 4b parity-check digits. Further, consider a burst of length 2(b+d) (fixed), the burst confining to the first n − b + 1 components. Such a vector is expressible as a sum or difference of two vectors, one of which is a 2-repeated burst of length b(fixed) and the other is a 2-repeated burst of length d(fixed). Both such component vectors, one being a detectable error and the other being a correctable error, can not belong to the same coset of the standard array. Therefore such a vector can not be a code vector, i.e., a burst of length 2(b+d) (fixed) can not be a code vector. Hence the code must have at least 2(b + d) parity-check digits. Ratio Mathematica, 19, pp. 11-24 19 Remark 3. Incidentally, this result coincides with [Theorem 3, Berardi, Dass and Verma (2009)], when bursts considered are open-loop bursts. Example. We conclude the paper with an example. Consider a (7, 2) binary code with parity check matrix H =   0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0   This matrix has been constructed by the synthesis procedure, outlined in the proof of Theorem 2, by taking b = 3 . It can be seen from Table 1 that the syndromes of the different 2-repeated bursts of length 3 (fixed) are nonzero, showing thereby that the code that is the null space of this matrix can detect all bursts of length 3 (fixed). Table 1 Error vectors Syndromes 1000000 00001 1001000 01001 1001100 11001 1001010 01110 1001110 11110 1000100 10001 1000110 10110 1000101 11111 1000111 11000 1100000 00010 1101000 01010 1101100 11010 1101010 01101 (Contd.) Ratio Mathematica, 19, pp. 11-24 20 Error vectors Syndromes 1101110 11101 1100100 10010 1100110 10101 1100101 11100 1100111 11011 1010000 00101 1011000 01101 1011100 11101 1011010 01010 1011110 11010 1010100 10101 1010110 10010 1010101 11011 1010111 11100 1110000 00110 1111000 01110 1111100 11110 1111010 01001 1111110 11001 1110100 10110 1110110 10001 1110101 11000 1110111 11111 0100000 00011 0100100 10011 0100110 10100 0100101 11101 0100111 11010 0110000 00111 0110100 10111 0110110 10000 0110101 11001 0110111 11110 0101000 01011 0101100 11011 (Contd.) Ratio Mathematica, 19, pp. 11-24 21 Error vectors Syndromes 0101110 11100 0101101 10101 0101111 10010 0111000 01111 0111100 11111 0111110 11000 0111101 10001 0111111 10110 0010000 00100 0011000 01100 0010100 10100 0011100 11100 0001000 01000 0001100 11000 0001010 01111 0001110 11111 0000100 10000 0000110 10111 0000101 11110 0000111 11001 References [1] Abramson, N.M. (1959), A class of systematic codes for non- independent errors, IRE Trans. on Information Theory, IT-5, No. 4, pp. 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., Vol. 39, No. 3, pp. 431–476. [3] Berardi, L., Dass, B.K. and Verma, Rashmi (2009), On 2-repeated burst error detecting codes, Journal of Statistical Theory and Practice, Vol. 3, No. 2, pp. 381–391. [4] Bridwell, J.D. and Wolf, J.K. (1970), Burst distance and multiple- burst correction, Bell System Tech. J., Vol. 49, pp. 889–909. Ratio Mathematica, 19, pp. 11-24 22 [5] Campopiano, C.N. (1962), Bounds on burst error correcting codes, IRE Trans., IT-8, pp. 257–259. [6] Chien, R.T. and Tang, D.T. (1965), On definitions of a burst, IBM Journal of Research and Development, Vol. 9, No. 4, pp. 292–293. [7] Dass, B.K. (1980), On a burst-error correcting code, Journal of Information and Optimization Sciences, Vol. 1, No. 3, pp. 291–295. [8] Fire, P. (1959), A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Report RSL-E-2, Sylvania Reconnaissance Systems Laboratory, Mountain View, Calif. [9] Hamming, R.W. (1950), Error-detecting and error-correcting codes, Bell System Technical Journal, Vol. 29, pp. 147–160. [10] Peterson, W.W. and Weldon, E.J., Jr. (1972), Error-Correcting Codes, 2nd edition, The MIT Press, Mass. [11] Reiger, S.H. (1960), Codes for the correction of “clustered errors”, IRE Trans. Inform. Theory, IT-6, pp. 16–21. [12] Stone, J.J. (1961), Multiple burst error correction, Information and Control, Vol. 4, pp. 324–331. Ratio Mathematica, 19, pp. 11-24 23