Cryptography Reference
In-Depth Information
σ
(
α
8
)=
α
16
+
α
21
+
α
11
=
α
+
α
6
+
α
11
= 0010 + 1100 + 1110 = 0000
The transmission errors concern the terms
x
8
and
x
3
of received word
r
(
x
)
.
The transmitted codeword is therefore
c
(
x
)=0
and the two errors have
been corrected.
The reader can verify that in the presence of a single error,
r
(
x
)=
x
j
;
0
≤
j
≤
(
n
−
1)
, the correction is still performed correctly since:
S
1
=
α
j
;
S
3
=
α
3
j
;
σ
1
=
α
j
;
σ
2
=0;
σ
d
(
x
)=
x
(
x
+
σ
1
)
and the error locator polynomial has one sole root
σ
1
=
α
j
.
Chien algorithm
To search for the error locator polynomial roots in the case of codes with binary
symbols, we can avoid going through all the elements of field
F
q
by using Chien's
iterative algorithm.
Dividing polynomial
σ
d
(
x
)
by
x
t
, we obtain:
σ
d
(
x
)=
σ
d
(
x
)
x
t
=1+
σ
1
x
−
1
+
+
σ
j
x
−j
+
+
σ
t
x
−t
···
···
The roots of polynomial
σ
d
(
x
)
that are also the roots of
σ
d
(
x
)
have the form
α
n−j
where
j
=1
,
2
,...,n
−
1
and
n
=
q
−
1
.
Thus
α
n−j
is a root of
σ
d
(
x
)
if:
σ
1
α
−n
+
j
+
+
σ
p
x
−np
+
jp
+
+
σ
t
x
−nt
+
jt
=1
···
···
Taking into account the fact that
α
n
=1
, the condition to satisfy in order for
α
n−j
to be a root of the error locator polynomial is:
t
σ
p
α
jp
=1;
j
=1
,
2
,
···
,
(
n
−
1)
(4.42)
p
=1
Chien's algorithm has just tested whether condition (4.42) is satisfied using the
circuit shown in Figure 4.7.
This circuit has a register with
t
memories initialized with the
t
coecients
σ
j
of the error locator polynomial and a register with
n
memories that stocks
symbols
r
j
;
j
=0
,
1
,
1)
of word
r
(
x
)
. At the first clock pulse, the
circuit performs the computation of the left-hand part of expression (4.42) for
j
=1
. If the result of this computation is equal to 1,
α
n−
1
is a root of the error
locator polynomial and the error that concerned symbol
r
n−
1
is then corrected.
If the result of this computation is equal to 0, no correction is performed. At
the end of this first phase, the
σ
j
coecients contained in the
t
memories of
the register are replaced by
σ
j
α
j
. At the second clock pulse the circuit again
···
,
(
n
−
