728
Modeling Arithmetic, Computation, and Languages
9. Consider the canonical parity-check matrix
h = F
1 1 1
0 1 1
1 0 1
1 0 0
0 1 0
0 0 1
V
a. Prove that the code generated by h is singleerror correcting.
b. Write the set of binary m-tuples h encodes
and write the code word for each one.
10. Consider the canonical parity-check matrix
h = I
1 1 0 1
0 1 1 1
0 1 0 1
1 0 0 1
1 1 0 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
Y
a. Prove that the code generated by h is singleerror correcting.
b. Write the set of binary m-tuples h encodes
and write the code word for each one.
11. Give an example of a canonical parity-check matrix that will generate a single-error correcting code for
the set of words in Z
6
2 .
12. Give a canonical parity-check matrix for a single-error correcting (15, 11) code.
13. Let h be an n × r binary matrix mapping :Z
n
2 , + 2 ; to :Z
r
2 , + 2 ; by the operation X # h for X in Z
n
2 . Prove
that this function is a homomorphism by showing that for X, Y in Z
n
2 , (X + 2 Y ) # h = X # h + 2 Y # h.
14. Which of the following are perfect codes? Which are single-error correcting?
a. (5, 3)
b. (12, 7)
c. (15, 11)
15. Complete the coset leader/syndrome table of Example 28.
16. Use your table from Exercise 15 and the matrix h from Example 28 to decode the following received
words.
a. 1010011
b. 0001110
c. 0101101
For Exercises 17 and 18, use a canonical parity-check matrix for the (15, 11) perfect code (see Exercise 12) to
decode the given received words. (Hint: Because this is a perfect code, you do not need to generate the entire
coset leader/syndrome table to solve these problems.)
17. 011000010111001
18. 110111001010011
S e c t i o n 9 . 3 Finite-StAte MAChineS
The algebraic structures of Section 9.1 served as models for various simple arithmetic
systems. However, we would surely agree that computation should go beyond mere
arithmetic. We would like a model that captures the general nature of computation.
Perhaps looking at a simplified version of a modern digital computer would be a start.
A computer stores information internally in binary form. At any instant, the
computer contains certain information, so its internal storage is set in certain patterns
of binary digits, which we’ll call the state of the computer at that instant. Because a
computer contains a finite amount of storage, there is a finite (although large) number of different states that the computer can assume. An internal clock synchronizes
Modeling Arithmetic, Computation, and Languages
9. Consider the canonical parity-check matrix
h = F
1 1 1
0 1 1
1 0 1
1 0 0
0 1 0
0 0 1
V
a. Prove that the code generated by h is singleerror correcting.
b. Write the set of binary m-tuples h encodes
and write the code word for each one.
10. Consider the canonical parity-check matrix
h = I
1 1 0 1
0 1 1 1
0 1 0 1
1 0 0 1
1 1 0 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
Y
a. Prove that the code generated by h is singleerror correcting.
b. Write the set of binary m-tuples h encodes
and write the code word for each one.
11. Give an example of a canonical parity-check matrix that will generate a single-error correcting code for
the set of words in Z
6
2 .
12. Give a canonical parity-check matrix for a single-error correcting (15, 11) code.
13. Let h be an n × r binary matrix mapping :Z
n
2 , + 2 ; to :Z
r
2 , + 2 ; by the operation X # h for X in Z
n
2 . Prove
that this function is a homomorphism by showing that for X, Y in Z
n
2 , (X + 2 Y ) # h = X # h + 2 Y # h.
14. Which of the following are perfect codes? Which are single-error correcting?
a. (5, 3)
b. (12, 7)
c. (15, 11)
15. Complete the coset leader/syndrome table of Example 28.
16. Use your table from Exercise 15 and the matrix h from Example 28 to decode the following received
words.
a. 1010011
b. 0001110
c. 0101101
For Exercises 17 and 18, use a canonical parity-check matrix for the (15, 11) perfect code (see Exercise 12) to
decode the given received words. (Hint: Because this is a perfect code, you do not need to generate the entire
coset leader/syndrome table to solve these problems.)
17. 011000010111001
18. 110111001010011
S e c t i o n 9 . 3 Finite-StAte MAChineS
The algebraic structures of Section 9.1 served as models for various simple arithmetic
systems. However, we would surely agree that computation should go beyond mere
arithmetic. We would like a model that captures the general nature of computation.
Perhaps looking at a simplified version of a modern digital computer would be a start.
A computer stores information internally in binary form. At any instant, the
computer contains certain information, so its internal storage is set in certain patterns
of binary digits, which we’ll call the state of the computer at that instant. Because a
computer contains a finite amount of storage, there is a finite (although large) number of different states that the computer can assume. An internal clock synchronizes