Cryptography Reference
In-Depth Information
Termination :
Λ( x )=Λ (2 t− 1) ( x )
Example 4.19
Again taking the BCH code that was used to illustrate the computation of
the error locator polynomial with the direct method, let us assume that the
received word is r ( x )= x 8 + x 3 when the transmitted codeword is c ( x )=0 .
1. Syndrome S has four components.
S 1 = r ( α )= α 8 + α 3 = α 13
S 3 = r ( α 3 )= α 24 + α 9 =0
S 2 = S 1 = α 26 = α 11
S 4 = S 2 = α 22 = α 7
Polynomial S ( x ) is equal to:
S ( x )= α 13 x + α 11 x 2 + α 7 x 4
2. Calculate polynomial Λ( x ) from the Berlekamp-Massey algorithm
Λ 2 p +1 ( x )
Θ 2 p +1 ( x )
p
Δ 2 p +1
δ 2 p +1
L 2 p +1
x 1
-1
0
1
α 13
1+ α 13 x
α 2
0
1
1
α 9
1+ α 13 x + α 11 x 2
α 6 + α 4 x
1
1
2
Note that polynomial Λ( x ) obtained is identical to that determined using
the direct method. The roots of Λ( x ) are 1 3 and 1 8 , and the errors
therefore concern terms x 3 and x 8 . The estimated codeword is c ( x )=0 .
Euclid's algorithm for binary codes
Example 4.20
Let us again take the decoding of the (15,7) BCH code. The received word
is r ( x )= x 8 + x 3 .
j
=
0
j
=
1
x 5
R 1 ( x )=
R 0 ( x )=
S ( x )
α 4 x 3 + α 6 x 2
R 0 ( x )=
S ( x )
R 1 ( x )=
α 8 x
α 3 x + α 5
Q 0 ( x )=
1 ( x )=
R 1 ( x )= α 4 x 3 + α 6 x 2
α 13 x
R 2 ( x )=
α 8 x
U 2 ( x )= α 11 x 2 + α 13 x +1
U 1 ( x )=
Search WWH ::




Custom Search