Duadic Codes over the Ring Fq[u] /＜um-u＞ and Their Gray Images

Show more

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.

References

[1] Pless, V. and Qian, Z. (1996) Cyclic Codes and Quadratic Residue Codes over Z_{4. IEEE Transactions on Information Theory, 42, 1594-1600.}

[2] Chiu, M.H., Yau, S.T. and Yu, Y. (2000) Z_{8}-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 Z_{9}. 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 F_{p}+uF_{p} 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 F_{p}+vF_{p}. 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 F_{2}+uF_{2}+u2F_{2}. 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 F_{p}+vF_{p}+v2F_{p}. Arithmetic of Finite Fields 5th International Workshop WAIFI 2014, Gebze, 204-211.

[8] Raka, M., Kathuria, L. and Goyal, M. (2016) (1-2u^{3})-Constacyclic Codes and Quadratic Residue Codes over F_{p}[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.