Cryptography Reference
In-Depth Information
codewords were multiples of the generator polynomial. Thus, for any codeword,
we can write:
c
(
α
i
)=0;
,
2
t
Decoding RS codes and binary BCH codes can be performed from a vector with
2
t
components
S
=[
S
1
···
∀
i
=1
,
2
,
···
S
2
t
]
, called a
syndrome
.
S
j
=
r
(
α
j
)=
e
(
α
j
)
,
S
j
···
j
=1
,
2
,
···
,
2
t
(4.32)
When the components of vector
S
are all null, there are no errors or, at least, no
detectable errors. When some components of the vector
S
are non-null, errors
are present that, in certain conditions, can be corrected.
In the presence of
t
transmission errors, the error polynomial
e
(
x
)
is of the
form:
+
e
n
t
x
n
t
where the
e
n
l
are non-null coecients taking their value in the field
F
q
.
The components
S
j
of syndrome
S
are equal to:
S
j
=
e
n
1
(
α
j
)
n
1
+
e
(
x
)=
e
n
1
x
n
1
+
e
n
2
x
n
2
+
···
+
e
n
t
(
α
j
)
n
t
Putting
Z
l
=
α
n
l
and, to simplify the notations
e
n
l
=
e
l
, the component
S
j
of the syndrome is again equal to:
S
j
=
e
1
Z
1
+
+
e
n
l
(
α
j
)
n
l
+
···
···
+
e
l
Z
l
+
e
t
Z
t
···
+
···
(4.33)
To determine the position of the transmission errors it is therefore sucient
to know the value of quantities
Z
l
;
j
=1
,
2
,
···
,t
then, in order to correct the
errors, to evaluate coecients
e
l
;
l
=1
,
2
,
,t
.
The main diculty in decoding RS codes or binary BCH codes is determining
the position of the errors. Two methods are mainly used to decode RS codes
or binary BCH codes: Peterson's direct method and the iterative method using
the Berlekamp-Massey algorithm or Euclid algorithm .
···
4.4.2 Peterson's direct method
Description of the algorithm for codes with non-binary symbols
This method is well adapted for decoding RS codes or binary BCH codes cor-
recting a low number of errors, typically 1 to 3. Indeed, the complexity of this
method increases as the square of the correction capability of the code, whereas
for the iterative method, the complexity increases only linearly with the correc-
tion capability of the code.
To determine the position of the errors let us introduce a polynomial
σ
d
(
x
)
called the
error locator
polynomial whose roots are exactly the quantities
Z
l
.
t
σ
d
(
x
)=
(
x
+
Z
l
)
l
=1
