2018 September 22,
Carleton College, Joshua R. Davis
There are four problems, marked A-D.
A. Section 3.12 Exercise 1.
B. Section 3.12 Exercise 2.
C. Section 3.12 Exercise 20.
When data are stored in a computer or transmitted between computers, they are expressed as sequences of bits, with each bit being 0 or 1. For example, the 7-bit sequence 1000010 expresses either the number 66 or the letter B, depending on the context. (You do not need to understand how or why.)
Unfortunately, when data are stored or transmitted, there is a chance for errors to creep into them. For example, a small electrical disturbance might cause the fifth bit above to flip from 0 to 1, changing the sequence to 1000110, meaning 70 or F.
The simplest way to detect such errors is to append a parity bit. The parity bit is chosen to be either 0 or 1, so that the entire bit sequence has an even number of 1s. In our running example, the 7-bit sequence 1000010 has an even number of 1s, so we append a 0 to make the 8-bit sequence 10000100, which still has an even number of 1s. Then, if the fifth bit gets flipped during storage or transmission, so the sequence becomes 10001100, then there are no longer evenly many 1s, so we know that an error has occurred.
As far as error detection goes, parity bits are quite primitive. One of their flaws is that they cannot detect whether two errors have happened. For example, if the fourth and fifth bits get flipped, so the sequence becomes 10011100, then there is still an even number of 1s, so we have no reason to believe that any errors have occurred.
To clarify, I am not interested in the case where a single bit flips twice. For example, suppose that I send you 10000100. During transmission, the sequence changes to 10001100 and then back to 10000100. So you receive 10000100, which is the correct bit sequence. We say that no error has occurred.
D. Suppose that I store or send a 7-bit sequence with a parity bit, for a total of 8 bits. Errors can happen in any of these 8 bits, independently of each other. The rate of error in any bit is 0.001. When you retrieve or receive the 8-bit sequence, it has even parity. What is the probability that the sequence is erroneous?