MODERATE-DENSITY CLOSE-CLOSED LOOP BURST ERROR DETECTING CODES 15 MODERATE-DENSITY CLOSE-CLOSED LOOP BURST ERROR DETECTING CODES Bal Kishan Dass1 Sapna Jain2 Abstract: In this paper, we study cyclic codes detecting a subclass of close-closed loop bursts viz. moderate-density close-closed loop bursts. A subclass of CT close-closed loop bursts called CT moderate-density close-closed loop bursts is also studied. A comparative study of the results obtained in this paper has also been made. Keywords: Cyclic Codes, Moderate-Density Bursts, Close-Closed Loop Bursts, Error Detecting Codes. 1. Introduction Burst errors are the most common type of errors that occur in several communication channels. Codes developed to detect and correct such errors have been studied extensively by many authors. The most successful early burst error correcting codes were due to Fire (1959). Fire in his report gave the idea of open and closed loop bursts defined as follows: Definition 1. An open loop burst of length b is a vector all of whose non-zero components are confined to some b consecutive components, the first and the last of which is non-zero. Definition 2. A closed loop burst of length b is a vector all of whose non-zero components are confined to some b consecutive components, the first and the last of which is non-zero and the number of positions from where the burst can start is n (i.e. it is possible to come back cyclically at the first position after the last position for enumeration of the length of the burst). Definition 2 of closed loop burst can also be formulated mathematically on the lines Campopiano (1962) as follows: Definition 2a. Let )(qV n be the set of all ordered n- tuples with components belonging to GF(q). Let X = ),...,,( 110 −naaa be a vector in )(qV n . Then X is 1 Department of Mathematics, University of Delhi, Delhi 110 007, India 2 Department of Mathematics, University of Delhi, Delhi 110 007, India 16 called a closed loop burst of length b, ,2 nb ≤≤ if ∃ an i , 10 −≤≤ ni , such that 0. ≠ji aa where j = ( i + b - 1) modulo n and     <======== >==== −++− −++ j i if 0...... j i if 0... 121110 121 njji ijj aaaaaa aaa There is yet another definition of a burst due to Chien and Tang (1965) which runs as follows: Definition 3. A CT burst of length b is a vector all of whose non-zero components are confined to some b consecutive components, the first of which is non-zero. Based on these definitions, Dass & Jain (2000) defined close-closed loop bursts, open-closed loop burst, CT close-closed loop burst, and CT open-closed loop burst and proved results for close-closed loop bursts and CT close-closed loop bursts. The definitions and the results proved by Dass & Jain (2000) are as follows: Definition 4. Let ),...,,( 110 −= naaaX be a vector in )(),( qGFaqV i n ∈ and let nb ≤≤2 . Then X is called a close-closed loop burst of length b if ∃ an i , 11 −≤≤ bi such that .0...,0. 1111 ====≠ −+−+−+− ibniiibn aaaaa Definition 5. The class of open loop burst as considered in Definition 1 may be termed as open-closed loop bursts. Definition 6. Let X= ),...,,( 110 −naaa be a vector in )(qV n and nb ≤≤2 . Then X is called a CT close-closed loop bursts of length b if ∃ an i , 11 −≤≤ bi such that 0≠+− ibna ; at least one of 110 ,...,, −iaaa is non-zero and 0... 11 ==== −+−+ ibnii aaa . Definition 7. The class of CT open loop burst as considered in Definition 3 may be termed as CT open-closed loop bursts. Theorem A. An (n, k) cyclic can not detect any close-closed loop burst of length b where 12 +≤≤ kb . Theorem B. The fraction of close-closed loop bursts of length b ( 12 +≤≤ kb ) that goes undetected to the total number of close-closed loop bursts in any (n, k) cyclic code is 17 = 2 132 )1)(1( )1( −− −−+− qb qq bbk . Theorem C. An (n, k) cyclic code can not detect any CT close-closed loop burst of length b where 12 +≤≤ kb . Theorem D. The fraction of CT close-closed loop burst of length b )12( +≤≤ kb that goes undetected to the total number of CT close-closed loop bursts in any (n, k) cyclic code is = ( ) 1)1( )1( 1 11 +−− − − −+− bqbq qq b bbk . There are of course many situations in which errors occur in the form of bursts but not all digits inside the burst get corrupted. Usually, the weight of the burst lies between two numbers 1w and 2w such that 212 ww ≤≤ ≤ length of burst. Such bursts are known as moderate-density bursts. Moderate-density bursts with respect to close-closed loop burst are known as moderate-density close-closed loop bursts and are defined as follows: Definition 8. A close-close loop burst of length b whose weight lies between 1w and 2w , bww ≤≤≤ 212 , is called a moderate-density close-closed loop burst. The development of codes which detect/correct moderate-density close-closed loop bursts can economize in the number of parity check digits required, suitably reducing the redundancy of the code or in the other words, suitably increasing the efficiency of transmission. In the second section of this paper, we obtain results similar to Theorem A and B for moderate-density close-closed loop bursts whereas in the third section, we obtain results similar to Theorems C and D for CT moderate- density close-closed loop bursts. The last section viz. Section 4 gives a comparison of the results obtained in Section 2 and Section 3. In what follows, an (n, k) cyclic code over GF(q) is taken as an ideal in the algebra of polynomials modulo the polynomial 1−nX . 18 2. Moderate-Density Close-Closed Loop Burst Error Detection In this section, we obtain results of Theorems A and B for moderate- density close- closed loop bursts. Theorem 1. An (n, k) cyclic codes can not detect any moderate-density close-closed loop burst of length b with weight lying between 1w and 2w )( 21 bww ≤≤ where 12 +≤≤ kb . Proof. There is no deviation in the final conclusion of this theorem from that of Theorem A because the proof is based on the length of the burst giving rise to a polynomial which is of the same degree even when the weight consideration over the burst is considered. Hence the proof is omitted. Q.E.D. Theorem 2. The fraction of moderate-density close-closed loop bursts of length b )12( +≤≤ kb with weight lying between 1w and 2w that goes undetected to the total number of moderate-density close-closed loop bursts in any (n, k) cyclic code is = } }∑     ∑    ∑ −      −−      −− − − = − = − 〉−〈= − − + − +− 1 1 1 1 1, 1 1 1 1 1 2 1 12 112 2 2 1 1 )1(1)1(1 )1( b i w r rw rwr r r r r bk qiqib qq where }1,.{max1, 1111 rwrw −=− Proof. Let r(X) denote a moderate-density close-closed loop burst of length )12( +≤≤ kbb with weight w lying between 1w and 2w )( 21 bww ≤≤ . Let g(X) denote the generator polynomial of the code of degree k.n − Now r (X) will be of the form r(X)= )...( 111 ib nibnibn ibn XaXaaX −−−++−+− +− +++ );...( 11 2 210 − −+++++ i i XaXaXaa ibnabi +−−≤≤ ,11 0, 1 ≠−ia and the number of non-zero coefficients, including 1, −+− iibn aa lies between 1w and 2w . ),()( 21 XrXrX ibn += +− say where ibniibnibn XaXaaXr −− −++−+− +++= 1 11 ...)( and ....)( 11 2 2102 − −++++= i i XaXaXaaXr Let 1r be the number of non-zero coefficients in 1r (X) and 2r be the number of non-zero coefficients in 2r (X), 19 where 11 21 −≤≤ wr and 11 22 −≤≤ wr Such that 2211 wrrw ≤+≤ . For any fixed value of i, let us give different values of 1r . (i) Let 11 =r . Then 11 ,1 221 −≤≤〉−〈 wrw ( ,122112211 rwrrwwrrw −≤≤−⇒≤+≤Q also 12 ≥r )1 , 12211 rwrrw −≤≤〉−〈∴ where { }.1 ,max1 , 1111 rwrw −=〉−〈 We have then Number of polynomials of type ()1()(1 −= qXr ) 0 0 )1(1 −−− qib Number of polynomials of type 1 1 1,1 1 2 2 2 12 2 )1(1)1()( − − 〉−〈= − −∑       −−= r w wr r qiqXr ∴Number of polynomials of type r(X) = 1 1 1,1 1 2 0 2 2 12 2 )1(1)1(1 − − 〉−〈= − −∑       −−     −− r w wr r qiqib (ii) For 21 =r we get 21 ,2 221 −≤≤〉−〈 wrw Number of polynomials of type ()1()(1 −= qXr ) )1(1 1 −−− qib Number of polynomials of type 1 2 1,2 1 2 2 2 12 2 )1(1)1()( − − 〉−〈= − −∑       −−= r w wr r qiqXr ∴ Number of polynomials of type r(X) = 1 2 1,2 1 3 1 2 2 12 2 )1(1)1(1 − − 〉−〈= − −∑       −−     −− r w wr r qiqib Continuing the computation for various values of ,...,4,31 =r we finally, have 11 221 =⇒−= rwr and Number of polynomials of type =)(1 Xr 2 2 2 2 )1(1)1( − − −      −−− w w qibq Number of polynomials of type )(2 Xr = = 11 1 1 2 2 2 )1(1)1( − = − −∑       −− r r r qiq ∴ Number of polynomials of type r(X) = 2 2 )1(1 2 w w qib −      −− − 11 1 1 2 2 2 )1(1 − = − −∑       − r r r qi So, for a fixed value of i, 20 Number of polynomials of type r(X) = }1 1, 1 1 1 1 1 2 12 112 2 1 2 1 1 )1(1)1(1 − − 〉−〈= − + − = − −∑       −−∑          −− r rw rwr r r w r r qiqib Summing over i, we get Total number of polynomials of type r(X) = { }1 1, 1 1 1 1 1 1 1 2 12 112 2 1 2 1 1 )1(1)1(1 − − 〉−〈= − + − = − − = −∑       −−∑          −−∑ r rw rwr r r w r r b i qiqib Again, r(X) will go undetected if g(X) divides r(X) ⇒ r(X) =g(X)Q(X) for some polynomials Q(X) ⇒ )()( 21 1 XrXrX bn ++− = g(X)Q(X) Now, number of polynomials of type Q(X) = )11( +−− bk qq (refer[3]) ∴Ratio of moderate-density close-closed loop bursts that goes undetected to the total number of moderate-density close-closed loop bursts is = } }∑     ∑    ∑ −      −−      −− − − = − = − 〉−〈= − − + − +− 1 1 1 1 1, 1 1 1 1 1 2 1 12 112 2 2 1 1 )1(1)1(1 )1( b i w r rw rwr r r r r bk qiqib qq where }1 ,.{max1 , 1111 rwrw −=− Hence the proof. Q.E.D. Special Cases. (i) For ,221 === wwb the ratio obtained in the preceding theorem reduces to the ratio given in Theorem B for b=2 and the ratio in each case becomes )1( 1 − − q q k . (ii) For ,21 =w the result obtained in the preceding theorem reduces to the case of low-density close-closed loop bursts considered by Dass & Jain (2000). (iii) For ,2 bw = the result obtained in the preceding theorem reduces to the case for high-density close-closed loop bursts, considered by Dass & Jain (2000). 21 3. CT Moderate-Density Close-Closed Loop Burst Error Detection In this section we extend the studies made in Section 2 for CT moderate-density close-closed loop bursts. Firstly, we obtain the following result, the proof of which is omitted. Theorem 3. An (n, k) cyclic code can not detect any CT moderate-density close- closed loop burst of length )12( +≤≤ kbb with weight lying between 1w and ).( 212 bwww ≤≤ We now prove the following result. Theorem 4. The fraction of CT moderate-density close-closed loop bursts of length b )12( +≤≤ kb with weight lying between 1w and 2w that goes undetected to the total number of CT moderate-density close-closed loop bursts in any (n, k) cyclic code is = } }∑     ∑    ∑ −      −      −− − − = − = − 〉−〈=− +− 1 1 1 1 1,1 1 2 1 12 112 2 2 1 1 )1()1(1 )1( b i w r rw rwr r r r r bk qiqib qq where }1 ,.{max1 , 1111 rwrw −=− Proof. Let r(X) denote a CT moderate-density close-closed loop burst of length b )12( +≤≤ kb with weight lying between 1w and 2w )( 21 bww ≤≤ . Let g(X) denote the generator polynomial of the code of degree kn − . Now r(X) will be of the form r(X) = )...( 111 ib nibnibn ibn XaXaaX −−−++−+− +− +++ );...( 11 2 210 − −+++++ i i XaXaXaa ibnabi +−−≤≤ ,11 0≠ and the number of non-zero coefficients, including 1, −+− iibn aa lies between 1w and 2w . ),()( 21 XrXrX ibn += +− say where ibniibnibn XaXaaXr −− −++−+− +++= 1 11 ...)( and ....)( 11 2 2102 − −++++= i i XaXaXaaXr Let 1r be the number of non-zero coefficients in )(1 Xr and 2r be the number of non-zero coefficients in )(2 Xr , where 11 21 −≤≤ wr and 11 22 −≤≤ wr 22 Such that 2211 wrrw ≤+≤ . For any fixed value of i, let us give different values of 1r . (i) Let 11 =r . Then 11 ,1 221 −≤≤〉−〈 wrw and Number of polynomials of type ()1()(1 −= qXr ) 0 0 )1(1 −−− qib Number of polynomials of type 2 2 12 2 )1()( 1 1,1 2 r w wr r qiXr −∑       = − 〉−〈= ∴ Number of polynomials of type r(X) = 2 2 12 2 )1()1(1 1 1,10 r w wr r qiqib −∑       −     −− − 〉−〈= (ii) Let 21 =r we get 21 ,2 221 −≤≤〉−〈 wrw Number of polynomials of type ()1()(1 −= qXr ) )1(1 1 −−− qib Number of polynomials of type 2 2 12 2 )1()( 2 1,2 2 r w wr r qiXr −∑       = − 〉−〈= ∴ Number of polynomials of type r(X) = 2 2 12 2 )1()1(1 2 1,2 2 1 r w wr r qiqib −∑       −     −− − 〉−〈= Continuing the computation for various values of ,...,4,31 =r we finally, have 11 221 =⇒−= rwr and Number of polynomials of type =)(1 Xr 2 2 2 2 )1( 1 )1( − − −      −−− w w qibq Number of polynomials of type )(2 Xr = 2 2 2 )1( 1 1 r r r qi −∑       = Number of polynomials of type r(X) = 1 2 2 2 )1(1 − − −      −− w w qib 2 2 2 )1( 1 1 r r r qi −∑       = So, for a fixed value of i, Number of polynomials of type r(X) = }212 112 2 1 2 1 1 )1()1(1 1, 1 1 1 r rw rwr r r w r r qiqib −∑       −∑          −− − 〉−〈= − = − Summing over i , we get Total number of polynomials of type r(X) = { }212 112 2 1 2 1 1 )1()1(1 1, 1 1 1 1 1 r rw rwr r r w r r b i qiqib −∑       −∑          −−∑ − 〉−〈= − = − − = Again, r(X) will go undetected if g(X) divides r(X) ⇒ r(X) = g(X)Q(X) for some polynomials Q(X) 23 ⇒ )()( 21 XrXrX ibn ++− = g(X)Q(X) Now, number of polynomials of type Q(X) = )11( +−− bk qq (refer[3]) ∴Ratio of moderate-density close-closed loop bursts that goes undetected to the total number of moderate-density close-closed loop bursts is = }∑     ∑    ∑ −      −      −− − − = − = − 〉−〈=− +− 1 1 1 1 1,1 1 2 1 12 112 2 2 1 1 )1()1(1 )1( b i w r rw rwr r r r r bk qiqib qq where }1,.{max1, 1111 rwrw −=− Hence the proof. Q.E.D. Special Cases. (i) For ,221 === wwb the ratio obtained in the preceding theorem reduces to the ratio given in Theorem B for b=2 and the ratio in each case becomes )1( 1 − − q q k . (ii) For ,21 =w the result obtained in the preceding theorem reduces to the case of low-density close-closed loop bursts considered by Dass & Jain (2000). (iii) For ,2 bw = the result obtained in the preceding theorem reduces to the case for high-density close-closed loop bursts, considered by Dass & Jain (2000). 4. Comparative Study In this section, we present the comparison of the results obtained in Section 2 and Section 3 viz. Theorem 2 and Theorem 4. The comparison has been presented in the form of a table by taking specific values of b, 1w and 2w in the binary case. For 221 === wwb , both definitions viz. of moderate-density close-closed loop burst and of CT moderate-density close-closed loop burst coincide. Therefore, we start comparing the results for b=3, and onwards. 24 TABLE [ ]2=q ____________________________________________________________________ Moderate-Density Close-Closed CT Moderate-Density Close-Closed Loop Bursts Loop Bursts (Theorem 2) (Theorem 4) ________________________________________________________________ [ ]2,2;3 21 === wwb 00.64 00.33 50.12 = = = k k k 00.4 00.2 00.1 [ ]3,2;3 21 === wwb 00.34 50.13 75.02 = = = k k k 40.2 20.1 60.0 [ ]3,3;3 21 === wwb 00.64 00.33 50.12 = = = k k k 00.6 00.3 50.1 ________________________________________________________________ [ ]2,2;4 21 === wwb 33.95 66.44 33.23 = = = k k k 66.4 33.2 16.1 [ ]3,2;4 21 === wwb 11.35 55.14 77.03 = = = k k k 00.2 00.1 50.0 [ ]4,2;4 21 === wwb 33.25 66.14 58.03 = = = k k k 64.1 82.0 41.0 [ ]3,3;4 21 === wwb 66.45 33.24 16.13 = = = k k k 50.3 75.1 87.0 25 [ ]4,3;4 21 === wwb 11.35 55.14 77.03 = = = k k k 54.2 27.1 63.0 [ ]4,4;4 21 === wwb 33.95 66.44 33.23 = = = k k k 33.9 66.4 33.2 ________________________________________________________________ [ ]2,2;5 21 === wwb 00.156 50.75 75.34 = = = k k k 00.6 00.3 50.1 [ ]3,2;5 21 === wwb 75.36 87.15 93.04 = = = k k k 00.2 00.1 50.0 [ ]4,2;5 21 === wwb 14.26 07.15 53.04 = = = k k k 33.1 66.0 33.0 [ ]5,2;5 21 === wwb 87.16 93.05 46.04 = = = k k k 22.1 61.0 30.0 [ ]3,3;5 21 === wwb 00.56 50.25 25.14 = = = k k k 00.3 50.1 75.0 [ ]4,3;5 21 === wwb 50.26 25.15 62.04 = = = k k k 71.1 85.0 42.0 26 [ ]5,3;5 21 === wwb 14.26 07.15 53.04 = = = k k k 53.1 76.0 38.0 [ ]4,4;5 21 === wwb 00.56 50.25 25.14 = = = k k k 00.4 00.2 00.1 [ ]5,4;5 21 === wwb 75.36 87.15 93.04 = = = k k k 15.3 57.1 78.0 [ ]5,5;5 21 === wwb 00.156 50.75 75.34 = = = k k k 00.15 50.7 75.3 Note. The fractions have been calculated up to 2 decimal places. Acknowledgement. The second author wishes to thank University Grants Commission for providing grant (vide Ref. No. F-13-3/99(SR-I)) under Minor Research Project to carry out this research work. References 1. C.N. Campopiano (1962), Bounds on Burst Error Correcting Codes, IRE Trans., IT-8, pp. 257-259. 2. R.T. Chien and D.T. Tang (1965), On Definitions of a Burst IBM J. Res. & Devlop. , July pp. 292-293. 3. B.K. Dass and Sapna Jain (2000), On a Class of Closed Loop Bursts Error Detecting Codes, International Journal of Nonlinear Sciences and Numerical Simulation 2, pp. 305- 306, 2001. 4. B.K. Dass and Sapna Jain (2000), Low-Density Close-Closed Loop Burst Error Detecting Codes, accepted for publication in Korean Journal of Computational and Applied Mathematics. 5. B.K. Dass and Sapna Jain (2000), High-Density Close-Closed Loop Burst Error Detecting Codes, submitted. 6. P. Fire (1959), A Class of Multiple-Error-Correcting Binary Codes for Non-Independent Errors, Sylvania Report RSL-E-2, Sylavania Recon. Sys. Lab., Mountain View, California. 7. W.W. Peterson (1961), Error Correcting Codes, Cambridge, Mass: The M.I.T. Press.