4.1 Introduction
45
Definition 4.1.7 The minimum distance of a code C (not necessarily linear) is the
smallest Hamming distance between distinct codewords of C.
Definition 4.1.8 Let v ∈ F
n
q . The Hamming weight wt(v) of v is defined as the
number of nonzero coordinates in v.
It is easy to see that, for all vectors v, w ∈ F
n
q , it follows that
d(v, w) = wt(v − w).
Since in the linear case, ∀ v, w ∈ C implies v − w ∈ C, we have the following
result.
Proposition 4.1.1 Let C be a linear code over F q . Then the minimum distance of C
is equal to the minimum weight of all nonzero codewords of C.
Thus, if the code is linear, its minimum distance is also called the minimum weight
of the code.
We have now the complete set of parameters of a linear code, i.e., length, dimension and minimum distance: a linear code C over F q , of length n, dimension k and
minimum distance d is denoted by [n, k, d] q .
There exists a well-known way to find the minimum distance of a linear code.
Proposition 4.1.2 Let C be a linear code over F q with parity check matrix H . Then
C has minimum weight d if and only if H has a set of d linearly dependent columns
but no set of d − 1 linearly dependent columns.
The minimum distance of a code is totally correlated with the error-correcting
capacity of the code.
Theorem 4.1.2 A code C having minimum distance d can correct
(d−1)
2
errors.
If d is even, the code can simultaneously correct
(d−2)
2
errors and detect d/2 errors.
By applying Proposition 4.1.2 in the parity check matrix
H =
⎡
⎣
0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 0 1 1 0 1 0
⎤
⎦
of the binary [7, 4] Hamming code of Example 4.1.1, we see that the code has
minimum distance 3, i.e., the Hamming code is a single-error-correcting code due
to Theorem 4.1.2.
Exercise 4.1.3 Show Theorem 4.1.2.
45
Definition 4.1.7 The minimum distance of a code C (not necessarily linear) is the
smallest Hamming distance between distinct codewords of C.
Definition 4.1.8 Let v ∈ F
n
q . The Hamming weight wt(v) of v is defined as the
number of nonzero coordinates in v.
It is easy to see that, for all vectors v, w ∈ F
n
q , it follows that
d(v, w) = wt(v − w).
Since in the linear case, ∀ v, w ∈ C implies v − w ∈ C, we have the following
result.
Proposition 4.1.1 Let C be a linear code over F q . Then the minimum distance of C
is equal to the minimum weight of all nonzero codewords of C.
Thus, if the code is linear, its minimum distance is also called the minimum weight
of the code.
We have now the complete set of parameters of a linear code, i.e., length, dimension and minimum distance: a linear code C over F q , of length n, dimension k and
minimum distance d is denoted by [n, k, d] q .
There exists a well-known way to find the minimum distance of a linear code.
Proposition 4.1.2 Let C be a linear code over F q with parity check matrix H . Then
C has minimum weight d if and only if H has a set of d linearly dependent columns
but no set of d − 1 linearly dependent columns.
The minimum distance of a code is totally correlated with the error-correcting
capacity of the code.
Theorem 4.1.2 A code C having minimum distance d can correct
(d−1)
2
errors.
If d is even, the code can simultaneously correct
(d−2)
2
errors and detect d/2 errors.
By applying Proposition 4.1.2 in the parity check matrix
H =
⎡
⎣
0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 0 1 1 0 1 0
⎤
⎦
of the binary [7, 4] Hamming code of Example 4.1.1, we see that the code has
minimum distance 3, i.e., the Hamming code is a single-error-correcting code due
to Theorem 4.1.2.
Exercise 4.1.3 Show Theorem 4.1.2.