2017 September 22,
Carleton College, Prof. Joshua R. Davis
Complete these problems. Write them up carefully, in the order assigned, for handing in with the rest of your homework.
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.
Suppose that we're storing 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. What is the probability that an 8-bit sequence is erroneous, but the error or errors are not detected by the parity bit?