Cryptography Reference
In-Depth Information
3. Search for the roots of the error locator polynomial
By looking through all the elements of field F 16 we find that α 12 and
α 9 are roots of polynomial Λ( x ) . The errors are therefore in position
x 3 ( α 12 = α 3 ) and x 6 ( α 9 = α 6 ) and error polynomial e ( x ) is equal to:
e ( x )= e 3 x 3 + e 6 x 6
4. Calculate error coecients e j (4.45).
α 3 α 6
α 2
= α 7
e 3
=
α 6 α 14
α 2
e 6
=
= α 3
Error polynomial e ( x ) is therefore equal to:
e ( x )= α 7 x 3 + α 3 x 6
and the estimated codeword is c ( x )= r ( x )+ e ( x )=0 . The two transmis-
sion errors are corrected.
Euclid's algorithm
Euclid's algorithm enables us to solve the key equation for decoding, that is, to
determine polynomials Λ( x ) and Γ( x ) .
Initial conditions :
R 1 ( x )= x 2 t ; R 0 ( x )= S ( x ); U 1 ( x )=0; U 0 ( x )=1
Recursion :
calculate Q j ( x ) , R j +1 ( x ) and U j +1 ( x ) from the two following expressions:
R j− 1 ( x )
R j ( x ) = Q j ( x )+ R j +1 ( x )
R j ( x )
U j +1 ( x )= Q j ( x ) U j ( x )+ U j− 1 ( x )
When deg( U j )
t and deg( R j )
t then:
Λ( x )= U j +1 ( x )
Γ( x )= R j +1 ( x )
Example 4.17
Let us again take the RS code used to illustrate the Berlekamp-Massey al-
gorithm. Assuming that the received word is always r ( x )= α 7 x 3 + α 3 x 6 when
the transmitted codeword is c ( x )=0 , the decoding algorithm is the following:
Search WWH ::




Custom Search