Cryptography Reference
In-Depth Information
The generator polynomial of a Reed-Solomon code, with a constructed dis-
tance d has ( d
l + d− 2 where α is a primitive element
of Galois field F q . It therefore has the expression:
1) roots α l ,
l + j ,
···
···
,m α l + d− 2 ( x ))
where m α l + j is the minimal polynomial associated with the α l + j element of field
F q .
g ( x )= S.C.M . ( m α l ( x ) ,
···
,m α l + j ( x ) ,
···
Using the results of the appendix on the minimal polynomials with coe-
cients in F q , the minimal polynomial m α l + j has only one root α l + j .
m α j + i ( x )=( x + α j + i )
The generator polynomial of a Reed-Solomon code is therefore of the form:
g ( x )=( x + α j )( x + α j +1 ) ... ( x + α j + i ) ... ( x + α j + d− 2 )
In general, parameter j is set to 0 or 1 like for binary BCH codes. The
generator polynomial of a Reed-Solomon code, of degree ( n
k ) ,has ( d
1)
roots, that is n
k = d
1 . Its constructed distance is therefore equal to:
d = n
k +1
For a block code k C ( n, k ) the minimum distance d min being lower than or equal
to n
k +1 , the minimum distance of a Reed-Solomon code is therefore always
equal to its constructed distance. A code whose minimum distance is equal to
n
k +1 is called a maximum distance code.
The parameters of a Reed-Solomon code correcting t errors in a block of nq -ary
symbols are therefore:
n = q
1;
n
k = d min
1=2 t ;
k = n
2 t
Example 4.11
Let us determine the generator polynomial of a Reed-Solomon code built
from a Galois field with 16 elements having a correction capability of t =2
errors. The minimum distance of this code is therefore d min =5 . Taking for
example l =1 , the generator polynomial of this code is therefore of the form:
g ( x )=( x + α )( x + α 2 )( x + α 3 )( x + α 4 )
Developing the expression above, we obtain:
x 2 + x ( α + α 2 )+ α 3
x 2 + x ( α 3 + α 4 )+ α 7
g ( x )=
Using the binary representations of the elements of field F 16 (Appendix), the
polynomial g ( x ) after development and simplification is equal to:
g ( x )= x 4 + α 3 x 3 + α 6 x 2 + α 3 x + α 10
Search WWH ::




Custom Search