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
Supplement2012 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
3C 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