Cryptography Reference
In-Depth Information
The generator polynomial of a Reed-Solomon code, with a constructed dis-
tance
d
has
(
d
,α
l
+
d−
2
where
α
is a primitive element
of Galois field
F
q
. It therefore has the expression:
1)
roots
α
l
,
,α
l
+
j
,
−
···
···
,m
α
l
+
d−
2
(
x
))
where
m
α
l
+
j
is the minimal polynomial associated with the
α
l
+
j
element of field
F
q
.
g
(
x
)=
S.C.M
.
(
m
α
l
(
x
)
,
···
,m
α
l
+
j
(
x
)
,
···
Using the results of the appendix on the minimal polynomials with coe-
cients in
F
q
, the minimal polynomial
m
α
l
+
j
has only one root
α
l
+
j
.
m
α
j
+
i
(
x
)=(
x
+
α
j
+
i
)
The generator polynomial of a Reed-Solomon code is therefore of the form:
g
(
x
)=(
x
+
α
j
)(
x
+
α
j
+1
)
...
(
x
+
α
j
+
i
)
...
(
x
+
α
j
+
d−
2
)
In general, parameter
j
is set to 0 or 1 like for binary BCH codes. The
generator polynomial of a Reed-Solomon code, of degree
(
n
−
k
)
,has
(
d
−
1)
roots, that is
n
−
k
=
d
−
1
. Its constructed distance is therefore equal to:
d
=
n
−
k
+1
For a block code k
C
(
n, k
)
the minimum distance
d
min
being lower than or equal
to
n
k
+1
, the minimum distance of a Reed-Solomon code is therefore always
equal to its constructed distance. A code whose minimum distance is equal to
n
−
k
+1
is called a maximum distance code.
The parameters of a Reed-Solomon code correcting
t
errors in a block of
nq
-ary
symbols are therefore:
−
n
=
q
−
1;
n
−
k
=
d
min
−
1=2
t
;
k
=
n
−
2
t
Example 4.11
Let us determine the generator polynomial of a Reed-Solomon code built
from a Galois field with 16 elements having a correction capability of
t
=2
errors. The minimum distance of this code is therefore
d
min
=5
. Taking for
example
l
=1
, the generator polynomial of this code is therefore of the form:
g
(
x
)=(
x
+
α
)(
x
+
α
2
)(
x
+
α
3
)(
x
+
α
4
)
Developing the expression above, we obtain:
x
2
+
x
(
α
+
α
2
)+
α
3
x
2
+
x
(
α
3
+
α
4
)+
α
7
g
(
x
)=
Using the binary representations of the elements of field
F
16
(Appendix), the
polynomial
g
(
x
)
after development and simplification is equal to:
g
(
x
)=
x
4
+
α
3
x
3
+
α
6
x
2
+
α
3
x
+
α
10