 Cyclic codes of length 2kover Z8Arpana 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 k2 over 8Z for any natural number k. It is known that cyclic codes of length k2 over 8Z are ideals of the ring R=! 12kxx /][Z8. In this paper we prove that the ring R= ! 12kxx /][Z8is 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 k2 over 8Z 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 nR. 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 nR. Let 8Z denote the ring of integers modulo 8. Cyclic codes over ring mpZof length n such that. (n,p)=1 are studied by A.R. Calderbank, N.J.A. Sloane in  and P. Kanwar, S.R. Lopez-Permouth in . Most of the work has been done on the generators of cyclic code of length n over 4Z where 2 | n. In , Abualrub and Oehmke, gave the structure of cyclic codes over 4Zof length k2, in  Blackford classified all cyclic codes over 4Z of length 2n where n is odd and in  Steven T. Dougherty & San Ling gave the generator polynomial of cyclic codes over 4Z for arbitrary even length. The structure of cyclic codes over 2pZof length epis given by Shi Minjia, Zhu Shixin in . *(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 2Z of length n are principal ideals. Moreover, cyclic codes over 2Z of length n are generated by polynomials of the type tx)( 1where t | n and these generators are divisors of 1nx. But the situation is different in case of cyclic codes over rings. In this paper we prove that the ring R= ! 12kxx /][Z8is 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nx over 8Z. We also prove that cyclic codes of length k2 over 8Z are generated as ideals by at most three elements. Throughout this paper we assume that n = k2so that R = 8Z[x]/< 1nx>. 2. PreliminariesAny codeword from a cyclic code of length n can be represented by polynomials modulo 1nx. Any codeword c = (c0,c1,c2,…,cn-1) can be represented by polynomial 1110  nnxcxccxc ...)(in the ring R. Definition 2.1: Define a map !o)1-x[x]/ZR:n2 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 2Z and 8Z are rings under different binary operations, but addition and multiplication of elements in 2Zcan be obtained from the addition and multiplication of elements of 8Z reducing them by modulo 2. Any element a 8Z can be written as a= b+2c+4d s.t. b,c,d 2Z. Therefore any polynomial f(x) 8Z[x] can be represented as(x),f(x)+f(x)+f(x)=f321222whe re][Z2x (x) fifor every i. Open Journal of Applied Sciences Supplement：2012 world Congress on Engineering and Technology104 Copyright © 2012 SciRes. The image of any polynomial f(x)  R, under the homomorphism  is(x)f1. Definition 2.2: The content of the polynomial mmxaxaaf(x)  ...10where the ai’s belong to8Z, is the greatest common divisor of.,...,, maaa 10 Theorem 2.3: The Correspondence Theorem.If AA co: is a surjective ring homomorphism having kernel ߟ, then II co1' is a 1-1 correspondence between the totality of ideals Icof Ac and the totality of those ideals of A which contain Ș. Theorem 2.4: The General Isomorphism Theorem. If AA co: 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 cco)()(such that //: for all a in A. Moreover,  is an isomorphism of A/I with IAcc/. Lemma 2.5 : If R is a local ring with the unique maximal ideal M and M= (a) = (a1,a2,…, an), then M = for some i. 3. Generators of Cyclic Codes Over Z8.Consider the ring R = 8Z[x] / <1nx>. 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 ! 11nxxR /][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() = <2, x – 1> is ideal of R  By theorem 2.4, there exists a unique ring isomorphism /IR(I)Ș5 1o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= )(I1) 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 = or >,xM=< 12 =<2>. But neither 2  nor (x - 1)  <2>. Therefore, R is not a principal ideal ring. Now, we prove that cyclic codes of length k2 over 8Zare generated as ideals by at most three elements. We have the following: Lemma3.3: Let C be a cyclic code of length k2 over 8Z. If minimal degree polynomial g(x) in C is monic, then C = where (x) g(x) + g(x) + g(x) = g321 42 such that 01z)(xg and ][ Z2x(x) gifor i = 1, 2, 3. Proof:Suppose C is a cyclic code of length n = k2 over 8Z. Let (x) g(x) + g(x) + g(x) = g321 42 such that ][ Z2x(x) gi 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 8Z 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 ifimplies Thisdegdegorwhere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 = . Lemma 3.4: Let C be a cyclic code of length k2 over 8ZIf C contains no monic polynomial and leading coefficient of minimal degree polynomial g(x) in C is 2 or 6, then C = = <)(xq12> where )(xq1! 1nxx/][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 ssxcxccxg ...)( 10 and there exist some t such that 0ztc (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{ic (mod 2) for all ݅ and content of g(x) is 2. So g(x) = )(xq12where )(xq1 ! 1nxx/][Z4. 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 )(xq12 where )(xq1! 1nxx/][Z4. 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) = )(xq12 Therefore, there exists ))((02zxr א 8Z[x]/< 1nx> Such that (x) + r(x) v xqu(x) =-st2112 where deg )(xr2< deg u(x) and v=1 or 2 or 3 Copyright © 2012 SciRes.105 Now, C is an ideal )(|)(2)()(2 then )()( deg)( deg if)(2)()( Therefore12122121xuxqx|rxqCx&rxuxrCvxxqxuxrst  which is a contradiction. Hence )(xr2=0 ֜ )(xq12| u(x). i.e. u(x) g(x)> = < )(xq12> i.e., every codeword of C is generated by g(x) = )(xq12. i.e. C = = < )(xq12> Lemma 3.5: Let C be a cyclic code of length k2 over 8Z containing monic polynomials and leading coefficient of minimal degree polynomial g(x) = )(xq12in C is 2 or 6, then C = = where f(x) be a monic polynomial of minimal degree t among all monic polynomials in C. Moreover, )(|)( xfxq1and any code ! )(),(xqxfC 12is 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)=f321222 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) = < )(xq24> where )(xq2 ! 1x/]x[Zn2. 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) = )(xq24 where )(xq2 2[x]/< 1nx> Now, we claim that all polynomials in C are multiples of )(xq24, where )(xq2 ! 12nxxZ/][. Suppose this is not so, then ׌ a polynomial in C which is not a multiple of g(x)=)(xq24. Let u1(x) be a polynomial of minimal degree t2 in C which is not divisible by)(xq24, Cx)x(q)x(u)(x r C)x(uxrx(rx)x(q)x(u.t.sx/]x[Z))(x(rststn ? !z2221313321834 idealan is deg))(deg( where )410 thenNow if )(xr3is not equal to 0, then deg )(xr3 = < )(xq24>, where )(xq2belongs to Z2[x]/< 1nx>. Lemma 3.7 Let C be a cyclic code of length k2 over 8Z not containing monic polynomials and let the leading coefficient of minimal degree polynomial g(x) = )(xq24in C be 4, then ! )(),(xqxqC21 42 , where )(xq12 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, )(|)( xqxq12 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)()( xqxg24 . 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) =)(xq12. Here )(xq12 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()(xq12) then by lemma 3.4. )(xq12divides c(x). Therefore content of c(x) is 2. If deg(c(x )) < deg()(xq12), then Sxc )( and by lemma 3.6. )(xq24| c(x). Therefore content of c(x) is alteast 2. i.e. c(x)= 2u(x). Now divide u(x) by )(xq1.As )(xq1is monic polynomial therefore there exist Q(x) and R(x) such that 106 Copyright © 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(u1111122 then (2) 222or 0 where   2 implies this 42get we(2),equation in value thesubstitute 42 such that exist theretherefore24q 3.6. lemmaby therefore 2 implies this2122S)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 k2 over 8Zsuch that the leading coefficient of minimal degree polynomial g(x) = )(xq24in 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 = . Moreover, )(|)( xfxq2 and therefore ! )(),(xqxfC24is 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)=f321222 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) rC)x(fdeg)x(rdeg)x(r)x(r)x(q)x(f)x(c.t.s)x(r),x(q  444444343if Now idealan is Asor 0 where(3) Let g(x)= )(xq24 be the minimal degree polynomial in S with leading coefficient 4. It follows, as in Lemma 3.6 that (x)r4 is multiple of )(xq24and !  !)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 n2223224824 implieswhich 4get we(3),equation in ngsubstituti41Lemma 3.9: Let C be a cyclic code of length k2 over 8Zsuch that leading coefficient of minimal degree polynomial g(x) = )(xq24in C is 4. Further, let the minimal degree polynomial among all polynomials in C with leading coefficient not equal to 4 be)(xq12of degree‘s’ and f(x) be a monic polynomial of minimal degree t among all monic polynomials in C. Then C = . Moreover, )(|)(|)( xfxqxq12 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)=f321222 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 )(xfxrxrxrxqxfxcr(x)xq  0 If ))(deg())(deg( xfxr then Sxr )(,by Lemma 3.7. ! )(),()( xqxqxr 21 42therefore there exist )()()()(such that )( and )(xvxqxuxqr(x)xvxu2142 where )(xq12 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 k2 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 k2 over mZ2 for all m. REFRENCES  T. Abualrub and R. Oehmke, “Cyclic codes of length e2 over Z4” Discrete Applied Mathematics 128 (2003) 3 – 9.  A.R. Calderbank, N.J.A. Sloane, Modular and p-adic cyclic codes, Designs Codes Cryptogr. 6 (1995) 21–35.  P. Kanwar, S.R. Lopez-Permouth, Cyclic codes over the integers modulo p, Finite Fields Appl. 3 (4) (1997) 334–1352.  F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, Ninth impression, North-Holland, Amsterdam, 1977.  T. Blackford, Cyclic codes over Z4 of oddly even length, Discrete Applied Mathematics, Vol. 128 (2003) pp. 27–46.  Steven T. Dougherty, San Ling,Cyclic Codes Over Z4 of Even Length, Designs, Codes and Cryptography, vol 39, pp 127–153, 2006  Shi Minjia, Zhu Shixin. Cyclic Codes Over The Ring ZP2Of Length pe. Journal Of Electronics (China), vol 25, no 5,(2008), 636-640.  I.S.Luthar, I.B.S.Passi. Algebra volume 2 Rings, Narosa Publishing House, first edition,2002. Copyright © 2012 SciRes.107