Cryptography Reference
In-Depth Information
The so-called BCH bound leads us into another fact about cyclic codes,
namel, that theycan be specified byroots of a generating polynomial consid-
ered in a suitable extension field of
,we
are merely saying that every code polynomial (the elements of
C
in
R
n,q
), is a
multiple of
g
(
x
) so theyare all equal to 0 at the roots of
g
(
x
). Looking at it
another way, if
β
1
,
β
2
,...,β
r
are elements of a finite extension of
F
q
. When we stipulate that
C
=
g
(
x
)
F
q
, and
m
j
(
x
)
is the minimal polynomial of
β
j
over
F
q
for
j
=1
,
2
,...,r
, then we maydefine
g
(
x
) = lcm(
m
1
(
x
)
,...,m
r
(
x
))
.
such that
β
n
= 1 for all
j
=1
,
2
,...,r
, then
g
(
x
)
(
x
n
If
n
∈
N
−
1). Hence, if
q
is the cyclic code with generator polynomial
g
(
x
), then
f
(
x
)
C
C
if and
onlyif
f
(
β
j
) = 0 for all
j
=1
,
2
,...,r
. An application of the above discussion
is the following.
If
C
=
⊆
F
∈
is the binarycclic code of length
N
=2
r
g
(
x
)
−
1 , where
g
(
x
)
is the minimal polynomial over
F
2
of a primitive element of
F
2
r
, then
C
is
equivalent to Ham(r
,
2).
BCH Defined
: Let
b
∈
F
q
m
, a primitive
n
th root
of unity, where
m
= ord
n
(
q
). Then a
BCH code
over
≥
0 be an integer and
α
F
q
of length
n
and
designed
n
) is a cyclic code defined by the roots
α
b
,α
b
+1
,...,α
b
+
d
−
2
of the generator polynomial. Hence, if
m
(
j
)
(
x
) denotes the minimal polynomial
of
α
j
over
distance
d
(2
≤
d
≤
F
q
, then the generator polynomial
g
(
x
) of a BCH code is given by
g
(
x
) = lcm(
m
(
b
)
(
x
)
,m
(
b
+1)
(
x
)
,...,m
(
b
+
d
−
2)
(
x
))
,
for some nonnegative integer
b
. When
b
= 1, theyare called
narrow-sense BCH
codes
. When
n
=
q
m
−
1, the BCH code is called
primitive
.If
n
=
q
−
1, then
the BCH code is called a
Reed-Solomon code
.
It can be shown that indeed a BCH code of designed distance
d
has minimum
weight at least
d
. The following illustrates this fact.
Example 11.14
We maintain the notation from the above discussion. Let
q
=
2
3
,
n
=7
,
m
=3
,
t
=4
,
b
=0
,
s
=2
, and
d
=4
. Then the cyclic
[7
,
3
,
4]
-code,
described as follows, illustrates a BCH code. We have the following factorization
over
F
2
:
1)(
x
3
+
x
2
+ 1)(
x
3
+
x
+1)
.
If we set
g
(
x
)=
x
4
+
x
3
+
x
2
+1
, and let
α
be a primitive
7
th root of unity,
then the cyclic code,
x
7
−
1=(
x
−
,
may be described as follows. First, we note that
C
=
g
(
x
)
F
2
(
α
)(
see page
487
)
. It can be shown that
α
j
for
j
=1
,
2
,
4
are the roots of
x
3
+
x
+1=0(
see
page 599
)
. Since
g
(1) =
g
(
α
)=
g
(
α
2
)=0
, then the BCH bound tells us that
d
F
2
m
=
F
8
=
≥
4
. Moreover, if we set
m
(0)
(
x
)=(
x
−
1)
,m
(1)
(
x
)=
m
(2)
(
x
)=
x
3
+
x
+1
,
then
g
(
x
) = lcm(
m
(0)
(
x
)
,m
(1)
(
x
)
,m
(2)
(
x
)) = lcm(
x
1
,x
3
+
x
+1)
,
−
Search WWH ::
Custom Search