Paper Menu >>
Journal Menu >>
Cyclic codes of length 2kover Z8 Arpana Garg, Sucheta Dutt* Department of Applied Sciences PEC University of Technology, Sector - 12 Chandigarh. India arpana22_2005@yahoo.com suchetapec@yahoo.co.in Abstract - We study the structure of cyclic codes of length k 2 over 8 Z for any natural number k. It is known that cyclic codes of length k 2 over 8 Z are ideals of the ring R= ! 1 2 k xx /][Z 8 . In this paper we prove that the ring R= ! 1 2 k xx /][Z 8 is a local ring with unique maximal ideal >,xM=< 12 , thereby implying that R is not a principal ideal ring. We also prove that cyclic codes of length k 2 over 8 Z are generated as ideals by at most three elements. Keywords – Codes; Cyclic Codes; Ideal; Principal Ideal Ring. 1. Introduction Let R be a commutative finite ring with identity. A linear code C over R of length n is defined as a R-submodule of n R. An element of C is called a codeword. A cyclic code C over R of length n is a linear code such that any cyclic shift of a codeword is also a codeword i.e. whenever (c1,c2,c3,...,cn) is in C then so is (cn,c1,c2,...,cn-1). Cyclic codes of order n are ideals of the ring n R. Let 8 Z denote the ring of integers modulo 8. Cyclic codes over ring m p Z of length n such that. (n,p)=1 are studied by A.R. Calderbank, N.J.A. Sloane in [2] and P. Kanwar, S.R. Lopez-Permouth in [3]. Most of the work has been done on the generators of cyclic code of length n over 4 Z where 2 | n. In [1], Abualrub and Oehmke, gave the structure of cyclic codes over 4 Zof length k 2 , in [5] Blackford classified all cyclic codes over 4 Z of length 2n where n is odd and in [6] Steven T. Dougherty & San Ling gave the generator polynomial of cyclic codes over 4 Z for arbitrary even length. The structure of cyclic codes over 2 p Z of length e p is given by Shi Minjia, Zhu Shixin in [7]. *(corresponding author : phone: 172-275-3268; fax: 172-274-5175) Cyclic codes of any length n over fields are principal ideals. Therefore cyclic codes over 2 Z of length n are principal ideals. Moreover, cyclic codes over 2 Z of length n are generated by polynomials of the type t x)( 1where t | n and these generators are divisors of 1 n x . But the situation is different in case of cyclic codes over rings. In this paper we prove that the ring R= ! 1 2 k xx /][Z8 is a local ring with unique maximal ideal >,xM=< 12 . Thereby implying that R is not a principal ideal ring (there exist cyclic codes which cannot be generated by one element). Even the generators of a cyclic code need not divide 1 n x over 8 Z . We also prove that cyclic codes of length k 2 over 8 Z are generated as ideals by at most three elements. Throughout this paper we assume that n = k 2 so that R = 8 Z [x]/< 1 n x >. 2. Preliminaries Any codeword from a cyclic code of length n can be represented by polynomials modulo 1 n x . Any codeword c = (c0,c1,c2,…,cn-1) can be represented by polynomial 1 110 n nxcxccxc ...)( in the ring R. Definition 2.1: Define a map !o)1-x[x]/ZR:n 2 s.t. ) maps 0,2,4,6 to 0; 1,3,5,7 to 1; and x to x. It is easy to prove that is an epimorphism of rings. Note that 2 Z and 8 Z are rings under different binary operations, but addition and multiplication of elements in 2 Z can be obtained from the addition and multiplication of elements of 8 Z reducing them by modulo 2. Any element a 8 Z can be written as a= b+2c+4d s.t. b,c,d 2 Z. Therefore any polynomial f(x) 8 Z [x] can be represented as (x),f(x)+f(x)+f(x)=f 321 2 22 whe re ][Z2x (x) fi for every i. Open Journal of Applied Sciences Supplement:2012 world Congress on Engineering and Technology 104 Cop y ri g ht © 2012 SciRes. The image of any polynomial f(x) R, under the homomorphism is(x)f1. Definition 2.2[8]: The content of the polynomial m m xaxaaf(x) ... 10 where the ai’s belong to 8 Z , is the greatest common divisor of .,...,, m aaa 10 Theorem 2.3[8]: The Correspondence Theorem.If AA c o: is a surjective ring homomorphism having kernel ߟ, then II c o 1 ' is a 1-1 correspondence between the totality of ideals Ic of Ac and the totality of those ideals of A which contain Ș. Theorem 2.4[8]: The General Isomorphism Theorem. If AA c o: and if the ideals IIc , respectively correspond to each other as in theorem 2.3. (i.e. )( II c 1 or equivalently, if )( IIandI c , then there is a unique ring homomorphism IaIaIAIA c cc o)()(such that //: for all a in A. Moreover, is an isomorphism of A/I with IAcc/ . Lemma 2.5 [1]: If R is a local ring with the unique maximal ideal M and M= (a) = (a1,a2,…, an), then M = <ai> for some i. 3. Generators of Cyclic Codes Over Z8. Consider the ring R = 8 Z [x] / < 1 n x >. Let C be an ideal (cyclic code) in R. Now, we prove that the ring R is a local ring but not a principal ideal ring Lemma 3.1: R is a local ring with the unique maximal ideal >,xM=< 12 . Proof : The ring ! 1 1n xxR /][Z2is a local ring with unique maximal ideal I = < (xí1)>. Now, is a ring homomorphism which is onto. Therefore by theorem 2.3., M = -1(I) = -1(<x – 1>) = <2, x – 1> is ideal of R By theorem 2.4, there exists a unique ring isomorphism /IR(I)Ș5 1 o 1 . As I is maximal ideal of R1 therefore R1/Iis a field and is a isomorphism therefore )(/IR 1 ) is also a field. This implies that M= )(I 1 ) is a maximal ideal of R. Therefore, R is a local ring with unique maximal ideal M. Lemma 3.2: R is not a principal ideal ring. Proof: Suppose R is a principal ideal ring. Let us consider the maximal ideal >,xM=< 12 of R. By the lemma 2.5., >,xM=< 12 =<x - 1> or >,xM=< 12 =<2>. But neither 2 <x - 1> nor (x - 1) <2>. Therefore, R is not a principal ideal ring. Now, we prove that cyclic codes of length k 2 over 8 Z are generated as ideals by at most three elements. We have the following: Lemma3.3: Let C be a cyclic code of length k 2 over 8 Z . If minimal degree polynomial g(x) in C is monic, then C = <g(x)> where (x) g(x) + g(x) + g(x) = g321 42 such that 0 1 z)(xg and ][ Z 2 x(x) g i for i = 1, 2, 3. Proof:Suppose C is a cyclic code of length n = k 2 over 8 Z . Let (x) g(x) + g(x) + g(x) = g321 42 such that ][ Z 2 x(x) g i for i = 1, 2, 3; be a polynomial of minimal degree in C whose leading coefficient is a unit. Let c(x) be a codeword in C, then By division algorithm q(x) and r(x) over 8 Z such that g(x) r(x) r(x) Cg(x)q(x) c(x) r(x) (g(x))(r(x)) r(x) r(x) g(x)q(x)c(x) degdegthen if implies This degdegorwhere z 00 which is a contradiction to the choice of degree of g(x) 0 )( Therefore xr i.e. every polynomial c(x) in C is a multiple of g(x). i.e. C = <g(x)>. Lemma 3.4: Let C be a cyclic code of length k 2 over 8 Z If C contains no monic polynomial and leading coefficient of minimal degree polynomial g(x) in C is 2 or 6, then C = <g(x)> = < )(xq 1 2 > where )(xq1 ! 1 n xx/][Z4 . Proof: If leading coefficient of minimal degree polynomial g(x) is 2 or 6 then we claim that content of g(x) is 2. Suppose this is not so. Let s sxcxccxg ...)( 10 and there exist some t such that 0z t c (mod 2), then 4g(x) is a non zero polynomial of degree less than degree of g(x) and belongs to C, which contradicts the minimality of g(x). Hence 0{ i c (mod 2) for all ݅ and content of g(x) is 2. So g(x) = )(xq 1 2 where )(xq1 ! 1 n xx/][Z 4 . Let C be a code which contains no monic polynomial. Then all polynomials in C are with leading coefficient non unit. We claim that all the elements in C are multiples of )(xq 1 2 where )(xq1 ! 1 n xx/][Z 4 . Suppose this is not so. Then there exists a polynomial u(x) of minimal degree t1 in C which is not a multiple of g(x) = )(xq 1 2 Therefore, there exists ))((0 2 zxr א 8 Z [x]/< 1 n x > Such that (x) + r(x) v xqu(x) =-st21 1 2 where deg )(xr2< deg u(x) and v=1 or 2 or 3 Cop y ri g ht © 2012 SciRes.105 Now, C is an ideal )(|)(2 )()(2 then )()( deg)( deg if )(2)()( Therefore 1 2122 12 1 xuxq x|rxqCx&rxuxr Cvxxqxuxr st which is a contradiction. Hence )(xr2=0 ֜ )(xq 1 2 | u(x). i.e. u(x) g(x)> = < )(xq 1 2 > i.e., every codeword of C is generated by g(x) = )(xq 1 2 . i.e. C = <g(x)> = < )(xq 1 2 > Lemma 3.5: Let C be a cyclic code of length k 2 over 8 Z containing monic polynomials and leading coefficient of minimal degree polynomial g(x) = )(xq 1 2 in C is 2 or 6, then C = =<f(x), )(xq 1 2 > where f(x) be a monic polynomial of minimal degree t among all monic polynomials in C. Moreover, )(|)( xfxq 1 and any code ! )(),(xqxfC 1 2is strictly contained in the code generated by )(xq1 . Proof: Suppose C is a code which contains a monic polynomial (x),f(x)+f(x)+f(x)=f321 2 22 of minimal degree t among all monic polynomials in C. Let S be the set of polynomials of C of degree less than t. Then leading coefficient of all polynomials in S is a non unit or zero divisor. Let c(x) C, by division algorithm unique polynomials = S(x)r f(x)deg(x) < rdeg if Now C (x) r idealan is C As (1) )f(xdeg(x)<rdegor 0(x) = r where(x) (x)+rc(x)=f(x)q s.t. (x)(x), rq 4 4 4 4443 43 then leading coefficient of (x)r4 must be a zero divisor. Let g(x)= )(xq 1 2 be minimal degree polynomial in S with leading coefficient 2 or 6 . It follows as in Lemma 3.4, (x)r 4 is multiple of )(xq 1 2 and ! ! )(2),( implieswhich )()(2)( get we(1),equation in ngsubstituti )()(2..1/][)( 1 113 11481 xqxfC xwxqxf(x)qc(x) xwxqxrtsxxZxw n As f(x) is monic, therefore 2f(x) is polynomials with leading coefficient 2. Therefore )(xq 1 2 | 2f(x) ֜ )(|)( xfxq 1 . Lemma 3.6: Let C be a cyclic code of length k 2 over 8 Z which contains polynomials with leading coefficient 4 only. Let g(x) be minimal degree polynomial in C, then C = <g(x)> = < )(xq2 4 > where )(xq2 ! 1x/]x[Z n 2 . Proof: We claim first that content of g(x),the minimal degree polynomial in C, is 4. If this is not so, then 2g(x) is a non zero polynomial of degree less than degree of g(x) belong to C, which is a contradiction to the choice of deg g(x). ֜content of g(x) =4 ֜ g(x) = )(xq 2 4 where )(xq2 2[x]/< 1 n x > Now, we claim that all polynomials in C are multiples of )(xq 2 4 , where )(xq2 ! 1 2n xxZ/][ . Suppose this is not so, then a polynomial in C which is not a multiple of g(x)= )(xq 2 4 . Let u1(x) be a polynomial of minimal degree t2 in C which is not divisible by )(xq 2 4 , Cx)x(q)x(u)(x r C )x(uxrx(rx)x(q)x(u.t.s x /]x[Z))(x(r st st n ? ! z 2 2 213 13321 83 4 idealan is deg))(deg( where )4 10 then Now if )(xr 3is not equal to 0, then deg )(xr 3<deg )(xu1 , )(xr 3C implies )(xq2 4 |)(xr 3 ֜ )(xq 2 4 | )(xu1 , which is a contradiction. Therefore )(xr 3= 0 and )(xu1 is a multiple of )(xq2 4 . Hence every polynomial in C is multiple of )(xq 2 4 . Thus C = <g(x)> = < )(xq2 4 >, where )(xq2 belongs to Z2[x]/< 1 n x >. Lemma 3.7 Let C be a cyclic code of length k 2 over 8 Z not containing monic polynomials and let the leading coefficient of minimal degree polynomial g(x) = )(xq 2 4 in C be 4, then ! )(),(xqxqC21 42 , where )(xq1 2 is a polynomial with leading coefficient 2 or 6 of minimal degree ‘s’ among all polynomials with leading coefficient 2 or 6 in C. Moreover, )(|)( xqxq 12 and therefore ! )(),(xqxqC21 42 is strictly contained in the code generated by )(xq2 . Proof: Let g(x) be minimal degree polynomial in Cwith leading coefficient 4, then from Lemma 3.6 it is clear that content of g(x) is 4. That is )()( xqxg 2 4 . Let v(x) be a polynomial with leading coefficient 2 or 6 of minimal degree ‘s’ among all polynomials with leading coefficient 2 or 6 in C. It is easy to prove that content of v(x) is 2. That is v(x) = )(xq 1 2 . Here )(xq 1 2 is not unique. Let S be set of all polynomials with degree less than ‘s’. Therefore S contains polynomial with leading coefficient 4 only. Let Cxc)( therefore leading coefficient of c(x) is 2,4 or 6. If deg(c(x) ) > deg( )(xq 1 2 ) then by lemma 3.4. )(xq1 2 divides c(x). Therefore content of c(x) is 2. If deg(c(x )) < deg( )(xq 1 2 ), then Sxc )( and by lemma 3.6. )(xq2 4 | c(x). Therefore content of c(x) is alteast 2. i.e. c(x)= 2u(x). Now divide u(x) by )(xq1 .As )(xq1 is monic polynomial therefore there exist Q(x) and R(x) such that 106 Cop y ri g ht © 2012 SciRes. ))x(qdeg())x(Rdeg())x(qdeg())x(Rdeg(if )x(R)x(Q)x(q)x(u)x(c ))x(qdeg())x(Rdeg()x(R )x(R) x(Q)x(q)x(u 11 1 1 1 22 then (2) 222 or 0 where 2 implies this 42 get we(2),equation in value thesubstitute 42 such that exist theretherefore 24q 3.6. lemmaby therefore 2 implies this 21 2 2 S)x(R)x('w)x(q)x((x)Qqc(x) )x('w)x(q)x(Rw'(x) )x(R|)x( S)x(R This implies ! )(),()( xqxqxc 21 42 . That is .)(),(! xqxqC21 42 Lemma 3.8: Let C be a cyclic code of length k 2 over 8 Z such that the leading coefficient of minimal degree polynomial g(x) = )(xq 2 4 in C is 4. Further, let the minimal degree polynomial among all polynomials in C with leading coefficient not equal to 4 be monic, say f(x) of degree‘t’. Then C = <f(x), )(xq2 4 >. Moreover, )(|)( xfxq 2 and therefore ! )(),(xqxfC 2 4 is strictly contained in the code generated by )(xq2 . Proof: Suppose C is a code which contains a monic polynomial (x),f(x)+f(x)+f(x)=f321 2 22 of minimal degree t among all polynomials with leading coefficient unit or 2 or 6. Here f(x)is not unique. Let S be the set of polynomials of C of degree less than t. Then leading coefficient of all polynomials in S is 4. Let c(x) C, by division algorithm unique polynomials S(x)r f(x)deg(x) < rdeg C (x) r C )x(fdeg)x(rdeg)x(r )x(r)x(q)x(f)x(c .t.s)x(r),x(q 4 4 4 44 43 43 if Now idealan is As or 0 where (3) Let g(x)= )(xq2 4 be the minimal degree polynomial in S with leading coefficient 4. It follows, as in Lemma 3.6 that (x)r 4 is multiple of )(xq2 4 and ! ! )x(q),x(fC )x(w)x(q)x(f(x)qc(x) )x(w)x(q)x(r.t.sx/)x(Z)x(w n 2 223 22482 4 implieswhich 4 get we(3),equation in ngsubstituti 41 Lemma 3.9: Let C be a cyclic code of length k 2 over 8 Z such that leading coefficient of minimal degree polynomial g(x) = )(xq2 4 in C is 4. Further, let the minimal degree polynomial among all polynomials in C with leading coefficient not equal to 4 be )(xq 1 2 of degree‘s’ and f(x) be a monic polynomial of minimal degree t among all monic polynomials in C. Then C = <f(x), )(xq1 2 , )(xq2 4 >. Moreover, )(|)(|)( xfxqxq 12 and therefore ! )(),(),(xqxqxfC 21 42 is strictly contained in the code generated by )(xq2 . Proof: Suppose C is a code which contains a monic polynomial (x),f(x)+f(x)+f(x)=f 321 2 22 of minimal degree t among all monic polynomials in C. Here f(x) need not be unique. Let S be the set of polynomials of C of degree less than t. Then leading coefficient of all polynomials in S is either 2,4 or 6. Let c(x) C, by division algorithm unique polynomials ))(deg())(deg(or )(either where (4) )()()()(such that and )( xfxrxr xrxqxfxcr(x)xq 0 If ))(deg())(deg( xfxr then Sxr )( ,by Lemma 3.7. ! )(),()( xqxqxr 21 42 therefore there exist )()()()(such that )( and )(xvxqxuxqr(x)xvxu 21 42 where )(xq 1 2 be a polynomial with leading coefficient 2 or 6 of minimal degree ‘s’ among all polynomials with leading coefficient 2 or 6 in C. Substitute the value of r(x) in (4), we get )()()()()()()(xvxqxuxqxqxfxc 21 42 . That is ! )(),(),(xqxqxfC 21 42. Theorem 3.10: Cyclic codes in R of length k 2 are generated as ideals by at most three elements. Proof: The theorem follows from Lemmas 3.3 to 3.9. Note: This result has also been generalised by us for cyclic codes of length k 2 over m Z 2 for all m. REFRENCES [1] T. Abualrub and R. Oehmke, “Cyclic codes of length e 2 over Z4” Discrete Applied Mathematics 128 (2003) 3 – 9. [2] A.R. Calderbank, N.J.A. Sloane, Modular and p-adic cyclic codes, Designs Codes Cryptogr. 6 (1995) 21–35. [3] P. Kanwar, S.R. Lopez-Permouth, Cyclic codes over the integers modulo p, Finite Fields Appl. 3 (4) (1997) 334–1352. [4] F.J. MacWilliams, N.J.A. Sloane, The Theory of Error- Correcting Codes, Ninth impression, North-Holland, Amsterdam, 1977. [5] T. Blackford, Cyclic codes over Z4 of oddly even length, Discrete Applied Mathematics, Vol. 128 (2003) pp. 27–46. [6] Steven T. Dougherty, San Ling,Cyclic Codes Over Z4 of Even Length, Designs, Codes and Cryptography, vol 39, pp 127–153, 2006 [7] Shi Minjia, Zhu Shixin. Cyclic Codes Over The Ring ZP2Of Length pe. Journal Of Electronics (China), vol 25, no 5,(2008), 636-640. [8] I.S.Luthar, I.B.S.Passi. Algebra volume 2 Rings, Narosa Publishing House, first edition,2002. Cop y ri g ht © 2012 SciRes.107 |