Share This Article:

New MDS Euclidean and Hermitian Self-Dual Codes over Finite Fields

Abstract Full-Text HTML XML Download Download as PDF (Size:346KB) PP. 325-333
DOI: 10.4236/apm.2017.75019    869 Downloads   1,165 Views  

ABSTRACT

In this paper, we construct MDS Euclidean self-dual codes which are ex-tended cyclic duadic codes. And we obtain many new MDS Euclidean self-dual codes. We also construct MDS Hermitian self-dual codes from generalized Reed-Solomon codes and constacyclic codes.

1. Introduction

Let F q denote a finite field with q elements. An [ n , k , d ] linear code C over F q is a k-dimensional subspace of F q n . These parameters n, k and d satisfy d n k + 1 . If d = n k + 1 , C is called a maximum distance separable (MDS) code. MDS codes are of practical and theoretical importance. For examples, MDS codes are related to geometric objects called n-arcs.

The Euclidean dual code C of C is defined as

C : = { x F q n : i = 1 n x i y i = 0 , y C } . (1)

If q = r 2 , the Hermitian dual code C H of C is defined as

C H : = { x F r 2 n : i = 1 n x i y i r = 0 , y C } . (2)

If C satisfies C = C or C = C H , C is called Euclidean self-dual or Hermitian self-dual, respectively. In [1] [2] discussing Euclidean self-dual codes or Hermitian self-dual codes. If C is MDS and Euclidean self-dual or Hermitian self-dual, C is called an MDS Euclidean self-dual code or an MDS Hermitian self-dual code, respectively. In recent years, In [2] - [9] study the MDS self-dual codes. One of these problems in this topic is to determine existence of MDS self-dual codes. When 2 | q , Grassl and Gulliver completely solve the existence of MDS Euclidean self-dual codes in [5] . In [6] , Guenda obtain some new MDS Euclidean self-dual codes and MDS Hermitian self-dual codes. In [8] , Jin and Xing obtain some new MDS Euclidean self-dual codes from generalized Reed- Solomon codes.

In this paper, we obtain some new Euclidean self-dual codes by studying the solution of an equation in F q . And we generalize Jin and Xing’s results to MDS Hermitian self-dual codes. We also construct MDS Hermitian self-dual codes from constacyclic codes. We discuss MDS Hermitian self-dual codes obtained from extended cyclic duadic codes and obtain some new MDS Hermitian self-dual codes.

2. MDS Euclidean Self-Dual Codes

A cyclic code C of length n over F q can be considered as an ideal, g ( x ) , of the ring R = F q [ x ] x n 1 , where g ( x ) | x n 1 and ( n , q ) = 1 . The set T = { 0 i n 1 | g ( α i ) = 0 } is called the defining set of C, where o r d α = n .

Let S 1 and S 2 be unions of cyclotomic classes modulo n, such that S 1 S 2 = and S 1 S 2 = n \ { 0 } and a S i ( mod n ) = S i + 1 ( mod 2 ) . Then the triple μ a , S 1 and S 2 is called a splitting modulo n. Odd-like codes D 1 and D 2 are cyclic codes over F q with defining sets S 1 and S 2 , respectively. D 1 and D 2 can be denoted by μ a ( D i ) = D i + 1 ( mod 2 ) . Even-like duadic codes C 1 and C 2 are cyclic codes over F q with defining sets { 0 } S 1 and { 0 } S 2 , respectively. Obviously, μ a ( C i ) = C i + 1 ( mod 2 ) . In [10] , A duadic code of length n over F q exists if and only if q is a quadratic residue modulo n.

Let n | q 1 and n be an odd integer. D 1 is a cyclic code with defining set T = { 1 , 2 , , n 1 2 } . Then D 1 is an [ n , n + 1 2 , n + 1 2 ] MDS code. Its dual C 1 = D 1 is also cyclic with defining set T { 0 } . There are a pair of odd-like duadic codes D 1 = C 1 and D 2 = C 2 and a pair of even-like duadic codes C 2 = μ 1 ( C 1 ) .

Lemma 1 [6] Let n | q 1 and n be an odd integer. There exists a pair of

