Cryptography Reference
In-Depth Information
so
C
is an ideal in
R
3
of dimension
n
−
t
=2
since
C
=
g
(
x
)
.
Also, since
g
(
x
)
p
(
x
)=(
x
+ 1)(
x
2
+
x
+1)=
x
3
−
1(mod 2)
,
then
p
(
x
)=
x
2
+
x
+1
is the parity-check polynomial for
C
. Hence, the generator
matrix for
C
is given by
G
=
110
011
,
and the parity-check matrix is given by
P
=
111
.
Since the discussion preceding the example tells us that the only possible
cyclic codes in
R
3
are those corresponding to polynomial divisors of
x
3
1
, then
the only other possible binary cyclic codes of length
3
can be those associated
with the polynomials
g
(
x
)=1
corresponding to all of
−
2
; those corresponding
F
to
g
(
x
)=
x
2
+
x
+1
, namely,
C
=
{
(000)
,
(111)
}
; and the trivial one for
{
0
g
(
x
)=
x
3
−
1
corresponding to the singleton code
C
=
{
(000)
}
=
}
. Since
there are no other divisors of
x
3
−
1
, this constitutes all possible binary cyclic
codes of length
3
.
Although the parity-check matrix allows for
detection
of errors, correcting
them for general cyclic codes can be quite arduous. The next set of cyclic codes
provide us with more robust decoding, and error-detection features.
BCH Codes
In 1959, a class of codes was discovered byHocquenghem [124], as well as
independentlyin 1960 byBose and Ra-Chaudhuri [39] and [40]. The codes
were initiallynamed after the latter two authors, but later it was discovered
that Hocquenghem had anticipated them, so the codes were renamed and are
now accepted as BCH codes.
For a description of the following, the reader must be familiar with primitive
roots and the notions surrounding them (see Appendix A, especiallypages 480
and 490). First, we need the following.
F
q
where
q
=
p
m
BCH Bound
: Suppose that
C
is a cyclic [
n,k,d
]-code over
for some prime
p
and
m
and
α
is a
primitive
n
th root of unityfor which there exist integers
r,s
such that
∈
N
with gcd(
p,n
)=1. If
C
=
g
(
x
)
g
(
α
r
)=
g
(
α
r
+1
)=
=
g
(
α
r
+
s
)=0
,
···
then
d
≥
s
+2
.
Search WWH ::
Custom Search