56 ALGEBRAIC CODING THEORY
First-order Reed–Muller code R(1,m)
■ The first-order Reed–Muller code R(1,m) isabinarycodethatisableto
correct more than one error.
■ Code word length
n = 2
m
(2.51)
■ Minimum Hamming distance
d = 2
m−1
(2.52)
■ Code rate
R =
1 +
m
1
2
m
(2.53)
Figure 2.32: First-order Reed–Muller code R(1,m)
i.e. the binary first-order Reed–Muller code R(1,m) consists of code vectors with weights
0, 2
m−1
and 2
m
. The hard-decision decoding of a Reed–Muller code can be carried out by
a majority logic decoding scheme.
There is a close relationship between the binary first-order Reed–Muller code R(1,m)
and the simplex code S(m) with code word length n = 2
m
− 1 and k = m information
symbols as well as the Hamming code H(m). The m × 2
m
matrix used in the construction
of the generator matrix of the first-order Reed–Muller code R(1,m) corresponds to the
parity-check matrix of the binary Hamming code H(m) with the all-zero column attached.
This parity-check matrix in turn yields the generator matrix of the simplex code S(m).
Therefore, this m × 2
m
matrix generates all code words of the simplex code S(m) with a
zero attached in the first position. The attachment of the all-one row vector to the m × 2
m
matrix is equivalent to adding all inverted code words to the code. In summary, the simplex
code S(m) yields the Reed–Muller code R(1,m) by attaching a zero to all code words in
the first position and adding all inverted vectors to the code (Bossert, 1999).
If we compare this code construction scheme with the relationship between simplex
codes S(m) and Hadamard matrices H
m
, we recognise that the rows of the 2
m+1
× 2
m
matrix
H
m
−H
m
subjected to the mapping 1 → 0 and −1 → 1 yield the code vectors of the first-order
Reed–Muller code R(1,m).
This observation in combination with the orthogonality property
H
m
H
m
= 2
m
I
2
m