Cryptography Reference
In-Depth Information
Coecient
e
j
is null (no errors) if
α
−j
is not a root of error locator polynomial
Λ(
x
)
. In this case, we have
S
∗
(
α
−j
)=0
since
α
−jn
=1
(recall that
n
=
q
−
1
and
α
q−
1
=1
).
A contrario
if
α
−j
is a root of the locator polynomial, coecient
e
j
is non-null
(presence of an error) and
S
∗
(
α
−j
)
is of the form
0
/
0
. This indetermination can
be removed by calculating the derivation of the numerator and the denominator
of expression (4.48).
S
∗
(
α
−i
)=Γ(
α
−i
)
nα
−j
(
n−
1)
Λ
(
α
−j
)
Using Equation (4.45) and taking into account the fact that
α
−j
(
n−
1)
=
α
j
and
that
na
=
a
for
n
odd in a Galois field, coecient
e
j
is equal to:
e
j
=
S
∗
(
α
−j
)
(4.49)
The extended syndrome can be computed from polynomials
Λ(
x
)
and
Γ(
x
)
using
the following relation deduced from expression (4.48).
Λ(
x
)
S
∗
(
x
)=Γ(
x
)(1 +
x
n
)
(4.50)
Coecients
S
j
of the extended syndrome are identical to those of syndrome
S
(
x
)
for
j
from 1 to
2
t
and are determined by cancelling the coecients of the
x
j
terms in the product
Λ(
x
)
S
∗
(
x
)
,for
j
from
2
t
+1
to
n
.
Example 4.18
Again taking the example of the RS code (
q
=16
;
n
=15
;
k
=11
;
t
=2
)
used to illustrate the Berlekamp-Massey algorithm let us determine the extended
syndrome.
15
S
∗
(
x
)=
S
j
x
j
j
=1
with:
S
1
=
α
13
S
3
=
α
11
S
2
=
α
6
S
4
=
α
6
Equation (4.50) provides us with the following relation:
S
(
x
)+
α
2
xS
(
x
)+
α
9
x
2
S
(
x
)=
α
13
(
x
+
x
2
+
x
16
+
x
17
)
S
1
x
+(
α
2
S
1
+
S
2
)
x
2
k
=3
15
(
α
9
S
k−
2
+
α
2
S
k−
1
+
S
k
)
x
k
+(
α
2
S
15
+
α
9
S
14
)
x
16
+
α
9
S
15
x
17
+
α
13
(
x
+
x
2
+
x
16
+
x
17
)
=
