44
4 Linear Block Codes
form [I k |A] with entries in F q , where I k is the identity matrix of order k. This matrix
is said to be in standard form.
Another way of defining a linear code is by means of parity check matrices.
Definition 4.1.5 Let C be a linear code over F q with parameters [n, k]. A parity
check matrix for C is an (n − k) × n matrix H with entries in F q defined by
C = {c ∈ F
n
q |H c
T
= 0},
where c
T denotes the transpose of vector c.
The rows of H are also linearly independent (they form a basis for the (Euclidean)
dual C
⊥ of C). Evidently, in general, a parity check matrix of a given code is not
unique.
Theorem 4.1.1 Let C be a linear code over F q with parameters [n, k]. If G = [I k |A]
is a generator matrix for C, then H = [−A
T
|I n−k ] is a parity check matrix for C.
Exercise 4.1.1 Show Theorem 4.1.1.
Example 4.1.1 An example of a linear code is the well-known binary Hamming
code with parameters [7, 4] with generator matrix (in standard form)
G =
⎡
⎢
⎢
⎣
1 0 0 0 0 1 1
0 1 0 0 1 0 1
0 0 1 0 1 1 0
0 0 0 1 1 1 1
⎤
⎥
⎥
⎦
and parity check matrix (in standard form)
H =
⎡
⎣
0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 0 1 1 0 1 0.
⎤
⎦ .
As we will see later, the Hamming code has minimum distance three (see Proposition 4.1.2).
Another important parameter of a linear code is the minimum distance. To define
this concept we need first to define Hamming distance.
Definition 4.1.6 The Hamming distance d(v, w) between two vectors v, w in F
n
q is
the number of coordinates in which v and w differ.
Exercise 4.1.2 Show that the Hamming distance is, in fact, a metric (cf. Definition 1.6.1) on F
n
q .
We are now ready to define the minimum distance of a code, which is totally
correlated with the power of error-correction of the code.
4 Linear Block Codes
form [I k |A] with entries in F q , where I k is the identity matrix of order k. This matrix
is said to be in standard form.
Another way of defining a linear code is by means of parity check matrices.
Definition 4.1.5 Let C be a linear code over F q with parameters [n, k]. A parity
check matrix for C is an (n − k) × n matrix H with entries in F q defined by
C = {c ∈ F
n
q |H c
T
= 0},
where c
T denotes the transpose of vector c.
The rows of H are also linearly independent (they form a basis for the (Euclidean)
dual C
⊥ of C). Evidently, in general, a parity check matrix of a given code is not
unique.
Theorem 4.1.1 Let C be a linear code over F q with parameters [n, k]. If G = [I k |A]
is a generator matrix for C, then H = [−A
T
|I n−k ] is a parity check matrix for C.
Exercise 4.1.1 Show Theorem 4.1.1.
Example 4.1.1 An example of a linear code is the well-known binary Hamming
code with parameters [7, 4] with generator matrix (in standard form)
G =
⎡
⎢
⎢
⎣
1 0 0 0 0 1 1
0 1 0 0 1 0 1
0 0 1 0 1 1 0
0 0 0 1 1 1 1
⎤
⎥
⎥
⎦
and parity check matrix (in standard form)
H =
⎡
⎣
0 1 1 1 1 0 0
1 0 1 1 0 1 0
1 0 1 1 0 1 0.
⎤
⎦ .
As we will see later, the Hamming code has minimum distance three (see Proposition 4.1.2).
Another important parameter of a linear code is the minimum distance. To define
this concept we need first to define Hamming distance.
Definition 4.1.6 The Hamming distance d(v, w) between two vectors v, w in F
n
q is
the number of coordinates in which v and w differ.
Exercise 4.1.2 Show that the Hamming distance is, in fact, a metric (cf. Definition 1.6.1) on F
n
q .
We are now ready to define the minimum distance of a code, which is totally
correlated with the power of error-correction of the code.