Cryptography Reference
In-Depth Information
For a BCH code with binary symbols correcting up to
t
=2
errors, also taking
into account the previous remark and using the expressions of the two coecients
σ
j
of the error locator polynomial, we obtain:
σ
1
=
S
1
(4.41)
S
3
+
S
1
S
1
σ
2
=
Finally, in the presence of an error
σ
2
=
σ
3
=0
and
σ
1
=
S
1
.
Example 4.15
Let us consider a BCH code correcting two errors (
t
=2
)inablockof
n
=15
symbols of a generator polynomial equal to:
g
(
x
)=
x
8
+
x
7
+
x
6
+
x
4
+1
Let us assume that the transmitted codeword is
c
(
x
)=0
and that the received
word
r
(
x
)
has two errors.
r
(
x
)=
x
8
+
x
3
There are three steps to the decoding: calculate syndrome
S
, determine the
coecients
σ
l
of the error locator polynomial and search for its roots in field
F
16
.
1. Calculate syndrome
S
: we only need to calculate the odd index components
S
1
and
S
3
of syndrome
S
. Using the binary representations of the elements
of field
F
16
given in the appendix, and taking into account the fact that
α
15
=1
,wehave:
S
1
=
r
(
α
)=
α
8
+
α
3
=
α
13
S
3
=
r
(
α
3
)=
α
24
+
α
9
=
α
9
+
α
9
=0
2. Determine the coecients
σ
1
and
σ
2
of the error locator polynomial. Using
the expressions of coecients
σ
1
and
σ
2
, we obtain:
σ
1
=
S
1
=
α
13
σ
2
=
S
3
+
S
1
S
1
=
S
1
=
α
26
=
α
11
(
α
15
=1)
and the error locator polynomial is equal to:
σ
d
(
x
)=
x
2
+
α
13
x
+
α
11
3. Search for the roots of the error locator polynomial in field
F
16
.Bytrying
all the elements of field
F
16
, we can verify that the roots of the error
locator polynomial are
α
3
and
α
8
. Indeed, we have
σ
(
α
3
)=
α
6
+
α
16
+
α
11
=
α
6
+
α
+
α
11
= 1100 + 0010 + 1110 = 0000
