Cryptography Reference
In-Depth Information
Maximum length code
The columns of the generator matrix of a maximum length code are the binary
representations of the numbers from 1 to
n
. The parameters of this code are
therefore
n
=2
m
1
,k
=
m
and we can show that its minimum distance is
2
k−
1
.
The maximum length code with parameters
n
=2
m
−
−
1
,k
=
m
is the dual code
of the Hamming code with parameters
n
=2
m
1
,k
=2
m
1
,thatis,the
generator matrix of the one is the parity check matrix of the other.
−
−
m
−
Hadamard code
The codewords of a Hadamard code are made up of the rows of a Hadamard
matrix and of its complementary matrix. A Hadamard matrix has
n
rows and
n
columns (
n
even) whose elements are 1s and 0s. Each row differs from the
other rows at
n/
2
positions. The first row of the matrix is made up only of 0,
the other rows having
n/
2
0and
n/
2
1.
For
n
=2
, the Hadamard matrix is of the form:
M
2
=
00
01
From a
M
n
matrix we can generate a
M
2
n
matrix.
M
2
n
=
M
n
M
n
M
n
M
n
where
M
n
is the complementary matrix of
M
n
,thatis,whereeachelement
at 1 (respectively at 0) of
M
n
becomes an element at 0 (respectively at 1) for
M
n
.
Example 4.6
If
n
=4
M
4
and
M
4
have the form:
⎡
⎤
⎡
⎤
0000
0101
0011
0110
1111
1010
1100
1001
⎣
⎦
⎣
⎦
M
4
=
M
4
=
The rows of
M
4
and
M
4
are the codewords of a Hadamard code with parameters
n
=4
,
k
=3
and with minimum distance equal to 2. In this particular case, the
Hadamard code is a parity check code.
More generally, the rows of matrices
M
n
and
M
n
are the codewords of a
Hadamard code with parameters
n
=2
m
,k
=
m
+1
and with minimum distance
d
min
=2
m−
1
.