coding theory can for instance be found in [MS77; Til93a].

1.2.1 Goppa codes

In this subsection, a short introduction to Goppa codes will be given. For a

more detailed description, as well as for proofs of most (unproven) statements given

below, see [MS77, Section 12.3].

First, choose a Goppa parameter r, which will determine both the dimension

and the minimum distance of the code. Let G(x) be a polynomial of degree r over

the ¬nite ¬eld Fqm and let “ = {γ1 , γ2 , . . . , γn } contain n distinct members of Fqm

(n will be the length of the codewords) such that G(γi ) = 0 for all 1 ¤ i ¤ n. In

practice, the choice “ = Fqm , together with an irreducible polynomial G(x) is often

made. The Goppa code C“ generated by the Goppa polynomial G(x) consists of all

words c = (c1 , c2 , . . . , cn ) ∈ Fn satisfying

q

n

ci

≡0 (mod G(x)).

x ’ γi

i=1

Observe that the inverse of each polynomial x’γi exists modulo G(x), as G(γi ) =

0 for all 1 ¤ i ¤ n. The code C“ is linear and of dimension k ≥ n’mr. Its minimum

distance d satis¬es d ≥ r + 1. Moreover, if the characteristic of Fq is 2 and G(x)

does not have multiple zeros, then it even satis¬es d ≥ 2r + 1. The usual form of

4 Preliminaries and notation

the parity check matrix of C“ is given by

G(γ1 )’1 G(γn )’1

«

···

γ1 G(γ1 )’1 γn G(γn )’1

···

¬ ·

γ1 G(γ1 )’1 γn G(γn )’1

2 2

¬ ·

···

H“ = ¬ ·. (1.1)

¬ ·

. .

. .

¬ ·

. .

r’1

γ1 G(γ1 )’1 · · · γn G(γn )’1

r’1

From this form, a parity check matrix over Fq can be obtained by writing each

entry as the corresponding column vector of length m from Fq .

An important feature of Goppa codes is the existence of an e¬cient decoding

algorithm At for any t less than or equal to the designed error“correcting capability

t. In practice, one therefore corrects up to the designed error“correcting capability.

Decoding can be done as follows: suppose that the vector y = (y1 , y2 , . . . , yn ) is

received. The syndrome polynomial Sy (x) of y is de¬ned by

r’1 r’1 n

γj yj G(γj )’1 ,

i T i i

x (H“ · y )i+1 =

Sy (x) = x

i=0 i=0 j=1

or equivalently

n

yi

Sy (x) ≡ (mod G(x)).

x ’ γi

i=1

The syndrome polynomial Sy (x) is zero if and only if y ∈ C“ . Now write y as

y = c + e, where c ∈ C“ and wH (e) ¤ t. (1.2)

Let E be the set of non“zero coordinates of e = (e1 , e2 , . . . , en ). Then the error“

locator polynomial σ(x) and the error evaluator polynomial ω(x) are de¬ned by

(x ’ γi )

σ(x) =

i∈E

and

(x ’ γj ).

ω(x) = ei

i∈E j∈E\{i}

Then deg ω(x) < deg σ(x) ¤ t, gcd(σ(x), ω(x)) = 1 and the following, so“called

key equation holds:

Sy (x)σ(x) ≡ ω(x) (mod G(x)). (1.3)

In order to decode the received word y, this equation has to be solved. Of course,

many solutions exist for this equation, and the one with the least degree of σ(x)

should be found. Such a solution certainly exists and is unique, since it was assumed

that at most t errors occurred.

1.2 Coding Theory 5

One way to do this is by using Euclid™s extended algorithm. On input of two

starting values r’1 (x) and r0 (x), this algorithm can be used in step i to calculate

Ui , Vi and ri satisfying

ri (x) = (’1)i (Ui (x)r0 (x) ’ Vi (x)r’1 (x)) ≡ (’1)i Ui (x)r0 (x) (mod r’1 (x)).

Now, starting with the values r’1 (x) = G(x) and r0 (x) = Sy (x), proceed until

one ¬nds a rl (x) satisfying deg rl (x) ¤ 1 r ’ 1. Then σ(x) and ω(x) can be written

2

as

Uk (x)

σ(x) = (1.4)

Uk (0)

and

ω(x) = (’1)k Uk (0)Uk (x). (1.5)

These polynomials are proven to be the correct ones in [MS77]:

Proposition 1.2.1 ([MS77, Chapter 12, Theorem 16]) The polynomials σ(x)

and ω(x) given by Equations (1.4) and (1.5) are the unique solution to the Key

Equation (1.3) with σ(0) = 1, deg σ(x) ¤ 2 r, deg ω(x) ¤ 1 r ’ 1 and deg σ(x) as

1

2

small as possible.

Clearly, once σ(x) and ω(x) are determined, one can easily determine c and e.

The error locations set E is completely determined by the roots of σ(x). Further,

for each i in E one can compute the error value ei (the i“th coordinate of e) from

the relation ei = ω(γi ) . Finally, the original codeword c can be computed as c =

i)

σ(γ

y ’ e. Note that for this algorithm to work, the parity check matrix must be in the

usual form (1.1), since the key equation only holds in that case. Also, the order of

coordinates {γi } in Fqm must be known, since otherwise the error vector e could not

be reconstructed from the error set E. Also note that this algorithm will correct up

to r/2 errors, regardless of the characteristic of Fq .

In order to correct up to r errors if the code is binary (i.e. if the characteristic

of Fq is 2) and if G(x) has no multiple zeroes, one has to slightly adapt the above

algorithm. First note that in this case the Key Equation (1.3) can be rewritten as

S(x)σ(x) ≡ σ (x) (mod G(x)).

Splitting of the squares and the non-squares in σ(x), one can write σ(x) =

± (x) + xβ 2 (x), where deg β(x) < deg ±(x) ¤ r/2. Thus the key equation can be

2