Cryptography Reference
In-Depth Information
Reed-Muller codes
A Reed-Muller code (RM) of order
r
and with parameter
m
, denoted RM
r,m
,
has codewords of length
n
=2
m
and the datawords are made up of
k
symbols
with:
k
=1+
m
1
+
+
m
r
,
N
q
=
N
!
q
!(
N
···
with
−
q
)!
where
r<m
. The minimum distance of an RM code is
d
min
=2
m−r
.
The generator matrix of an RM code of order
r
is built from the generator matrix
of an RM code of order
r
1
and if
G
(
r,m
)
represents the generator matrix of
the Reed-Muller code of order
r
and with parameter
m
, it can be obtained from
G
(
r−
1
,m
)
by the relation:
−
G
(
r,m
)
=
G
(
r−
1
,m
)
Q
r
where
Q
r
is a matrix with dimensions
m
r
×
n
.
By construction,
G
(0
,m
)
is a row vector of length
n
whose elements are equal
to 1. The matrix
G
(1
,m
)
is obtained by writing on each column the binary
representation of the index of the columns (from 0 to
n
−
1
). For example, for
m
=4
,thematrix
G
(1
,m
)
is given by:
⎡
⎤
0000000011111111
0000111100001111
0011001100110011
0101010101010101
⎣
⎦
G
(1
,
4)
=
.
Matrix
Q
r
is obtained simply by considering all the combinations of
r
rows of
G
(1
,m
)
and by obtaining the product of these vectors, component by component.
The result of this multiplication constitutes a row of
Q
r
. For example, for
the combination having the rows of
G
(1
,m
)
with indices
i
1
,
i
2
, ...,
i
r
,the
j
-
th coecient of the row thus obtained is equal to
G
(1
,m
)
i
1
,j
G
(1
,m
)
i
2
,j
G
(1
,m
)
i
r
,j
,the
multiplication being carried out in the field
F
2
. For example, for
r
=2
,we
obtain:
···
⎡
⎤
0000000000001111
0000000000110011
0000000001010101
0000001100000011
0000010100000101
0001000100010001
⎣
⎦
Q
2
=
We can show that the code RM
m−r−
1
,m
is the dual code of the code RM
r,m
,
that is, the generator matrix of code RM
m−r−
1
,m
is the parity check matrix of
