Cryptography Reference
In-Depth Information
Example 4.16
To illustrate the decoding of an RS code using the Berlekamp-Massey algo-
rithm, let us consider an RS code correcting up to two errors (
t
=2
) and having
the following parameters:
m
=4;
q
= 16;
n
= 15;
n
−
k
=4
Let us assume, for example, that the transmitted codeword is
c
(
x
)=0
and that
the received word has two errors.
r
(
x
)=
α
7
x
3
+
α
3
x
6
The set of calculations performed to decode this RS code will be done in field
F
16
whose elements are given in the appendix.
1. Calculate syndrome
S
=(
S
1
,S
2
,S
3
,S
4
)
S
1
=
α
10
+
α
9
=
α
13
S
3
=
α
16
+
α
21
=
α
11
S
2
=
α
13
+
α
15
=
α
6
S
4
=
α
19
+
α
27
=
α
6
The polynomial
S
(
x
)
is therefore equal to:
S
(
x
)=
α
13
x
+
α
6
x
2
+
α
11
x
3
+
α
6
x
4
2. Calculate polynomials
Λ(
x
)
and
Γ(
x
)
from the Berlekamp-Massey algo-
rithm
Λ
p
(
x
)
Θ
p
(
x
)
Γ
p
(
x
)
Ω
p
(
x
)
p
Δ
p
δ
p
L
p
0
0
1
1
0
1
α
13
1+
α
13
x
α
2
α
13
x
1
1
1
0
1+
α
8
x
α
2
x
α
13
x
2
α
0
1
0
α
10
1+
α
8
x
+
α
12
x
2
α
5
+
α
13
x
α
13
x
α
3
x
3
1
2
α
10
1+
α
2
x
+
α
9
x
2
α
5
x
+
α
13
x
2
α
13
x
+
α
13
x
2
α
3
x
2
4
0
2
In the table above, all the calculations are done in field
F
16
and take into
account the fact that
α
15
=1
.
The error locator and error evaluator polynomials are:
Λ(
x
)=1+
α
2
x
+
α
9
x
2
Γ(
x
)=
α
13
x
+
α
13
x
2
We can verify that the key equation for the decoding has been satisfied.
Indeed, we do have:
Λ(
x
)
S
(
x
)=
α
13
x
+
α
13
x
2
+
α
4
x
5
+
x
6
α
13
x
+
α
13
x
2
=Γ(
x
)
modulo
x
5
≡
