Exponential sums and Goppa codes: II

I

I

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 38, NO. 4, JULY 1992

1222

Exponential Sums and Goppa Codes: Carlos J. Moreno and Oscar Moreno

W:

Abstract-A research problem in The Theory of Error Correcting Codes by MacWilliams and Sloane asks for the true dimension and the minimum distance of a Goppa Code. The problem is solved for the minimum distance whenever the length of the code satisfies a certain inequality on the degree of the Goppa polynomial. In order to do this, conditions are improved on a theorem of E. Bombieri. This improvement is used also to generalize a previous result on the minimum distance of the dual of a Goppa code. This approach is generalized and results are obtained about the parameters of a class of subfield subcodes of geometric Goppa codes; in order words, the covering radius are estimated, and further, the number of information symbols whenever the minimum distance is small in relation to the length of the code are found. Finally, a bound on the minimum distance of the dual code is discussed.

parity check matrix

Index Terms-Exponential sums, algebraic geometric and classical Goppa codes, parameters of Goppa codes.

where r = deg g Now we can factor g(z) in a unique manner as g ( z ) = g : ( z ) g 2 ( z ) with g l ( z ) , g 2 ( z )~ F [ z of l degree rl, r2 respectively and g 2 ( z ) square free. It is also well known (see [15], [9], [lo]) that d , the minimum distance of the code must have d 5 2( r , r 2 ) 1. The purpose of Section I is to prove the following.

... ... H =

...

+

INTRODUCTION

T

HIS article has three sections: I, 11, III. In Section I, we estimate the parameters of classical binary Goppa Codes, in Section 11, that of binary geometric Goppa Codes, and in Section III, we will deal with the case of arbitrary characteristic. Since the classical case is easier to understand Section I can be seen as an introduction to Section II and III. We also give more complete proofs in Section I. On the other hand Section II also includes generalizations of results of a previous paper [ 171.

A . Introduction to Section I Let F = F2m= { P , , P 2 , P2m}be the finite field with 2 "' elements and g ( z ) any polynominal over F of degree r z l . L e t L=F-Z,whereZ={z,;..,z,} istheset of zeros of g ( z ) in F. We consider the binary Goppa Code r ( L , g) of length n = I L I. This is the binary code (see [15], [9], [lo]) with a,

Manuscript received April 11, 1989. C. J. Moreno was supported in part by the National Science Foundation (NSF) under Grants DMS-8711566 and DMS-8712742. 0. Moreno was supported in parl by NSF Grants RII9014056, and Component IV of the EPSCoR of Puerto Rico Grant. C. J. Moreno is with the Baruch College and Graduate Center, City University of New York, Box 545 N. Salem, NY 10560. 0. Moreno is with the Department of Mathematics, University of Puerto Rico, RIO Piedras, PR 0093 1. IEEE Log Number 9200158. 0018-9448/92$03.00

+

1) The minimum distance of r(L, g ) is exactly 2 s 1, where s = r , r 2 , whenever 2"' 1 max((BZS+l l)', ((2s)!/s!2'12), with B = - 2 r_+ t , where t is the number of distinct roots of g in F, the algebraic closure of F , and for L = F. 2) The minimum distance of r(L, g ) , the dual code of r ( L , g ) is at least 2"-' - ( k - 1)/2 - (deg g - 2 + t)2"'/*-',and k is the number of those roots that are in F. Also, if g has no roots in F, then the 1/2 minimum distance of r(L, g ) is at least 2"- (deg g - 2 t)2"'/'-'.

+

+

I. CLASSICAL GOPPACODES

+

+

+

'+

Result 1 is analogous to the sufficient condition part for BCH codes of problem 9.1 of [15], resolved by Helleseth ([ll]). A particular case of result 2 for Goppa codes with separable polynomial g was already obtained in [17]. Many applications of result 2 are given in Sections I-D and I-E.

B. Bombieri 3 Inequality and Improvements We need the following results from MacWilliams and Sloane [15], which we quote without proof. They are originally due to Delsarte [5]. We define the generalized Reed-Solomon code as

-

where a = { CY,, * , a,} is a fixed set of distinct elements of F and y = { y 1 ; * * y, , } is a fixed set of n elements in F. 0 1992 IEEE

MORENO AND MORENO: EXPONENTIAL SUMS AND GOPPA CODES: I1

1223

For a code C over F = FZm, u ( C ) denotes that code over F2 whose elements are obtained from code words of C by taking U , the trace from F = F2m down to F, componentwise.

Furthermore, the number of such polynomials is at least (2")".

Theorem I (Mac Williams and Sloane [IS, p . 3411): The dual of a Goppa code is given by

Corollary 1: with previous notations and assumptions, we have dimension r ( L , g)' 5 m ( r - r , ) = m ( r , r2).

+

Lemma 2: If f(z ) E F2m[z]has deg (f)< r , and Y = f( z ) /g ( z ) is solvable in F2(z ) then deg (f)> r, + r2. Letuscall W = (f(z)/g(z):f(z)EF2m[z],degf < r } . r ( L , g ) ' = o ( G R s , ( ~ ,Y ) ) , Further let us call H , the subset of W , where f is as in where yi = g ( a i ) - ' and I = deg g . Lemma 1 , and H2 the subset of W , where f(z ) is such that f < r , r2. Then, it is clear that W is a vector space deg Our calculations will rely heavily on Bombieri's result [2] and improvements on it 1181. Bombieri's result reads as over F2 with dimension mr, and H I ,H2 are subspaces with dimension mr, , and m( r, r 2 )respectively. Now if we call follows. If f ( z ) / g ( z ) ( f and g in F [ x ] ) has poles Qi(i = H the subspace of W for which Y 2 - Y = f( z ) / g ( z ) has z ) , then we have the following lemma. 1 ; - * , t ) in the projective line P ( q ) , over an algebraic solutions over closure of F 2 , with multiplicities ni, and if Y 2 - Y = Lemma 3: W is the direct sum of H and H 2 , furtherf ( z ) / g ( z ) has no solutions in & ( z ) , the field of rational more H = H I . functions over an algebraic closure of F 2 , then Proof: H n H , = ( 0 ) from Lemma 2. Now, since dim W = dim H I dim H , and H I C H , the rest follows easily. 0 Y

+

+

K(

+

5

(

-2

t i

+ t + 1 n, 2 m / 2 , i= 1

where the summation runs over all points P of the projective line P(F2m) over F Z m ,excluding poles of f ( z ) / g ( z ) that are in the projective line over F 2 m . Our improvement on Bombieri's result (in our particular case of deg f < deg g , and summing over the projective line) read as follows. If for f ( z ) / g ( z ) (f and g as before) g has t distinct roots in some algebraic closure of F and Y 2 - Y = f ( z ) / g ( z ) has no solutions in FZm(Z), the field of rational functions over F Z m ,then

IP E P ( FC~-~{poles} )

( - 1 )d f ( P ) l g ( P ) )

I (-2

I

+r +t) , l

[2"'2+1],

L

where [ X I denotes the integral part of the real number x. Since the proof of the previous estimate that we obtained in 1181 relies on the theory of Artin-Schreier coverings, we will provide here an elementary proof for the case of the projective line, previously quoted. We will use recent results of Van der Vlugt in [27]. We will quote without proof Lemmas 1 and 2 from his paper.

Y - Y = f(z ) / g ( z ) is solvable over F2(z ) , then it is already solvable over Fzm( z). Using this corollary and Bombieri's result we can weaken Bombieri's conditions and obtain the following theorem.

-Corollary 1: If

Theorem 2: Let f(z ) be a polynomial of degree < r = deg(g) with g aeolynomial with t distinct roots over the algebraic closure F2. If Y - Y = f( z ) / g( z ) has no solutions in the rational function field F2m(Z), then

where Z is the set of poles of f( z ) / g( z ) , which are rational over FZm.

C. Minimum Distance of the Goppa Code Throughout this section, as well as some other places further along in the paper, we denote 2" as q. Using the notation of the introduction and of 1151, we recall that the parity matrix of the Goppa code r ( L , g ) with L = ( P I , - . . ,P,} = F - Z is

Lemma I: Let g ( z ) = g l ( z ) g 2 ( z )be a polynomial in F z m [ ~ with ] g , ( z ) of degree rl and g 2 ( z ) square free. If f ( z ) has the form

with h ( z )E F ~ ~ [ofz degree ] < r , , then h / g , is a solution of Y - Y = f / g and therefore,

where = deg g . It is easily seen that the minimum distance of r ( L , g) is Ip if there is a non extraneous solution = (x , ,* x p )E P ( F)". (The p Cartesian product over the projective line) to the system ( 1 ) next. A solution is non extraneous if it induces

x

Tr($#)

=O.

e ,

I

I

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 38, NO. 4, JULY 1992

I224

a nonzero codeword, and this happens if after dropping any occurrence of P, and pairing off equal xi's, there is still a number of different xi's left, and of course this number is >2(r1 r2) 1 :

+

1

+

+ -

dx,)

1

g(x2)

+

... +

1 -

=o

g(x,)

I H, I

Then Lemma 1 gives

=

qrl and we obtain

with B = - 2 + r + t . Since r = 2 r 1 r2, if we denote s divide both sides by 4'1, and obtain

+

=

We assume for ease of notation that g does not have zeros in = L. Now, if N, denotes the number of p-tuples 5 = (x I , x p ) in ( P ( F ) ) , which are solutions of the system ( 1 ) then,

F, i.e., F

e ,

+

+

+

I

- ( 4 + 1)2s+1 = (q

'

,

can

This can be seen doing induction on s. It is clearly true for s = 1 and if we assume it is true for s = t - 1 , then using that N F ( t ) = ( q 1)(2t - 1)NF(t - l), we obtain that N F ( t ) I( q 1)'(2t)!/t!2'. Now let us assume N, = Np", i.e., there are only extraneous solutions. Then, given that p = 2 s + 1 , we obtain

I qsN2'+I

= ( a 1 ,. .Ea,)€F'

+ r 2 , we

Since we know that the minimum distance 2 2 s 1 let us 1 . Also in the N, solutions above there assume p = 2 s are extraneous solutions, and they are, as mentioned before solutions that induce a zero vector in the Goppa code r(L , g). Since we are looking for nonextraneous solutions, let us call Np" the number of such extraneous solutions. Now s = ( p 1 ) / 2 , then we know that there must be a pairing of equal x i in _x in order to induce the zero vector in the code. Now let us notice that

+

In the following, we write $( x ) = ( - l ) " ( x ) .Since $ is a nontrivial additive character of F, then recall that

rl

24! + 1 y S + l - q S ( q + 1 ) s (s!2" -*

Then,

and therefore, we have

Using now the notation of Lemma 3, we have that the last expression is equal to

! 21,' i.e., when and this is true whenever ( 2 ~ ) ! / q ' / ~ sI q 2 ( ( 2 s ) ! / s ! 2 " ) * We . can conclude that if q 2 max((BZS+I l ) ? , ( ( 2 s ) ! / ~ ! 2 then ' ) ~ )there must be nonextraneous solutions and the minimum distance is exactly 2 s 1.

+

+

D . Minimum Distance of the Dual Code In this section, we use our elementary proof of the improvement on the conditions of Bombieri to obtain results on Furthermore we have that the inner sum equals ( q + l ) p the minimum distance of the dual code. The results of this precisely when f(z ) / g ( z )€ H I according to Lemma 3. For section can be improved by applying the full improvement to any other f ( z ) / g ( z ) # H I ,we can use our improvement of the Bombieri bound mentioned in Section I-B. Actually noSection I-B, on the conditions of Bombieri (i.e., theorem 2 ) . tice that all you must do is replace the last negative term by

MORENO AND MORENO: EXPONENTIAL SUMS AND GOPPA CODES: I1

1225

the appropriate bracketed expression of the theorem quoted in Section I-B. If necessary, see [18] for the exact expression, as well as for complete proofs of our theorems in this section, and in particular for a proof of Theorem 6 and the corollaries. If we assume the same notation as in Section I-C and further that the zeros of g ( x ) in an algebraic closure of F , are all distinct, then the following theorem and corollary were proven in [ 171.

19 in F . If we now consider an arbitrary polynomial F of degree < deg g , using Theorem 2, we obtain

Theorem 3: The Minimum distance of r ( L , g)' , the dual code of r ( L , g ) is at least 2"-' - ( k - 1)/2 (deg g - 1)2"/', where k is the number of zeros of g( z ) in F. Corollary I : If g ( x ) has no roots in F , then the minimum distance of r ( L , g)' is at least 2"-' 1/2 - (deg g 1)2"/2. In the proof of Theorem 3 we used the following result from [17], restricted to Characteristic 2.

+

Theorem 4: Let F = FZm.Let R ( x ) = f ( x ) / g ( x )be a quotient of two polynomials with coefficients in F and deg f < deg g . Let g ( x ) have distinct zeros in the algebraic closure F of F . If $ denotes a nontrivial additive character of F , then we have

11

+

X€L

$(

%) I

-2

5 (deg g

+ t)2m/2

and note that L is precisely F - Z , where Z is the set of zeros of g ( x ) in F . We observe now that if x = ( x l , * . .x, , > ~ r ( Lg ,) " then x = ( u ( F ( a , ) / g ( c y , ) ) , . . . , a(F(cy,)/g(cy,)))and hence, the weight w of x and the number z of zero components of x have the property z w = nand

+

E$($+)= z - w = n - 2 w . X€L

Therefore,

1

+n

-

2w

I(deg

g

-

2

+ t)2"I2

and

w

L

n/2

+ 1/2

-

(deg g

-

2

+ t)2m/2.

These inequalities yield that the minimum distance is at least 2-1

-

k-1

___ -

degg-2+t

2 This proves the theorem.

2

2"i2.

0

Theorem 6: For an? arbitrary Goppa polynomial the minimum distance of ( r ( L ,g)) ' , the dual of the extended where the sum runs over X E F that are not zeros of g ( x ) . Goppa code, is at least Using Theorem 2 of Section I-B, we can prove this for a 2-1 - ( k - 1)/2 - (deg g - 2 t)2"/*-', completely arbitrary Goppa polynomial g ( x ) . Notice that we can take g ( x ) arbitrary since the conditions on the rational where t is the number of distinct roots of g in F , and k is function R ( x ) = f ( x ) / g ( x ) on our Theorem 2 of Section the number of them that are in F . I-B are weaker than those of Bombieri's theorem of Section Corollary I: Consider the BCH code with zeros 11. Previously the solution H ( x ) , had coefficients in F2, the 1 for cy of order prealgebraic closure of F2. The point is that using Theorem 2 1, cy, cy2;.*, c y 2 / - 1 and length 2" will give us that any exceptional R ( x ) will induce the zero cisely 2 " 1. Then, the minimum distance of the dual code vector under the trace operation. The theorem we have now is at least is the following. 2m-' 1/2 - (21 - 1)2"2.

+

+

+

+

Theorem 5: For an arbitrary Goppa polynomial g ( x ) , the minimum distance of r ( L , g ) ' , the dual code of the Goppa Code r(L , G ) , is at least 2"-'

- ( k - 1)/2 - (deg g - 2

+ t)2"/'-',

where t is the number of distinct roots of g in the number of them that are in I;.

F , and

2"-'

1

= (-

- 1/2 - (21 - 1)2"/2.

E. Self Intersection Properties

F ( x ) E F [x ] , deg F < deg g .

#(e)

.

k is

Proofi According to Theorem 1 of Section I-B, we have

Consider the additive character

Corollary 2: Consider the reversible cyclic code with zeros c y p ( 2 / - l ) a p ' ( 2 / - 2 ) . ., c y - 1 , 1, c y , cy2,.. ., c y 2 / - 1 and length 2" - 1 for cy of order 2" - 1. Then, the minimum distance is at least

1)"(@defined for

In this section, we will use a result from [4] to prove a theorem on the self intersecting properties of the dual of the Goppa codes (also, see [20]). First we must define the concept of self intersecting. A binary code is r-intersecting to itself if for any two arbitrary codewords they must have ones in common in at least r places. A code is self intersecting if it is r-intersecting for r 2 1. Denote d,,, the maximum distance between words of the code and denote d the minimum distance. Then, we have the following result from [4]: If r = d - (1/2)dmaxthen the

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 38, NO. 4, JULY 1992

1226

code is r-intersecting to itself. We now state the main results of this section. Theorem 7: Consider the dual of the Goppa code r(L , G), where G is of degree Land has no roots in F = L , also it has s distinct roots in F. Then, the code is self-intersecting whenever 3(t + s - 2) I 2"'12 - 1. Proof: The proof follows simply by applying the bounds 0 we obtained for d and d,,, in the previous section.

have the property of exceeding the Gilbert-Varshamov bound asymptotically. In a series of recent papers [171 and [113- [131, exponential sums techniques have been used to estimate the parameters of classical binary Goppa codes. We will also use exponential sums now (in this section) to prove the following results about our class of binary geometric Goppa codes. The minimum distance d for the dual of C,*(D, G) must satisfy:

OF GEOMETRIC GOPPA 11. BINARY SUBFIELD SUBCODES CODES

d r

A. Introduction to Section II

We will first define geometric Goppa Codes; for a more detailed introduction see Goppa [8], van Lint-Springer [28], Moreno [ 161. Let X be a complete non singular projective curve of genus g in projective space Ps,defined over the finite field F= i.e., defined by polynomial equations having coefficients in F . Let { Pi I i = 1,2, * , n} be the rational points of X . We know that n can be estimated by Weil's bound In-(2m+1)I 1 2 g v T .

+

We will assume in this paper that n > 2"'. Let D = P, P2 * P,, be the divisor of the rational points of X over F. Let G = CmQQ be another divisor, with m? = 1, on X whose support is disjoint from that of D (in Section 11 of this paper, we deal only the case mQ = 1, but see Section I11 for the case of an arbitrary divisor). Also, divisor G should be closed under the Frobenius substitution. This means that for any Q in G the conjugates of Q are also in G, for example, this would be true if G consists of rational points. Let F( X) be the function field of X . Then, consider the set L(G) consisting of all the rational functions f ( x ) in the function field F ( X ) such that the order of f at each Q of G is 2 -m It is well known that L(G) is a vector space of Q' finite dimension over F, and therefore, there is a basis { f l ; . - , fr} for it, where f i E F ( X ) . The geometric Goppa code C*(D, G) is the code whose parity check matrix is

+

n - (2deg G

+ 2 g - 2)2"'12 2

The number of information symbols of C,*(D, G) is exactly n - m(r - 1) - 1 if (2 deg G 2 g - 2) < nq- 'I2. The covering radius of the code C,*(D, G), with block length n , must be I 2deg g - 2 g 2 whenever n r B4(degG--g)+2, where B = 2deg G 2 g - 2.

+

+ +

the proof of result 1, we use techniques similar to those in [17] for classical Goppa codes. Also we use in result 2 similar techniques to [19], and in result 3 as in [17]. In [6], Goppa describes binary geometric Goppa codes as the most interesting for practical purposes. We also believe the binary subfield subcodes of geometric Goppa codes have been neglected and merit further study, and in this section of our paper, we give a beginning contribution to that effect (see also [30], [22]).

B. Bombieri's Bound for Curves, Delsarte's Theorem, and Minimum Distance of the Dual Code As mentioned previously, in [5] Delsarte characterized the dual of a classical Goppa code (see [15, p. 3411 or Theorem 1 of Section I-B. His result can be said to include the following generalization. Theorem 8: The dual of a binary geometric Goppa code is given by C,*(D, G) = a(C(D, G)) where ~7 is the trace function from F to F2, C ( D , G) is the dual code to C*(D,G), and d C ( D , G ) ) = {(uf(PI);**, af(P,,)):fE L(G)If Now we need the following estimate based on Bombieri, see [2] or [17]. We say that f E F( X ) satisfies condition b) if

If we assume that 2 g - 2 known that r=degG-g+

< deg G < n then it is well

1, wheredegG=

me. Q

Recall that the binary subfield subcode of C*(D, G), which we denote C,*(D , G), consists of all x = (xi) E FJ such that Hx' = 0. Geometric Goppa codes were introduced in [1]-[3], and in [25] certain geometric codes were shown to

b) f p h2 - h for any h E F ( X ) , and closure of F.

F

is the algebraic

Lemma 4: If G = CmQQ with mQ = 1, then for f E L(G) and f nonconstant, we have that condition b) is satisfied.

Proof: If f were a nonconstant function in L(G) that does not satisfy condition b), it would have poles of even order in contradiction to mQ = 1. From Bombieri's estimate we get the following theorem.

MORENO AND MORENO: EXPONENTIAL SUMS AND GOPPA CODES: I1

Theorem 9: Let f E L ( G ) be nonconstant and G with mQ = 1 , then we must have n

1 i= 1 ( -

l)"'f(p'"

I

I(2deg

G

=

CmeQ

1227

always a solution in X ( F ) , (the 29 Cartesian product of the rational points of X ) to the following system

+ 2 g - 2)2mf2.

Now we are ready for our main result of this section.

Theorem 10: The minimum distance of C,*(D,G ) , the dual of the binary geometric Goppa code for G = CmQQ with mQ = 1, is at least

Remarks: A solution to the above system for arbitrary , 0,- would imply that the map Q : FT + FZm('-' ) given by Q ( x ) = H x ' for x = ( x , ; * * x, , ) E F ; is onto and therefore, the rank of H must be m ( r - 1). n - (2deg G + 2 g - 2)2m/2 Now, for ease notation let us write $ ( x ) = ( - l)O(x). 2. Since is a nontrivial additive character of F, then recall Proof: Let X E C , * ( D , G ) ' then x = ( u f ( P 1 ) , , that uf (P,)), and if f E L ( G ) and f nonconstant, then the weight w of x and the number of zero components z have the w = n and property z where q = 2 m = I F I. Now if A$ denotes the number of &tuples x = ( x 1, * , x , ) E ( X ( F ) ) ' , which are solutions of the system (2), then,

PI,

+

e

-

.

+

therefore,

'*I,

.

qr+lNZy = xeX( F )Iy

n

- 2 w I(2deg

G

+ 2 g - 2)2mf2

and

n W 2

- (2deg

G

+ 2y

- 2)2m/2

2

This proves the result, if we note that if f were constant then x would be the 0 or 1 vector. 0

Remark: We have generalized the results of this section (see Section 111) to cover an arbitrary characteristic and divisor. Please also note that we can use Theorem 10 to obtain similar self-intersection properties as in Theorem 7 of Section I-E. C. Number of Information Symbols Recall that the parity check matrix for C,*(D,G ) must be

We know that we can take f , = 1, and consider now H which is the matrix H without the last row. Note that the row space of H consists of non-constant functions of L ( G ) evaluated at the rational points of X . We will prove that the binary rank of H is m ( r - 1) if we prove that for given arbitrary PI,. * * , Or+ I E F , there is

Now, we know that excluding a1 = = =0 would give us that CY] f l ( x ) f r P l ( x )is nonconstant and we can apply the above estimate of Theorem 2. Therefore, we obtain

+

\

-

I

\

-

,

I

1

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 38, NO. 4, JULY 1992

1228

+

where B = 2 g 2 deg G - 2. Suppose that N’ = 0 then n’ < qr-’ B’q’l2 and therefore, n < q(‘-’)/’Bq’/’. Now, if we take B < nq-1/2q(-r+1)/’, then there is a solution to the system and the number of information symbols is as stated. On the other hand, since we can take an arbitrarily large 29, it is enough if we have B < nq-’/’, and this proves the result. Since we can take 29 at will even or odd, the result for the original matrix H also follows and we have the following theorem. Theorem ZZ: The number of information symbols of C:(D, G) is exactly n - m(r - 1) - 1 if (2 deg G 2 g 2) c nq-’/’.

= 1). Then Theorem 10 (Section 11) can be extended as follows.

Theorem 13: The minimum distance of Cp(D , G) * the dual of the Fp subfield subcode of the geometric Goppa code, and for G = CmQQ with mQ > 0 and t the number of distinct Q in the divisor G, is at least ( ( P - l ) / p ) ( n ) - ((deg G

+ t +2g - 2)[2~”/~])

+

Remark: Notice that if the curve X has maximal n = q 1 2gq1/*, then the previous inequality reduces to 2deg G - 2 Iq l / ’ .

+ +

D. Covering Radius It is known that the problem of estimating the covering radius for the binary code with parity check matrix H is equivalent to that of solving the system of equations of f i r - 1, and with the least Section 11-C, with arbitrary PI, number of variables. Helleseth in [l 11 was the first to observe that the character sums trick of separating the variables we used in the previous section would give an estimate for the covering radius and the minimum distance of BCH codes. The methods of [111 were further improved by Tietavainen in 1231. In a similar manner, in our case, we will obtain that the covering radius for C,*(D , G) must be I2 deg G - 2 g 2, by applying the methods of the previous section and letting 19 be 2deg G - 2 g 1 or 2deg G - 2 g 2. Of course the length of the code will have to satisfy a certain inequality. First, notice that the hypothesis n > 2 m = q applied to the inequality we obtained from Bombieri in the last part of the previous section implies n’/’q’/’ < n’ < qr’-’B’q’/’ and if 29 = 2deg G - 2 g 1, and if we denote t = deg G - g we obtain upon substitution that: n(’‘+’)/’q-‘ < B2‘+’ and therefore n < B4‘+’. It is sufficient to take n 2 B4t+2 and our estimate on the covering radius holds.

--

e ,

+

+

+

+

Theorem 12: The covering radius of the code C:(D, G) with block length n must be I2 deg G - 2 g 2 whenever n 2 B4(degC-g)+2 and where B = 2deg G 2 g - 2.

+

+

III. ARBITRARY CHARACTERISTIC AND DIVISOR G Sections I and 11 of this paper dealt with Characteristic 2, since this made our presentation simpler. Furthermore, as pointed out, binary codes are more interesting from the applied point of view. On the other hand, our previous results can be frequently extended to cover an arbitrary characteristic and divisor, and in this section, we would like to give a precise statement of the theorems we obtain in the general case. Let us use the same notation and assumptions as in Section 11, but our finite field F would be assumed to have arbitrary characteristic p and our division G = C m Q Q has mQ > 0 but is otherwise general (me does not have to be

Here [e] denotes the greatest integer function. We can prove this statement using our full improvement of Bombieri (see [18]). F. Rodier in 1211 has obtained a nice generalization of our Theorem 11 (Section 11), for a general characteristic and divisor. He uses a bond obtained by Lachaud in [14]. On the other hand, if we substitute in [21] the use of the bound of [14] and use instead Theorem 13, we can improve [21] as follows Theorem 14: Let G’ = E[mQ/p]Q, and deg G’ > 2 g - 2, then the number of information symbols of C,*(D,G) is exactly n - m(deg G - deg G’) - 1 whenever we have

n>

deg G

+ t + 2 g - 2 [2pm/’]. 2

ACKNOWLEDGMENT The authors would like to thank C. Retter for pointing out the fact that in Section I-D, theorems imply Theorem 7 of Section I-E. Also, thanks to A. Tietavainen for mentioning that a similar estimate as the one he obtains in [24] permits us to compute the number of extraneous solutions.

REFERENCES E. R. Berlekamp and 0. Moreno, “Extended double-error-correcting binary Goppa codes are cyclic,” IEEE Trans. Inform. Theory, vol. IT-19, pp. 817-818, 1973. E. Bombieri, “On exponential sums in finite fields,” Amer. J . Math., vol. 88, pp. 71-105, 1966. A. Cdceres and 0. Moreno, “On the number of information symbols of extended cyclic Goppa codes of length 2 + 1,” Proc. Allerton Conf., 1984, pp. 553-558. G. Cohen and A. Lempel, “Linear intersecting codes,’’ Discrete Math., vol. 56, pp. 35-43, 1985. P. Delsarte, “On subfield subcodes of Reed-Solomon codes,’’ IEEE Trans. Inform. Theory, vol. IT-21, pp. 575-576, 1975. V. D. Goppa, “Codes on algebraic curves,” Soviet Math. Doklady, vol. 24, pp. 170-172, 1981. -, “Algebraic-geometric codes,” Math. USSR, Izvestiya, vol. 21, no. 1, pp. 75-91, 1983. -, “Codes and information,” Russian Math. Surveys, vol. 39, no. 1 , pp. 87-141, 1984. -, “A new class of linear error-correcting codes,” Probl. Peredach. Inform., vol. 6, no. 3, pp. 24-30, Sept. 1970. -, “Rational representation of codes and (15,g) codes,’’ Probl. Peredach. Inform., vol. 7, no. 3, pp. 41-49, Sept. 1971. T. Helleseth, “On the covering radius of cyclic linear codes and arithmetic codes,’’ Discrete Appl. Math., vol. 11, pp. 157-173, 1985. J . W. P. Hirschfeld, “Linear codes and algebraic curves,’’ in Geometrical Combinatorics, F. C. Holroyd and R. J. Wilson, Eds. Boston MA: Pitman, 1984.

MORENO AND MORENO: EXPONENTIAL SUMS AND GOPPA CODES: I1

1229

~ 3 1G. Lachaud and J. Wolfmann, “The weights of the orthogonals of the extended quadratic binary Goppa codes, ” IEEE Trans. Inform. Theory, vol. 36, pp. 686-692, May, 1990. G. Lachaud, “Exponential sums, algebraic curves and linear codes,” to appear in J. Num. Theory. F. J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes. Amsterdam: North Holland, 1977. C. J. Moreno, Algebraic Curves over Finite Fields, Tracks in Mathematics. Cambridge: Cambridge Univ. Press, 1971, vol. 97. C. I. Moreno and 0. Moreno, “Exponential sums and Goppa codes: I,” Proc. A M s , vol. 1 1 1 pp. 523-531, 1991. -, “An improved Bombieri-Weil bound and applications to coding theory,” to appear in J. Numb. Theory, 1991. -, “On the number of information symbols and covering radius of long Goppa codes,’’ presented at h t . Workshop Algebraic and Combinat. Coding Theory, Varna, Bulgaria, Sept. 18-24, 1988. C. Retter, “Intersecting Goppa codes,” IEEE Trans. Inform. Theory., vol. 35, pp. 822-828, July 1989. F. Rodier, “On the dimension of Goppa codes,’’ preprint.

P21 H. Stichtenoth, “On the dimension of subfield subcodes, preprint. r231 A. Tietavainen, “On the covering radius of long binary BCH codes,” Discrete Appl. Math., vol. 16, pp. 75-77, 1987. r241 -, “Lower bounds for the maximum moduli of certain character sums,” J . Lon. Math. Soc., vol. 29, no. 2, pp. 204-210, 1984. ~251 M. A. Tsfasman, S. G. Vladut, and Th. Zink, “Modular curves, Shimura curves and Goppa codes, better than Varshamov-Gilbert bound,’ Math. Nachr., vol. 104, pp. 13-28, 1982. K. K. Tzeng and K. P. Zimmerman, “On extending Goppa codes to cyclic codes,’’ IEEE Trans. Inform. Theory, vol. 21, pp. 712-716, 1975. M. Van der Vlugt, “On the true dimension of binary Goppa codes,” to appear IEEE Trans. Inform. Theory. J. H. Van Lint and T. A. Springer, “Generalized Reed-Solomon codes from algebraic geometry,” IEEE Trans. Inform Theory, vol. IT-33, pp. 305-309, May 1987. r291 J. H. Van Lint, “Algebraic geometric codes,’’ preprint. [301 Wirtz, “On the parameters of Goppa codes,’’ IEEE Trans. Inform. Theory, vol. 34, pp. 1341-1343, Sept. 1988.