Cryptography Reference
In-Depth Information
The generator polynomial of this code is equal to:
g
(
x
)=
m
β
(
x
)
m
β
3
(
x
)
which, after development and simplification, gives:
g
(
x
)=
x
9
+
x
8
+
x
7
+
x
5
+
x
4
+
x
+1
The parameters of this non-primitive BCH code are:
n
= 21; (
n
−
k
)=9;
k
=12
•
Golay code
Among non-primitive BCH codes, the most well-known is certainly the
Golay code constructed over a Galois field
F
q
with
m
=11
,q
= 2048
.
Noting that
2
m
89
, the non-primitive element used
to build a Golay code is
β
=
α
89
. The computation of the generator
polynomial of this code constructed on field
F
2048
leads to the following
expression:
−
1 = 2047 = 23
×
g
(
x
)=
x
11
+
x
9
+
x
7
+
x
6
+
x
5
+
x
+1
We can show that the minimum distance
d
min
of a Golay code is 7 and
thus, its correction capability is 3 errors in a block of 23 binary symbols
(
β
23
=
α
2047
=1)
. The parameters of a Golay code are therefore:
n
= 23; (
n
−
k
) = 11;
k
= 12;
t
=3
Note that the reciprocal polynomial of
g
(
x
)
,equalto
g
(
x
)=
x
11
g
(
x
−
1
)
also enables a Golay code to be produced.
g
(
x
=
x
11
+
x
10
+
x
6
+
x
5
+
x
4
+
x
2
+1
4.2
Block codes with non-binary symbols
4.2.1 Reed-Solomon codes
Reed-Solomon or RS codes are the most well-known and the most widely-used
codes having non-binary symbols. For codes with non-binary symbols the coef-
ficients
c
j
of the codewords and
d
j
of the datawords take their value in a Galois
field
F
q
with
q
=2
m
elements. Thus, each symbol of these codes can be en-
coded on
m
binary symbols. Reed-Solomon codes being cyclic codes, they are
generated by a generator polynomial
g
(
x
)
divisor of
x
n
+1
whose coecients
g
j
j
=0
,
1
,
···
,n
−
k
−
1
also take their value in the Galois field
F
q
.