La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

On Algorithms for Coding and Decoding
Algebraic-Geometric Codes and Their
Implementation
Dissertation zur Erlangung des Doktorgrades Dr. rer. nat.
der Fakultät für Mathematik und Wirtschaftswissenschaften der Universität Ulm
Vorgelegt von Jörg Marhenke aus Hameln | Juli 2008
x
x
x
x2der
3
ter:
J?rg
2008
Marhenk
Bou
e
v
Dek
eitgutac
an:
Dr.
Prof.
T
Dr.
7.
F
b
rank
Zw
Stehling
h

Prof.
h
Irene
ter:
w
Prof.
ag
Dr.
Promotion:
W
No
erner
em
L?tk
er
eb
ohmert4L(D)∞
L(D)
.
15
.
1.1
.
Riemann-Ro
.

of
h
.
Spaces
.
and
.

.
Co
In
des
.
.
.
.
4.4
.
.
.
Spaces
.
.
.
to
.
.
.
.
.
.
.
.
.
.
.
.
15
P
1.2
.
The
.
Normalization
.
.
d
.
.
.
.
.
.
.
to
.
.
.
63
.
.
.
.
.
w
.
Round-2
.
Notation
.
.
.
.
.
.
.
Theorem
.
.
.
.
.
.
.
46
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
to
.
.
.
.
.
Computing
.
tro
22
.
2
.
The
.
Metho
57
d
h
of
.
Coates
.
23
ers
2.1
General
Notation
.
.
.
.
.
.
A
.
F
.
es
.
.
.
43
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Applying
.
Theorem
.
.
.
.
.
.
.
.
.
.
.
Round-2
.
.
.
.
.
.
.
.
.
.
.
.
23
.
2.2
4.5
A
Grauert-Remmert

.
Algorithm
.
to
.
Compute
.
a
55
Basis

of
5.1
Preliminaries
and
1
.
9
.

.
tro
.
.
.
.
.
.
.
.
An
.
Riemann-Ro
.
.
.
.
.
.
.
.
.
6
.
o
24
Curv
2.3
Using
An
ds
Algorithm
.
to
.
Compute
.
a
.
Basis
.
of
.
In
63
ts
ecial
ten
Co
Con
T
.
of
.
.
.
.
.
4
65
.
.
.
.
.
40
.
The
.
Algorithm
.
4.1
.
tro
.
and
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
27
.
3
.
The
.
Grauert-Remmert
.
Metho
43
d
Dedekind's
33
.
3.1
.
Notation
.
and
.
Preliminaries
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.3
.
the
.
ohst-Zassenhaus
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
.
The
.
Algorithm
33
.
3.2
.
A
.
Criterion
.
for
.
Normalit
.
y
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
.
Comparison
.
the
.
Metho
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
.
Riemann-Ro
.
h
.
57
.
In
.

.
Notation
.
.
34
.
3.3
.
The
.
Algorithm
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.2
.
Algorithm
.
Compute
.

.
Spaces
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
58
.
Applications
.
T
.
w
.
of
.
es
.
6.1
.
the
.
Metho
.
.
.
.
.
.
.
.
37
.
3.4
.
Applications
.
in
.
Co
.
ding
.
Theory
.
.
.
.
.
.
.
.
6.2
.
Sp
.
Class
.
Goppa
.
des
.
rom
.
o
.
ers
.
Curv
.
.
.
.
.
.
.
.
.
.
.
.
.
5
..
6
.
CONTENTS
.
7
.
The
.
F
.
eng
C.1.5
and
.
Rao
.
Metho
.
d
.
for
.

.
ding
.
67
.
7.1
.
The
106
Idea
107
of
.
the
.
Algorithm
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
In
.
.
.
.
.
.
.
.
.
C.1
.
.
.
.
.
.
.
.
.
.
.
.
67
.
7.2
.
The
.
Algorithm
.
of
.
F
.
eng
C.1.7
and
.
Rao
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Residual
.
.
.
.
.
.
.
ding
.
.
.
.
.
.
.
B.6
.
.
.
.
.
.
.
.
.
erview
.
.
.
.
.
.
75
.
8

Soft-Decision


.
ding
.
of
.
Goppa-Co
.
des
.
79
.
8.1
.
In
.
tro
.

.
.
115
.
.
.
.
.
.
.
120
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C.1.8
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
134
.
.
.
.
.
.
.
139
.
.
79

8.2
Co
Preliminaries
.
.
.
.
.
.
.
.
.
.
.
.
Soft-Decision
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ariables
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B.7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
109
.
de
80

8.3
.
Channels
.
with
.
Reliabilit
.
y
.
Information
.
.
.
.
.
.
C.1.1
.
.
.
.
.
.
.
.
.
.
.
.
.
C.1.2
.
.
.
.
.
.
.
.
.
.
.
.
.
MyNormalization
.
.
.
.
.
.
.
.
81
.
8.4
.
Using
.
Reliabilit
MyMaximalOrderFiniteGR
y
.
Information
.
in
.
the
.

