:31:
V59 .
. A;

 

.2:
....

 
 

 
 

 

.2.

.I

 

 

 

 

. . , i
. a A. ..
. . V _
AA. ,
s , .v A A
u~ .. V v ”.14 ‘.
,.. . . ..
. - .vfi .1 .
.19.. . .. A u
.17 A ‘ . .r.‘ .
. .
‘ .. . .
xiv... 1..

 

 

 

 

 
 
 
 

 

 
 

 
 

 
 
 
 
 

 

 
 

 

 

 
 
 
 
 

 
 
 
 

 

 

 

 

 
 

 

 
 

 

 
 

 
 

 

 
 
 
   
   
 

 

 

 
 
 
 

   
 

, a <
.040;
.3‘ .. .L ;. , V , . A
.. . . , . . . . ,.
. . . . f v . .
,. . . . A . . . .
v.- . ~ I . b~ - ,
. , j, , . . , .A ._ ... ,
T _ A A. . . A T. .V
.. .. v . .. .. . . .,. .A
. .y :0 4 .u . ,
. , ‘ .. ‘., r.. . 1 , . . 4A
.. . . . . . . A . ..
A .A , . ,. . in. .1.
.. v . A
A ,u n
, . , ‘ .y ,
.. . A ‘ . A
A 2 .. , A ,
A . A.A . ,.
. . . .
, u . I. . .- .
, tAt .- : , . ‘
L... A. . l . A
I . .. . ...,. . A ...:.-.v—¢.-.-
. . . . .i
. I .A p.» .A
. A . A
‘ . n A . n. 3‘
‘ n . ‘ ‘ “.
A . .. ‘
J 5. ,~, AA
. . ,. A .
A ..
a . A, . .
. . . , .
, . V
A .
‘ . T
‘ , .
.. ,
..
. t , I .

 

 
 

 

 
 

 

 

  

.s_._...”.,.. “5193A

. 3.5 r. .

 

.:.
1......

 

 

     

 

 

 

 

02 MICHIGAN STATE UNIVERSITY LIBRARIES

III I I III IIII’II IIIIII

I II

3 1293 00604 6811

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

This is to certify that the
dissertation entitled

THE TRACE OPERATOR AND GENERALIZED
GOPPA CODES

presented by

Albert Manuel Roseiro

has been accepted towards fulfillment
of the requirements for

Ph. D. degreein Electrical Engineering

 

 

g

x; ‘ !Z é/I
M

ajor professor

Date 5 I 8?.

MS U i: an Affirmative Action/Equal Opportunity Institution 0- 12771

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or More ode din.

 

-—_——————-—1'
DATE DUE DATE DUE DATE DUE

l___
I_______l

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

II’

 

‘=—T

 

 

 

 

 

 

 

 

 

 

MSU Is An Affirmative ActiorVEwal Opportunity Institution

 

THE TRACE OPERATOR AND GENERALIZED GOPPA CODES

By

Albert Manuel Roseiro

A DISSERTATION

Submitted to
Michi an State University
in partial ful lment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Electrical Engineering

1989

(004 3-3 CD 5

ABSTRACT
THE TRACE OPERATOR AND GENERALIZED GOPPA CODES
By

Albert Manuel Roseiro

The computation of the dimension of an error correcting block code is essential to
achieve an implementation of these codes in practice. Most of the known results on the

dimension of block codes are usually derived by exhaustive search using a computer which

limits the number of codes that can be studied.

A new analytical method has been developed for the study of the dimension of general-
ized Goppa codes using properties of the trace operator over finite fields. This method does

not require the use of a computer and can be applied to the family of generalized Goppa

codes.
New bounds have been obtained for a general class of Goppa codes analytically. Two

specific set of Goppa codes defined by Gl(X) =X2'+X and Gz(X) =X2'“+l over a

CF (22‘ ) locator field are studied in detail and tighter bounds than previously reported in the

literature are derived for any 5 >1.

Copyright by
ALBERT MANUEL ROSEIRO
1989

With tender love and affection for Evelyne

iv

ACKNOWLEDGMENTS

The author is grateful to major Professor M. Siegel for his guidance throughout this
research. He wishes to thank guidance committee members Pr. J. Hall, Pr. J. Adney, Pr. H.
Rigas and Pr. R. Zapp for their encouragement and support. He is also thankful] to the
Department of Electrical Engineering for making office and computers facilities available.

Finally, he acknowledges all the other personal advices given by Dr. 0. Krauss and Pr. E.

Strangas.

TABLE OF CONTENTS

LIST OF TABLES ............................................................................................................ viii
INTRODUCTION ............................................................................................................. 1
CHAPTER 1: REVIEW OF THE LINEAR CORRECTING BLOCK CODES ............... 5
1.1: Introduction ................................................................................................... 5

1.2: What is an error correcting block code? ...................................................... 5

1.3: Hamming distance and maximum likelihood decoding method .................... 6

1.4: Channel capacity ........................................................................................... 7

1.5: Complexity considerations ............................................................................. 7

1.6: Linear block codes ........................................................................................ 8

1.7: Separable codes ............................................................................................. 9

1.8: The distance of a linear code ........................................................................ 10

1.9: Other bounds ................................................................................................. 11

1.10: The generalized Goppa family .................................................................... 12

1.11: Practical decoding of a generalized Goppa code ......................................... 16

1.11.1: The key equation of a generalized Goppa code ........................... 16

1.11.2: MPR algorithm ............................................................................ 18

1.11.3: Simplified Berlekamp algorithm .................................................. 19

1.12: BCH codes .................................................................................................. 20

1.13: Goppa codes ................................................................................................ 22

1.14: Example of encoding ................................................................................... 25

1.14.1: BCH( 15 , 5 , 7) .......................................................................... 25

1.14.2: The (11 , 1 , 11) Goppa code ...................................................... 26

CHAPTER 2: THE TRACE OPERATOR ........................................................................ 28
2.1: Introduction ................................................................................................... 28

2.2: General properties ......................................................................................... 28

2.3: Polynomial extension ..................................................................................... 31

vi

 

2.4: Special case m = 2.9
2.5: Basis of CF (pm) and trace operator

 

CHAPTER 3: THE TRACE OPERATOR AND GENERALIZED GOPPA CODES

 

3.1: Introduction

 

3.2: The redundancy equation of a generalized Goppa code

 

3.3: Interpretation
3.4: Linear mapping

 

3.5: Sub classes of the generalized Goppa family - .........

3.5.1: Wide sense BCH codes

 

3.5.2: Binary narrow sense BCH codes

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.5.3: Goppa codes ......... , ............
3. 6: Primitive Goppa codes ......... -. .....
3 7: Unification and case p=2... - _ -- -
CHAPTER 4: THE TRACE OPERATOR AND LOELOEIAN CODES .............................
4.1: Introduction ......................................................................
4.2: Simulation ................................................................................................
4.3: Important remarks .......................................................................... . -
4.4: Study of the case s = 2 .............................................................................................
4.4.1: Loeloiean codes .........................................................................................
4.4.2: Heuristic for general Loeloeian codes ..................................................
4.4.3: Bezzateev codes ....................
4.4.4: Heuristic for general Bezzateev codes ..................
4.5: Improved bounds for G 1(X ) ........ - .......
4.6: Improved bounds for 62(X ) .....................
4.7: Maximality of the solutions
4.8: Practical interpretation - .....
CONCLUSIONS -- -
RECOMMENDATIONS
APPENDIX A: REVIEW OF THE FINITE FIELD ALGEBRA
LIST OF REFERENCES

 

vii

32
33

36
36
36
38

41
41
41
42
42
43
45
45
46
47
48
49
50
51
52
53
54
57
S7
59
60
61
83

LIST OF TABLES

Table 1 .............................................................................................................................. 46
Table 2 .............................................................................................................................. 47

viii

INTRODUCTION

During 1948 and 1949, Shannon [1,2] published very interesting results about the fun-
damentals of information theory. The notion of channel capacity showed that there is always
a way of coding information to obtain a probability of error during a transmission as small as
possible given that the rate of transmission is compatible with the properties of the channel
introducing the errors. Unfortunately, Shannon’s channel capacity theorem doesn’t indicate

which coding method should be used.

In 1950, Hamming [3] and Golay [4] were able to lay down the fundamentals of error
detection and correction coding theory. The Hamming codes could correct one error but still
were very far from the limits of information theory. Hocquenghem [5] in 1959, Bose and
Chaudhuri [6] in 1960 introduced an important family of codes known as BCH that could
correct more than one error and generalized the Hamming codes. In fact, BCH codes are a
subset of the Reed-Solomon codes found by Reed and Solomon [7]. Still, BCH code cannot

reach the theoretical limits announced by information theory.

Peterson [8,9] was the first to introduce in 1960 an algebraic decoding method for BCH

codes and later, an even more efficient method was derived by Berlekamp [10].

Important parameters associated with linear error correcting block codes are the length
n, the dimension k, and the distance d. These codes are usually referred to as (n ,k,d )-codes.

The problem from a theoretical standpoint is for a given distance and length to find a code

having the largest dimension possible. A family of codes is said to be good asymptotically if
for a fixed (M: > 0, there exist codes in the family with k/n > 0 as n -) co. It has been
shown that primitive BCH codes are not good asymptotically, Lin and Weldon [11], Ber-
lekamp [12]. Nevertheless, the Varshamov-Gilbert bound indicates that linear block codes
are good, Peterson [9, pp. 51-52]. Interestingly, two sub-families of the linear block codes,
namely the Altemant family (Helgert [13,14,15], Mac Williams and Sloane [16, pp. 332-350]

) and the Goppa family (Goppa [17,18]) still reach the Varshamov-Gilbert bound.

The standard decoding methods are Euclid’s algorithm, Mac Williams and Sloane [16,
pp. 365-368], Berlekamp’s algorithm, Berlekamp [10] and MPR (minimal partial realization)
Conan [19]. These algorithms indicate typically that for a binary Goppa code of length n and
constructive distance d,c = 2t+l, the redundancy n—k is at most mt where a Galois field
GF (2”) is used as a locator field. The Varshamov-Gilbert bound shows that for some Goppa
codes, the actual true minimum distance can be greater than the constructive distance even if
the redundancy remains mt. Since it is only possible to decode up to the constructive disrance
with the actually known decoding algorithms ( the minimum distance decoding method, Lin
and Costello [20] is not considered in the discussion), the actual problem is to find for a
given constructive distance and length, a code with the largest dimension k or equivalently

the smallest redundancy n—k.

The standard analytical approaches to finding good Goppa codes are partitioning and
algebraic transformations, Moreno [21], Chen [22], Berman et al [23]. Thus far, the study of
the rank of the parity check matrix has been done by computer search or by the use of

minimal polynomials in the case of BCH codes.

By using the trace operator over GF (pm) ( Berlekamp er al [24], Mac williams and

Sloane [16]) a new equation referred to, as the redundancy equation of a generalized Goppa

code can be obtained. The solutions of that equation form a vector space over GF (p). The
dimension of that vector space is related to the true redundancy, namely, the number of
independent rows over GF (p) of the parity check matrix of a generalized Goppa code. A
computer, thus is not needed to find the dimension of such codes given that the redundancy

equation can be solved analytically.

