Cryptography Reference
In-Depth Information
Figure 4.3 - Schematic diagram of an encoder for a cyclic code.
BCH codes
Bose-Chaudhuri-Hocquenghem codes, called BCH codes, enable cyclic codes to
be built systematically correcting at least
t
errors in a block of
n
symbols, that
is, codes whose minimum distance
d
min
is at least equal to
2
t
+1
.
To build a BCH code, we set
t
or equivalently
d
, called the constructed
distance of the code and we determine its generator polynomial
g
(
x
)
. The code
obtained has a minimum distance
d
min
that is always higher than or equal to
the constructed distance.
Primitive BCH code
The generator polynomial
g
(
x
)
of a primitive BCH code constructed over a
Galois field
F
q
with
q
=2
m
elements, with a constructed distance
d
has
(
d
−
1)
roots of the form:
α
l
,
,α
l
+
d−
2
,where
2
t
+1
is a primitive element
of Galois field
F
q
and
l
an integer. The BCH code is said to be primitive since
the roots of its generator polynomial are powers of
α
, a primitive element of
F
q
.
We will see later that it is possible to build non-primitive BCH codes.
Generally, parameter
l
issetto0or1andweshowthatforaprimitive
BCH code exponent
(
l
+
d
,α
l
+
j
,
···
···
2)
of root
α
j
+
d−
2
must be even. When
l
=0
,the
constructed distance is therefore necessarily even, that is, equal to
2
t
+2
for a
code correcting
t
errors. When
l
=1
, the constructed distance is odd, that is,
equal to
2
t
+1
for a code correcting
t
errors.
−
•
Primitive BCH code with
l
=1
The generator polynomial of a primitive BCH code correcting at least
t
errors (constructed distance
2
t
+1)
therefore has
α,
,α
2
t
as
roots. We show that the generator polynomial
g
(
x
)
of a primitive BCH
code is equal to:
,α
j
,
···
···
g
(
x
)=
S.C.M.
(
m
α
(
x
)
,
···
,m
α
i
(
x
)
,
···
,m
α
2
t
(
x
))