.
ding
.
T
.
ask
.
.
.
.
.
.
.
.
.
.
C.1.6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
83
.
8.5
.
Sp
.
ecial
.
Case:
.
The
.
Algorithms
.
of
.
Gurusw
.
ami
.
and
.
Sudan
.
.
.
.
.
.
.
.
C.1.9
.
.
.
.
.
.
.
.
.
.
.
.
.
133
88
.
8.6
.
Finding
.
an
.
Optimal
.

.
y
MyOrderedBasis
Matrix
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
B.4
.
ding
.
Goppa
.
des
.
.
.
.
.
.
.
.
.
.
.
.
.
.
90
.
9
.
Conclusions
.
and
.
Remarks
.
97
B.5
A

Do
.

.
tation
.
for
.
In
.

.
F
.

.
101
.
A.1
.
F
.

.
to
.
Compute
.
Maximal
.
Orders
107
in
V
F
of

terest
Fields
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
101
.
A.2
.
The
.
Normalization
.
.
108
.
Ov
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C
.
Co
.
111
.
In
.
F
.
.
.
.
.
.
.
.
.
.
.
.
102
.
A.3
.
F
.

.
to
.
Compute
.
Riemann-Ro
.

.
h
.
Spaces
.
.
111
.
MyMaximalOrderFinite
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
111
.
MyMaximalOrderInfinite
.
.
103
.
A.4
.
F
.

.
for
.
Co
.
ding
.
.
.
.
.
.
.
.
.
.
C.1.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C.1.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
104
.
B
.
Running
123
the
MyMaximalOrderInfiniteGR
Examples
.
105
.
B.1
.
Hermite
.
Curv
.
es
.
.
.
.
.
.
.
.
.
.
.
.
125
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
127
.
MyPlaces
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
105
.
B.2
.

.
h
.
tenoth
130
T
MyGoppaCode
o
.
w
.
ers
.
of
.
Curv
.
es
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
131
.
MyResidualGoppaCode
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
105
.
B.3
.
Generating
C.1.10
Co
.
des
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
C.1.11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.C.2.4
CONTENTS
.
7
161
C.2
.
Examples
.
.
.
.
Residual
.
.
.
.
.
.
.
.
.
.
.
C.2.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
wledgmen
.
.
.
.
.
.
.
.
.
ding
.
Co
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
151
.

.
165
141
.
C.2.1
.
Initialization
.
of
.
Examples
.
.
.
.
.
.
143
.

.
of
.
Goppa
.
des
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
145
.
Soft-Decision
.
ding
.
.
.
.
.
.
.
.
.
.
141
.
C.2.2
.
Places
.
and
.
Generation
.
of
.
Co
.
de
.
.
Zusammenfassung
.
A
.
kno
.
ts
.
.CONTENTS
8F qq
n nC n F C Fq q
nx,y∈Fq
d (x,y)H
d (x,y) := #{i∈{1,...,n} ; x =y }.H i i
δ = min d (x,y)H
x,y∈C
x=y
C δ
⌊(δ− 1)/2⌋ n κ
δ [n,κ,δ]
(v ,...,v )1 κ
κ(x ,...,x )∈F1 κ q Pκ xvi ii=1
minim
k
that
eep
Is
the
Shannon
probabilit
ed
y
ond-
of
is
an
an
error
Linear
arbitrarily
ys
small
determined
for

an
theorem
y
.

armativ
hannel
de
that
unication
do
an
es
protection
not
as
pro
h

k

aim
random

output.
theory
Ho
stated
w

ev
of
er,
to
Shannon's
w
Theorem
ord.
is
and
not
is

a
e.
v
In

this
a
thesis
nd
w
data
e
k
explain
scratc
the
the


of
b

bination
des

and
in
fo
resp

It
on6
their
fundamen
implemen
when
tation.
the
W
of
e

only
um



b
hannels
answ
whic
errors
h

transmit
linear
sym
length
b
nel?
ols

from
an
a
en
nite
-co
eld
des
data
the
the
that
with
e
that
terms
elemen
hanism
ts.
h
A
ossible

If
o
represen
de
blo
is
alw
of
or
blo
ngerprin

surface
k
dew
length
y

blo
is
giv
a
the
subset
linear
of
irregularities
yl
to
vin
de
er
w
.
the
If
ord
v
to
is
asserts
a
.
linear
information

of
of
tal
o
his
Discs
he
Compact
1948,
the


minimum
de
e
is
in

A
line
de
ar
minim
.

A

single
up
elemen
y
t
ely
of
ered
the
as

question
de
in
is
y

dew
a
A


o
of
dewor
This
d
dimension
.
with
F
um
or
han-
of

tage

an

adv
giv
The
for
Disc.
de.
Compact

w
ha
e
e
dene
adv
the
tage
Hamming
they

b
e
describ
the
in
is
of
des
basis
there

de
a
After

ding
to
blo
p
k
.
information
the

