Repeated Burst Error Detecting Linear Codes B. K. Dass1 and Rashmi Verma2 ∗ Department of Mathematics University of Delhi Delhi - 110 007, India 1 e-mail: dassbk@rediffmail.com 2 e-mail: riva 7@rediffmail.com Abstract. This paper presents lower bounds on the number of parity- check digits required for a linear code that is capable of detecting errors which are ‘m-repeated burst errors’. Further, codes capable of detecting and simultaneously correcting such errors have also been studied. ∗Corresponding author. Ratio Mathematica, 19, pp. 25-30 25 1 Introduction Many kinds of errors in coding theory have been dealt with for which codes have been constructed to combat such errors. Apart from random errors, one of the widely studied error is a burst error. It has been observed that in several communication systems, errors occur predominantly in bursts. 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. Stone (1961), and Bridwell and Wolf (1970) considered multiple burst errors. Chien and Tang (1965) observed that in many channels errors occur in the form of a burst but errors do not occur in the end digits of the burst, e.g., channels due to Alexander, Gryb and Nast (1960) fall in this category. 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. Codes that detect and correct 2-repeated open-loop bursts have been studied by Berardi, Dass and Verma (2007). A 2-repeated burst (open-loop) of length b has been defined as follows: Definition 2. A 2-repeated burst of length b is a vector of length n whose only non-zero components are confined to two distinct sets of b consecutive components, the first and the last component of each set being non-zero. In very busy communication channels, errors repeat themselves more frequently. In view of this, it is desirable to consider more than two repeated bursts. Ratio Mathematica, 19, pp. 25-30 26 In this paper, we define ‘m-repeated burst of length b’ as follows: Definition 3. An m-repeated burst of length b is a vector of length n whose only non-zero components are confined to m distinct sets of b consecutive components, the first and the last component of each set being non-zero. For example, (001020024100314030100) is a 4-repeated burst of length 3 over GF(5). Bounds for the detection and correction of such bursts have been derived in this paper. 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 m-Repeated Burst Error Detecting Code In this section, we consider linear codes that are capable to detect m-repeated burst of length b or less. Clearly, the patterns to be detected should not be code words. Firstly, we obtain a lower bound over the number of parity-check digits for such a code. Theorem 1. Any (n, k) linear code over GF(q) that detects any m- repeated burst of length b or less must have atleast mb parity-check digits. Proof. The result will be proved by showing 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 m fixed distinct b consecutive components. Ratio Mathematica, 19, pp. 25-30 27 We claim that no two vectors of X can belong to the same coset of the standard array, else a code word would 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. Then their difference viz., x1 − x2 must be a code word. But x1 − x2 is a vector all of whose non-zero components are confined to the same m fixed b consecutive components and so is a member of X , i.e., x1 − x2 is m-repeated burst of length b or less, which is a contradiction. Thus all the vectors in X must belong to distinct cosets of the standard array. The number of such vectors overGF(q) is clearly qmb . Also, total number of cosets in an (n, k) linear code equals qn−k , so we must have qn−k > qmb , i.e., n − k > mb, which proves the result. Remarks. For m = 1, this result reduces to the case of single non-repeated bursts (refer Theorem 4.13, Peterson and Weldon (1972)). For m = 2, this result coincides with Theorem 1 due to Berardi, Dass and Verma (2007) when bursts considered are 2-repeated bursts of length b or less. 3 Simultaneous Detection and Correction of m-Repeated Burst Errors In the following, we consider linear codes which are capable to detect and correct simultaneously m-repeated bursts and obtain a necessary condition over the number of parity-checks required for such a code. Ratio Mathematica, 19, pp. 25-30 28 Theorem 2. Any (n, k) linear code over GF(q) that corrects m-repeated bursts of length b or less must have at least 2mb parity-check digits. Further, if the code corrects m-repeated bursts of length b or less and simultaneously detects m-repeated bursts of length d or less (d > b), then the code must have at least m(b + d) parity-check digits. Proof. Consider a burst of length 2mb. Such a vector is expressible as a sum or difference of two vectors each of which is m-repeated burst of length b or less. These component vectors must belong to different cosets of the standard array because both such errors are correctable errors. Accordingly, such a vector viz., a burst of length 2mb or less cannot be a code word. In view of Theorem 1, such a code must have atleast 2mb parity-check digits. Further, consider a burst of length m(b + d). Such a vector cannot be a code word because it is always expressible as a sum or difference of two vectors, one of which is m-repeated burst of length b or less and the other is m-repeated burst of length d or less. As earlier, any pair of such component vectors cannot belong to the same coset of the standard array and so a burst of length m(b + d) cannot be a code word. Therefore, the code must have atleast m(b + d) parity-check digits. Remarks. For m = 1, this result coincides with Reiger’s bound (Reiger (1960); also refer Theorem 4.15, Peterson and Weldon (1972)). For m = 2, this result reduces to a result due to Berardi, Dass and Verma (Theorem 3, (2007)) when bursts considered are 2-repeated bursts of length b or less. Ratio Mathematica, 19, pp. 25-30 29 References [1] 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. [2] 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. [3] Bridwell J.D. and Wolf J.K. (1970), Burst distance and multiple-burst correction, Bell System Tech. J., Vol. 99, pp. 889–909. [4] Chien R.T. and Tang D.T. (1965), On definitions of a burst, IBM Journal of Research and Development, Vol. 9, No. 4 (July), pp. 292– 293. [5] Peterson W.W. and Weldon E.J., Jr. (1972), Error-Correcting Codes, 2nd edition, The MIT Press, Mass. [6] Reiger S.H. (1960), Codes for the correction of “clustered errors”, IRE Trans. Inform. Theory, IT-6 March, pp. 16–21. [7] Stone J.J. (1961), Multiple burst error correction, Information and Control, Vol. 4, pp. 324–331. Ratio Mathematica, 19, pp. 25-30 30