Cryptography Reference
In-Depth Information
3. Search for the roots of the error locator polynomial
By looking through all the elements of field
F
16
we find that
α
12
and
α
9
are roots of polynomial
Λ(
x
)
. The errors are therefore in position
x
3
(
α
−
12
=
α
3
)
and
x
6
(
α
−
9
=
α
6
)
and error polynomial
e
(
x
)
is equal to:
e
(
x
)=
e
3
x
3
+
e
6
x
6
4. Calculate error coecients
e
j
(4.45).
α
3
α
6
α
2
=
α
7
e
3
=
α
6
α
14
α
2
e
6
=
=
α
3
Error polynomial
e
(
x
)
is therefore equal to:
e
(
x
)=
α
7
x
3
+
α
3
x
6
and the estimated codeword is
c
(
x
)=
r
(
x
)+
e
(
x
)=0
. The two transmis-
sion errors are corrected.
Euclid's algorithm
Euclid's algorithm enables us to solve the key equation for decoding, that is, to
determine polynomials
Λ(
x
)
and
Γ(
x
)
.
Initial conditions
:
R
−
1
(
x
)=
x
2
t
;
R
0
(
x
)=
S
(
x
);
U
−
1
(
x
)=0;
U
0
(
x
)=1
Recursion
:
calculate
Q
j
(
x
)
,
R
j
+1
(
x
)
and
U
j
+1
(
x
)
from the two following expressions:
R
j−
1
(
x
)
R
j
(
x
)
=
Q
j
(
x
)+
R
j
+1
(
x
)
R
j
(
x
)
U
j
+1
(
x
)=
Q
j
(
x
)
U
j
(
x
)+
U
j−
1
(
x
)
When
deg(
U
j
)
≤
t
and
deg(
R
j
)
≤
t
then:
Λ(
x
)=
U
j
+1
(
x
)
Γ(
x
)=
R
j
+1
(
x
)
Example 4.17
Let us again take the RS code used to illustrate the Berlekamp-Massey al-
gorithm. Assuming that the received word is always
r
(
x
)=
α
7
x
3
+
α
3
x
6
when
the transmitted codeword is
c
(
x
)=0
, the decoding algorithm is the following: