Cryptography Reference
In-Depth Information
d
min
=
in
C
(
n,k
)
w
H
(
c
)
(4.11)
c
=0
,
c
∈
When the number of codewords is very high, searching for the minimum
distance can be laborious. A first solution to get round this di
culty is to
determine the minimum distance from the parity check matrix.
We have seen that
d
min
is equal to the minimum Hamming weight of the
non-null codewords. Let us consider a codeword of weight
d
min
. The orthog-
onality property
cH
T
=
0
implies that the sum of
d
min
columns of the parity
check matrix is null. Thus
d
min
corresponds to the minimum number of linearly
dependent columns of the parity check matrix.
A second solution to evaluate
d
min
is to use higher bounds of the minimum
distance. A first bound can be expressed as a function of the
k
and
n
parameters
of the code. For a linear block code whose generator matrix is written in the
systematic form
G
=[
I
k
P
]
,the
(
n
−
k
)
columns of the matrix
I
n−k
of the
parity check matrix (
H
=
P
T
I
n−k
)
being linearly independent, any column
of
P
T
can be expressed as at most a combination of these
(
n
−
k
)
columns. The
minimum distance is therefore upper bounded by:
d
min
≤
n
−
k
+1
(4.12)
Another bound of the minimum distance, called the Plotkin bound, can be
obtained by noting that the minimum distance is necessarily lower than the
average weight of the non-null codewords. If we consider the set of codewords,
it is easy to see that there are as many symbols at 0 as symbols at 1. Thus
the sum of the weights of all the codewords is equal to
n
2
k−
1
.Thenumberof
non-null codewords being
2
k
−
1
, the minimum distance can be upper bounded
by:
n
2
k−
1
2
k
d
min
≤
(4.13)
−
1
4.1.4 Extended codes and shortened codes
From a blo ck co de
C
(
n, k
)
with minimum distance
d
min
we can build a linear
code
C
(
n
+1
,k
)
by adding to the end of each codeword a symbol equal to 1
(respectively to 0) if the codeword includes an odd (respectively even) number
of 1s. This code is called an extended code and its minimum distance is equal
to
d
min
+1
if
d
min
is an odd number.
The parity check matrix
H
e
of an extended code is of the form:
⎡
⎤
0
.
0
⎣
⎦
H
H
e
=
1
···
1
1
where
H
is the parity check matrix of code
C
(
n, k
)
.
