PS11: Codes

1. Consider the four-codeword code given in Example 4.1 (on page 405). Propose a new code with four codewords, at least two of which are from the original code, that can correct up to one error. Prove concisely that your changed code can correct up to one error. (By “prove concisely”, I mean “don't enumerate all the possible one-bit errors”.)

Each of the following questions presents a Hamming codeword, potentially corrupted by one error. For each one, give the original message, and show what the original codeword would have been, with the corrupted bit underlined.

1. 0111100
2. 1001111
3. 1101000

For this next question, you are given a Hamming codeword that was corrupted by two errors. Propose two different messages that could have generated this bit sequence, and give both uncorrupted codewords, with the corrupted bits underlined.

1. 0100110

The following questions concern the interpretation of the Hamming code (which encodes a four-bit message in a seven-bit codeword) in terms of the definition of a code on page 405 (Definition 4.2). For each question, decide on a formula for the answer. Briefly explain your formula in words, then write down the formula, and finally compute the value of the formula.

For this set of questions, let $L = \{0,1\}^7$; that is, $L$ is the set of all seven-bit sequences, of which the Hamming codewords are a subset.

1. How many distinct messages can be encoded by the Hamming code?
2. How many distinct codewords does the Hamming code have?
3. How many elements of $L$ are not Hamming codewords?
4. How many of these non-codeword sequences can be corrected? (That is, how many differ by only one bit from some codeword?)
5. How many of the non-codeword sequences are uncorrectable? (That is, how many differ from all codewords by at least two bits?)