Section 9.2 Coding Theory
721
From now on, we will assume that the matrix h has the form
h = c
b
i r
d
(1)
where i r is the r × r identity matrix and b is an arbitrary (n − r) × r binary
matrix. In computing the product X # h for some X [ Z
n
2 , we multiply elements
of X by corresponding elements of the columns of h, and then sum modulo 2. For
each column of h, the pattern of 1s in the column determines which components
of X contribute to the sum. If the sum is to be 0 (as is true when X # h = 0 r ), then
those selected components of X must sum to 0 and therefore must consist of an
even number of 1s. The i r portion of h has the effect that each column of h selects
a distinct component from among the last r components of X. Each of the last r
components of X therefore controls the even parity check for one of the r multiplications that are done. A matrix h that matches Equation (1) is called a canonical
parity-check matrix.
For X to be a code word, the first n − r components of X can be arbitrary, but
the final r components will then be determined. The maximum number of code
words is therefore the maximum number of ways to select binary (n − r)-tuples,
or 2
n−r
. Let m = n − r. We can code all members of Z
m
2 in Z
n
2 by leaving the first
m components alone and then choosing the last r components so that the even
parity check works for each column of h. Such a code is called an (n, m) code.
The first m components of a code word are the information bits, and the last r
components are the check bits.
example 23
The code words of Example 21were generated using the matrix h where
h = E
1 0 1
1 1 1
1 0 0
0 1 0
0 0 1
U
h has no row of all 0s and no two rows that are alike, but rows 1, 2, and 4 add to
(0,0,0). Again, we see that the minimum distance of this code is 3.
PrACtiCe 39 For each code word X of Example 21, verify that X # h = 0 3 , where h is given in
Example 23.
■
example 24
The matrix h of Example 23 is a canonical parity-check matrix where n = 5, r = 3,
and m = n − r = 2. h can thus generate 2
m
= 2
2
= 4 code words. The four
members of Z
2
2 are 00, 01, 10, and 11. Each can be coded as a member of Z
5
2 by
keeping the first two digits and adding the appropriate check digits. To code 10,
for instance, we have
721
From now on, we will assume that the matrix h has the form
h = c
b
i r
d
(1)
where i r is the r × r identity matrix and b is an arbitrary (n − r) × r binary
matrix. In computing the product X # h for some X [ Z
n
2 , we multiply elements
of X by corresponding elements of the columns of h, and then sum modulo 2. For
each column of h, the pattern of 1s in the column determines which components
of X contribute to the sum. If the sum is to be 0 (as is true when X # h = 0 r ), then
those selected components of X must sum to 0 and therefore must consist of an
even number of 1s. The i r portion of h has the effect that each column of h selects
a distinct component from among the last r components of X. Each of the last r
components of X therefore controls the even parity check for one of the r multiplications that are done. A matrix h that matches Equation (1) is called a canonical
parity-check matrix.
For X to be a code word, the first n − r components of X can be arbitrary, but
the final r components will then be determined. The maximum number of code
words is therefore the maximum number of ways to select binary (n − r)-tuples,
or 2
n−r
. Let m = n − r. We can code all members of Z
m
2 in Z
n
2 by leaving the first
m components alone and then choosing the last r components so that the even
parity check works for each column of h. Such a code is called an (n, m) code.
The first m components of a code word are the information bits, and the last r
components are the check bits.
example 23
The code words of Example 21were generated using the matrix h where
h = E
1 0 1
1 1 1
1 0 0
0 1 0
0 0 1
U
h has no row of all 0s and no two rows that are alike, but rows 1, 2, and 4 add to
(0,0,0). Again, we see that the minimum distance of this code is 3.
PrACtiCe 39 For each code word X of Example 21, verify that X # h = 0 3 , where h is given in
Example 23.
■
example 24
The matrix h of Example 23 is a canonical parity-check matrix where n = 5, r = 3,
and m = n − r = 2. h can thus generate 2
m
= 2
2
= 4 code words. The four
members of Z
2
2 are 00, 01, 10, and 11. Each can be coded as a member of Z
5
2 by
keeping the first two digits and adding the appropriate check digits. To code 10,
for instance, we have