RATIO MATHEMATICA 22 (2012) 61-68 ISSN:1592-7415 Codes on s-periodic errors Pankaj Kumar Das* and Vinod Tyagi** *Department of Mathematics, Shivaji College (University of Delhi), Raja Garden, Delhi-110 027, India **Department of Mathematics, Shyam Lal College (Eve.)(University of Delhi), Shahdara, Delhi-110032, India *pankaj4thapril@yahoo.co.in, **vinodtyagi@hotmail.com Abstract In this paper, we study linear codes capable of detecting and cor- recting s-periodic errors. Lower and upper bounds on the number of parity check digits required for codes detecting such errors are ob- tained. Another bound on codes correcting such errors is also ob- tained. An example of a code detecting such errors is provided. Key words: parity check matrix, syndromes, standard array, pe- riodic error. 2000 AMS subject classifications: 94B25, 94B60, 94-02. 1 Introduction Investigations in coding theory have been made in several directions but one of the most important directions has been the detection and correction of errors. It began with Hamming codes[9] for single errors, Golay codes[10, 11] for double and triple random errors and thereafter BCH codes[12, 13, 14] were studied for multiple error correction. There is a long history towards the growth of the subject and many of the codes developed have found appli- cations 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, burst errors occur more frequently than random errors. A burst of length b may be defined as follows: 61 P. K. Das and V. Tyagi Definition 1.1. A burst of length b is a vector whose only non-zero com- ponents are among some b consecutive components, the first and the last of which is non zero. Extending the work of Hamming[9], Abramson[1] developed codes which dealt with the correction of single and double adjacent errors. The work due to Fire[8] depicted a more general concept of burst errors. Stone[19], and Bridwell and Wolf[4] considered multiple bursts. It was noted by Chien and Tang[5] that in several channels errors do occur in the form of a burst but not near the end of the vector. Channels due to Alexan- der, Gryb and Nast[2] fall in this category. In this light, Chien and Tang proposed a modification in the definition of a burst, now known as CT burst, according to which a CT burst of length b is defined as follows: Definition 1.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. Recently a new kind of error, known as repeated burst, has been observed by Berardi, Dass and Verma[3]. For further work on this type of error, one may refer to [6, 7, 18] and references therein. It is very clear that the nature of error differ from channel to channel depending upon the behaviour of channels or the kind of errors which occur during the process of transmission. There is a need to deal with many types of error patterns and accordingly codes are to be constructed to combat such error patterns. Though the errors are generally classified mainly in two categories - random errors and burst errors, it has also been observed that the occurrence of errors may follow a pattern, different from random and burst. In certain communication channel like Astrophotography[21], small mechanical error occurs periodically in the accuracy of the tracking in a motorized mount that results small movements of the target that can spoil long-exposure images, even if the mount is perfectly polar-aligned and appears to be tracking perfectly in short tests. It repeats at a regular interval - the interval being the amount of time it takes the mount’s drive gear to complete one revolution. This type of error pattern is termed as periodic or alternate pattern. It was in this spirit that the codes correcting s-alternate errors were developed by Tyagi and Das [20]. An s-periodic error is defined as follows: 62 Codes on s-periodic errors Definition 1.3. An s-periodic error is an n- tuple whose non zero compo- nents are located at a gap of s positions where s = 1, 2, 3,....,(n −1) and the number of its starting positions is among the first s + 1 components. For s=1, the 1-periodic error vectors are the ones where error may occur in 1st, 3rd, 5th...positions or 2nd, 4th, 6th,... positions. For example, in a vector of length 8, 1-periodic error vectors are of the type 10101000, 00101000, 0010101, 10101010, 10001010, 01010101, 01000101, 00000101, 00000001 etc. For s=2, the 2-periodic error vectors are those where error may occur in 1st, 4th, 7th,... positions or 2nd, 5th, 8th,...positions or 3rd, 6th, 9th,... positions. The 2-periodic error vectors may look like 10010010, 10000010, 00010010, 01000001, 01000000, 00001001, etc in a vector of length 8. For s=3, in a code length 8, the 3-periodic errors are 10001000, 01000100, 00100010, 00010001, 10000000, 01000000 etc. 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 con- sidered in the Hamming sense. The rest of the paper is organized as follows: In section 2, we study the linear codes that detect any s-periodic error. We obtain lower and upper bounds on the parity check digits for codes detecting such errors. It is followed by an example of such a code. In second 3, we give a bound (based on Reiger’s bound[16]) on codes correcting such errors . 2 Codes detecting s-periodic errors We consider the linear codes that are capable of detecting any s-periodic error. Clearly, the patterns to be detected should not be code words. In other words we consider codes that have no s-periodic error as a code word. Firstly, we obtain a lower bound over the number of parity-check digits required for such a code. The proof is based on the technique used in theorem 4.13, Peterson and Weldon [15]. Theorem 2.1. Any (n, k) linear code over GF(q) that detects any s-periodic error must have at least ⌈ n s + 1 ⌉ parity-check digits. Proof. The result will be proved on the basis that no detectable error vector can be a code word. 63 P. K. Das and V. Tyagi Let V be an (n, k) linear code over GF(q). Consider a set X of all those vectors such that the non-zero components are located at the first position and thereafter a gap of s positions. 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 located at the 1st position or after a gap of s position and so is a member of X, i.e., x1-x2 is an s-periodic error, 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 qp, where p = ⌈ n s + 1 ⌉ . The theorem follows since there must be at least this number of cosets. 2 In the following, an upper bound on the number of check digits required for the construction of a linear code discussed in theorem 2.1 is provided. This bound assures the existence of such a linear code and has been obtained by constructing a matrix under certain constraints. The proof is based on the well known technique used in Varshomov-Gilbert Sacks bound (refer Sacks[17], also theorem 4.7 Peterson and Weldon [15]). Theorem 2.2. There exists an (n, k) linear code over GF(q) that has no s-periodic error as a code word provided that n − k ≥ ⌈ n s + 1 ⌉ . Proof. The existence of such a code will be shown by constructing an appropriate (n − k) × n parity-check matrix H. The requisite parity-check matrix H shall be constructed as follows. Select any non-zero (n − k)-tuples as the first j − 1 columns h1, h2,..., hj−1; the jth(j > s + 1) column hj is added provided that hj ̸= ∑p i=1 uihj−i(s+1) where ui ∈ GF(q) and p = ⌈ j s + 1 ⌉ − 1. This condition ensures that no s-periodic error will be a code word. The number of ways in which the coefficients ui can be selected is clearly q p. 64 Codes on s-periodic errors At worst, all these linear combinations might yield a distinct sum. Therefore a column hj can be added to H provided that qn−k > qp. or, n − k ≥ ⌈ j s + 1 ⌉ . For a code of length n, replacing j by n gives the result. 2 Remark: The above two theorems can be combined as follows: For detecting s-periodic errors in a linear code of length n, ⌈ n s + 1 ⌉ parity check symbols are necessary and sufficient. Example 2.1. Consider a (7, 4) binary code with parity check matrix H =   1 1 1 0 0 1 00 1 0 1 1 1 0 0 0 1 0 1 1 1   This matrix has been constructed by the synthesis procedure, outlined in the proof of Theorem 2.2, by taking s = 2 and n =7. It can be seen from Table 1 that the syndromes of the different 2-periodic errors are nonzero, showing thereby that the code that is the null space of this matrix can detect all 2-periodic errors. Table 1 Error patterns Syndromes 1000000 100 0001000 010 0000001 001 1001000 110 1000001 101 0001001 011 1001001 111 0100000 110 0000100 011 0100100 101 0010000 101 0000010 111 0010010 010 65 P. K. Das and V. Tyagi 3 Codes correcting s-periodic errors The following theorem gives a bound on the number of parity-check dig- its for a linear code that corrects s-periodic errors. The proof is based on the technique used to establish Reiger’s bound[16] (also refer Theorem 4.15, Peterson and Weldon [15]) for correction of s-periodic errors. Theorem 3.1. An (n, k) linear code over GF(q) that corrects all t-periodic errors, t = 2s + 1 must have at least ⌈ n s + 1 ⌉ parity-check digits. Proof. Any vector that has the form of an s-periodic error can be ex- pressible as a sum or difference of two vectors, each of which is an t-periodic error. These component vectors must belong to different cosets of the stan- dard array because both such errors are correctable errors. Accordingly, such a vector viz. s-periodic error can not be a code vector. In view of Theorem 2.1, such a code must have at least ⌈ n s + 1 ⌉ parity-check digits. Acknowledgement The authors are very much thankful to Prof. B. K. Dass, Department of Mathematics, University of Delhi for his valuable suggestions, revising the contents and bringing the paper to the current form. References [1] N. M. Abramson, A class of systematic codes for non-independent errors, IRE Trans. on Information Theory, IT-5, No. 4(1959), 150-157. [2] A. A. Alexander, R. M. Gryb and D. M. Nast, Capabilities of the tele- phone network for data transmission, Bell System Tech. J., Vol. 39, No. 3(1960), 431-476. [3] L. Berardi, B. K. Dass and R. Verma, On 2-repeated burst error de- tecting codes, Journal of Statistical Theory and Practice, Vol. 3, No. 2(2009), 381-391. [4] J. D. Bridwell and J. K. Wolf, Burst distance and multiple-burst correc- tion, Bell System Tech. J., Vol. 49(1970), 889-909. [5] R. T. Chien and D. T. Tang, On definitions of a burst, IBM Journal of Research and Development, Vol. 9, No. 4(1965), 292-293. 66 Codes on s-periodic errors [6] B. K. Dass and S. Madan, Repeated Burst Error Locating Linear Codes, Discrete Mathematics, Algorithms and Applications, Vol. 2, No. 2(2010), 181-188. [7] B. K. Dass, and R. Verma, Repeated Burst Error Detecting Lin- ear Codes, Ratio Mathematica Journal of Applied Mathematics, Vol. 19(2009), 25-30. [8] P. Fire, A class of multiple-error-correcting binary codes for non- independent errors, Sylvania Report RSL-E-2, Sylvania Reconnaissance Systems Laboratory, Mountain View, Calif,(1959). [9] R. W. Hamming, Error-detecting and error-correcting codes, Bell Sys- tem Technical Journal, Vol. 29(1950), 147-160. [10] M. J. E. Golay, Notes on digital coding, Proc. IRE, Vol. 37(1949), 657. [11] M. J. E. Golay, Binary Coding, IRE Trans., PGIT-4(1954), 23-28. [12] R. C. Golay and D. K. Ray-Chaudhuri, On a class of Error Correcting Group Codes, Inf. and Control, Vol. 3(1960), 68-79. [13] R. C. Golay and D. K. Ray-Chaudhuri, Further Results on Error Cor- recting Binary Group Codes, Inf. and Control, Vol. 3(1960), 279-290. [14] A. Hocquenghem, Codes Corecteurs d’Erreurs, Chiffres, Vol. 2(1959), 147-156. [15] W. W. Peterson and E. J. Weldon(Jr.), Error-Correcting Codes, 2nd edition, The MIT Press, Mass, 1972. [16] S. H. Reiger, Codes for the correction of clustered errors, IRE Trans. Inform. Theory, IT-6(1960), 16-21. [17] G. E. Sacks, Multiple error correction by means of parity-checks, IRE Trans. Inform. Theory IT, 4(1958), 145 - 147. [18] B. D. Sharma, B. Rohtagi, Some Results on Weights of Vectors Having 2-Repeated Bursts, Cybernetics and Information Technologies, Vol. 11, No. 1(2011), 36-44. [19] J. J. Stone, Multiple burst error correction, Information and Control, Vol. 4(1961), 324-331. 67 P. K. Das and V. Tyagi [20] V. Tyagi and P. K. Das, s-Alternate Error Correcting Linear Codes, J. of Combinatorics, Information & System Sciences, Vol. 35, No. 1-2(2010), 17-26. [21] www.themcdonalds.net/richard/index.php?title= Astrophotography−Mounts:−Periodic−Error−Correction. 68