Cryptography Reference
In-Depth Information
code RM
r,m
. For some values of
r
and
m
, the generator matrix of code RM
r,m
is also its parity check matrix. We then say that code RM
r,m
is
self dual
.Code
RM
1
,
3
, for example, is a
self dual
code.
4.1.7 Cyclic codes
Cyclic codes are the largest class of linear block codes. Their relatively easy
implementation, from shift registers and logical operators, has made them at-
tractive and widely-used codes.
Definition and polynomial representation
A
linear
block
code
C
(
n, k
)
is
cyclic
if,
for
any
codeword
c
=
c
0
c
n−
2
, obtained by circu-
lar shift to the right of a symbol of
c
, is also a codeword. This definition
of cyclic codes means that any circular shift to the right of
j
symbols of a
codeword, gives another codeword.
For cyclic codes, we use a polynomial representation of the codewords and of the
datawords. Thus, with codeword
c
we associate the polynomial
c
(
x
)
of degree
n
c
n−
1
,
c
1
=
c
n−
1
c
1
···
c
0
···
−
1
.
+
c
n−
1
x
n−
1
and with dataword
d
the polynomial
d
(
x
)
of degree
k
+
c
j
x
j
+
c
(
x
)=
c
0
+
c
1
x
+
···
···
−
1
.
+
d
j
x
j
+
+
d
k−
1
x
k−
1
d
(
x
)=
d
0
+
d
1
x
+
···
···
where
d
j
and
c
j
take their values in
F
2
.
Multiplying
c
(
x
)
by
x
,
xc
(
x
)=
c
0
x
+
c
1
x
2
+
+
c
j
x
j
+1
+
+
c
n−
1
x
n
···
···
then dividing
xc
(
x
)
by
x
n
+1
, we obtain:
xc
(
x
)=(
x
n
+1)
c
n−
1
+
c
1
(
x
)
where
c
1
(
x
)
is the remainder of the division of
xc
(
x
)
by
x
n
+1
with:
c
j
x
j
+1
+
c
n−
2
x
n−
1
c
1
(
x
)=
c
n−
1
+
c
0
x
+
···
···
We can note that
c
1
(
x
)
corresponds to the codeword
c
1
=(
c
n−
1
c
0
...c
j
...c
n−
2
)
.
Using the same method as above, we obtain:
x
j
c
(
x
)=(
x
n
+1)
q
(
x
)+
c
j
(
x
)
(4.14)
where
c
j
(
x
)
is also a codeword obtained by
j
circular shifts to the right of the
symbols of
c
(
x
)
.
