Cryptography Reference
In-Depth Information
Generator matrix of a cyclic code
From the generator polynomial
g
(
x
)
it is possible to build a generator matrix
G
of code
C
(
n, k
)
. We recall that the
k
rows of the matrix
G
are made up of
k
linearly independent codewords. These
k
codewords can be obtained from a set
of
k
independent polynomials of the form:
•
x
j
g
(
x
)
j
=
k
−
1
,k
−
2
,...,
1
,
0
.
Let
d
(
x
)
be the polynomial representation of any dataword. The
k
codewords
generated by the polynomials
x
j
g
(
x
)
have the expression:
c
j
(
x
)=
x
j
g
(
x
)
d
(
x
)
j
=
k
−
1
,k
−
2
,
···
,
1
,
0
and the
k
rows of the matrix
G
have for their elements the binary coecients
of the monomials of
c
j
(
x
)
.
Example 4.7
Let
C
(7
,
4)
be the generator polynomial code
g
(
x
)=1+
x
2
+
x
3
.Letustake
d
(
x
)=1
for the dataword. The 4 rows of the generator matrix
G
are obtained
from the 4 codewords
c
j
(
x
)
.
c
3
(
x
)=
x
3
+
x
5
+
x
6
c
2
(
x
)=
x
2
+
x
4
+
x
5
c
1
(
x
)=
x
+
x
3
+
x
4
c
0
(
x
)=1+
x
2
+
x
3
A generator matrix of the code
C
(7
,
4)
is equal to:
⎡
⎣
⎤
⎦
0001011
0010110
0101100
1011000
G
=
Cyclic code in systematic form
When the codewords are in systematic form, the data coming from the infor-
mation source are separated from the redundancy symbols. The codeword
c
(
x
)
associated with dataword
d
(
x
)
is then of the form:
c
(
x
)=
x
n−k
d
(
x
)+
v
(
x
)
(4.20)
where
v
(
x
)
is the polynomial of degree at most equal to
n
−
k
−
1
associated
with the redundancy symbols.