is
ord
ted
transmitted
a
v

the
a
hannel.
it
transmission
dust.
b
hes

ts,
y
as


that
its
sym

ols
ord
the
b
ed
one
ord
h



is
no
en
attempts
y
retriev

the
ing



on
to
exists
a
ord
minor
the
mission.

.


of
a
application

as
of
the
the
e
dew
of
is
example
o
opular
er
p

most
The
The


e
tro
b
In
noise
b
h

some
disc
b
the
of
hanism


w
protection
are
this
The
With
er

w
against
to
de
e

original
Reed-Solomon
dew6
from
a
trans-
y
The
b
is
protected
de
is
o
The
a
n
ed
um
ord
b
to
er

ed
dew
y
with
pla
ect
error-free
9
despite⌊(δ−1)/2⌋
F L(t) Fq q
t E ⊂F nq
n κ
nev : L(κ−1)→F , f 7! (f(x); x∈E).E q
κ−1
κ−1
n−κ + 1
n
κ n+1
X
L(D) D X
ties
around
obtained
the
divisor

at
dew
e
ords.
lo
If
b
a


y
ed
Giv
w
h
ord

lies
ws
in
the
one
des
of
half
the
linear
spheres
w
it
a
is
R

um
ded
linear
to
um
the
of

at
dew

ord
Singleton
in
of
the
b

sp
ter.
the
The
ds

v
ding
is
is
ts
unique

if
o
the

radius
its
is

at
is
most
e

hard
er,
o
ev
ound
w
a
Ho
more
.

easy
p

der
and
um
.
least
If
the
the
that
radius
of
is
its
larger

the
Th
spheres
design

The
o
Reed-Solomon
v

erlap,

whic
function,
h
ositions.
results
b
in
of
a
are
list
b
of
eld.

more
dew
es
ords.
algebr
This

is
,
referred
v
to

as
w

sp
ding
where
b
space.
eyond
their
half

the
termined,
minimum
in

en
e
des.
.
e
A
er
dditionally
the
,
note
w
dew
e

distinguish
giv
b
since
et
ords
w
ev
een
of
har
spheres
d-
It
and
the
soft-de
of

is
algorithms.

F
.
or
hand,
man
ound
y
sum

um
hannels

the
used.

is
probabilities
ding
of
hence
ha
is
ving
Reed-Solomon
sen
used
t
des
a



sym-
algorithms
b
des
ol
for
giv
up
en
minim
the


determine
ed
h
sym
erroneous
b
the
ol
is
are
solving
a
A
v

ailable.
their

ounded
ding
n
algorithms
of
that
the
use
this
this

reliabilit

y
that
information
ha
are
limitations,


soft-decision,
.
otherwise
or
they
o
are


es
hard-decision.
nite
The
an
Reed-Solomon
de

function
des

used
o
on
e
Compact
ounde
Discs
is
are

linear
des

that
des
minim
with

go
b
o
de-
d
whic
prop
is
erties
general
for
ev
applications.
for
They

are
T
easily
deriv
generated
a
and
w

b
t
on
implemen
minim
tations

of
that
metho

ds
ord
for
not

tain
ding
than
up
a
to
zeros,
half
the
the
dew
minim
are
um
from

aluating
exist.
olynomials
A
degree
dditionally
most
,
puts
algorithms
.
for
follo

that
ding
minim
b

ey
the
ond
de
half
at
the

minim
ounded
um
A

On
and
other
soft-decision
the

b
ding
asserts
are
the
a
of
v
minim
ailable.

T
a
o
de

length
a
plus
Reed-Solomon
dimension

is
de
most
o
o
v
,
er
this
h
ound

exact.

us,
the

v
are
ector
to
space

reasonable
with
a

is

ding
most
of
t
all
ding
p
for
olynomials

o
are
v
algorithms
er
de-

ding
d
to
with
the
degree
um
at
These
most
metho
o
rst
and
a
an
whic
ordered
iden
set
the
eliho
p
um-lik
Then
Maxim
error
.
ector
that
determined

y
of
a
ding
system.
pairwise
limitation
dieren
Reed-Solomon
t
des
elemen
that
ts.
lengths
The
b
Reed-Solomon
b

the
de
um
of
er
length
elemen
o
in
and
base
dimension
In

thesis
is
e
the
a
image
general
of
of
the
des
ev
do
aluation
not
map
v
de
these
d
the
radius

o

maximum-likeliho
des


is
des,
This
Gopp


Hamming
des
the
are
e,
from
10

Hamming
o
alternativ
er
an
elds.
As
en


ecial
e
sp
and
for

en
eld
.
e
means
the
divisors
iemann-R
e

describ
ac
the
e
and
d
ole
,
eha
b
of
a
functions
on
the
ailable
By
v
of
a
w
only

are
e
algorithms
zero
t
p
In
b
further
vior
adv
the
an
in
tage
Riemann-Ro
of
h
Reed-Solomon

most
A

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin