Cryptography Reference
In-Depth Information
The value of error
e
j
is then given by the Forney algorithm:
Γ(
Z
−
j
)
Λ
(
Z
−
1
j
e
j
=
Z
j
(4.45)
)
Introducing the polynomial
S
(
x
)
defined by:
2
t
S
j
x
j
S
(
x
)=
(4.46)
j
=1
we can show that:
Γ(
x
)
modulo
x
2
t
+1
Λ(
x
)
S
(
x
)
≡
(4.47)
This relation is called
the key equation
for decoding a cyclic code.
To determine polynomials
Λ(
x
)
and
Γ(
x
)
two iterative algorithms are mainly
used, the Berlekamp-Massey algorithm and Euclid's algorithm.
Berlekamp-Massey algorithm for codes with non-binary symbols
Computation of polynomials
Λ(
x
)
and
Γ(
x
)
using the Berlekamp-Massey al-
gorithm is performed iteratively. It requires two intermediate polynomials
denoted
Θ(
x
)
and
Ω(
x
)
. The algorithm has 2
t
iterations. Once the algorithm
has terminated, the Chien algorithm must be implemented to determine the
roots
Z
−
j
of
Λ(
x
)
and consequently the position of the errors. Next, the Forney
algorithm expressed by (4.45) enables the value of the errors
e
j
to be calculated.
Initial conditions
:
L
0
=0
Λ
(0)
(
x
)=1Θ
(0)
(
x
)=1
Γ
(0)
(
x
)=0Ω
(0)
(
x
)=1
Recursion
:
1
≤
p
≤
2
t
=
j
Λ
(
p−
1)
j
Δ
p
S
p−j
δ
p
=1
if
Δ
p
=0
and
2
L
p−
1
≤
p
−
1
=0
otherwise
L
p
=
δ
p
(
p
−
L
p−
1
)+(1
−
δ
p
)
L
p−
1
Λ
(
p
)
Ω
(
p
)
Λ
(
p−
1)
Ω
(
p−
1)
Γ
(
p
)
Γ
(
p−
1)
1
p
x
=
Θ
(
p
)
Δ
−
p
δ
p
Θ
(
p−
1)
(1
−
δ
p
)
x
Termination
:
Λ(
x
)=Λ
(2
t
)
(
x
)
Γ(
x
)=Γ
(2
t
)
(
x
)
