Spring 2015

CS 202: Math of CS

Jadrian Miles

Due Wed 4/29 @ 1:30pm.

- 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.

`0111100``1001111``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.

`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.

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