722
Modeling Arithmetic, Computation, and Languages
(10C 1 C 2 C 3 )E
1 0 1
1 1 1
1 0 0
0 1 0
0 0 1
U = (000)
Multiplication by the first column of h gives 1 # 1 + 1 # C 1 ; therefore C 1 must
equal 1 to give the sum value of 0. Similarly C 2 = 0 and C 3 = 1. We encode 10 as
10101.
PrACtiCe 40 Use the encoding procedure of Example 24 to code 00, 01, and 11 in Z
5
2 . Compare the
results with Example 21.
■
For a given n × r canonical parity-check matrix h, we know how to encode
all of Z
m
2 = Z
n−r
2
as a subgroup of Z
n
2 , and we also know how to determine from h
the minimum distance of the resulting code. Now let’s turn the problem around.
Suppose we want to encode Z
m
2 for some m as, say, a single-error correcting code.
How big will the code words have to be (what is n) or, equivalently, how many
check bits must be added (what is r)? Once we know the dimensions of a paritycheck matrix h, how can we find a canonical h that generates the code? We know
that to produce a single-error correcting code, h must have no row consisting
of all 0s and no two rows that are alike. That means that in the canonical form
h = c
b
i r
d , b cannot contain the row of all 0s nor can it contain any row with a
single 1 because this would match one of the rows in i r . The rows are r-tuples,
so from the 2
r
possible r-tuples, we have to subtract those that cannot occur in b.
b can have at most 2
r
−1−r rows so m, the number of rows in b, must be ≤ 2
r
−1−r.
If m and r are such that
m = 2
r
−1−r
the resulting code is called a perfect code.
example 25
A (7, 4) code is a perfect code. Here n = 7, m = 4, r = n − m = 3, and
4 = 2
3
− 1 − 3. The matrix h will be a 7 × 3 matrix of the form
c
b
i 3
d
where the m = 4 rows of b are all of the 3-tuples with at least two 1s.
PrACtiCe 41
a. Write an h matrix for the (7, 4) perfect code.
b. A (7, 4) code can encode all of Z
4
2 in Z
7
2 . Using your h from part (a), write the set of binary
4-tuples that h encodes and write the code word for each one.
■
Modeling Arithmetic, Computation, and Languages
(10C 1 C 2 C 3 )E
1 0 1
1 1 1
1 0 0
0 1 0
0 0 1
U = (000)
Multiplication by the first column of h gives 1 # 1 + 1 # C 1 ; therefore C 1 must
equal 1 to give the sum value of 0. Similarly C 2 = 0 and C 3 = 1. We encode 10 as
10101.
PrACtiCe 40 Use the encoding procedure of Example 24 to code 00, 01, and 11 in Z
5
2 . Compare the
results with Example 21.
■
For a given n × r canonical parity-check matrix h, we know how to encode
all of Z
m
2 = Z
n−r
2
as a subgroup of Z
n
2 , and we also know how to determine from h
the minimum distance of the resulting code. Now let’s turn the problem around.
Suppose we want to encode Z
m
2 for some m as, say, a single-error correcting code.
How big will the code words have to be (what is n) or, equivalently, how many
check bits must be added (what is r)? Once we know the dimensions of a paritycheck matrix h, how can we find a canonical h that generates the code? We know
that to produce a single-error correcting code, h must have no row consisting
of all 0s and no two rows that are alike. That means that in the canonical form
h = c
b
i r
d , b cannot contain the row of all 0s nor can it contain any row with a
single 1 because this would match one of the rows in i r . The rows are r-tuples,
so from the 2
r
possible r-tuples, we have to subtract those that cannot occur in b.
b can have at most 2
r
−1−r rows so m, the number of rows in b, must be ≤ 2
r
−1−r.
If m and r are such that
m = 2
r
−1−r
the resulting code is called a perfect code.
example 25
A (7, 4) code is a perfect code. Here n = 7, m = 4, r = n − m = 3, and
4 = 2
3
− 1 − 3. The matrix h will be a 7 × 3 matrix of the form
c
b
i 3
d
where the m = 4 rows of b are all of the 3-tuples with at least two 1s.
PrACtiCe 41
a. Write an h matrix for the (7, 4) perfect code.
b. A (7, 4) code can encode all of Z
4
2 in Z
7
2 . Using your h from part (a), write the set of binary
4-tuples that h encodes and write the code word for each one.
■