720
Modeling Arithmetic, Computation, and Languages
W(Z ) = H(X, Y ) = d. Thus the minimum weight of the code is ≤ d. If the minimum weight is < d, let M be a nonzero code word with W(M ) the minimum
weight. Then (remember that 0 n is a code word) H(M, 0 n ) = W(M ) < d, which
contradicts the fact that d is the minimum distance of the code. Therefore the
minimum distance equals the minimum weight.
example 21
The set 500000, 01111, 10101, 110106 is a group code (you can check closure,
identity, and inverses) in 3Z
5
2 , + 2 4. The minimum distance of the code is 3, so it is
a single-error correcting code (3 = 2 * 1 + 1).
All well and good, but how can we produce subgroups of Z
n
2 to use as code
words, and how can we control the minimum distance of the code? Algebraic
ideas again come to our rescue. Let h be any n × r binary matrix with r < n. If
X [ Z
n
2 , we can perform the matrix multiplication X # h, where all additions are
done modulo 2. The result of this multiplication is a binary r-tuple.
example 22
Let r = 3, n = 5, and
h = E
1 1 0
0 1 1
1 0 1
1 0 0
1 1 0
U
Then
(11101)E
1 1 0
0 1 1
1 0 1
1 0 0
1 1 0
U = (110)
We can think of multiplication by h as a mapping from the group :Z
n
2 , + 2 ; to
the group :Z
r
2 , + 2 ;. Moreover, this mapping is a homomorphism (see Exercise 13 at
the end of this section). We know that the kernel K of this homomorphism is a subgroup of :Z
n
2 , + 2 ; and it consists of all those X in Z
n
2 such that X # h = 0 r , the zero
of the group :Z
r
2 , + 2 ;. We’ll take K as the set of code words. Then we can easily
determine the minimum weight (minimum distance) of the code simply by looking at h. If h has d distinct rows that add to 0 r in :Z
r
2 , + 2 ;, say i 1 , … , i d , we can
choose an X in Z
n
2 having 1s exactly in the i 1 , … , i d , components. Then X # h = 0 r ,
so that X is a code word, and W(X) = d. On the other hand, if X is a code word
with W(X) = d and X has 1’s exactly in components i 1 , … , i d ,, then the equation
X # h = 0 r forces rows i 1 , … , i d , of h to sum to 0 r . Therefore, the minimum
weight of the code equals the minimum number of distinct rows of h that add to 0 r .
In particular, to produce a single-error correcting code, we must have minimum
distance at least 3, so we would have to choose an h with no row consisting of all
0s and no two rows that are alike (these would add to 0 r ).
Modeling Arithmetic, Computation, and Languages
W(Z ) = H(X, Y ) = d. Thus the minimum weight of the code is ≤ d. If the minimum weight is < d, let M be a nonzero code word with W(M ) the minimum
weight. Then (remember that 0 n is a code word) H(M, 0 n ) = W(M ) < d, which
contradicts the fact that d is the minimum distance of the code. Therefore the
minimum distance equals the minimum weight.
example 21
The set 500000, 01111, 10101, 110106 is a group code (you can check closure,
identity, and inverses) in 3Z
5
2 , + 2 4. The minimum distance of the code is 3, so it is
a single-error correcting code (3 = 2 * 1 + 1).
All well and good, but how can we produce subgroups of Z
n
2 to use as code
words, and how can we control the minimum distance of the code? Algebraic
ideas again come to our rescue. Let h be any n × r binary matrix with r < n. If
X [ Z
n
2 , we can perform the matrix multiplication X # h, where all additions are
done modulo 2. The result of this multiplication is a binary r-tuple.
example 22
Let r = 3, n = 5, and
h = E
1 1 0
0 1 1
1 0 1
1 0 0
1 1 0
U
Then
(11101)E
1 1 0
0 1 1
1 0 1
1 0 0
1 1 0
U = (110)
We can think of multiplication by h as a mapping from the group :Z
n
2 , + 2 ; to
the group :Z
r
2 , + 2 ;. Moreover, this mapping is a homomorphism (see Exercise 13 at
the end of this section). We know that the kernel K of this homomorphism is a subgroup of :Z
n
2 , + 2 ; and it consists of all those X in Z
n
2 such that X # h = 0 r , the zero
of the group :Z
r
2 , + 2 ;. We’ll take K as the set of code words. Then we can easily
determine the minimum weight (minimum distance) of the code simply by looking at h. If h has d distinct rows that add to 0 r in :Z
r
2 , + 2 ;, say i 1 , … , i d , we can
choose an X in Z
n
2 having 1s exactly in the i 1 , … , i d , components. Then X # h = 0 r ,
so that X is a code word, and W(X) = d. On the other hand, if X is a code word
with W(X) = d and X has 1’s exactly in components i 1 , … , i d ,, then the equation
X # h = 0 r forces rows i 1 , … , i d , of h to sum to 0 r . Therefore, the minimum
weight of the code equals the minimum number of distinct rows of h that add to 0 r .
In particular, to produce a single-error correcting code, we must have minimum
distance at least 3, so we would have to choose an h with no row consisting of all
0s and no two rows that are alike (these would add to 0 r ).