Cryptography Reference
In-Depth Information
3. If
x
n
−
1=
g
(
x
)
p
(
x
), then
h
(
x
)
∈
R
n,q
corresponds to an element of
C
if
and onlyif
0(mod
x
n
1)
,
In other words, a polynomial is in
C
if and onlyif it is a multiple of
the generating polynomial. The polynomial
p
(
x
) is called the
parity-check
polynomial
.
p
(
x
)
h
(
x
)
≡
−
Suppose that the generator polynomial for a cyclic code
C
has degree
t
given
by
+
c
t
x
t
,
then it follows from part 3 above that everyelement of
C
in
R
n,q
is a polynomial
of the form
g
(
x
)=
c
0
+
c
1
+
···
1
,
so
f
(
x
) maybe viewed as a linear combination of the monomials
x
j
for
j
=
0
,
1
,...,n
f
(
x
)
g
(
x
) where deg(
f
(
x
))
≤
n
−
t
−
1. In other words, the codewords are linear combinations of the
polynomials
x
j
g
(
x
) for
j
=0
,
1
,...,n
−
t
−
−
−
−
t
1. Hence, dim(
C
)=
n
t
and a
generator matrix for
C
is
c
0
c
1
c
2
···
c
t
00
···
0
0
c
0
c
1
c
2
···
c
t
0
···
0
00
c
0
c
1
c
2
···
c
t
···
0
G
=
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
000
···
c
0
c
1
c
2
···
c
t
There is also a good reason for the polynomial
p
(
x
) in part 3 of the preceding
page to be called a parity-check polynomial. Let
+
p
n
−
t
x
n
−
t
,
p
(
x
)=
p
0
+
p
1
x
+
···
then the
t
×
n
matrix given as follows is the parity-check matrix for
C
,
p
n
−
t
p
n
−
t
−
1
p
n
−
t
−
2
···
p
0
0
0
···
0
0
p
n
−
t
p
n
−
t
−
1
p
n
−
t
−
2
···
p
0
0
···
0
P
=
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
0
0
···
p
n
−
t
p
n
−
t
−
1
p
n
−
t
−
2
···
p
0
Example 11.13
Let
g
(
x
)=
x
+1
∈
R
3
, with
q
=2
, then
t
=1
,
n
=3
, and
c
0
=
c
1
=
c
t
=1
. Thus,
C
=
{
(000)
,
(110)
,
(011)
,
(101)
}
,
and
C
is a subspace of
F
3
2
of dimension
n
−
t
=2
with basis
{
}
.
(110)
,
(011)
Viewed as a code in
R
3
,
0
,x
2
+
x,x
+1
,x
2
+1
C
=
{
}
,
Search WWH ::
Custom Search