Exercises 8.6 Exercises
1.
Why is the following encoding scheme not acceptable?
Information | |||||||||
Codeword |
2.
Without doing any addition, explain why the following set of
3.
Compute the Hamming distances between the following pairs of
4.
Compute the weights of the following
5.
Suppose that a linear code
6.
In each of the following codes, what is the minimum distance for the code? What is the best situation we might hope for in connection with error detection and error correction?
7.
Compute the null space of each of the following matrices. What type of
8.
Construct a
9.
Let
Decode the message
if possible.
10.
Suppose that a
11.
Which matrices are canonical parity-check matrices? For those matrices that are canonical parity-check matrices, what are the corresponding standard generator matrices? What are the error-detection and error-correction capabilities of the code generated by each of these matrices?
12.
List all possible syndromes for the codes generated by each of the matrices in Exercise 8.6.11.
13.
Let
Compute the syndrome caused by each of the following transmission errors.
An error in the first bit.
An error in the third bit.
An error in the last bit.
Errors in the third and fourth bits.
14.
Let
15.
For each of the following matrices, find the cosets of the corresponding code
16.
Let
17.
A metric on a set
for all exactly when
In other words, a metric is simply a generalization of the notion of distance. Prove that Hamming distance is a metric on
18.
Let
19.
Let
20.
Show that the codewords of even weight in a linear code
21.
If we are to use an error-correcting linear code to transmit the 128 ASCII characters, what size matrix must be used? What size matrix must be used to transmit the extended ASCII character set of 256 characters? What if we require only error detection in both cases?
22.
Find the canonical parity-check matrix that gives the even parity check bit code with three information positions. What is the matrix for seven information positions? What are the corresponding standard generator matrices?
23.
How many check positions are needed for a single error-correcting code with 20 information positions? With 32 information positions?
24.
Let
25.
Let
-
Find the dual code of the linear code
where is given by the matrix Show that
is an -linear code.Find the standard generator and parity-check matrices of
and What happens in general? Prove your conjecture.
26.
Let
-
Show that the matrix
generates a Hamming code. What are the error-correcting properties of a Hamming code?
The column corresponding to the syndrome also marks the bit that was in error; that is, the
th column of the matrix is written as a binary number, and the syndrome immediately tells us which bit is in error. If the received word is compute the syndrome. In which bit did the error occur in this case, and what codeword was originally transmitted?Give a binary matrix
for the Hamming code with six information positions and four check positions. What are the check positions and what are the information positions? Encode the messages and Decode the received words and What are the possible syndromes for this code?What is the number of check bits and the number of information bits in an
-block Hamming code? Give both an upper and a lower bound on the number of information bits in terms of the number of check bits. Hamming codes having the maximum possible number of information bits with check bits are called perfect. Every possible syndrome except occurs as a column. If the number of information bits is less than the maximum, then the code is called shortened. In this case, give an example showing that some syndromes can represent multiple errors.