Error checking and correction

Overview

Recall questions on parity bits, majority voting, checksums and check digits, what each detects, and which of them can correct an error rather than only spot one.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Why do transmitted or stored data need error checking?

   Model answer

   Because bits can be corrupted. Electrical interference, noise on a line, a weak signal, a damaged storage medium or a mistyped entry can all change a 0 into a 1 or the reverse. Without a check, the receiving system has no way of knowing that what arrived is not what was sent, so it would act on wrong data.

2. 2

   Describe how a parity bit works.

   Model answer

   An extra bit is added to each group of bits, usually to each byte, before it is sent. Its value is chosen so that the total number of 1s in the group obeys an agreed rule. The receiver counts the 1s in what arrives; if the rule is broken, at least one bit has been corrupted and the data can be rejected or a retransmission requested. Sender and receiver must agree the rule beforehand.

3. 3

   The seven data bits 1010011 are to be sent. State the parity bit under even parity and under odd parity.

   Model answer

   The data contains four 1s. Under even parity the total number of 1s must be even, and four already is, so the parity bit is 0. Under odd parity the total must be odd, so the parity bit is 1, making five 1s in all.

4. 4

   What errors can a parity bit detect, and what can it not do?

   Model answer

   It detects any odd number of corrupted bits — one, three, five — because the count of 1s changes parity. It cannot detect an even number of errors, since two bits flipping restores the original parity, and it is completely blind to two bits swapping values. It also cannot say which bit is wrong, so it can never correct an error, only report that one has occurred.

5. 5

   Describe majority voting.

   Model answer

   Each bit is transmitted more than once, typically three times. The receiver compares the copies of each bit and takes the value that appears most often as the true value. So if the three copies of a bit arrive as 1, 1, 0 the bit is taken to be 1, on the assumption that a single copy was corrupted.

6. 6

   A receiver using three-fold majority voting receives the triples 111, 101 and 000. What data bits does it accept?

   Model answer

   1, 1 and 0. In the first triple all copies agree. In the second, two of the three copies are 1 so the bit is taken as 1 and the corrupted middle copy is corrected. In the third all copies agree on 0.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.