Cryptography Reference
In-Depth Information
The codewords of a cyclic code are multiples of a normalized polynomial
g
(
x
)
of degree
(
n
−
k
)
called a generator polynomial .
+
g
j
x
j
+
+
x
n−k
g
(
x
)=
g
0
+
g
1
x
+
···
···
where
g
j
takes its values in
F
2
. The generator polynomial of a cyclic code is a
divisor of
x
n
+1
. There exists a polynomial
h
(
x
)
of degree
k
such that equation
(4.15) is satisfied.
g
(
x
)
h
(
x
)=
x
n
+1
(4.15)
The product
d
(
x
)
g
(
x
)
is a polynomial of degree lower than or equal to
n
1
,
so it can represent a codeword. The polynomial
d
(
x
)
having
2
k
realizations,
d
(
x
)
g
(
x
)
enables
2
k
codewords to be generated. Let us denote
d
l
(
x
)
the
l
-th
realization of
d
(
x
)
and
c
l
(
x
)
the polynomial representation of the associated
codeword. We can write:
−
c
l
(
x
)=
d
l
(
x
)
g
(
x
)
(4.16)
We will now show that the codewords satisfying relation (4.16) satisfy the prop-
erties of cyclic codes. To do so, we re-write relation (4.14) in the form:
c
j
(
x
)=(
x
n
+1)
q
(
x
)+
x
j
c
(
x
)
(4.17)
Since
c
(
x
)
represents a codeword, there exists a polynomial
d
(
x
)
of degree at
most
k
1
, such that
c
(
x
)=
d
(
x
)
g
(
x
)
. Using (4.15), we can therefore express
(4.17) in another way:
−
c
j
(
x
)=
g
(
x
)[
h
(
x
)
q
(
x
)+
x
j
d
(
x
)]
(4.18)
The codewords
c
j
(
x
)
are therefore multiples of the generator polynomial, and
they can be generated from the
d
j
(
x
)
by applying relation (4.16).
Generator polynomial of the dual code of
C
(
n, k
)
The dual code of a cyclic block code is also cyclic. Polynomial
h
(
x
)
of degree
k
can be used to build the dual code of
C
(
n, k
)
. The reciprocal polynomial
h
(
x
)
of
h
(
x
)
is defined as follows:
h
(
x
)=
x
k
h
(
x
−
1
)=1+
h
k−
1
x
+
h
k−
2
x
2
+
•
+
h
1
x
k−
1
+
x
k
···
We can write (4.15) differently:
[
x
n−k
g
(
x
−
1
)][
x
k
h
(
x
−
1
)] =
x
n
+1
(4.19)
The polynomial
h
(
x
)
is also a divisor of
x
n
+1
; it is the generator polynomial
of a
C
⊥
=
C
(
n, n
k
)
code that is the dual code of
C
(
n, k
)
.
Note: the code of generator polynomial
h
(
x
)
is equivalent to dual code
C
⊥
.
The vector representation of the codewords generated by
h
(
x
)
corresponds to
the reversed vector representation of the codewords of
C
⊥
.
C
⊥
,
generated by
h
(
x
)
−
↔
Code generated by
h
(
x
)
c
=
c
0
c
n−
1
c
=
c
n−
1
c
0
c
1
···
↔
···
c
1