Applying the derived equations to specific codes has provided original bounds (not pre-
viously reported) on the dimension of a general class of binary Goppa codes. In 1984, Loc-
loeian and Conan [25,26] introduced a set of Goppa codes defined by G,(X ) = X 2’-t-X and
locator field GF(22"). In 1987, Bezzateev and Shekhunova [27] found a (55.16.19) Goppa
code defined by G (X) = X 9+1 with locator field GF (26). This latter code is generalized here
by introducing the polynomial 62(X ) = X 2“1+1 for any s > 1 over a locator field GF(22’).
Tighter bounds on the dimension of the two previous sets of codes will be obtained by par-
tially solving the redundancy equation ( a simulation has shown that these bounds are actu-
ally met for s = 2,3,4,5 ).

Since the (55,16,19)-code (case s=3) is for the moment the best binary linear block
code known for n=55 and dc=19 (Verhoeff [28]), codes defined by Gz(X) are interesting

especially for values of 3 >3 and may have practical applications.

Chapter 1 contains a general survey of linear error correcting block codes. The general-
ized Goppa family (Loeloeian and Conan [29]) has been chosen for the sake of clarity ( this
family is strictly equivalent to the Altemant family).

Chapter 2 is devoted to important properties of the trace operator and its extension to

rational polynomial ring modulo XPM—X .

Chapter 3 derives some new relationships between the dimension of generalized Goppa
codes and the trace operator; the redundancy equation is then defined. A particular case of
binary Goppa codes where GZ‘(X) a G(X) mod (X 22' +X ) allows the redundancy equation
to be solved partially, and original bounds on the dimension of these codes to be obtained.

Finally, Chapter 4 provides a further study of the dimension of the binary Goppa codes

defined by G 1(X) and 02(X) for s>1.

Due to the extreme importance of finite field algebra, Appendix A provides a review of

the basic properties of such fields.

CHAPTER 1

REVIEW OF THE
LINEAR ERROR CORRECTING BLOCK CODES

1.1. Introduction:

The role of linear error correcting block codes is well established and the applications
of such codes is constantly growing. It appears reasonable to study one of the largest linear
family known, the generalized Goppa codes introduced by Loeloeian and Conan [29]. This
family contains in particular all the Hamming codes, BCH codes, Goppa codes and is

equivalent to the Altemant family introduced earlier by Helgert [13,14,15].

1.2. What is an error correcting block code?

Important parameters associated with an error correcting block code are the length n,
the dimension 1: and the distance d. These codes are usually refered to as ( n , k , d )-code.
There are k symbols of information available to the user. Through an isomorphic mapping,
the k symbols of information are uniquely mapped to n symbols (n > k). This operation is
equivalent to add n—k symbols of redundancy to the 1: symbols of information thus provid-
ing an error correcting capacity. The mapping (or encoding) is closely related to the structure

of the code used.

The distance d of the code defines exactly the maximum number of independent errors
the code can correct. The decoding consists of actually correcting the errors that have

occurred during a transmission, whenever feasible.

1.3. Hamming distance and maximum likelihood decoding method:

A block code of length n can be seen as a set of n -tuples with coefficients belonging to

some 86 [.

Definition 1.1. The Hamming distance (or Hamming weight) between two n-tuples C 1

and C2 is:

n Oifcu =62i]:
d(C1’C2)= Z 1ifcli¢CZiI

i=1
It can be verified from Def. A.12. that the above definition is really a distance.

Definition 1.2. The distance of a block code C is defined by:

dc=min(d(C,- ,Cj) I C,- ,Cj8C ,i $.10

Proposition 1.1. If a code C has distance d = 2r+1, then it is possible when using the
minimum distance decoding scheme to correct up to t errors in any codeword. This is called

a decoding situation as opposed to a non decoding situation when more than t errors have

occurred.

Proof. Since the distance is 2t+1, it is possible by using the induced geometry of the
Hamming distance to put spheres of radius r around each codeword, each sphere having a
codeword at the center and no other codeword being contained inside each sphere. The
decoding consists first of computing the distance of the received codeword to all the possible

codewords. Then, if the minimum of all the previous distances is less than or equal to r, the

corresponding codeword is the corrected codeword.

1.4. Channel capacity:

Shannon [1,2] has shown that when a channel introduces an error bit probability p uni-
formly distributed, there always exists a binary block code (the coefficients of the codewords
being only 0 or 1) that can be transmitted with a probability of error as small as possible

given that:
k/n S l—H2(p)

where H 2(x) = —xlog2x - (1—x)log 2(1—x) is the entropy function. In fact, Shannon proved
that if one tries to transmit information at a rate higher than that predicted by the channel

capacity, it is then not possible to transmit without errors.

1.5. Complexity considerations:

The first problem that arises with Shannon’s channel capacity is that the proof is only
an existence one and actually doesn’t tell how to choose good block codes. Furthermore, an

exhaustive computer search is impractical.

Additionally, the minimum distance decoding method can be very difficult and costly to
implement in practice when n becomes large since it would be necessary to store in memory
2“ n-tuples plus comparing them each time to the received word in order to compute the

Hamming distance.

For all these reasons, considerable research has been done to put some specific alge-
braic structure on codes which would not require as much memory to store all the code-

words, and especially that could correct the errors without having to compute the Hamming

distance but rather decode by algebraic methods closely related to the structure of the code.

Since the code lengths of interest are finite, it appears normal to use finite field algebra

to induce algebraic properties on these codes.

1.6. Linear block codes:

Given a code C of length n , each codeword being a n-tuples with coefficients belong-
ing to some finite field GF (q ). This code might be then viewed as a CF (q )" vector space

over 61” (q) when using Def. A.10.

Definition 1.3. A block code C is said to be linear if and only if it forms a vector space

- over G)“ (q) with the two binary composition corresponding to Def. A.11.:
(0C1, C2€C then C1+C2€C
(ii) C, e C and AEGF(q) then AC1 EC.

Since a linear code is a vector space and there are by construction finitely many code-
words, C can be generated by a finite basis, in other words, C has a finite dimension over
GF (q ). The dimension of the code is usually denoted k. Let’s call {GI , G; , . . . ,Gk} the
basis of C, then every codeword can be represented as a linear combination over GF (q) of
the 65’s. Representing each vector of the basis with the n-tuples notation, the linear combi-
nation can be rewritten with a matrix, namely:

r
C1 611 621 . . le ' 1
C2 012 022 - . Grz

 

 

 

 

 

 

C, G,,G,,,..G,,J:

The vector (11 , 12 , . . . , 1,.) represents the k symbols of information that have to be
encoded by the code C defined by the above matrix. In fact, there is a one to one correspon-
dence between all the linear codes (n , k , d) and the set of all the matrices (n x k) with
coefficients over GF (q ). The matrix G is called the generator matrix of the code. Since the
dual of a vector space of the dimension k is also a vector space of dimension n-k, there is a

matrix H of size (n —k x n) known as the parity check matrix such that:
HG = 0

It will be seen later on how to get the distance d from the matrix H.

1.7. Separable codes:

Definition 1.4. A block code is said to be separable if and only if it is possible to

separate after encoding the k bits of information from the n-k bits of redundancy.

Proposition 1.2. For any separable block code, d S n—k+l (otherwise known as the

Singleton bound).

Proof. The proof is provided only for linear codes. Since the code is separable, the
smallest Hamming weight of k-tuple information is 1 (otherwise the encoding would give the
null codeword in the linear case). Then, the worst case is after encoding to have all the

redundancy bits not equal to 0 indicating a distance of at most n—k +1.
For the non linear case, see Delsarte [30] Q.E.D.
Proposition 1.3. All the linear block codes are separable.

Proof. It is a well known fact that by linear combination of rows and eventual column
permutations, it is possible to transform the parity check matrix to obtain a separated form of

the parity check matrix:

10

”3 = (In-k E)

where 1,, _,, is the identity matrix of rank n—k. Whenever a column permutation was required
to derive H, , the parity check matrices H and H, still define the same code (they are said to

be equivalent) as long as the corresponding symbol coordinate is permutted.

One possible separated form for separated generator matrix can be:

a. = [31‘]

Multiplying the matrix G, by an information vector of dimension k gives a vector of
length n , the last k coefficients of the corresponding codeword are the k informations sym-
bols. Q.E.D.

The control matrix can be defined as a parity check matrix having some linear depen-

dent rows added to it. Later on, it will be common to regroup the rows by pack and represent

them with elements of some GF (qm), m 2 1.

It is important to remember that not all separable codes are linear !

1.8. The distance of a linear code:

Proposition 1.4. If a linear block code has a distance d, then it is impossible to find a
non null codeword of weight less than d belonging to the kernel of the parity check matrix

(or of the control matrix).

Proof. From Def. 1.2., the distance d of a block code C is the minimum Hamming dis-
tance between every possible pair of codewords. Since for a linear code, the sum or
difference of two codewords is a codeword of the same code, this implies that the null code-

word always belongs to any linear code.

11

Then, from the linearity argument, it is sufficient to find the non-zero codewords with
the smallest weight that belongs to the kernel of H. If the distance of a code is d, then there
is no way that a non-zero codeword C 1 of weight less than d could verify

When performing the decoding of a linear code, a case of false decoding might appear
since there could be a number of d errors which would send a given codeword to another
codeword at a distance d. The result belonging of course to the kernel of H, the user would

then think that no errors have occurred!

1.9. Other bounds:

Proposition 1.5. The family of linear codes reach the Varshamov-Gilbert bound, namely

there always exist a (n , k , d)-code such that:

n-k

 

61-1
5 H2("'n—)

Proof. See Peterson [9, pp. 51-52].

Unfortunately, the proof of Prop. 1.5 is an existence proof and doesn’t indicate how to
choose good codes inside the linear family of block codes. Information theory says that for
n -> co, the code has to correct an average of t =np errors (if p is the average error bit pro-

bability) in order to ensure that the probability of losing a block of information is as small as

possible. From Prop. 1.5., this implies that gil- = -2—t- -—> 2p so:
It

£21-H20P)
n

12

For small values of p , the asymptotic behaviour of the Varshamov-Gilbert bound is
very close to the channel capacity, thus the linear family of block code is an interesting fam-

ily to study.

1.10. The generalized Goppa family:

This family was introduced by Loeloeian and Conan [29] and it will be shown later that
the Alternant family is equivalent to the generalized Goppa family. The approach used by

Loeloeian is very practical because of its simplicity.

Definition 1.5. Let’s choose three polynomials G(X ), P(X ) and rt(X ) with coefficients
over GF (qm) and respective degrees r, s and n. It is necessary that 1t(X ) splits entirely in
GF(q"‘). Let’s or] , a2 , . . . . an be the n roots of 1t(X ) with the restriction that the ori’s

are not roots of G(X ) and P(X ). Then the generalized Goppa code I‘(1r(X ) , P(X) , G(X ))

of length It consists of all the codewords (a1 , a2 , . . . , an) belonging to CF (q )" such that:
" aiP(ai)

— E 0 d G X 1.1

21 X_a‘_ mo ( ) ( )

Lemma 1.1. If gcd(G(X) , X—or) = 1 then:

1 a —(G(X)—G(a»G"(a)

X_a x-a mod G(X) (1.2)

Proof. Since gcd (G (X ) , X —or) = 1, it is equivalent to say that G(a) at O or, G(X ) and
X —or are relatively prime. Then from Theorem A.1., there exist two polynomials U (X ) and

V(X ) with deg U (X ) and deg V(X ) both less than deg G(X ) such that:
U(X)(X—0t)+V(X)G (X) = 1 (1.3)

Furthermore, doing an Euclidian division of G (X) by X —or yields:

13

G (X) = A(X)(X—ot)+G (or)

 

E.1.3h tht
q( )sows aX-or

U(X)<X—a)+v (X )G (X) = G“(a)(G (X )—MX)<X—a>)

By identifying the factors of G (X) and (X -a) in Eq. (1.5), it is found:

V(X) = G"(a)
U(X) = -MX)G“(a>

Finally, using Eq. (1.6) and (1.4) yields:

_ —l
U(X): G (my-204m»

In other words, the inverse of (X —or) mad G(X ) is:

r 1—1 .
U(X) = - G‘1(a)zgjza1""x’
j=l (=0

Proposition 1.6. The control matrix of a generalized Goppa code is:

 

 

 

 

 

 

lPtal) ‘
0
1' 1 1 . . 1 ‘ G (0‘1)
or] a2 . . n 0 P(Olz)
0112 0.22 . . or} K C(09)
H = O .
o o o
‘alr-l 027-1 . . (xii-l] 0 0 P(an)
L G(orn) J
Proof. Replacing Eq. (1.8) into Eq. (1.1) yields:
" aiP(a,-) " _1 r 1-1 ._l_1 z
z— I —20;P(0;)G (or;)Zgj 20." X mod G (X)
i=1 X '01 i=1 j=l (=0

For the sake of clarity, the following matrices are defined:

I! U(X) mod G(X). Then from Eq. (1.3) and (1.4):

(1.4)

(1.5)

(1.6)

(1.7)

(1.8)

(1.9)

(1.10)

l4

 

 

 

 

 

 

 

. , '1 1 1 l
g, 0 . . 0 a1 02 an
gr-l Sr (112 022 (13
A: V=
‘81 82 ' ' ng Lalt-1 (lg-l . . (xvi-l]
VP(a1) 0 ‘
G(ar)
P(Olz)
G(0‘2)
D = 0
0
O 0 P(an)
( G(a.),

 

 

Since the degree of Eq. (1.10) is less that r and the computations are done in a residue class

ring modulo a polynomial of degree r, it is equivalent to cancelling each power of X i for

1' = O , 1 , . . . , r—l. Using the previous matrices, it is derived:
1
a2
AVD . = 0
an
S J

 

 

A being diagonal and g, at 0( because the degree of G (X) is equal to r), it is then invertible.

Multiplying both sides by A"1 yields the desired form for H. Q.E.D.

Proposition 1.7. The family of Altemant code is strictly equivalent to the family of the

generalized Goppa code for a fixed 1t(X ), n and r.

Proof. Defining y,- = P(a;)G’1(01,-) shows that generalized goppa code is also an Alter-

nant code (for the definition of Altemant code, see Helgert [14,15] or Mac Williams and

15

Sloane [16]).

Now for a given yi’s and n, pick any G(X) of degree r such that G(ori) at 0. Then,
using the Lagrange interpolation formula, it is possible to derive P(X ) by:
n n X_a.
P(X) = £y.G(a.)rIa—+ QED-

;-1 j-l 1'" j
jti

Proposition. 1.8. The generalized Goppa code F(rt(X) , P(X) , G(X)) defined over

GF (q"') and with coefficients over GF (q) has the following parameters:

'

n =deg 1t(X)
4r =deg G(X) 11
n-k Smr (1' )

r+l S d S. mr+l
L

 

Proof. n = deg rt(X) and r = deg G(X) follows imediately from Def. 1.15 and Eq.
(1.9). n—k is the rank of the control matrix defined by Eq. (1.9) when projected over GF (q)
using a basis of m elements to represent GF (qm); there are r rows in GF (q"') so using any
basis with m vectors, mr rows are derived over GF (q). In the worst case, there no depen-

dent rows over GF (q) so n—k S mr.

Supposing there is a non-zero codeword with Hamming weight at S r having
coefficients over GF (q ), then this codeword by definition would belong to the kernel of H
(Eq. (1.9)). The product aiG'l(or,-) has also the same weight as a,- since G(a;) ¢ 0. Thus if
d S r is possible, that would mean that the Vanderrnonde of order r has a non zero solution,

which is impossible.

16

It is then clear that d 2 r+1. The fact that d S. mr+l is due from Prop. 1.2. Q.E.D.

Proposition 1.9. It is a well known fact that the Altemant family reach the Varshamov

Gilbert bound (so do the generalized Goppa family).
Proof. See Mac Williams and Sloane [16].

Proposition 1.10. If G(X ) is separable in some splitting field, let’s denote
x1 , x2 , . . . , 1:, its r distinct roots. Then, another form for the control matrix of a general-

ized Goppa code over the splitting field of G (X) is:

 

 

 

 

 

 

 

 

 

'Pta.) P(az) Han]
J51-0‘1 Jl51—012 . . Iran
P (on) P (a2) P (an)
x 2—(11 x 2—(12 x z—an
(1.12)
P(al) P(a2) P(an)
Lxr—al “tr-(12 xr—an J

Proof. Obvious from Eq. (1.1).

1.11. Practical decoding of a generalized Goppa code:

1.11.1. The key equation of a generalized Goppa code:

A generalized Goppa code of length n with deg G (X) = r is used. Let’s assume that a
codeword C = (c, , c2 , . . . , c") was sent through a channel. The received word will be
called R = (r1 , r2 , . . . , r"). R is different from C when errors have occurred during the
transmission. In order to simplify the notation and assuming that e errors occurred, the posi-

tion of these errors are called:

17
X1=a1‘,X2=0.12,..., X, =or,‘
and the error values denoted:
51,52....,E,

If the channel is additive, it is obtained:

RI=CI fori¢11,12,...,l¢
Ri=Ci+Ei f0fi=11,12,...,le

(1.13)

(1.14)

(1.15)

To simplify the proof, the Altemant notation will be used, namely, y,- = P(or;)G"(0t,-).

Let’s define the syndrome polynomial S (X), the locator polynomial G(X ) and the evaluator

polynomial (1)(X ) by:

r
r-l n

5m = thnkjaju‘
i=0 j=1

{U(X) = 1'1(1-X,-X)

1:1

mm = ME.- Ira-w)

i=1 j=l
[ 1 ti

 

(1.16)

From Eq. (1.13), (1.14), (1.15), (1.16) and the fact the syndrome polynomial of any

codeword is null (Eq. ( 1.9)), it is then deduced:

r-l e . _
$00 = Etzyzrjxnx'

1-0 j-l

e r-l _
= ZYIjEj 2(XjXY
j=l i=0

. 1-(XjX)'
gly’i 1' l—XjX

J

18

hence the following equation otherwise known as the key equation of an Altemant code (or

generalized Goppa code) is derived:

S(X)O(X) 2 (0(X) mod X'
deg (0(X) < deg G(X) = e (1'17)
Berlekamp [10] has shown that Eq. (1.17) has a unique solution (S (X) , (0(X )) for a

fixed r and S (X ), given that e S r/2.

Efficient methods for solving Eq. (1.17) are available; the Berlekamp algorithm, Ber-
lekamp [10] and the MPR (minimal partial realization) Conan [19]. In the general case,
MPR is the most easy to implement. In the particular case where S (X) has the special pro-
perty 521-1 = 5,-2.1 for 1' = 1 , 2 , . . . , r and q = 2’" for some arbitrary positive integer m,
the simplified version of Berlekamp’s algorithm [10] requires about one half the computations

than MPR and is thus recommended.

When the key equation is solved, it is necessary to find the roots of G(X) which
correspond to the location of the errors. Then, using (0(X ) and the roots of G(X), the error
values can be obtained. It is important to keep in mind that G(X ) has to divide 1t(X ) other-

wise it is a non decoding situation.

In the binary case (q = 2), it is not necessary to find (0(X ) since the location of an error

is sufficient to correct the error (just add 1 to the corresponding received symbol).

1.11.2. MPR algorithm:

Define the following syndromes:

n o
Vj = 2R1)? 011’

i=1

l9
Initialization:
G(X)=l,(r)(X)=O,b(X)=O,c(X)=—1,dp =1

Iterative procedure: Do for m = 0 to r—l

deg G(X)
d = Z Vm-jow-j
j-O

Ifd at 0 then u = dp— deg( U(X))

If u s o , G(X) = o(X)—d.X”‘b(X)
m(X) = (0(X)—d.X"‘c(X)

dp = dp-I-l , continue
else a, = deg (o(X)) , r1(X) = G(X) , :2(X) = (0(X)
G(X) =X"o(X)—d.b(X) , (0(X) =X“(0(X)—d.c(X)
b(X) =d-1.:,(X) , cor) =d-1:2(X)

dp = dp+l , continue

else , dp = dp-I-l , continue

1.11.3. Simplified Berlekamp algorithm:
Let’s define S,- = VH for i = l , 2 ,...,r and So: 1. Assume that $2,- = 5,2 and
q = 2’".
Initialization:
00(X)=1,b(X)= 0
while k < r/2, do:

01+1(X ) = G(XHAkXNX)
b(X) =X2b(X) 1m, = 0 0r deg 0,,(X) > k
b(X) = A"Xo(X) if A, at 0 0r deg 0,,(X) s k

20

where A), is defined by:

498(000)
A): = Z 01 S 2k+l-1'
i=0

1.12. BCH codes:

Definition 1.6. For any given G(X) of fixed degree r, a BCH code is defined by
P(X)=X”G(X) and orj = ed (on being an element of GF(p"‘) of order n where p is a
prime number and the code having a length n ).

If n = pm-l, the BCH code is said to be primitive otherwise, it is said non-primitive. If
b=1, the corresponding BCH codes are called narrow sense, otherwise for b > 1, wide sense.

Proposition 1.11. A BCH code of length n has the following control matrix:

'r e e 1 I
1 or . . (or )""
1 ab+l . . (ab-I-IYI-l
(1.18)
i1 ab+r-l . . (ab+r-l )n-l
L J

 

 

Proof. Obvious from Prop. (1.6) and Def. (1.6).

Proposition 1.12. For a BCH code of length n with coefficients over GF (p) (p a prime

number), the redundancy is:

n-k = deg lcm(Ma.(X) , Ma..,(X) , . . . , Ma...-,(X)) (1.19)

Proof. Let’s represent a BCH codeword with coefficients c,- by:

11-1 _
C(X) = EQX‘
i=0

21

then if C belongs to the kernel of Eq. (1.18):

C(a”) = C(ab“) =...= C(a”+"‘) = o (1.20)
Since C(X) 8 GF (p)[X ], then from Prop. A20. it is also equivalent to having the minimal
polynomials of 01" , or"+1 , . . . , 111"?"1 divide C(X ). Defining:

E(X) = lCM(Mab(X) , Mab+1(X) , . . . , Mabw-1(X))

and n-k = deg E (X ), then the encoding of k bits of information represented by

n—l .
K (X) = z 1,-X' is done by the following Euclidian division:

i=n-k
K(X)= 5(X)E(X)+R(X) with deg R(X) < deg E(X) = n-k

the separable encoded codeword being C (X) = X (X )—R (X), which satisfies by construction

Eq. (1.20). QED.

Proposition 1.13. A narrow sense binary BCH code (q = 2) with r = 2: has the follow-

ing control matrix over GF (2") with d 2 2t+1 and n-k 5 mt (Hamming codes correspond

 

to t = 1):
1 or . . 01""
1 a3 .. (0:3)“l
I:
21—1 21-1 11-1
‘1 0t . . (0t ) J

 

Proof. If b=1, then Eq. (1.19) is simplified, because from Prop. A.15,

M “(X ) = M az(X ), M cl3(X ) = M 01‘“ ) and so on. In other words:
n—k = deg lcm (Ma(X) , Ma3(X) , . . . , Ma2,_1(X)) (1.20)

Clearly from section 1.11, this BCH can correct up to t errors when solving the key equation

22

since r = 2t and n—k 5 mt Q.E.D.

1.13. Goppa codes:

Definition 1.7. Let P(X ) = 1 and G(X) be a polynomial of degree r. The correspond-

ing code is called a Goppa code( introduced by Goppa [17,18]) and satisfies from Eq. (1.1):

Ejia— 0 mod G(X) (1.21)
i=1 1'

Prop. 1.8 has already shown that the distance of a Goppa code ensures d 2 r+1.

Proposition 1.14. For a binary separable Goppa code (G (X) is square free in some

splitting field), d 2 2r+1.

Proof. For each codeword of weight w, define the weight polynomial by:

G(X) = U(X’agfl
j=l

where (j) denores the indice of the j "' non zero component of the codeword. Using the for-

mal derivative on finite field (section A.8), it is clear since a,- 8 GF (2) that:

1
X -aU-)

 

01X ) = G(X )2
j=l

The codeword with components a,- belongs to the Goppa code defined by G(X ) if and only

if:

 

" a: W 1 0'91)
3:1 X-a; ‘jsl—X-atj) a G(X) aOmod G(X) (1.22)

Since G (X) doesn’t have any common roots with rt(X ), G (X) and G(X ) are relatively prime

and invoking Theorem A.1., there must exist two polynomials A (X) and B (X) of degree less

23

than deg G (X) such that:

A(X)o(X)+B(X)G (X) = 1 (1.23)
In other words, Eq. (1.23) is equivalent to :

o(X)A(X) s 1 mod G(X) (1.24)
so A (X) is the inverse of o(X) modulo G (X). Rewriting Eq. (1.24) yields:

o(X)o'(X)A (X) -=— o'(X) mod G (X)
but from Eq. (1.22):

o’(X)A(X) a 0 mod G(X)
It is then clear that:

o’(X) a 0 mod G (X) (1.25)

Practically, Eq. (1.25) implies that G(X ) divides G(X). Since the derivative of any polyno-
mial in a field of characteristic two is always a perfect square polynomial, the multiplicity
order of the roots of C(X ) is even. Every root of G (X) is a root of G(X ) but every root of

G(X ) has an even order so the following polynomial also divides G(X ):

G’tX) = G(X) n (X-Y)
G(Y)=0
yodd order

Using degree considerations, it is clear that w—l 2 deg G. (X), so:
d 2 deg G.(X)+1= r+l

If G (X) is square free (or separable) in some splitting field (for example an irreducible poly-

nomial) then G. (X) = 02(X ) which proves:

d 2 2.deg C(X)-+1 = 2r+1 Q.E.D.

24

Of course, the binary separable Goppa codes are the most interesting since they guaran-
tee a good distance. The most studied are the irreducible ones, and the Srivastava codes (

Helgert [31], G (X) is separable and split entirely in GF (2"I ), the locator field).

Proposition 1.15. Irreducible Goppa codes reach asymptotically the Varshamov-Gilbert

bound.
Proof. See Goppa [17,18]

Proposition 1.16. The narrow sense BCH codes are Goppa codes and can be represented
by G (X ) = X ' .

Proof. Obvious from Eq. (1.9) and (1.18).

Proposition 1.17. If G(X ) is separable in some splitting field (denote x1 , x2 , . . . , x,

its r roots), then another form for the control matrix of the corresponding Goppa code is a

Cauchy matrix, namely:

 

 

 

 

 

 

 

 

.
1 1 1 I
x 1‘01 Jr1'4le x 1’0".
1 1 1
x 2‘01 3‘ 2—0‘2 1‘ 2‘0!»
1 1 1
Lxr—al I, —a2 X, .071 j

Proof. Obvious from Prop. 1.10.

Practically, in the binary case (q = 2), a separable polynomial G(X ) of degree t is
chosen and the MPR algorithm is used with G‘(X). This gives the same control matrix as
the one defined by G(X ), but allows the correction of up to t errors algebraically with at

most mt bits of redundancy whenever a CF (2”) locator field is used. For binary narrow

25

sense BCH codes, Prop. 1.12. indicates that the encoding can be done using an Euclidian
division rather than a control matrix and can correct up to 1‘ errors with at most mt bits of

redundancy whenever a GF (2”) locator field is used (Berlekamp algorithm is recommended

for complexity reasons).

1.14. Examples of encoding:

1.14.1. BCH ( 15 ,5 ,7):

From Prop. 1.13., choosing t = 3, m = 4 and or a primitive element in GF (16) of order

15 implies that the encoding polynomial is:

5m = lcm(Mn(X) .M,:(X) .Mas(X))

This code can correct up to 3 errors by construction so d 2 7 and has length n = 15. It

can be verified from section All. that in CF (16):
Ma(X) = X4+X+1

iMa3(X) = X4+X3+X2+X+1

Ma5(X) = X2+X+l

b

 

in other words:
E(X) = X‘°+X 8+X5+X4+X2+X +1
so n-k = 5+5+2 = 10, or equivalently k = 5.

See the proof of Prop. 1.12. for the encoding procedure from E (X).

26

1.14.2. The (11 , l , 11) Goppa code:

Choosing G (X) = X 5+X 4+X to define a primitive Goppa code defines the roots of 1t(X)
in a GF(16) (see section A.11) to be {1,2,3,4,5,6,7,8,10,12,15} or in exponential notation

4
{1,a,or ,a2,or8,a5 ,a1°,or3,019,a6,or‘2}.

The code has length n = 16 - deg G(X)=11 and from Prop. 1.14,
dc = 2.deg G(X )+1 = 11. Computing the control matrix from Eq. (1.9) and projecting over
GF (2) yields:

10011011001
01111111111

01111111111
00000000000

 

10010101101
00110110011
01010111010
01111001111

 

11110110101
01001001001
00101000110
01111000000

 

11001011010
00011111001
01100110110
00000000000

 

10001101011
01001111100
00101110101
91111001111 J

 

 

27

After performing an elimination of the linearly dependent rows of H over GF (2) (some
permutations of columns might be necessary in some cases when no pivot is found in the

desired column), the separable form of H is obtained, namely:

30000000001]
01000000001
00100000001
00010000001
00001000001
00000100001
00000010001
00000001001
00000000101
_00000000011,

 

 

It is clear from section 1.7. that k = l (a repetition code) since 10 linear dependent

rows were found.

CHAPTER 2

THE TRACE OPERATOR

2.1 Introduction:

Due to the importance of the trace operator in the next chapters, a review of the useful
properties of such operator over a CF (pm) is presented in detail. An extension of these pro-
perties is proposed for the ring of residue classes over GF(p"‘) modulo (XV-X). It is
assumed that the reader has knowledge of algebraic computation over GF (pm). Important

properties about basis of GP (pm) over GF (p) will be derived.

2.2 General properties:

Definition 2.1. The trace of an element x 8 GF (pm) is defined by:

m—l .
Tm(x) := 2x”.
i=0

Definition 2.2. The restricted trace of order r (r .<. m) of an element x 6 GF (pm) is

defined by:

r-1

T,(x) :2 Ex!“
i=0

28

29

where all the computations are done in GF (pm ).
Proposition 2.1. T”, (xp ) = T", (x) = T,’,’, (x)

Proof. Applying Def. 2.1 and noting that xP' = x (since x 6 GF (pm)), it follows:

""1 i "“1 1+1 n: ""1 i
Tm(x”)= £(xP)P = 2x” =x" +pr =T,,,(x)
i=0 i=0 i=1

m-l . m—l . m-l .1
T,’,’,(x) = ( ZXP‘Y = E(XP')” = Exp” = Tm(x) Q.E.D.
i=0 i=0 i=0

Proposition 2.2. Tm (x) 8 GF (p)

Proof. Since Tm(x) 8 GF (pm) and GF (p) is imbedded from Prop. A21. in GF(p'"),

Prop. 2.1. indicates that T,’,’,(x )—T,,,(x)=-O or in other words, Tm (x) 8 GF (p). Q.E.D.

Proposition 2.3. The trace Operator is linear over GF (p), namely, for any

x,y eGF(p"') and At»: GF(p):

Tm (1 +y )=Tm (x )‘I'Tm (y )
Tm O‘x )=me (X )

Proof. Using Prop. A.12., it follows that

m-l . m-l . .
Tm(X+y )= 2 CM) )P'= Z xp'+y”'=Tm(x)+Tm0)
i=0 i=0

Since A 8 GF (p ), then N’ =1 and:

111-1 1‘ 111-1 i i m-l 1‘
73,411): )3 out)" = EM 1:” = )3 w =>.T,,(x) Q.E.D.
i=0

i=0 i=0

Proposition 2.4. 7”,, (x) is not identically equal to zero, namely there exists at least one

element x 8 GF (pm) such that T,,' (x) at 0

30

Proof. Since T”,(X) is a polynomial of degree pm’l, it has at most p""l roots in

CF (pm) so it remains at least one element of GP (pm) with a non null trace. Q.E.D.

Proposition 2.5. The trace operator is uniformly distributed, namely,
|{x I Tm(x) =i }| =p""l for any i e GF(p).

Proof. Let’s define A,- = {x | Tm(x) = i , x e GF(p’") }. It is clear from Prop. 2.3.
that A0 is a vector space over GF (p) so IAOI == pj for some positive integer j. Also from
Prop. 2.4., there is an element or e GF(p'") such that Tm(ot) = k with k 6 GF (p)-{0}. For
any x 8A0, Tm(or+x) = k. Supposing there exists y eGF(p"') such that T,"(y) = k and
y at a+x for any x 6 A0, then y = ot+x+'y. In other words TM (7) = O, which is a contradic-

tion. So it may be concluded that IA), l = pj .

i i
The following sequence y,- = 2y = y 21 for i = l , - - ' , p generates respectively
[=1 (:1

one element of each Ai’s. Using the same argument as before, it can be derived that

IA)! =pj for i = 0 , . .. , p-l. Since the A’s are disjoint, then:
m-1 . . 1
p’" = E |A.-| =Pp’ =1)“
i=0

hencej = m-l. Q.E.D.

Proposition 2.6. If X denotes a polynomial indeterminate variable, then:

Tm(X)—S = n (X-B)
T..(B)'~'

Proof. Since the polynomial Tm(X) - s has degree pm], this polynomial must have

m

p '1 roots in some splitting field. It is clear that if T,,, (B) = s, B is a root and from Prop.

2.5, there are exactly pm“1 distincts [3’s so the degrees match. Q.E.D.

31

2.3 Polynomial extension

It is possible to keep the previous properties of the trace operator when extended to
rational polynomials with coefficients over GF (pm) given that the trace operator is defined in
residue classes mod (X P "-X ). It can be noted that the ring of these residue classes is not an
integral domain since X Pu-X is not irreducible over GF (pm)[ X ]. When not specified oth-

erwise, the symbol 2 indicates that the computations are done mod (XV—X ).

Definition 2.3. The ring of fractional polynomials Q (p")[X ] is defined by:

Q(P"‘)[X]= {% If(X).h(X)eGF(p"‘)[X ],h(X)¢0}

Definition 2.4. For any g(X) eQ(p'")[X], the trace of g(X) in the residue class

mod (XPM—X ) is then defined by:

m—l .
Tm(g(X)) :'=' 23” (X)
i=0

Definition 2.5. For any g(X) e Q(p"')[X], the restricted trace of order r (r S m) of

g (X) in the residue class mod (X Pm—X ) is then defined by:

r-l .
Tr(8(X)) IE 28” (X)
i=0

Proposition 2.7. For any g(X) e Q(p"')[X] , gP"(X) a g(X)
Proof. It is enough to show this result for f (X) or either h(X) e GF(p’")[ X ] (since

g (X) = fi). Using Theorem A.2. on the coefficients of f (X), it is shown:

,_ dorm . , deem) ,_ ,_. dearer) .
f" (X)£( 2 f1X' )‘D a 2 f.” (X" )‘a 2‘, f.-X‘ =f(X) Q.E.D.

i=0 i=0 i=0

32

1: is worthwhile noting that r}; (g (x )) = Tm(gP(X)).
PFOPOSitiOH 23' Tm (8” (X )) -—" Tm (8 (X )) 5 751(8 (X ))

Proof. Applying the definition and Prop. 2.7,

m-l . m—l M " m-l ..
Tm(gP(X))= 2(gP(X))” 5 28” (X)g g” (X)+£g”(X)=Tm(g(X))
i=0 i-O

i=1

111-1 1 m-l l m-l 1+1
Tide (X ))E( Z 3” (X We 2‘. (8” (X ))”= 2‘, g” (X )=T,,, (g (x )) Q.E.D.
i=0 i=0 i=0

Proposition 2.9. if gP'(X) = g(X) with r s m then mg (X )) = T, (g (X))

Proof. Using Def. 2.5 and the hypothesis:

r-l .fl ' r-1 ,
T?(8(X))=‘=- 28” (X) E 8” 00+ng (X)
i=0 i=1

r-l .
Ei;(X)+Z‘.g”(Jlf)-=-T,(8(X)) Q-E-D-

i=1

2.4 Special case m = 2s:
Proposition 2.10. If T,(x) = 0 for x e GF(pz’) then x e GF(p’)

Proof.

s-l s—l

Tf(x >—T.(x) = ( zxp‘X-zxp‘
i-O i=0

.r-l i ’ s-l I.
= Exp +x" —x-Zx”

i=1 i=1

1
=x” —x

Since T, (x) = 0, this implies x’” —x = 0, so in other words, x e GF(p‘ ) (it is necessary to

33

recall that GF(p’) is embedded in GF(pz") from Prop. A.21. and r,(x) e GF(pz’) ) Q.E.D.
Proposition 2.11. Tzs(8 (x )1 = Te(g(X)) +Ti’tth» = T. (g (x )+sP’(X )1.

Proof.

2s-1 ,
T2s(8(X))= 2:08pm)

:-1 1' s-l i J
= 28’(X)+(Zg”(X))”
i=0 i=0

= 7.0100) + Ti”(g (X )1

= Te(g(X) + gP‘iX )) Q.E.D.

2.5 Basis of GF(p'") and trace operator:

From Prop. A.11., GF (pm) is a vector space over GF (p) of dimension m. Let

I31 . I32. . . . ,0". be one possible basis.
Proposition 2.12. There always exits a complementary basis 11, . . . ,1", of the basis
31.. . . ,3,” such that:

Oifiitj . .
TmOLiBj): lifi=j for 1S1,}Sm

Proof. In order to simplify the proof, the tensor notation will be used. Define the
matrix A by:
A =( Tm(BiBj) )1} 151' 11.9"

Clearly, from Prop. 2.2, A has all its coefficients on GF (p ). Suppose that A is not invertible

34

over the set of matrices with coefficients belonging to GP (p), then there must exits a vector
b with coefficients bi’s over GF (p) such that Ab = 0. By isomorphism, b can be seen as an

element of CF (p"' ), namely:

M
A- : Zbifii
i=1
and Ab = 0 becoming equivalent to TAIL-A) = 0 for i = 1 , 2 , . . . , m. Due to Prop. 2.3, it

is then derived that Tm (x1) = 0 for any x 6 G)“ (p"'). Prop. 2.4 shows that the trace operator

is not the null operator, it is then concluded that b = 0 so A has an inverse.

Take the matrix B = (bjk)jk for 15 j , k Sm , then it is clear that:

AB = ( Tm(I3i(ijkBj)) )ik

i=1

Defining the following set of elements of CF (pm) by:
M
7% = 25,13]
j=l

induces that:

AB = (Tm (Bi )‘k Dik

Since A has an inverse and taking 8 = A‘1 proves that A, , A.) , . . . , A," is a comple-
mentary basis of [31 , [32 , . . . , B". since AB = (511).} (5 being the Kronecker function).
Q.E.D.

Proposition 2.13. Let a,beGF(p”') and 0:20:51 and b=2bik; with

i=1 i=1

a: , b,- e GF(p), then:

Tm (”Fiai bi

i=1

35

Proof. Using the distributive law on the product ab, the fact that Bi’s and 24’s form

two complementary basis completes the proof. Q.E.D.

Proposition 2.14. For any a 8 GF (p"') then:

a = ET»: (01051

i=1
Proof. Follows immediately from Prop. 2.13. Q.E.D.

Proposition 2.15. It is possible to make any linear combination of the ai’s over GF(p)

by selecting the appropriate b and taking the trace of ab.

Proof. From Prop. 2.13., it is enough to select the b,-’s in CF (p) to get the desired

linear combination of the ai’s. Using then Prop. 2.14., b is uniquely constructed. Q.E.D.

CHAPTER 3

THE TRACE OPERATOR AND GENERALIZED GOPPA CODES

3.1 Introduction:

It will be shown that Prop. 2.15. can be used to derive a new analytical approach to the
determination of the dimension of the generalized Goppa codes introduced by Loeloeian and
Conan [29]. This family contains in particular all the Altemant codes, Goppa codes, Srivas-

tava codes, BCH codes and Hamming codes.

Some original bounds for specific Goppa codes will be derived with this analytical
approach without the need of a computer. It can be noted that it is not surprising to have the
trace operator related to the dimension of a linear block, in particular Delsarte [32] proved a
general result involving the dimension of a subfield code, its orthogonal code and the trace

operator.

3.2 The redundancy equation of a generalized Goppa code:

Let G(X ) be a fixed polynomial with coefficients over GF (pm) with degree r, P(X )
another polynomial of degree 3, and rt(X ) a separable polynomial of degree n that splits

entirely in GF(p’") such that gcd( G(X) , 1t(X ))=1 and gcd( P(X ) , 1t(X ))=1.

36

37

If the roots of 1t(X ) are 011, . . . ,0,“ then from Chapter 1, the generalized Goppa code
I‘(1t(X ) , G (X) , P(X ) ) of length n and constructive distance (or designed distance) dc =r+1

has the following control matrix H:

HU- =a}P(aj)G“(a,-) ,lSan, OSi<r (3.1)

When dealing with the corresponding generalized Goppa code, only the n-tuples with
coefficient over GF (p) belonging to the kernel of H are kept. It has been shown that it is
equivalent to project H over GF (p) as a vector space which yields a matrix having mt rows

with coefficients over GF (p) instead of m rows over GF (pm ).

In general, if it is possible to find one linear dependent row in the projected matrix H

over GF (p ), Prop. 2.15 shows the existence of a polynomial A (X) such that:

r

A(X): 2A,X‘ ,e = deg A(X) < deg G(X) = r ,A: eGF(p"')
i=0
* . (3.2)
ZA:o}P<o,)G"<o,-)=v,- .Tm(r,-)=0 . 151' Sn
k=0

 

L

The coefficients A,- correspond to the linear combination of the m rows defined by Hg]-
for a fixed j. Since it might be necessary to use all the terms for 0 .<_ i <1 to really eliminate
one possible dependent row over GF (p), this explain why deg A(X) < r. Of course, the
same linear combination has to succeed on all the columns of H. This combination succeeds
if and only if the trace of the corresponding 71- is equal to zero, but it is not necessary to

have all the yj’s equal to a same element.
From Prop. 2.5., there are exactly p”"l elements 7 of GF (pm) having T," (y) = 0. One

possible way to have a polynomial interpretation of Eq. 3.2 is for any fixed 7 having a null

trace, find all the 01,- satisfying:

38
‘ k 1
[EoAkaijflG- ((1,): 'Y

This is equivalent to finding the solutions of A(X )P (X )—')G (X ) = 0 in GF(p’”). It is
then hoped that solving the p""1 corresponding equations will yield all the roots of 1t(X ),
implying that the linear combination uniquely defined by the choice of the coefficients of
A (X) succeeded on all the columns of H. A necessary and sufficient condition for eliminat-

ing one of the dependent rows is then:

H (A (X )P (X )-'YG (X )) = A(X )1I(X ) (33)

T... (Y)=0

which implies that the linear combination conditioned by A (X) succeeded on the n columns

of H because of the divisibility by 1t(X ) in Eq. (3.3).

Prop. 2.6 (for s = 0) and Eq. (3.3) yield:

GP""(X>T,. [A(X)P(X)G“(X)l so mod («(X))
(3.4)

[A(X)= iAix‘, e =deg A(X)<deg G(X)=r ,A, eGF(p"')
i=0

It is worthwhile noting at this point that GP""(X)T,,, [ A (X )P (X )G"(X) ] is a polyno-
mial over GF (p"')[X ] (despite its fractional appearance).

Definition 3.1. Eq. (3.4) will be refered as the Redundancy Equation of a generalized

Goppa Code and, S (G (X ),P (X ),rt(X )) the set of all the solutions A (X) satisfying Eq. (3.4).

3.3 Interpretation:

Proposition 3.1. S(G (X) , P(X ) , 1t(X )) forms a vector space over GF (p) given the

following rules:

39

IfA,(X) ,A2(X) e S(G (X) , P(X) , rt(X)) and 7. e GF(p) then:

A10045420085(G(X).1D(X). 1c(X))
M1(X)ES(G(X).P(X),11(X)) (3.5)

Proof. Clearly, proving Eq. (3.5) shows that S(G (X) , P(X ) , 1t(X )) is a vector space
over GF (p ).

From Def. 3.1., A 1(X) and A2(X) e S(G (X) , P(X) , 1t(X )) is equivalent to saying that

deg A 1(X ) and deg A2(X ) is less that deg G (X) and:

 

GP""(X)T.. 1%] a o mod(1t(X))
i (3.6)
GP""(X)T.. 1%] 20 m0d(1r(X))

Combining the two equations of Eq. (3.6) with the residue classes properties and linear pro-

perties of the trace operator, yields:

 

..-. (A l(X)+A 2(X ))P (X) ..-, A :(X )P (X)
P P —
G (X)T,,,[ Gm 150 (X)T,,,[ G(X) ]
..-, A2(X)P(X)
P __
+G (X )T,,, [ G(X)

50 mod(1t(X))

so A,(X)+A2(X) e S(G (X) , P(X) , 1t(X)).
Using the same ideas for A 8 GF (p):

(M1(X))P(X) ]EGP"1(X)AT,,, [ A1(X)P(X) ]

G(X) G(X)

 

GP”“<X)T.. [

50 mod(rt(X))

40

SO M10!) 8 S(G(X) .P(X).1t(X)).
Finally, it is clear that:

deg A1(X)+A 2(X) < deg G(X)
deg M10!) < deg G(X) Q'E'D'

Proposition 3.2. The redundancy n-k of the generalized Goppa code satisfies:

n—k = m.deg G (X) — dim S (G (X),P (X ),1t(X )) (3.7)

Proof. From Prop. 3.1., the dimension of S (G (X ),P (X ),1t(X )) over GF (p) is well
defined. The control matrix of the T(n(X ) , G (X) , P(X )) when projected over GF (p) has
exactly m.deg G(X) rows. The dimension of S(G (X ),P (X ),1t(X )) is the number of depen-
dent non-null rows of the control matrix out of the mt initial rows and the number of remain-

ing independent rows is n-k from Prop. 1.3. Q.E.D.

3.4 Linear mapping:

Proposition 3.3. dim S (G (X ),P (X ),rt(X )) = dim S (G (aX +b ),P (aX +b ),1t(aX +b )) for
any a e GF(p’”)-{0} and b e GF(p'").

Proof. Since the transformation X -> aX +b (a at 0) doesn’t change the degrees of
A (X) , G (X) and 1t(X ), the solutions of S (G (X ),P (X ),1t(X )) are mapped isonnophically into

S(G(aX+b),P(aX+b),1t(aX+b)). Q.ED.

Proposition 3.4. It is enough to study monic generalized Goppa codes.

Proof. 1: is clear that S(G(X),P(X),1r(X)) is isomorphic to S(a‘1G(X),b’1P(X),1t(X))
for any a , b 8 GF (p”)-{O}. Taking a equal to the highest order coefficient of G(X) and b

equal to the highest order coefficient of P (X) completes the proof. Q.E.D.

41

3.5 Sub classes of the generalized Goppa family:

It has been shown in Chapter 1 how the family of Altemant codes is equivalent to the
family of generalized Goppa codes. For the moment, the only well known Altemant codes
are the Goppa codes and the BCH codes so, additional results using the trace operator are

derived for these particular codes.

3.5.1. Wide sense BCH codes:

A simpler form of the redundancy equation can be obtained for the narrow sense BCH

codes. From Prop. 1.11., another form for the control matrix of BCH codes is:
H”. = 019“” for ISj Sn 0 Si 5 r—l (3.8)

so using the general approach developed in section 3.2 leads to the definition of the following

polynomial for the redundancy equation:

‘ o
B(X)=XbZB,-X‘ ,B, £GF(p"') , e <r
i-O

Tm(B(X)) = 0 mod (X"-‘—l)

n being the length of the code or in other words, the order of 01.

3.5.2. Binary narrow sense BCH codes:

In the particular case of binary narrow sense BCH codes (b = 1), Prop. 1.13. indicates

an even simpler form for the redundancy equation leading to:

Q .
C(X): zcix2H , C,- eGF(2”') , e 5:

i=1

Tm(C(X)) = 0 mod (XH—l) (3.9)

42

n being the length of the code or in other words, the order of on.

3.5.3. Goppa codes:

Def. 1.7. says that Goppa codes correspond to all the cases where P(X ) = 1, Eq. (3.4)

becomes then:

GP"‘<X)T.. [A(X)G"(X)l so mod(1t(X))

, . (3.10)

A(X): ZAIX‘ , e =deg A(X)<deg G(X)=r ,A,- EGF(p"')
i=0

3.6. Primitive Goppa codes:

The binary Goppa codes that have been most studied previously are the primitive ones.
This require that (Xpm—X ) divides G(X )1t(X ). Since G(X ) might not split entirely in

GF (pm), multiplying both sides of Eq. (3.10) yields:

G(X)GP"'"(X)T,,, [A(X)G'1(X)] =0 mod (XP"'-X)

, (3.11)

A(X): 2Aixi, e =deg A(X) < deg G(X): 2,11,- EGF(p"')
iI-O

It is worthwile noting that this multiplication does not increase the number of solutions

as (1t(X) , G(X)) = 1.

Definition 3.2. Rm(G(X))=S(G(X),P(X),1t(X)) where P(X)=1 and (XV—X)

divides G (X )rt(X ).

43

3.7 Unification and case p = 2:

Using Prop. 2.11. when m = 2: and p = 2, Eq. (3.11) can be simplified and becomes:

 

 

2‘
GXGZMXT, ‘00:" (1) =0 d X2”+X 3.12
() ()lG(X)Gz,(X)] m0( ) ()
Assuming that:
GZ’(X) = G(X) mod (th +X) (3.13)
Eq. (3.12) becomes:
1 2‘ 2:
G(X)GZ"(X)T, I “23) (X)] 50 mod (X2 +X) (3.14)

Proposition 3.5. If G (X) satisfies Eq. (3.13), then:

n—k S 23.deg G(X) - s

Proof. Take A (X) = A0 such that A? +Ao = 0, then A (X) is always a solution of Eq.
(3.14). There are exactly 2" distinct solutions A0 in GF(22“) from Prop. A.23. It is also
clear that these particular solutions form a vector space over GF (2) of dimension 5' which is
contained in R25(G (X )). Invoking Prop. 3.2. completes the proof. Q.E.D.

One might ask if there is any solutions A (X) with deg A (X) > O. The following propo-

sition gives some more insight in the matter.
Proposition 3.6. If G (X) satisfies Eq. (3.13) and deg G (X) = 2‘+1, then:
n—k S s 23+1-s

Proof. Since deg G(X) = 2‘ +1, all the possible solutions A(X) require by definition

that deg A (X) S 2‘ . Let’s compute the following equation:

44
A (X HA 2'(X )5 A0+A1X+A2X2+...+A2,X2’
M 0' H 12’X 2'+A 22’X 7"2'+...+A 22,’X 2’2’
'5 (‘4 0+A 3’ HA1“; )X-!~AzX2+...+/12,_l X2’-1
+042” 12' )X2'+A 22'1'12'2'4m’rA $.11!” (2’4) mod (X2”+X)

Clearly, the only way A (X )+A 2'(X ) 5 O is by having:

r

1404743, = 0

A1+A22: = 0

1 , (3.15)
Al +A2, = 0

(12:162.: . .. =A2,_1=0

 

Eq. (3.15) has from Prop. A.23. 2’ distinct solutions A0. It is also possible to choose

independently of A0 any A1 8 GF(ZZ’ ), which then uniquely determines A2. . It can be

noted from Prop. A.22. that A 1+A 22: = 0 is equivalent to A 12' +A 2, = O in GF (27" ).

Overall, there are 2‘ 22’ = 23‘ distinct solutions. These solutions also form a sub-vector

space over GF (2) of R2,(G (X )) of dimension 33 so by Prop 3.2:

n—k s 2s(2~*'+1)—3s = sZ’H-s Q.E.D.

It is worthwhile noting that Prop. 3.6 provides a tighter bound than Prop. 3.5.

CHAPTER 4

THE TRACE OPERATOR AND LOELOEIAN CODES

4.1. Introduction:

Loeloeian and Conan [26] introduced a family of Goppa codes defined by
G 1(X ) = X 2’+X . One possible generalization of the Goppa code found by Bezzateev and
Shekhunova [27] could be the family of Goppa codes defined by 62(X ) = X 2"“1-1-1 (the case
s=3 was only considered by these authors and corresponds to a (55,16,19) code). Both of
these families require a GF (22“) as a locator field and also satisfy Eq. (3.13) providing a nice
unification. Furthermore, the codes derived are primitive with in particular;
G 1(X)1t1(X) = x2”+x and G2(X)1t2(X) = X2”+X.

Since the (55,16,19)-code is for the moment the best binary linear block code known
for n=55 and dc=l9 (Veorheff [28]), codes defined by 62(X ) might be very interesting to
study especially for s>3. Loeloeian and Conan [25,26] have also shown that for spectral con-

siderations, codes defined by G 1(X ) are closely related to the ones defined by G2(X ).

Tighter bounds than the one given by Prop. 3.5 and Prop. 3.6. for these specific codes

in the general case s>1 will be obtained by partially solving Eq. (3.14).

45

46

4.2. Simulation:

Using the results of computer simulation, the cases s=2,3,4,5 can be summarized in the
following tables where n is the length of the code, 1: its dimension, d6 the Goppa distance
bound derived from Prop. 1.14., (lb the Loeloeian distance bound (Loeloeian and Conan
[26]). An upper bound d5 on the distance is derived from the actual coefficients of the
corresponding parity check matrix; namely by forcing respectively every information bit to
zero except for one and computing the weight of the encoded codeword (this is done 1: times

and d5 corresponds to the smallest weight obtained).

Table 1

 

G l(X) = x2’+x

 

S n dG dL d5 k dim R23 (G 1(X ))

 

 

 

2 12 9 12 12 1 5
3 56 17 20 20 16 8
4 240 33 36 42 123 11

 

5 992 65 68 118 686 14

 

 

 

 

 

 

 

 

 

 

47

Table 2

 

62(X) = X2’+‘+1

 

 

 

 

 

s n d6 dL d5 1: dim R 2, (G 2(X ))
2 11 1 1 11 1 1 1 10
3 55 19 19 19 16 15
4 239 35 35 40 123 20
5 991 67 67 118 686 25

 

 

 

 

 

 

 

 

 

On a first approach, it looks like that dim R2,(G1(X )) = 35-1 and
dim R2,(G 2(X )) = 53 for s=2,3,4,5. For computational reasons, such results cannot be
proved using a computer for large values of s. It is hoped that the redundancy equation will

provide bounds on the redundancy of these two families of Goppa codes.

It has been shown previously that the true minimum distance d of a Goppa code

verifies dc; 5 dL 5 d S d5. Table 1 indicates that dL = d6 +3 for Gl(X ).

4.3. Important remarks:

Remark 4.1. When not specified otherwise, the symbol 3 indicates from now on that the

computations are done "mod (X 22'+X )".

48

Remark 4.2: 612’ (X) a G1(X) and 622’ (X) a G2(X)

Proof. Applying the definition of G 1(X ) and G2(X ) yields:
G,” (X) (X?+X)2’ s X2”+X2‘ a X+X2’ a G,(X)
022' (X) a (X2’+‘+1)2’ a X2”+2’+1 5 X1+2’+1 5 mm Q.E.D.

Remark 4.3. G,(X)n,(X) = X2”+X and G2(X)1c2(X) =X2”+X. In other words, these

codes are primitive.

Proof. The existence of 1:1(X ) is clear using Prop. A.23. For G2(X), pick a primitive
element or e GF(22‘), then all the roots of G2(X) in GP (22’) are 01‘0"” for

i = o, 1 ,. . . , 2’. Since G 2(X ) splits entirely in GF(ZZ'), n2(X) exists. Q.E.D.
Remark 4.4. dim Rz,(G1(X)) 2 s and dim R2,(G 2(X)) 2 3s

Proof. From Prop. 3.5., 3.6. remark 4.2 and Remark 4.3. Q.E.D.

4.4. Study of the case s=2:

Remark (4.4) yields bounds on the dimension of the redundancy vector space which are
still too far from the one expected in Table 1 and Table 2. Before attempting an extensive
analytical approach, it is interesring to derive the set of equations that have to be simultane—
ously solved when dealing with Eq. (3.14) where s=2 and for respectively, Gl(X) and
G2(X ). This will help to find a heuristic solution for better bounds. In this particular case,
all the residue computations are done mod (X 16~1-X ). Attempting here to solve Eq. (3.14) for

s = 2 yields:

 

4
G (X )G 2(X >721 A1223") 1 a 02(an (X >+A4<X)1+G (an (X )+A“(X)12 (4.1)

49
4.4.1. Loeloeian codes:
Since G(X) = G1(X) = X4+X and deg A(X) < deg G(X) = 4 then:
A (X )+A4(X) a A0+A1X+A 2X2+A 3X3+A 5‘ +A fX“+A {X8+A §X ‘2
Replacing the latter equation into Eq. (4.1) gives:

(X 8+X2)(A 0+A 1X +A 2X 2+11 3X3+A 3 +A fX 4+A {X 8+A fX 12)

+(X ‘+X )(A 3 +A 12X 2+11 §X‘+A 32X 6+A g +A 18X 8+A 28X16+A33X2‘) a o (43)
Using the fact that X 16 a X and developing Eq. (4.2) leads to:
(A 0+A 5‘ )X 2+A 1X3+A 2X‘+A 3X 5+4 14X6+A24X1°+A §X14
+(A 0+A3)X8+A1X9+A 2X 1"+11 3X11+AfX12+Afx+A;X5 4 3
( . )

+(A g +A g )X +A 12X 3+A §XS+A 32X7+A 18X9+A 28X2+A 38X 1°
+(A3+A g )X‘+A 12X6+A 3X3+A 3?X1°+.4 fX12+A §XS+A 38X” 2 0

After further complete simplification of Eq. (4.3): .

<43+43+A§)X+<45+AO+A§)X2+<A3+Atix3
+(A§+A3+A2)X4+(A§+A3+A;+A§)X5+(A {+4 ,2)X6
+A32X7-1-(A5‘+A22+Ao)X8+(A18+A l)X" (4.4)
+(A§+A32+A2+A§)X'°+A3X“+(A18+Af‘)X12

+A §X13+A 5%“ s. 0

Since the degree of Eq. (4.4) is less than 16 no further residue simplification can be done,

Eq. (4.4) is equivalent to the following system of equations:

50

'Agmgm; =0
A&Mmmf=0
A12+Al =0
A§+A3+A2=0
A22+A3+A§+A28 =0

 

AHA? =0
<[132:0
A3+A§+Ao=o
A18+A1=O
A§+A32+A2+A§ =0
A3=
Aft-A? =0
A§ =0
LA; =0

find the unknowns in GP (24)) allows for the simplification of system (4.5) as:

(F

A3+A0+A22 = 0

‘ T2(1‘11)= 0

AzeGF(22)
A3=O

L

 

4.4.2. Heuristic for general Loeloeian codes:

System (4.6) could be generalized by:

A&'+A0+A22,-t =0
< T,(A1)=0
Azs-I EGF(2’)

 

L

'42 =A3 = "' =Ark-1" A2'-'+1=A2'-‘+2 =m =Ar—r = 0

(4.5)

Using the field equation, namely, 0116 = or for or = A0 , A, , A2 , A3( since it is desired to

(4.6)

(4.7)

51
4.4.3. Bezzateev codes:
Since G(X) = G2(X) = X5+1 and deg A(X) < deg G(X) = 5 then:
A (X )+A4(X) = A0+A1X+A 2X2+A3X3+A 4X4+A 3+1; {‘X‘+A sz+A §X12+A 3X16
Replacing the latter equation in Eq. (4.1) gives:

(X l°+1)(A o+A 1X +A 2X2+A 3X3+A 4X4+A g +A {X4
+A 24X 8+A §X 12+A :X 16)

+(X5+1)(A3+A 12X2+A22X4+A32X5+AZX8+A8+A18X8 (4'8)
+A §X16+A §X24+A 2X32) = 0
Using the fact that X 16 a X and developing Eq. (4.8) leads to:
(A o+A g )+A lX +A 2X2+A 3X3+A ,X 4+A fX‘+A 24X 8+A g'X 12+A.;'X
(A0+A(‘,‘)X1°+A1X11+A2X12+A3X13+A4X14+A{‘X”+A;X3+A§X7+A2X”
(4.9)

(A ,2 +A g )+A 12XZ+A §X4+A 32X 6+A 42X 8+A ,8X 8+A 28X +A 38X9+A 2X2
(A3+A§ )X5+A 12X7+A22X9+A32X11+A3X13+A 18X13+A28X6+A38X14+A§X7 = 0

After further complete simplification of Eq. (4.9):

+(A3+A5‘+A3+Ao)+(A l+A§+A§)X-1(A2+A12+Af)X2+(A3+A§)X3
+(A.+A§+Afix‘nAtiMéuSH/iiwibx‘s
+(A,2+A;+A2)X7+(Af+A3+A§)X3+(A§+A§)X9 (4.10)
+(A 3+A 0)X1°+(A32+A1+A:)X“+(A 2+A§ )X12

+(A18+A42+A3)X13+(Af+A4+A38)X14 = 0

Since the degree of Eq. (4.10) is less than 16 no further residue simplification can be done,

Eq. (4.10) is equivalent to the following system of equations:

52

.
A3+A3+A§+Ao=0

A1+A,;‘+Az8 =0

A2+A3+Af = 0

A3+Af =0
A4+A22+Af =0
A3+A3 =0
A§+A§ =0

4 A12+A§+Af =
Af+A3+A§ =0

A22+A§ =0
A3+Ao=0
A32+A1+Af =0
A2+A§ =0

A18+A42+A3=0

Af-t-A,,+A38 = 0

 

L

Using the field equation, namely, (116

to find the unknowns in GF (24)) allows for the simplification of system (4.11) as:
A0 5 GF(22)

A,+A32+Af =0
A24+A3 = 0

4.4.4. Heuristic for general Bezzateev codes:

System (4.12) could be generalized by:

r

A0 8 GF(Z‘)
1 A1+A22,-t+l+A.§: =0

3
A 22"! +A 2'-1+1 = 0

A2 = A3 =00. =‘A23-|_1 = A23-1+2 = A2:-]+3 =... = A2:_1= o

 

L

(4.11)

= or for or=Ao ,A1,A2 ,A3 ,A4 (Since it is desired

(4.12)

(4.13)

53

4.5. Improved bound for G 1(X ):

Proposition 4.1. Eq. (4.7) has exactly 235-1 distinct solutions A (X).

Proof. One solution being determined by one possible A (X), one way of completely
solving Eq. (4.7) can be done by first choosing independently A2.-t (there are 2" possible
values since A2.-t 6 GF (2’ )). then for each given A2.-t derive the 2" values A0 using Prop.
A23 and finally picking any A1 such that T, (A1) = 0 (from Prop. 2.5. and Prop. 2.10, there

are exactly 2"1 possible values). This means that there exactly 2’ 2" 2"1 = 23‘”1 distinct

solutions A (X).

Proposition 4.2. dim R E(G 1(X)) 2 313—].

Proof. It is clear that the solutions of Eq. (4.7) form a vector space over GF (2). Using
Eq. (4.7) and Prop. 4.1. indicates that dim R ”(61(X )) 2 3.9—1 if and only if all the solu-
tions derived from Eq. (4.7) really satisfy Eq. (3.14), the redundancy equation of G1(X ). First

compute the quantity A2'(X)+A (X) using Eq. (4.7) (it has been shown in Prop. 2.10. that
Ts (A1) = O with A, e GF(22“) implies A1 a GF(2’ ), this result will be used later in this

proof):

A (X M 2’ (X ) = A 0+A1X +A 2..tX2"‘+A 3’ +A E’X2’+A 225.,X2’2”‘

= A22.-t+A1G1(X)+A 2.4612” (X) (4. 14)

Introducing Eq. (4.14) into Eq. (3.14):

 

 

 

 

2 2M
A(X)+A2’(X) A2H 42»th (X)
T :1 r A r
’I aim ] ’[Giooh’l ‘1'” 6100
A 2-. A .-.G 2’“ X
=T,[ 2’ ]+T,[ 2 l ( )1 (4.15)

GI(X) 61(X)

54

Using again Prop. 2.9, Remark 4.2 and the fact that A2,-t 8 GF (2") (or equivalently

A221.1 +A 2.-. = 0), Eq. (4.15) becomes:

 

 

T [A(X)+Az'(x)]“.2..t[_A_22--1_]+ A2.-tG,2:—1(X)]
: 61(X) S Gl(x) .1- 612’ (X)
A g- A -

G?”<X) G(“(Xi

Ill
0

Finally, from Prop. 2.11.:

G X 2““XT £191)- =0
1( >01 ( )23101001

233-1

which proves that the solutions of Eq. (4.7) are indeed in the redundancy vector space

of the Goppa code defined by G1(X ), in other words dim R z,(G1(X)) 2 3.9-1. An inequal-

ity is needed since it is not clear that Eq. (4.7) provides the unique solutions of Eq. (3.14)

when G(X) = Gl(X).

4.6. Improved bound for 02(X ):

Proposition 4.3: Eq. (4.13) has exactly 25‘ distinct solutions A (X).

Proof. One solution being determined by one possible A (X), a way of completely solv-
ing Eq. (4.13) can be found by first choosing independently A0 (there are 2’ possible values
since A0 8 GF(2’)), then picking any Art“ in era”) (22' possible values) which deter—

mine automatically AZH, and finally taking A2. 6 GF (21') induces uniquely A 1. This means

55

that there are exactly 2’ 22" 22’ = 25’ distincts solutions A (X).
Proposition 4.4: dim R 2,(G 2(X )) 2 Ss.

Proof. It is clear that the solutions of Eq. (4.13) form a vector space over GF (2).
Using Eq. (4.13) and Prop. 4.3. indicates that dim R ”(G2(X)) 2 5s if and only if all the
solutions derived from Eq. (4.13) really satisfy Eq. (3.14), the redundancy equation of Gz(X ).

First compute the quantity A2'(X)+A (X) using Eq. (4.13):

A (X )+A (X )2’ = A 0+A 1X +A 2...X2"'+A 2,-1HX2H“+A 2.x”
+A 3’ +A ,2’X2’+A 22,1,X 2”‘2’+A 22,’.,+,X<2"‘+”2‘+A 22IX22'

A(X)tA(X)2‘=A2 X+A2’ X2"'+A XZH“

2"'+1 2’-'+1 2"‘+l

X2‘2"'+A 2‘ X2’(2"‘+‘) (4.16)

2 2’ 2’
+(A2"‘+1) X +A2"‘+l 2’-‘+1

Using Prop. 2.11, remark 4.2 and substituting Eq. (4.16) implies:

 

 

 

 

 

 

2 2' 2H 2H 1
T [A(X )+A? (X ) ] = T [A2"'+1X+A 23-l+1x +A 2H+1X + ]
’ 620!) 2’ 0200
From Prop. 2.8., it is then obtained:
2 2: 2H 2H+1
A(X)+A2‘(X) 21-! A2”'+1X A2“‘+1X A2"‘+1X
T I 1' T [—]+T [————]+T [ ]
‘ Gz(X) 1’ 02m 2’ 62m 2' Gem
3 1' l 1
= T 1142,- X2 '( i )l
29 2 1+1 022,4 (X) 62(X)
A :- X2‘“+1
+72,[ 2 ‘+' 1 (4.17)

G200

56

It is clear from Remark (4.2) that:

l l l 1

EL 4

Gi"‘(X)T 02"" G§"‘(X> Ga” (X)

= 63‘“ (X)+1
— G 200

X (2'+‘)2'-1+1+1
G 20‘ )

X(2'+l)2H
G 2(X )

(4.18)

Replacing Eq. (4.18) into eq. (4.17) combined with Prop. 2.8. and Remark 4.2 yields:

‘ 2: 221-12: 23-11
T[A(X)+A2(X)]_=_T [Ar-tux + ]+Tb[A2’-‘+1X +1
‘ 02(X) 7" 020‘) 6200

3 23“ l 3-]
2’ A22:—1+1X2 +2 A2’_1+1Xz +1

ET?“ 0200 W“ Gem

 

 

]

A 21.1.” 23"1-1'22' A 21-1+1X 2’-l+l
= Tel ]+th[ l
620‘ ) G 2(X )

 

 

1-1 -1
A21-1+1X2 +1 A214+1Xr +1

5721 020‘) ]+Tzs[ G2(X) ]

 

 

:0

Finally, it is clear that:

22:4

A(X)
620062 T2’[62(X)] E 0

57

which proves that the 25’ solutions of Eq. (4.13) are indeed in the redundancy vector space
of the Goppa code defined by 02(X ); in other words dim Rz,(G 2(X )) 2 5s . An inequality is
needed since it is not clear that Eq. (4.13) provides the unique solutions of Eq. (3.14) when

4.7. Maximality of the solutions:

So far, when comparing real values from Table 1 and Table 2 to dim R2,(GI(X)) and
dim RZ,(G 2(X D, the bounds provided by Prop. 4.2. and Prop. 4.4. are reached (or maximal)

for s =2,3,4,5.

In fact, when s=2, it was shown that Eq. (4.7) and (4.13) are equivalent to Eq. (3.14).
It is, nevertheless, an open problem to verify this statement for any s > 2; such a study is

beyond the scope of this dissertation.

Interestingly, these bounds do not depend on the choice of the basis of GF (22’ ).

4.8. Practical interpretation:
Theorem 4.1. For G 1(X ), n-k S 52”“1—33 +1.
Proof. Using Prop. 3.2, Def. 3.2 and Prop. 4.2. Q.E.D.
Theorem 4.2. For G2(X ), n—k S s2’“-35.
Proof. Using Prop. 3.2, Def. 3.2 and Prop. 4.4. Q.E.D.
Proposition 4.5. the Goppa codes defined by G2(X ) = X2'+1+1 and

G3(X) = X2’+1+X2'+X are equivalent, in particular their corresponding parity check matrix

have the same rank.

58

Proof. Use Prop. 3.3 and the mapping X —) X +1 Q.E.D.

It is always better when possible to have zero as a root for G (X) for computational rea-
sons (it is not necessary to program 0° = 1 which saves one test), G3(X ) is then preferred to

G 20‘ )-

Finally, puncturing (Mac williams and Sloane [16]) one redundancy bit of the code
defined by G1(X ) yields the same redundancy bound as the one provided by Theorem 4.2.
without changing its constructive distance. If the results of Loeloeian and Conan [26] con-
cerning the spectral properties of the Goppa codes defined by G1(X) are true for any 5,
namely dL = d0 +3, then G1(X ) and G2(X) are similar in decoding performance when using
a MPR algorithm decoding scheme; algebraic decoding up to 2’ +1 errors with

n—k s s2‘+‘—3s and n .<_ 27-‘—2’-l.

CONCLUSIONS

A new polynomial theory for the dimension of generalized Goppa codes is possible
when using the trace operator. This approach to the determining of the dimension of general-
ized Goppa codes does not require a computer search, given that the redundancy equation can

be solved analytically.

Applying the derived equations to two specific codes has provided original bounds
(Theorem 4.1 and Theorem 4.2) on the dimension of a general class of binary Goppa codes;
the results match the computer simulation for s = 2,3,4,5. These bounds do not depend on

the basis of the finite field used so the results are general.

The condition given by Eq. (3.13) unifies the particular codes introduced by Loeloeian
and Conan [25,26] and by Bezzateev and Shekhunova [27]. Additionally, general bounds for

Goppa codes verifying Eq. (3.13) have been derived (Prop. 3.5 and Prop. 3.6).

59

RECOMMENDATIONS

The redundancy equation Should be applied to other codes different from G,(X ) and

G2(X ), in particular the ones unified by Eq. (3.13), namely:
GZ’(X) = G(X) mod (X21'+X)

Some possible future research topics are:
- studying how large is the real distance of these Goppa codes compared to their
constructive distance.
- proving the maximality of the bounds (Th. 4.1. and Th. 4.2).
- studying the redundancy equation when p > 2 for Goppa codes defined by

G4(X) = XP’—X and G5(X) = XP‘+‘—1 with locator field GF(pzs).

APPENDIX

APPENDIX A

REVIEW OF THE FINITE FIELD ALGEBRA

A.1. Introduction:

Due to the fundamental role of modern algebra in error correcting code theory, it seems
appropriate to include a general survey of the most important properties of finite fields
needed when using linear error correcting block codes. It will be Shown in particular how
polynomial rings with residue classes are related to the pratical construction of the Galois

fields.

Not all the proofs will be presented, the primary goal here is to gain understanding of
the relations between algebra and error correcting theory. If additional information is

required, Albert [33] or Jacobson [34,35] are good references.

A.2. Monoids:

Let S be a set of elements. A binary composition "‘ on S is a rule that assigns to each
pair of elements a and b of S a third unique element c = a*b. If for any a , b , c e S,
a* (b*c) = (a*b )*c, then * is said to be associative. If for any a , b e S, a*b = b*a, then *

is said to be commutative.

61

62
Definition A.1: A set M with the binary operation * is a monoid if the following condi-
tions are satisfied:
(i) M is non-empty
(ii) * is well defined on M, namely for any x and y e M, x*y e M.
(iii) there is one element 1 c M such that for any a e M, a* 1 = 1*a = a.
(iv) * is associative

A set satisfying the above conditions is usually noted (M , "‘ , 1). For example, the set

of the counting numbers N with the standard addition is a monoid.
Proposition A1. The unit element of a monoid is uniquely determined.

Proof. Suppose there are two units 1 and 1' in M then from Def. A.1.(iii):

1'*1=l*1'=1 ,
11*1=1*1'=1’_)1-1 Q.E.D.

A.3. Groups:
Definition A2. A set G with the binary composition * is a group if and only if:
(i) (G , * , 1) is a monoid

(ii) every element x of G has an inverse in G , namely there exists an element y such

that x*y =y*x = l.

A set satisfying the above conditions is usually noted (G , * , 1). For example, the set

of integers Z with the standard addition is a group.

Proposition A2. The inverse of any element x of a group is uniquely determined ( it is

usually denoted x’l).

63

Proof. Let y and y' be two inverses of x, then from Def. A.2.(ii), x*y’= y’*x = l.
Multiplying both sides by y and using the associativity yields (y*x)*y' = y*y'*x = y, in

other words y = y, Q.E.D.

It is a common rule to have for n e Z:

a" = a*a*...*a (n times)

which leads to the following useful properties for any x , y e G and n , m e Z:

m+n = xn *xm

-n = (xn)-l
° 1

HRH

A group (G , * , 1) is said to be abelian if * is commutative. If G is abelian, then

another useful property is derived for any x , y a G and n e Z, namely:
(x*y>" = x"*y"

An abelian group G is generated by finitely many elements if there exist some positive

integer n and a1 , a2 , . . . , an e G such that any element a of G can be represented by:
a _ i1* i2* * i. f u o o
—a, 02 ...a" orsome 11,12,...,t,, eZ
ltis commonuse to writeG =<a1,a2,. .. , a,>.

Definition A3. A group (G , * , 1) is cyclic if it is generated by only one element,
namely: G = < a > = { a" | n e Z}. Since the consecutive powers of a generates entirely

G , a is called a primitive element of G.

64

A.4. Finite groups:

A group is said to be finite if it has finitely many elements. The cardinality of a group

is usually written as |G I, so for a finite group, IG I < co.

It is interesting to study for a given or e G the following sequence; or , a2 , (:3 .... The
group G being finite, there must exist two positive integers k and I (k >1) such that
or" = a’, in other words or": 1 for u = k-l. Since it is finite, it is possible to have the fol-
lowing definition.

Definition A.4. Let G be a finite group, the order of an element a e G is the smallest
positive integer e such that a‘ = 1 and a‘ = 1 for 0 <1‘ < e ( the order of a is denoted
o(a )). The exponent of a group is the smallest strictly positive integer m such that for all

a e G , a'" = 1 ( it is usually denoted exp (G )).
Proposition A.3. Let G be a finite abelian group. If for some positive integer n and ele-

ment a e G, a" = 1 then o(a) divides 11.
Proof. Let’s call m = 0(a). Using the Euclidian division on n and m yields n = 7im+r
with O S r <m. This implies that:

an = (amytskar

l=1*a'

Suppose that r at 0, then the above equation shows a contradiction since the order of a
would be r < m and m was the smallest positive integer satisfying a'" = 1 so r = 0 and m

must divide n. Q.E.D.

Proposition A.4. Let G be an finite abelian group and a , b e G. If

gcd(o(a) , o(b)) = 1 then o(a*b) = o(a)o(b).

65

Proof. Let’s denote m = o(a ), n = o(b) and k = o(a*b ).
(a*b)""' = (am)"*(b")’" =1*1=l
so from Prop. A.3, k divides mn. On the other hand:
(a*b)" =1 —) a" =b'k -—) at" = (b")”‘ -> a‘m =1
so m divides kn but gcd (m , n) = 1 which shows that m divides k.
(a*b)" =1 -> b" =a"‘ —> b’” =(a"‘)"‘ -> b’“ =1

so n divides km but gcd (m , n) = 1 which shows that n divides k. Finally, n and m both
dividing k and god (m , n) = 1 implies that mn divides k but it was shown before that k

divides run so mn = k. Q.E.D.

Proposition A.5. Let G be a finite abelian group of exponent exp (G), then there is at

least one element of order exp (G ).

Proof. Let’s define o(a) = max{o (b) I b e G} and suppose that there is some b e G
such that b"“’ at 1. It is then always possible to find a set of distinct prime elements
p, ,p2,...,ps andpositiveintegersel ,e2,..., es ,f1,f2,...,f_, suchthat:

¢ 0 e
o(a) =pt‘p2‘---ps'

r f f,
o(b) =p1‘p2’---ps

Supposing bow at 1 shows that o(b) doesn’t divide o(a ), in other words there exist some i

such that f ,- > ei. After a renumbering, it can be determined that f 1 > e1. Defining, then,
, ‘1 , l2 ’3 . . . I:
a =d”l andb =12”2 ”3 P: implies:
I ¢ ¢ ¢
0(0 ) =P22P33-upr'

' f
o(b)=Pl‘

66

Clearly, gcd(o(a') , o(b)) =1 then from Prop. A.4, o(a’*b') =p{’p;2...p:’ which consti-
tutes a contradiction because the order of a'*b' would be greater than o(a ), the maximal

order in G. Then, there always exists a maximal element a such that
exp (G) = o(a). Q.E.D.

Proposition A.6. If G is a finite abelian group, then G is cyclic if and only if
exp (G) = IG I. In other words, there always exists at least one primitive element in G.

Proof. If G is cyclic, it is obvious that exp (G) = |G |.

If exp(G)= lG I, then from Prop. A.5, there is an element a 5G such that

o(a)=exp(G)=|Gl. In other words, |G|=|<a>| which proves that

G = < a > Q.E.D.

A.5. Rings:

Definition A5. A set R with two binary composition + and * (0 being the identity with
respect to + and 1 the identity with respect to *, 0 at 1) is said to be a ring if and only if:

(i) (R , + , 0) is an abelian group

(ii) (R , * , 1) is a monoid

(iii) for any x , y , z e R, (x+y )*z = x*z+y*z and 2* (x+y) = z*x+z*y (distributivity
PTOPCFW)

A set satisfying the above conditions is usually noted (R ,+ , * , l ,0). A ring R is
said to be commutative if * is commutative. Usually, * is omitted for simplifying purposes

when there is no ambiguity (x*y = xy). For example, Z with the standard addition and multi-

plication is a commutative ring.

67

Proposition A.7. For any element a belonging to a ring R , a0 = 0a = 0 (this property

shows that 0 is an absorbant element of R).
Proof. Using the distributivity and the fact that every element has an additive inverse:

(b+0)a=ba —) ba+0a=ba -)Oa =0
a(b+0)=ab —) ab+a0=ab —) a0=0 Q.E.D.

Definition A.6. A subset I of the ring R is said to be an ideal if:
(i) (I , +, 0) is a abelian group
(ii) For anya £1 and any b ER, thenab andba 81.

For example, the set of multiples of k e Z is an ideal usually denoted
k2 = { kn | for n e 2}. It can be shown that the quotient of R over an ideal forms a ring

called quotient ring R ,,.

A.6. Fields:

Definition A.7. A ring F having two binary composition + and * is said to be a field if
and only if:

(i) (F ,+ ,0) is an abelian group

(ii) (F—{O} , * ,1) is a group

A field is said to be commutative if * is commutative. For example, Q or R or C with
the standard addition and multiplication are commutative fields. It is common practice to note

the additive inverse of an element a by -a and the multiplicative inverse of a non zero ele-

ment a by a'l.

Proposition A.8. If a , b belong to a field F, then:

68

ab =0 —-> a =Oorb =0
Proof. Supposing that ab = 0 with a at 0 and b at 0, then using Prop. A.7. and the fact
F -{0} is a multiplicative group:

ab=0 —) a-lab=b=a-‘o=o -) b=0
ab=0 —> abb’1=a=0b‘1=0 —> a=0 Q.E.D.

Definition A.8. The characteristic of a field is the smallest positive integer e such that

C
foranya 8F, 2a =0.

i-l

The fields Q , R , C have a characteristic 0. It will be shown later on that there are
some fields with a characteristic different from 0.

Definition A.9. Let F1 and F 2 be two fields. A mapping 0 from F1 to F 2 is called an
isomorphism if for any elements x , y e F 1:

(i) ¢(x+,.-1y) = (P(X H1790 )

(ii) ¢(X*F,y ) = ¢(X )*F2¢0’)

It can be easily verified that ¢(1F1)= 1p2 and ¢(OF1)= 0p2 which is equivalent to say
that F 1 and F 2 behaves the same way, in other words, they are isomorphically identical. If

F 1 = F 2, then an isomorphism defined on F 1 is also called an automorphism.

A.7. Vector spaces:
Definition A.10. Let (F ,+,.- , Op ,*p , 1;) be a commutative field, the abelian group
(V , +v ,OV) forms a vector space over F if for any a , b e F and any X , Y e V there is

an external binary composition . such that:

69

(i) a.X e V

(ii) a. (X +V Y) = (UK +V a.Y
(iii) (a +p b)X = a.X +Vb X
(iv) (a *p b)X = a.(b.X)

(v) 1px = X

Definition A.11. A set V1 , V2 , . . . , V,, of the vector space V over the field F are

linearly independent if and only if:

h
205V,- = CV for some 0,- EF —) a; = 0,.-

i=1
A set V1 , V2 . . . . . V,, of the vector space V over the field F are linearly dependent
if and only if there exist a,- e F not all equal to zero such that:

ZaiV; = 0

i=1
The vector space V is generated over F by the set V, , V2 , . . . , V" if any X e V can
be represented with some coefficients a,- e F such that:

n
X = 20" Vi

i=1

Finally, the dimension of a vector space over F (denoted dimp-V) corresponds to the
number of elements of the smallest set representing V over F. Such a minimal set is called a

basis of V over F.

In general, for a given field F, the vector space F " is represented by n-tuples

(a, , a2 , . . . , a,,) with the following composition rules:

70

(01,02...., a,)+(b1,b2,..., bn)=(al+b1,a2+b2,..., a,,+b,,)
X.(al,a2,..., a,)=(}t.al,2t.a2,..., 1.0,.)

Definition A.12. A function d from a vector space V to R+ is called a distance if it

verifies the following properties for any vectors X , Y , Z e V:

d(X ,Y)sd(X ,Z)+d(z ,Y)
{d(X ,Y)=d(Y ,X)
d(X,Y)20

d(X,X)=0

L

 

A.8. Polynomial rings:

One of the most interesting rings are the rings of a polynomial with coefficients over a
certain field F. All the usual definitions and properties of the polynomial ring over the field
of reals R are in fact true for any commutative field F. Such properties will be used in this

section without proof since they are equivalent to those previously developed with F = R.

Let F be a field, then F [X] consists of all the possible polynomials with indeterminate

X and coefficients over F, namely:
a _ 3
F[X]=Za,-X‘|a,-€F,n€N'
i=0

It can be easily verified that F [X] with the standard rules of addition and multiplication

of polynomials forms a ring, these rules being:

r

 

n . m _ m(n,m)
ZarX‘+Eb,-X’= Z Mews)?”
4i=0 j-O k-O

n , m , n+0: k k
(ZarX‘)(Zb,-X” = 2(2)::th
Li=0 j=0 k-O [=0

71

The Euclidian division of the polynomial A(X) by the polynomial [(X) consists of

finding A(X ) and R(X ) such that:
A(X) = A(X)I(X)+R(X) with deg R(X) < deg [(X)
It can be shown that the couple A(X ) and R (X) are uniquely defined.

From the ring F [X ], it is always possible to derive the residue classes over an ideal
consisting of the set of multiples of a given polynomial I (X) by adjoining each polynomial
A(X ) its remainder F (X) when using the Euclidian division A(X) by 1(X ). Such ring is
called F [X 111m and contains all the polynomials of degree less than deg I (X).

If A (X) = B (X )C (X ) for some polynomial B (X) and C (X), then B (X) or C (X) are
called divisors of A(X ). Any polynomial in F [X] can be uniquely factorized, namely be the
unique product of monic irreducible polynomials and a constant.

A polynomial has at most a number of roots equal to its degree (in some splitting field
containing its coefficients).

A polynomial A (X) is irreducible if and only if it has A (X) or any element of F -{0} as
unique divisor.

The greatest common divisor is unique and is noted gcd (A (X ),B (X )). The least com-
mon multiple is also unique and is noted [cm (A (X ),B (X )). Two polynomials A (X) and B(X )
are relatively prime if they don’t have any common divisor other than a constant; meaning
that gcd (A (X ),B (X )) = 1 and (cm (A (X ),B (X )) = A (X )B (X).

Theorem .A.1. This theorem is also known as Bezout’s theorem. Let

C (X) = gcd (A (X ),B (X )) then there exist two polynomials U (X) and V(X ) such that:

A(X)U(X)+B(X)V(X) = C(X) with deg U(X),V(X) < max(deg A(X),deg B(X))

72
Proposition A.9. F [X ]/1 [X] is a field if and only if I [X] is irreducible over F [X].

n . g n .
The formal derivative of a polynomial A(X): Eagx‘ is A (X )= Zia,X"l. The

i=1 i=1
derivative of any constant polynomial is equal to zero and the formal derivative is a linear
operator, namely:
(A (X )+8 (X))' = A '(X PB’(X)

(M(X))’ = M'(X) for any 71. e F
(A (X )8 (X ))' = A'(X>B (X )+A (X )B’(X)

lf g'(0t) = 0 and g(or) = 0 for some or e F, then or is at least a double root of g(X ).

A.9. Linear algebra:

As with polynomial rings over field F, all the common properties of linear algebra
involving matrix theory and determinants are still valid when the coefficients of the matrices
belong to any commutative field F. It will be important to remember the following proper-
ties.

The kernel of a matrix is always a vector space over F.

The determinant of a matrix A , denoted det (A) is equal to the determinant of the tran-

spose of A (the transpose of A is noted AT).

The determinant of a Vandermonde is never equal to zero which means that the follow-
ing matrix has a non zero determinant for any n as long as the ori’s belonging to some com-

mutative field F are distinct:

73

 

 

‘
' 1 1 l
0.1 (12 an
2 2 2
0.1 (12 . . 01,,
n n n
“(11 a2 0 c Q» J

A.10. Commutative finite fields:

A finite field F is by definition a field with a finite number of elements. Let 4 = IF I
be the number of distinct elements of F. Since finite fields play such an important role in
error correcting code theory, additional time will be spent to prove some important properties

of these fields.

It is assumed for clarity that finite fields are commutative. In fact, such hypothesis is
redundant since Wedderbum’s theorem proves that all the finite fields are always commuta-
tive, Jacobson [35]. This theorem is difficult to prove and requires considerable knowledge of
commutative algebra. Since a good comprehension of error correcting theory can be obtained

without it, it is not included here.
Proposition A.10. The characteristic of a finite field is a prime number.

Proof. Examine the sequence 1, 1+1, 1+1+...+1 and so on. Since the unity l e F, the

elements of the previous sequence also belong to F. But F is finite so there exist two posi-

k 1
five integers k and l (k > I) such that 21 = 21. In other words, there exists a positive
i-l jal

p
integer p (p = k—l) such that 21 = 0. It is clear by the construction that p 2 2.

i=1
Suppose now that p is not a prime number, namely p = M where 7t and 5 are two

positive integers greater than 1. This would imply in particular by using the distributivity law

74

onF that:
A 5 p
(ZlXZl) = 21= 0
i=1 j-t i=1

1 8
From Prop. A.8, it follows that either 21 = 0 or 21 = 0 contradicting the fact that p was

ill i-l

p
the smallest positive integer satisfying 21 = 0, hence p is a prime number. Since for any
i=1

a e F, a = a* 1, it is clear that every element of F has characteristic p. Q.E.D.

p—l
The previous construction indicates that the set of {0 , 1 , 1+1 , . . . , 21 } is iso-

i=1

morphic to Z IpZ'
In the particular case p = 2, any or e F verifies or = —0t.

Proposition A.11. F is a vector space over Z 1192 and q = p'" for some prime number p

and strictly positive integer m.

Proof. It is clear from the previous construction that qZp , p being the characteristic of
F. A constructive method to determine a vector space basis over Z IpZ is to start with Br = l
and generate all the possible linear combination using 2,1,2. If there are Still elements of F
not generated by < [31 > then pick one of them for [32 and generate <01 , 02>. Continue this
process until all the elements are generated by some minimal basis <61 , [32 , . . . . flm> for
some finite m ( this process must stop since F is finite). In fact, using Def. A.10. it is also
clear that <01 , 02 , . . . , Bm> is included in F so it is equal to F. The cardinality must

then coincide so q = p’” for some finite m. Q.E.D.

Proposition A.12. : For any x , y c F, (x+y)”= x”+y”

75

Proof. For every commutative field , the binomial formula is always true, so:

10 p . _.
(x+y)P=2 [i ]x‘y" ‘
i=0

Since p is prime, it is clear that for some integer k:

for0<i<p

1” _p£p-1)---(p-i+fl _
[i]- i(i-1)...1 “AP

but the sum was over Z,pz, so 2p = 0 mod p Q.E.D.
Prop. A.12. can also be used in a polynomial ring over F and for example:

(X3+1)P = X3P+1

Theorem A.2. Any 0: e F satisfies the field equation, namely up" = or. In fact, the

polynomial Xpm—X splits entirely in F. This result is also known as Fermat’s theorem.

Proof. The case or = 0 is obvious. Let’s define for b e F —{0} the following map on F
¢(X) = bx. Clearly, 0 is an automorphism of F —{0}. In particular, the set of all the non zero

elements of F, let’s call it { a1 , a2 , . . . , a p..._l } is mapped into itself, so:
alaz - ° : ap,_1= balbaz - - - bap..._1

_. "-1
_ b” alaz...ap,.._l

which implies that b””"1 = l. Multiplying b0th sides of the previous equation by b com-

pletes the proof. Q.E.D.

The notion of order is defined since (F -{0},* ,1) is an abelian group.

76

Proposition A.13. Every finite field F has a primitive element generating all the non

zero elements.

Proof. Since F is commutative, it is enough from Prop. A.6. to show that exp (F-
{0}) = q-1. Call e = exp(F-{0}), then Theorem A.2. indicates that e S q—l. Assuming that
the e < q—l would require that the equation X‘—1 = 0 has q—l roots in F which is a con-
tradiction because a polynomial of degree e has at most e distinct roots in F so

e = q—l. Q.E.D.

Proposition A.14. All the finite fields of same order are isomorphic. It is then sufficient

to denote them with a unique terminology as GF (q ).
Proof. See Jacobson [35].

Proposition A.15. Let A(X) be a polynomial with coefficients in GF (p), then

AP(X) = A(X”). In particular, if or is a root ofA (X) then or” is also a root ofA(X).

Using Prop. A.12. on A (X) yields:
A”(X) = 2a,? X‘P
i=0
Since a,- e G (p), a,” = a,- from Theorem A.2., it then is obtained AP(X) = A (XP)

Let (it be a root of A (X) which implies A (or) = 0, then:
A”(0t) = A (of) = 0 Q.E.D.
Definition A.13. For any element or of F, the corresponding minimal polynomial

M a(X ) is a monic polynomial with coefficients over GF (p) and smallest degree such that

M 0,(ct) = 0.

77

Proposition A.16. The minimal polynomial of any element in F is unique and irreduci-

ble over GF (p )[X ].

Proof. Supposing that or has two minimal polynomial M 1(X) and M 2(X ) of same

degree, then doing an Euclidian division of M 1(X ) by M 2(X ) gives for some A(X ) and R (X):
M1(X) = M2(X)7u(X)+R(X) with deg R(X) < deg M2(X)

Since M1((1)=M2(a)= 0, this implies that R(a) = 0 which is a contradiction because
M 2(X ) was the polynomial with the smallest degree having or as a root, it is then required
that R(X) == 0. M1(X) and M2(X) have same degree and are both monic thus MX) = 1

which shows the unicity.

Clearly with the same argumentation as above, a minimal polynomial has to be irreduci-

ble. Q.E.D.

The unicity of the minimal polynomial of an element on leads to the definition of the

degree of such element.

Definition A.14. Let M c,(X ) be the minimal polynomial of a e F , then the degree of

M 0,(X ) is called the degree of 0:.
Proposition A.17 The degree of an element of GF(p’") is less or equal to 771

Proof. Since GF (pm) is a vector space over GF (p) of dimension m, a set of m+1
vectors are linearly dependent. Taking the set {1 , or , 012 , . . . , or"'} shows that there must
be a polynomial of degree less than m+1 with coefficients over GF (p) having a as a root. If
the corresponding polynomial is not monic, dividing it by its higher coefficient gives the

required polynomial. Q.E.D.

78

Definition A.15. The minimal polynomial of a primitive element is called a primitive

polynomial.
Proposition A.18. The degree of a primitive element on GF (pm) is always m .
Proof. From Prop. A.15., Ma(X) has at least a , or” ,0?2 , . . . , or?“ as roots. They

are all distinct since a has order p'"-1. Also from Prop. A.l7., M m(X ) has at most m roots

in F and m distinct roots have been found. Q.E.D.

Proposition A.19. GF(q’") is isomorphic to GF (q ),,m where I (X ) 8 GF (q)[X] is an
irreducible polynomial of degree m ( q being a prime power).

Proof. See application of Prop. A.9., the residue ring consists of all the polynomial with

coefficients over GF (q) of degree less than m , there are a total of q'" of them. Q.E.D.

Proposition A.20. Let f (X) be a polynomial with coefficients over GF (p) having a root
or 8 GF (p"'), then M d(X ) divides f (X) over GF (p )[X ]. In particular, the minimal polyno-
mial of any a 8 GF(p'") divides XP"—X.

Proof. Since f (or) = 0 and M (1(a) = 0, both polynomials have a common root. Perform-
ing an Euclidian division of f (X ) by M m(X ) implies that:

f(X) = KXWG(X)+R(X) with deg R(X) < deg Ma(X)
so R (or) = 0. If R (X) is not equal to zero, that would contradict the minimality of
M O,(X ) . Q.E.D.
Proposition A.21. GF (p"’) can be embedded in GF (pm) for any positive integer

s>1.

Proof. From Prop A.19., pick an irreducible polynomial of degree .9 with coefficients

over GF(p’"). The existence of such polynomial is not shown here, see Jacobson [35].

79

Q.E.D.

Proposition A.22. The map from GF (pm) to itself defined by ¢(X ) = X” is an automor-
phism (also known as the Frobenius automorphism). In particular, if an expression A = 0, it
is equivalent to say that A” = 0.

Proof. This map is clearly injective. It is also surjective since there is always a p"I root

in GF(p’"), namely:

x“” = 1”.“ Q.E.D.

Proposition A.23. The equation X2’+X+0t= 0 has exactly 2’ distinct solutions in

GF(22‘) when or e GF(2’).

Proof. Define H (X) = X 2'+X +01, then the formal derivative of H (X) is equal to 1 so it
cannot vanish implying that H (X) has distinct roots in some splitting field.

Let x, and x2 be two distinct roots of H (X ), then:

x12’+xl+a=0

, 2, -'> (11+xz)2‘+(x2+xl) = 0
x2 +x2+a = 0

From Prop. A.21., GF(ZZ’) contains GF (2‘) so the previous equation shows that
(x1+x2) 8 GF (2‘ ). If there is at least one root of H (X) in GF (27" ), then automatically there
are 2" distinct roots in that same field (constructing all the room from the first one

ye GF(27‘) by M for [3 e GF(2’) ).

Prop. A.22. also shows that for a root 7 6 GF (27") of H (X):
‘YZ’WOWO -> W'Hzr =0 —> (12' =0:

in other words, or 8 GF (2’ ) is a required condition for H (X ) to have a root in GF (22’ ).

 

80

Define the following sets for or 8 GF (2‘ ):

H. = {B 1 52313 = «.13 e GF(22’)}

It is clear that the H a’s are disjoint because assuming there is [3 6 GF (27") and
(11 , on; e GF(Z’) such that Bz'+[3+0t, = 0 and [32'+0+a2 = 0 implies or, = 012.
Finally, it is clear that scanning B 8 GF (27") creates non-empty sets H a , each no

empty-set containing exactly 2’ distinct elements. Q.E.D.

A.11. Example of the representation of the GF (2‘) = GF(16):
The method described here can be applied for any p and m to generate GF (pm ).

From Prop. A.19., it is sufficient enough to find one irreducible polynomial of degree 4

over GF (2) to construct GF (16). The irreducible polynomials of degree 1 are X and X +1.

For the degree 2, only X 2+X +1 is irreducible since X 2 and X 2+X can be divided by X

and from Prop. A.12. X2+1 = (X+1)2 so X2+l is divided by X+1.

It is not necessary to find any irreducible polynomial of degree 3 if it can be verified
that the only polynomial of degree 4 tested has a constant coefficient equals to 1 (not divided
by X) and an odd number of non zero coefficients (not divided by X +1). If an irreducible
polynomial of degree 4 could be divided by an irreducible polynomial of degree 3, this would

imply that it would have also to be divided by X or X +1.

It is clear that X 4+X +1 cannot be divided by X or X +1 since 0 or 1 are not roots
(0+0+1 a: 0 and 1+1+1 = 1 ¢ 0). The only test that has to be done to verify the irreduciblity

of X 4-i-X +1 is trying to divide it by X 2+X +1. Performing an Euclidian division yields:

X4+X+1 = (X2+X)(X2+X+1)+1

81

Since the remainder is not equal to 0, this completes the test.

Whenever programming a finite field, it is always interesting to choose an irreducible
polynomial which is also primitive. If the polynomial is irreducible and primitive, it has a
primitive root or which generates all the non zero elements of the finite field.

In the particular case of GF (16), X 4«i-X +1 is primitive because when using the depen-
dency relation 0:4 = 0t+1, all the consecutive powers of or are generated with a sequence of

order 15, namely:

0

(1 = l

a1 = a

012 = 012

a3 = a3

ct4 = ct+1

a5 = 0340

0.6 = 013+th

017 - 014 3 - a3+ct+1

a8 = a4+a2+ct = a2+1

a9 = 0940

or” = or“+cl2 = a2+0t+l

or“ = a3+0t2+ct

0:12 = 4+0t3+0t2 = 3+012+01+1
or13 = a4+0t3+ct2+ct = a3+012+1

or” = a4+013+0t = 0:34-11
at15 = a4+ct = 1 cyclic structure
One useful way to look at GF (16) is to use 1 , 0t , a2 , 013 as a primitive basis. When
Simulating the GF(16) with hardware or software, the coefficients of the basis representing

any element of GF(16) are the bits stored in memory.

Clearly, an addition is done by a XOR operation modulo 2. The multiplication is done

using the exponential and logarithm in base or and remembering that (115 = 1.

82

For example, 4+5 can be mapped isomorphically in base 2 by respectively a2 and 012+l.

So 4+5 is a2+a2+l = 1, then 4+5 = 1.
For the multiplication, 4 times 5 (noted 4.5) is:
a2(012+l) = ct"+ct2 = a2+ct+l

so 4.5 is 7. The same result would have been obtained using the logarithm form, namely 4 is

8 10_ 2

(12 and Sis as , so 4.5 is 0t2+ = or — +0t+1.
Finally, 4/5 is:

03/0:8 = (1’6 = a‘5a'6 = a9 = a3+0t

which is 10.

It can be verified that the only irreducible binary polynomials of degree 4 are:
X4+X +1

X4+X 3+1
X4+X 3+X2+X +1

the first two polynomials being primitive.

It is important to remember that the finding of irreducible or primitive polynomials is
something very difficult when the corresponding degree becomes large. For p = 2, referring
to the tables provided by Peterson [9] is the quickest way to locate them. More information

about computing in finite fields can be found in Berlekamp [10].

LIST OF REFERENCES

LIST OF REFERENCES

[1] C. Shannon, "A Mathematical Theory of Communication," Bell Sytern Tech. Journal,
Vol. 27, Part 1, Jul. 1948. pp. 379-423

[2] C. Shannon, "A Mathematical Theory of Communication," Bell Sytem Tech. Journal,
Vol. 27, part II, Oct. 1948, pp. 623-656

[3] R. W. Hamming, "Error Detecting and Error Correcting Codes,»
Bell System Tech. Journal, Vol. 28, pp. 147-160, Apr. 1950

[4] M. J. E. Golay, "Notes on digital Coding," Proc. IRE, Vol. 37, pp. 657, June 1949
[5] A. Hocquenghem, "Codes Correcteurs d’erreurs," Chif f res, Vol. 2, pp. 147-156, 1959

[6] R. C. Bose and D. K. Ray-Chaudhuri, "On A Class Of Error Correcting binary Group
Codes," Info. And Control, Vol. IT-3 , pp. 68-79, Mar. 1960

[7] I. S. Reed and G. Solomon, "Polynomial Codes over certain Finite Fields,"
Journal Soc. Indust. Appl. Math., Vol. 8, pp. 300-304, 1960

[8] W. W. Peterson, "Encoding and error correction Procedures for the Bose Chaudhuri
Codes," IRE Trans. Inf. Theory, Vol. IT-6, pp. 459-470, 1960

[9] W. W. Peterson, Error Correcting Codes, MIT, Cambridge, Mass and John Wiley and
sons, New York, 1961

[10] E. R. Berlekamp Algebraic Coding Theory, New York, Mac Graw Hill, 1968

[11] S. Lin and E. J. Weldon, Jr., "Long BCH codes are bad," Info. And Control, Vol. IT-
10 , pp. 445-451, Sept. 1967

[12] E. R. Berlekamp, "Long Primitive binary BCH Codes I-Iave distance
d ‘ =2nlnR-1/1og n," IEEE Trans. Info. Theory, Vol. IT-l8, pp. 415-426, May 1972

83

84

[13] H. J. Helgert, "Decoding of Altemant codes," IEEE Trans. Info. Theory, Vol. IT-23,
pp. 513-514, July 1977

[14] H. J. Helgert, "Non Cyclic Generalisation of BCH and Srivastava Codes,"
Info. And Control, Vol.21 , pp. 280-290, Oct. 1972

[15] H. J. Helgert, "Altemant code," Info. And Control, Vol.26 , pp. 369-380, Dec. 1974

[16] F. J. Mac Williams and N. J. A. Sloane The Theory of Error Correcting Codes,
Amsterdarn-New York-Oxford: North Holland, 1977

[17] V. D. Goppa, "A New Class of Linear Error Correcting Codes,"
Problems Info. Transmission , Vol. 6, pp. 205-225, Sept. 1970

[18] V. D. Goppa, "Rational Representation of codes and (L,g) codes,"
Problems Info. Transmission, Vol. 7, pp. 115-225, Sept. 1971

[19] J. Conan, "A recursive procedure for the solution of the minimal partial realization prob-
lem for scalar rational sequences," Revue Roumaine de Mathematiques Appliquees, Vol.
XXX, no. 8, pp. 625-645, Aug. 1985

[20] S. Lin and D. Costello, Jr. Error Control Coding ,, Prentice-Hall, Inc., Englewoods
Cliffs, NJ. 07632

[21] O. Moreno, "Symetries of binary Goppa codes," IEEE Trans. Info. Theory, Vol. IT-
25. pp. 609-612, Sept. 1979

[22] C. L. Chen, "Equivalent Irreducible Goppa Codes," IEEE Trans. Info. Theory, Vol.
IT-24, pp. 766-770, Nov. 1978

[23] A. L. Berrnan, H. J. Helgert and N. G. Berrnan, "Equivalent Classes Of Altemant
Codes," Comsat Technical Review, Vol. 14, pp. 313-338, Fall 1985

[24] E. R. Berlekamp, H. Rumsey and G. Solomon, "On the solutions of algebraic equation
over finite fields," Info. And Control, Vol.10 , pp. 553-564, May 1967

[25] M. Loeloeian and J. Conan, "A [55,16,19] Binary Goppa Code,"
IEEE Trans. Info. Theory, Vol. IT-30, p. 773, Sept. 1984

[26] M. Loeloeian and J. Conan, "A transform Approach to Goppa codes,"
IEEE Trans. Info. Theory, Vol. IT-33, pp. 105-115, Jan. 1987

[27] S. V. Bezzataev and N. A. Shekhunova, "Constructive Distance of the Best Among
Known (55,16,19) Goppa Codes," Problems Info. Transmission, Vol. 23, No. 4, p. 352,
Nov. 1987

85

[28] T. Verhoeff, "An Updated Table of Minimum-Distance Bounds for Binary Linear
Codes," IEEE Trans. Info. Theory, Vol. IT-33, pp. 665-680, Sept. 1987

[29] M. Loeloeian and J. Conan, "On a class of generalized Goppa codes," presented at the
IEEE Int. Symp. Information Theory, Ann Arbor, MI, Oct. 6-9, 1986

[30] P. Delsarte, "Bounds for unrestricted codes by linear programming,"
Philips Res. Reports, Vol. 27, pp. 272-289, 1972

[31] H. Helgert, "Srivastava codes," IEEE Trans. Info. Theory, Vol. 1T-18, pp. 292-297,
Mar. 1972

[32] P. Delsarte, "On Subfield subcodes of Reed Solomon codes,"
IEEE Trans. Info. Theory, Vol. IT-21, pp. 575-576, May 1975

[33] A. A. Albert, Fundamental Concepts of Higher Algebra, University of Chicago Press,
Chicago, Ill. (1956)

[34] N. Jacobson, Lectures in Abstract Algebra , Van Nostrand, Princeton, New Jersey, Vol.
1, 1951, Vol. 2, 1953, Vol. 3, 1964

[35] N. Jacobson, Basic Algebra I , 2"" Edition, W.H. Freeman and Compagny, New York,
1985

HICHIGAN STATE UNIV. LIBRARIES
Ill1111111111111111111111111111111111l1
31293006046811