MDS codes D 1 and D 2 with parameters [ n , n + 1 2 , n + 1 2 ] , and

μ 1 ( D i ) = D i + 1 ( m o d 2 ) .

Lemma 2 [11] Let D 1 and D 2 be a pair of odd-like duadic codes of length n over F q , μ 1 ( D i ) = D i + 1 ( mod 2 ) . Assume that

1 + γ 2 n = 0 (*)

has a solution in F q . Let D ˜ i = { c ˜ | c D i } for 1 i 2 and c ˜ = ( c 0 , c 1 , , c n 1 , c ) with c = γ i = 0 n 1 c i . Then D ˜ 1 and D ˜ 2 are Euclidean self-dual codes.

In [11] , the solution of (*) is discussed when n is an odd prime. In [5] , the solution of (*) is discussed when n is an odd prime power. Next, we discuss the solution of (*) for any odd integer n with n | q 1 .

Definition 1 (Legendre Symbol) [12] Let p be an prime and a be an integer.

( a p ) = { 0, if a 0 ( m o d p ) , 1, if a ( 0 ) is a quadratic residue modulo p , 1, if a is not a quadratic residue modulo p . (3)

Proposition 1 [12]

( a p ) = ( p 1 p ) ( p s p ) ,

where a = p 1 p s .

Definition 2 (Jacobi Symbol) [12] Let m and n ( 0 ) be two integers.

( m n ) = ( m p 1 ) ( m p h ) ,

where n = p 1 p h .

We cannot obtain m ( 0 ) is a quadratic residue modulo n from ( m n ) = 1 . But we have the next proposition.

Proposition 2 Let m ( 0 ) and n be two integers and ( m , n ) = 1 . If m is a quadratic residue modulo n, then

( m n ) = 1.

If

( m n ) = 1 ,

then m is not a quadratic residue modulo n.

Proof Obviously.

Lemma 3 (Law of Quadratic Reciprocity) [12] Let p and r be odd primes, ( p , r ) = 1 .

( p r ) ( r p ) = ( 1 ) r 1 2 p 1 2 . (4)

Corollary 1 Let p and r be odd primes.

(1) When p 1 ( m o d 4 ) or r 1 ( m o d 4 ) ,

( p r ) = ( r p ) .

(2) When p r 3 ( m o d 4 ) ,

( p r ) = ( r p ) .

Theorem 1 Let q = r t and r be an odd prime. Let n | q 1 and n be an odd integer. And

n = p 1 e 1 p s e s p s + 1 e s + 1 p h e h ,

where

p 1 p s 3 ( m o d 4 ) , p s + 1 p h 1 ( m o d 4 ) .

(1) When q 1 ( m o d 4 ) , there is a solution to (*) in F q .

(2) Let q 3 ( m o d 4 ) . If i = 1 s e i is an odd integer, there is a solution to (*) in F q .

Proof (1) q 1 ( m o d 4 ) .

(1.1) r 3 ( m o d 4 ) . So we have that t is even. Then every quadratic equation with coefficients in F r , such as Eq. (*), has a solution in F r 2 F q .

(1.2) r 1 ( m o d 4 ) and 2 | t . The proof is similar as (1.1).

(1.3) r 1 ( m o d 4 ) and 2 t .

1 = ( q n ) = ( r n ) = ( r p 1 ) e 1 ( r p h ) e h = ( p 1 r ) e 1 ( p h r ) e h = ( n r ) .

So n is a quadratic residue modulo r. And −1 is a quadratic residue modulo r. So there is a solution to (*) in F q .

(2) q 3 ( m o d 4 ) . Then r 3 ( m o d 4 ) and t is odd.

1 = ( q n ) = ( r n ) = ( r p 1 ) e 1 ( r p s ) e s ( r p s + 1 ) e s + 1 ( r p h ) e h = ( 1 ) e 1 ( p 1 r ) e 1 ( 1 ) e s ( p s r ) e s ( p s + 1 r ) e s + 1 ( p h r ) e h = ( 1 ) i = 1 s e i ( p 1 r ) e 1 ( p s r ) e s ( p s + 1 r ) e s + 1 ( p h r ) e h = ( 1 ) i = 1 s e i ( n r ) .

If i = 1 s e i is odd, n is not a quadratic residue modulo r. And −1 is not a quadratic residue modulo r. So n is a quadratic residue modulo r. There is a solution to (*) in F q .

Remark In fact, n | q 1 , and n is an odd integer and q 3 ( m o d 4 ) . We can easily prove that there is a solution to (*) in F q if and only if i = 1 s e i is an odd integer.

Let n | q 1 , q 1 ( m o d n ) . q is a quadratic residue modulo n. y 2 q ( m o d n ) . Let q = r t and q 3 ( m o d 4 ) , where r is a prime. Then r 3 ( m o d 4 ) and t is odd. Equation (*) has solutions in F q if and only if Equation (*) has solutions in F r . And r is a quadratic residue modulo n.

( y r t 1 2 ) 2 r ( m o d n ) . Let p be an odd prime divisor of n. r is a quadratic residue modulo p. Then ( r p ) = 1 . By Law of Quadratic Reciprocity, p | n ,

( p r ) = { 1 , p 1 ( mod 4 ) 1 , p 3 ( mod 4 ) .

The Legendre symbol

( n r ) = ( 1 r ) ( p 1 r ) e 1 ( p s r ) e s ( p s + 1 r ) e s + 1 ( p h r ) e h = ( 1 ) 1 + i = 1 s e i = { 1 , i = 1 s e i i s odd 1 , i = 1 s e i i s even ,

where n = p 1 e 1 p s e s p s + 1 e s + 1 p h e h , p 1 p s 3 ( m o d 4 ) and p s + 1 p h 1 ( m o d 4 ) .

Theorem 2 Let q = r t be a prime power, n | q 1 and n be an odd integer. Then there exists a pair D 1 , D 2 of MDS odd-like duadic codes of length n and

μ 1 ( D i ) = D i + 1 ( mod 2 ) , where even-like duadic codes are MDS self-orthogonal, and T 1 = { 1 , , n 1 2 } . Furthermore,

(1) If q = 2 t , then D ˜ i are [ n + 1, n + 1 2 , n + 3 2 ] MDS Euclidean self-dual codes.

(2) If q 1 ( m o d 4 ) , then D ˜ i are [ n + 1, n + 1 2 , n + 3 2 ] MDS Euclidean self-dual codes.

(3) If q 3 ( m o d 4 ) and i = 1 s e i is an odd integer, then D ˜ i are [ n + 1, n + 1 2 , n + 3 2 ] MDS Euclidean self-dual codes, where n = p 1 e 1 p s e s p s + 1 e s + 1 p t e h and p 1 p s 3 ( m o d 4 ) , p s + 1 p h 1 ( m o d 4 ) .

Proof Obviously, D i are [ n , n + 1 2 , n + 1 2 ] MDS odd-like duadic codes. If there is a solution to (*), we want to prove D ˜ i are [ n + 1, n + 1 2 , n + 3 2 ] MDS Euclidean self-dual codes, and we only need to prove that

c D i and w t ( c ) = n + 1 2 , then w t ( c ˜ ) = n + 1 2 + 1.

This is equivalent to prove that c 0 . It can be proved similarly by which proved in [5] .

When q = 2 t , there is a solution to (*) in F 2 t , D ˜ i are [ n + 1, n + 1 2 , n + 3 2 ] MDS Euclidean self-dual codes by Lemma 2.

We can obtain (2) and (3) from Theorem 1 and Lemma 2. Theorem 2 is proved.

We list some new MDS Euclidean self-dual codes in the next Table 1.

3. MDS Hermitian Self-Dual Codes

Let n q 2 . We choose n distinct elements { α 1 , , α n } from F q 2 and n nonzero elements { v 1 , , v n } from F q 2 . The generalized Reed-Solomon code

Table 1. Some new MDS Euclidean self-dual codes.

G R S k ( α , v ) : = { ( v 1 f ( α 1 ) , , v n f ( α n ) ) : f ( x ) F q 2 [ x ] , deg f ( x ) k 1 }

is a q2-ary [ n , k , n k + 1 ] MDS code, where α = ( α 1 , , α n ) and v = ( v 1 , , v n ) .

Theorem 3 Let n q and 2 | n . Let { α 1 , , α n } be n distinct elements from F q ( F q 2 ) and u i = 1 j n , j i ( α i α j ) 1 , 1 i n . Then there exist v i F q 2 such that u i = v i 2 , for i = 1 , , n , and the generalized Reed-Solomon code G R S n 2 ( α , v ) is an [ n , n 2 , n 2 + 1 ] MDS Hermitian self-dual code over F q 2 , where α = ( α 1 , , α n ) and v = ( v 1 , , v n ) .

Proof Obviously, u i ( 0 ) F q ( F q 2 ) for 1 i n . So there exist v i ( 0 ) F q 2 such that u i = v i 2 for 1 i n . The generalized Reed-Solomon

code G R S n 2 ( α , v ) is an [ n , n 2 , n 2 + 1 ] MDS code over F q 2 . For proving the generalized Reed-Solomon code G R S n 2 ( α , v ) is Hermitian self-dual over F q 2 , we only prove

( v 1 α 1 l , , v n α n l ) ( v 1 q α 1 k q , , v n q α n k q ) = 0, 0 l , k n 2 1.

From the choose of α i , v i and [8, Corollary 2.3],

( v 1 α 1 l , , v n α n l ) ( v 1 q α 1 k q , , v n q α n k q ) = ( v 1 α 1 l , , v n α n l ) ( v 1 α 1 k , , v n α n k ) = 0, 0 l , k n 2 1.

So the generalized Reed-Solomon code G R S n 2 ( α , v ) is an [ n , n 2 , n 2 + 1 ] MDS Hermitian self-dual code over F q 2 .

Next we construct MDS Hermitian self-dual codes from constacyclic codes.

Let C be an [ n , k ] l-constacyclic code over F q 2 and ( n , q ) = 1 . C is considered as an ideal, g ( x ) , of F q 2 [ x ] x n λ , where g ( x ) | ( x n λ ) . Simply, C = g ( x ) .

Lemma 4 [2] Let λ F q 2 * , r = ord q 2 ( λ ) , and C be a l-constacyclic code over F q 2 . If C is Hermitian self-dual, then r | q + 1 .

Lemma 5 [2] Let n = 2 a n ( a > 0 ) and r = 2 b r be integers such that 2 n and 2 r . Let q be an odd prime power such that ( n , q ) = 1 and r | q + 1 , and let λ F q 2 has order r. Then Hermitian self-dual l-constacyclic codes over F q 2 of length n exist if and only if b > 0 and q 1 ( m o d 2 a + b ) .

Let r = ord q 2 ( λ ) and r | q + 1 .

O r , n = { 1 + r j | j = 0 , 1 , , n 1 } .

Then α i ( i O r , n ) are all solutions of x n λ = 0 in some extension field of F q 2 , where ord α = r n . C is called a l-constacyclic code with defining set T O r , n , if

C = g ( x ) and g ( α i ) = 0 , i T .

Theorem 4 Let n = 2 a n ( a > 0 ) and r = 2 b r ( b > 0 ) . r n | q 2 1 . λ F q 2 * with ord λ = r . q 1 ( m o d 2 a + b ) . If r n | 2 ( q + 1 ) , there exists an MDS Hermitian self-dual code C over F q 2 with length n, C is a l-constacyclic code with defining set

T = { 1 + r j | 0 j n 2 1 } .

Proof If r n | q 2 1 , C q 2 ( i ) = { i } , for i O r , n , where C q 2 ( i ) denote the q2-cyclotomic coset of i mod r n . And | T | = n 2 , C is an [ n , n 2 , n 2 + 1 ] MDS l-constacyclic code by the BCH bound of constacyclic code.

When r n | 2 ( q + 1 ) , q = r n l 2 1 . Because q 1 ( m o d 2 a + b ) , l is odd.

( q ) ( 1 + r j ) = q q r j 1 r n l 2 + r j 1 + r ( n 2 + j ) ( mod r n ) .

So

( q ) T T = .

C is MDS Hermitian self-dual by the relationship of roots of a constacyclic code and its Hermitian dual code’s roots.

Remark The MDS Hermitian self-dual constacyclic code obtained from Theorem 4 is different with the MDS Hermitian self-dual constacyclic code in [12] , because ( q + 1 , q 1 ) = 2 for an odd prime power q.

If r = 2 , C is negacyclic. Theorem 4 can be stated as follow.

Corollary 2 Let n = 2 a n ( a 1 ) and n is odd. Let

q 1 ( mod 2 a n ) and q 2 a 1 ( mod 2 a + 1 ) ,

where n | n and n is odd. Then there exists an MDS Hermitian self-dual code C of length n which is negacyclic with defining set

T = { 1 + 2 j | j = 0 , 1 , , n 2 1 } .

Especially, when a = 1 , Corollary 2 is similar as [5, Theorem 11].

From Theorem 3 and Theorem 4, we obtain the next theorem.

Theorem 5 Let n q + 1 and n be even. There exists an MDS Hermitian self-dual code with length n over F q 2 .

4. Conclusion

In this paper, we obtain many new MDS Euclidean self-dual codes by solving the Equation (*) in F q . We generalize the work of [8] to MDS Hermitian self-dual codes, and we construct new MDS Hermitian self-dual codes from constacyclic codes. We obtain that there exists an MDS Hermitian self-dual code with length n over F q 2 , where n q + 1 and n is even. And we also discuss these MDS Hermitian self-dual codes, which are extended cyclic duadic codes. Some new MDS Hermitian self-dual codes are obtained.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Tong, H. and Wang, X. (2017) New MDS Euclidean and Hermitian Self-Dual Codes over Finite Fields. Advances in Pure Mathematics, 7, 325-333. doi: 10.4236/apm.2017.75019.

References

[1] Dicuangco, L., Moree, P. and Solé, P. (2007) The Lengths of Hermitian Self-Dual Extended Duadic Codes. Journal of Pure and Applied Algebra, 209, 223-237.
https://doi.org/10.1016/j.jpaa.2006.05.024
[2] Yang, Y.S. and Cai, W.C. (2015) On Self-Dual Constacyclic Codes over Finite Fields. Designs, Codes and Cryptography, 74, 355-364.
https://doi.org/10.1007/s10623-013-9865-9
[3] Aaron Gulliver, T., Kim, J.L. and Lee, Y. (2008) New MDS or Near-MDS Self-Dual Codes. IEEE Transactions on Information Theory, 54, 4354-4360.
https://doi.org/10.1109/TIT.2008.928297
[4] Georgiou, S. and Koukouvinos, C. (2002) MDS Self-Dual Codes over Large Prime Fields. Finite Fields and Their Applications, 8, 455-470.
https://doi.org/10.1016/S1071-5797(02)90353-9
[5] Grassel, M. and Aaron Gulliver, T. (2008) On Self-Dual MDS Codes. Proceedings of ISIT, Barcelona, 2008, 1954-1957.
[6] Guenda, K. (2012) New MDS Self-Dual Codes over Finite Fields. Designs, Codes and Cryptography, 62, 31-42.
https://doi.org/10.1007/s10623-011-9489-x
[7] Harada, M. and Kharaghani, H. (2008) Orthogonal Designs and MDS Self-Dual Codes. The Australasian Journal of Combinatorics, 35, 57-67.
[8] Jin, L.F. and Xing, C.P. (2016) New MDS Self-Dual Codes from Generalized Reed-Solomon Codes. Arxiv: 1601.04467v1
[9] Kim, J.L. and Lee, Y. (2004) Euclidean and Hermitian Self-Dual MDS Codes over Large Finite Fields. Journal of Combinatorial Theory, Series A, 105, 79-95.
https://doi.org/10.1016/j.jcta.2003.10.003
[10] Smid, M.H.M. (1983) Duadic Codes. IEEE Transactions on Information Theory, 33, 432-433.
[11] Huffman, W.C. and Pless, V. (2003) Fundamentals of Erro-Correcting Codes. Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511807077
[12] Pang, C.D. and Pang, C.B. (2002) Elementary Number Theory. Beijing University Press, Beijing. (In Chinese)

  
comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.