Cryptography Reference
In-Depth Information
q
,
then
d
(
C
) can be allowed to be quite large. Indeed, since
d
(
C
)=2
t
+ 1, this
helps explains whythe maximum such
d
(
C
) is achieved. Moreover, although any
linear [
n,k,d
]-code has the capacityto correct
n
-tuples. Hence, when a small proportion, such as this of the total space
F
errors if theylie within
the parity-check symbols (see part 2 of “maximum error-correction/detection”
on page 444), the RS(n,t) codes can correct
any
(
d
(
d
−
1)
/
2
−
1)
/
2=
t
symbols.
We conclude this section with a look at a generalization of BCH codes, which
were discovered in 1970 (see [112]).
Goppa Codes
Let
G
(
x
)
∈
F
q
[
x
] be a polynomial of degree
s
∈
N
, and let
(
α
0
,α
1
,...,α
n
−
1
)
∈
F
q
m
, where
m,n
∈
N
, and
G
(
α
j
)
= 0 for any
j
=
1. Then a
Goppa code
C
is defined as follows. An element
c
=(
c
0
,c
1
,...,c
n
−
1
)
−
0
,
1
,
2
,...,n
∈
F
q
is in
C
if and onlyif
n
−
1
c
j
α
j
≡
0(mod
G
(
x
))
,
x
−
j
=0
where
G
(
x
) is called the
Goppa polynomial
,
C
is a linear [
n,k,d
]-code over
F
q
satisfying the properties:
1.
d
≥
s
+1.
≥
−
2.
k
n
ms
.
There exist methods for decoding based upon syndrome calculations, but we
do not cover that here. These methods, as well as the decoding methods for
Reed-Solomon codes go beyond the scope of the text.
Goppa codes have some of the deepest and most outstanding of results in all
of coding theory. Indeed, we may come full circle to the beginning of this chapter
bytying together Goppa codes with the theorythat Shannon developed in the
1940s from a modern mathematical viewpoint. In 1948, Andre Weil published a
monograph (see [288]), that provided what is known as the proof of the Riemann
hypothesis for algebraic curves over finite fields, which is well beyond the scope
of this topic to describe. Yet, we mayspeak of it insofar as it is intimately
linked to coding theory, although in those early years nobody suspected any
such connection. Weil's paper was the genesis of an evolution in the area of
mathematics called
algebraic geometry
. Then a quarter of a centuryafter the
appearance of Weil's work and Shannon's introduction of information theory,
Goppa suggested the connection between algebraic curves and codes, which we
now call Goppa codes. (See [192] for the advanced theory.)
With this, we have alreadygone well beond a mere introduction to coding
theory, and its applications. This marks the end of our journey in the main
text. Yet, it is our hope that, for the reader, this is merelythe beginning of a
journeyto learn much more about the topics in this topic, which is but a brief
introduction to such a magnificent edifice of human accomplishment, bringing
intellectual innovation and applications to everyday life.
Search WWH ::
Custom Search