Journal of Computer and Communications
Vol.04 No.12(2016), Article ID:71547,13 pages
10.4236/jcc.2016.412003
Duadic Codes over the Ring and Their Gray Images
Mokshi Goyal, Madhu Raka
Centre for Advanced Study in Mathematics, Panjab University, Chandigarh, India
Copyright © 2016 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: August 10, 2016; Accepted: October 24, 2016; Published: October 27, 2016
ABSTRACT
Let be any natural number and let
be a finite non-chain ring, where
and q is a prime power congruent to 1 modulo
. In this paper we study duadic codes over the ring
and their extensions. A Gray map from
to
is defined which preserves self duality of linear codes. As a consequence self-dual, formally self-dual and self-orthogonal codes over
are constructed. Some examples are also given to illustrate this.
Keywords:
Quadratic Residue Codes, Duadic Codes, Extended Duadic-Codes, Gray Map, Self-Dual, Self-Orthogonal Codes, Formally Self-Dual Codes
1. Introduction
Duadic codes form a class of cyclic codes that generalizes quadratic residue codes from prime to composite lengths. While initially quadratic residue codes were studied within the confines of finite fields, there have been recent developments on quadratic residue codes over some special rings. Pless and Qian [1] studied quadratic residue codes over, Chiu et al. [2] extended the ideas to the ring
and Taeri [3] considered QR- codes over
. Kaya et al. [4] and Zhang et al. [5] studied quadratic residue codes over
where p is an odd prime. Kaya et al. [6] studied quadratic residue codes over
whereas Liu et al. [7] studied them over non-local ring
where
and p is an odd prime. The authors [8] along with Kathuria extended their results over the ring
where
and. In [9] the authors studied quadratic residue codes and their
extensions over the ring where
and p is a prime satisfying
generalizing all the previous results.
There are duadic codes which are not quadratic residue codes, but they have properties similar to those of quadratic residue codes. In this paper we extend our
results of [9] to duadic codes over the ring, where
, q is a prime power congruent to 1 modulo
. The Gray map defined in
[9] is also extended from which preserves linearity and in some special
cases preserves self duality. The Gray images of extensions of duadic codes over the ring lead to construction of self-dual, formally self-dual and self-orthogonal codes. We give some examples of duadic but non quadratic residue codes which give rise to a [40,20,6] self-dual code over
, a [27,12,6] self orthogonal code over
, a [30,12,8] self-orthogonal code over
and a formally self-dual [24,12,6] code over
.
The paper is organized as follows: In Section 2, we recall duadic codes of length n
over and state some of their properties. In Section 3, we study the ring
, cyclic codes over ring
and define the Gray map
. In Section 4, we study duadic codes over
, their extensions and give some of their properties. We also give some examples to illustrate our results.
2. Duadic Codes over and Their Properties
In this section we give the definition of duadic codes and state some of their properties. Before that we need some preliminary notations and results.
A cyclic code of length n over
can be regarded as an ideal of the ring
. It has a unique idempotent generator
.
Let. The
cyclic code
has generating
idempotent, its dual is the repetition code with generating idempotent
.
A polynomial is called even like if
otherwise it is
called odd like. A code is called even like (odd like) if all its codewords are even like (odd like). For
,
defined as
is called a multiplier where
. It is extended on
by defining
.
Suppose n is odd, and
, where
(i),
are union of q-cyclotomic cosets mod n.
(ii)
(iii) There exists a multiplier,
such that
and
.
Then codes and
having
and
as defining sets are called a pair of odd like duadic codes and codes
and
having
and
as def- ining sets are called a pair of even like duadic codes.
It is known that duadic codes exist if and only if q is a square mod n.
There is an equivalent definition of duadic codes in terms of idempotents. (For details see Huffman and Pless [10] , Chapter 6).
Let and
be two even like idempotents with
and
. The codes
and
form a pair of even like duadic codes if and only if
(1) the idempotents satisfy
(2) There is a multiplier such that
and
.
i.e. and
Associated to and
there is a pair of odd like duadic codes
and
generated by idempotents
and
respectively, where
,
If (1) and (2) hold we say that gives a splitting for even like duadic codes
and
or for the odd like duadic codes
and
.
Lemma 1: Let and
be a pair of even-like duadic codes of length n over
. Suppose
gives the splitting for
and
. Let
and
be the associated odd-like duadic codes. Then:
(i)
(ii) and
,
(iii) is even like subcode of
for
,
(iv) and
, and
(v) for
.
This is part of Theorem 6.1.3 of [10] .
Lemma 2: Let and
be a pair of even-like duadic codes over
with
and
the associated pair of odd-like duadic codes.
(i) If and
then and
.
(ii) If and
then and
Proof follows from Theorems 6.4.2 and 6.4.3 of [10] .
Lemma 3:,
,
,
. Further
and
.
Proof follows immediately from the definition and Lemma 1.
3. Cyclic Codes over the Ring R and the Gray Map
Let q be a prime power,. Throughout the paper,
denotes the commutative ring
, where
,
is a natural number and
.
is a ring of size
and characteristic p. For a primitive element
of
, take
, so that
and
. Let
denote the following elements of
:
(1)
A simple calculation shows that
(2)
The decomposition theorem of ring theory tells us that.
For a linear code of length n over the ring
, let
.
Then are linear codes of length n over
,
and
. For a code
over
, the dual code
is defined as
where
denotes the usual Euclidean inner
product. is self-dual if
and self-orthogonal if
. A code
is called formally self-dual if
and
have the same weight distribution.
The following result is a simple generalization of a result of [7] .
Theorem 1: Let be a linear code of length n over
. Then
(i) is cyclic over
if and only if
are cyclic over
.
(ii) If,
, then
where
and
.
(iii) Further.
(iv) Suppose that Let
then
.
(v)
(vi) where
, where
is the reciprocal polynomial of
(vii).
The following is a well known result :
Lemma 4: (i) Let C be a cyclic code of length n over a finite ring S generated by the idempotent E in then
is generated by the idempotent
.
(ii) Let C and D be cyclic codes of length n over a finite ring S generated by the idem-
potents in
then
and
are generated by the ide-
mpotents and
respectively.
Let the Gray map be given by
where M is an nonsingular matrix of Vandermonde determinant
and V is any nonsingular matrix over
of order
. This map can be extended from
to
component wise.
Let the Gray weight of an element be
, the Hamming weight of
. The Gray weight of a codeword
is defined
as. For any two elements
, the Gray distance
is given by
.
Theorem 2. The Gray map is an
-linear, one to one and onto map. It is also
distance preserving map from (, Gray distance
) to (
, Hamming distance).
Further if the matrix V satisfies,
, where
denotes the transpose
of the matrix V, then the Gray image of a self-dual code
over
is a self-
dual code in.
The proof follows exactly on the same lines as the proof of Theorem 2 of [9] . The only difference is that here q is an arbitrary prime power and not just an odd prime. For the sake of completeness of the result we reproduce the proof here.
Proof. The first two assertions hold as is an invertible matrix over
.
Let now,
, satisfying
. So that
(3)
Let be a self-dual code over
. Let
where
and
. Then
implies that (comparing the coefficients of on both sides)
(4)
(5)
for each r,
For convenience we call and
. Then
Similarly
Using (2), we find that
Now
Using (3) and (4), one can check that each is zero, which proves the result.
4. Duadic Codes over the Ring R
We now define duadic codes over the ring in terms of their idempotent generators. Let
denote the ring
. Using the properties (2) of idempotents
, we have
Lemma 5: Let and
be idempotents as defined in
(1). Then for and for any tuple
of odd-like idem-
potents not all equal and for any tuple of even-like idempotents not all equal,
and
are respectively odd-like and even-like idempotents in the ring
.
Throughout the paper we assume that q is a square mod n so that duadic codes of
length n over exist. The construction and the properties of duadic codes over the ring
is similar to that of quadratic residue codes over the ring
, where
given in [9] . We denote the set
by
. For each
, let
denote the odd-like idempotent of the ring
in which
occurs at the ith place and
occurs at the remaining
places i.e.
(6)
For,
let
denote the odd-like idempotent in which
occ- urs at the
and
places and
occurs at the remaining
places i.e.
(7)
In the same way, for,
let
denote the odd-like idempotent
(8)
For,
, where
let the corresponding odd-like idempotents be
(9)
(10)
Similarly we define even-like idempotents for and
,
,
(11)
(12)
(13)
(14)
Let denote the odd-like duadic codes and
denote the even-like duadic codes over
generated by the corresponding idempotents, i.e.
,
,
,
,
,
,
,
.
Theorem 3: Let, Then for
,
is equivalent to
and
is equivalent to
. For
,
,
is equivalent to
, and
is equivalent to
. Further there are
inequivalent odd-like duadic codes and
inequivalent even-like duadic codes over the ring
.
Proof: Let the multiplier give splitting of
and
or of
and
. Then
,
,
,
and so
,
,
,
. This proves that
,
, and
.
Note that,
,
,
. Therefore
(15)
(16)
For a given positive integer k, the number of choices of the subsets of
is
.
Let m be even first. Then. Using (15) and
(16), we find that the number of inequivalent odd-like or even-like duadic-codes is
. If m is odd the number of inequiv- alent odd-like or even-like duadic codes is
.
Let denote the greatest integer
. we have
when m is even and
when m is odd.
Theorem 4: If, then for subsets
of
with cardinality k,
, the following assertions hold for duadic codes over
.
(i)
(ii)
(iii)
(iv)
(v)
(vi)
(vii)
Proof: From the relations (2),(6)-(14) we see that,
,
and
. Therefore by Lemmas 1 and 4,
, and
;
, and
. This proves (i)-(iv).
Using that and
from Lemma 3 and noting that
we find that
.
Similarly using and
from Lemma 3, we see that
.
Therefore and
. This proves (v) and (vi).
Finally for, we have
it being a repetition code over. Therefore
This gives. Now we find that
since. This gives
.
Theorem 5 : If, and if
,
then for each possible tuple
, the following assertions hold for duadic codes over
.
(i)
(ii) is self orthogonal.
Proof: By using Lemma 2 and Lemma 4, we have so
. Similarly
. For
. Now result (i) follows from Lemma 4. Using (vi) of Theorem 4, we have
. Therefore
is self orthogonal.
Similarly we get
Theorem 6 : If and
,
then for all possible choices of
, the following assertions hold for duadic codes over
.
(i)
(ii)
The extended duadic codes over are formed in the same way
as the extended duadic codes over are formed. See Theorem 6.4.12 of [10] .
Consider the equation
(17)
This equation has a solution in
if and only if n and −1 are both squares or both non squares in
(see [10] , Chapter 6).
Theorem 7: Suppose there exist a in
satisfying Equation (17). If
,
then for all possible choices of
, the extended duadic codes
of length
are self-dual.
Proof: As, by Theorem 4, let
be the exten- ded duadic code over
generated by
where is a generator matrix for the even-like duadic code
. The row above the matrix shows the column labeling by
. Since the all one vector belongs to
and its dual
is equal to
, the last row of
is orthogonal to all the previous rows of
. The last row is orthog- onal to itself also as
in
. Further as
is self orthogonal by Theorem 5, we find that the code
is self orthogonal. Now the result foll-
ows from the fact that.
Theorem 8: Suppose there exists a in
satisfying Equation (17). If
,
then for all possible choices of
, the extended duadic codes satisfy
.
Proof: Let and
be the extended duadic codes over
generated by
and
respectively where is a generator matrix for the duadic code
and
is a generator matrix for the duadic code
. Let v denote the all one
vector of length n. As and
, v is orthogonal to all the
rows of. Also
. Further rows of
are in
, so are orthogonal to rows of
. Therefore all rows of
are orthogonal to all the rows of. Hence
. Now the result follows from comparing their orders.
Corollary: Let the matrix V taken in the definition of the Gray map satisfy
,
. If
, then for all possible choices of
, the Gray images of extended duadic codes
i.e.
are self-dual codes of length
over
and the Gray images of the even-like duadic codes
i.e.
are self-orthogonal codes of length
over
. If
, then
are formally self-dual codes of length
over
.
Next we give some examples to illustrate our theory. The minimum distances of all the examples appearing have been computed by the Magma Computational Algebra System.
Example 1: Let,
,
and
be a matrix over
satisfying. The even like idempotent generators of duadic codes of length 9 over
are
,
. Here
,
. The Gray image of even like duadic code
is a self-orthogonal [27,12,6] code over
. Here there is no
satisfying Equation (17).
Example 2: Let,
,
and
be a matrix over satisfying
. The even like idempotent generators of duadic codes of length 9 over
are
,
. Here
,
and
is a solution of (17). The Gray image
of extended duadic code
is a self-dual [40,20,6] code over
.
Example 3: Let,
,
and
be a matrix over satisfying
. The even like idempotent generators of duadic codes of length 5 over
are
,
. The Gray image of even like duadic code
is a self- orthogonal [30,12,8] code over
.
Example 4 : Let,
,
and let a be the primitive element of
be a matrix over satisfying
. The even like idempotent generators of duadic codes of length 5 over
are
,
. Here
,
and
is a solution of (17). The Gray image
of extended duadic code
is a formally self-dual [24,12,6] code over
.
Cite this paper
Goyal, M. and Raka, M. (2016) Duadic Codes over the Ring
References
- 1. Pless, V. and Qian, Z. (1996) Cyclic Codes and Quadratic Residue Codes over Z4. IEEE Transactions on Information Theory, 42, 1594-1600.
- 2. Chiu, M.H., Yau, S.T. and Yu, Y. (2000) Z8-Cyclic Codes and Quadratic Residue Codes. Advances in Applied Mathematics, 25, 12-33.
http://dx.doi.org/10.1006/aama.2000.0687 - 3. Taeri, B. (2009) Quadratic Residue Codes over Z9. The Korean Journal of Mathematics, 46, 13-30.
http://dx.doi.org/10.4134/JKMS.2009.46.1.013 - 4. Kaya, A., Yildiz, B. and Siap, I. (2014) Quadratic Residue Codes over Fp+uFp and Their Gray Images. ournal of Pure and Applied Algebra, 218, 1999-2011.
http://dx.doi.org/10.1016/j.jpaa.2014.03.002 - 5. Zhang, T. and Zhu, S. (2012) Quadratic Residue Codes over Fp+vFp. Journal of University of Science and Technology of China, 42, 208-213.
- 6. Kaya, A., Yildiz, B. and Siap, I. (2014) New Extremal Binary Self-Dual Codes of Length 68 from Quadratic Residue Codes over F2+uF2+u2F2. Finite Fields and Their Applications, 29, 160-177.
http://dx.doi.org/10.1016/j.ffa.2014.04.009 - 7. Liu, Y., Shi, M. and Solé, P. (2014) Quadratic Residue Codes over Fp+vFp+v2Fp. Arithmetic of Finite Fields 5th International Workshop WAIFI 2014, Gebze, 204-211.
- 8. Raka, M., Kathuria, L. and Goyal, M. (2016) (1-2u3)-Constacyclic Codes and Quadratic Residue Codes over Fp[u]/4>. Cryptogr. Commun.
http://dx.doi.org/10.1007/s12095-016-0184-7 - 9. Goyal, M. and Raka, M. (2016) Quadratic Residue Codes over the Ring F
[u]/m-u> and Their Gray Images. arXiv: 1609. 07862v1 [math.NT] 2016.
- 10. Cary Huffman, W. and Pless, V. (2003) Fundamentals of Error-Correcting Codes. Cambridge University Press, Cambridge.