Computer Science › Section B · Data storage › Topic B.10
Detecting and correcting communication errors
Bits sent down a wire, through the air or into storage sometimes come back flipped. By adding a few carefully chosen extra bits, a system can notice that something went wrong, and with a cleverer design it can even work out which bit to fix.
Bits go wrong
Electrical noise on a cable, interference on a radio link, a scratch on a disc, a failing circuit, or even a particle of natural radiation striking a memory chip can turn a 0 into a 1 or a 1 into a 0. There are two ways to respond. The receiver can detect the error and ask for the data again, which works well on a network. Or it can correct the error itself, which is essential when resending is slow or impossible, as with a distant space probe or a damaged disc. Both approaches rely on redundancy: extra bits that carry no new information but let the data check itself.
Parity bits
The simplest check adds one parity bit to each pattern. Under even parity, the bit is chosen so that the total number of 1s, including the parity bit, is even; under odd parity, the total is made odd. Take the 7-bit ASCII code for W, 1010111. It has five 1s, so even parity adds a 1, and with the parity bit on the left the pattern sent is 11010111, with six 1s. The receiver counts the 1s. An odd count under even parity proves that something changed on the way, and the receiver can reject the pattern.
What parity can and cannot catch
If one bit flips, the count of 1s changes by one, so its evenness changes and the error is caught. The same is true for three, five or any odd number of flips. But two flips cancel out: the count changes by 0 or 2, the evenness is unchanged, and the damaged pattern passes the check. A parity bit also cannot say which bit is wrong, only that one is. Some memory systems store a parity bit with every byte for exactly this kind of warning, while server memory usually goes further and uses a correcting code, often called ECC memory.
Checksums and CRCs
Long blocks of data, such as a disk sector or a network packet, need stronger checks, partly because errors often arrive in bursts that hit several neighbouring bits. One idea is to use several parity bits, each covering a different, interleaved set of positions, so a burst lands in the range of many of them. Checksums, which combine the data's bytes arithmetically, and cyclic redundancy checks (CRCs), which are based on a kind of binary division, extend this idea. CRCs protect Ethernet frames and the contents of ZIP and PNG files. All of these detect errors; the usual remedy is to send the data again.
Hamming distance
To correct errors, we need a way to say how far apart two patterns are. The Hamming distance between two patterns of equal length is the number of positions in which they differ. For example, 1011010 and 0011100 differ in the first, fifth and sixth positions, so their distance is 3. The concept is named after Richard Hamming, who designed error-correcting codes at Bell Labs in the late 1940s. A code is a chosen set of legal patterns, and what matters most is its minimum distance: the smallest distance between any two of its patterns.
Worked example: correcting with a distance-3 code
Four symbols are sent with the code W = 00000, X = 01011, Y = 10101 and Z = 11110. Every pair differs in at least 3 positions, so the minimum distance is 3. Pattern 11011 arrives. 1. It is not a legal pattern, so an error has occurred. 2. Its distance to W is 4. 3. Its distance to X is 1, since only the first bit differs. 4. Its distance to Y is 3. 5. Its distance to Z is 2. 6. X is the only legal pattern within one flip, so the receiver decodes the symbol as X. With only one flip, this is always right.
Distance sets the power of a code
If a code's minimum distance is d, then fewer than d flips can never turn one legal pattern into another, so up to \(d - 1\) errors are always detected. To correct, the damaged pattern must stay strictly closer to its original than to any other, which works for up to
errors, where the brackets mean round down. The distance-3 code detects up to 2 errors or corrects 1; a distance-5 code detects up to 4 or corrects 2. The simplest example is the repetition code, sending 000 for 0 and 111 for 1: its distance is 3, so a majority vote fixes any single flip. The price of more power is more redundant bits.
The Hamming (7,4) code
Hamming found an efficient way to correct one error: 4 data bits travel with 3 parity bits, 7 bits in all. Number the positions 1 to 7. The parity bits sit at the powers of two, positions 1, 2 and 4, and the data bits fill positions 3, 5, 6 and 7. Each parity bit gives even parity over a set of positions: bit 1 covers 1, 3, 5 and 7; bit 2 covers 2, 3, 6 and 7; bit 4 covers 4, 5, 6 and 7. Each position belongs to a different combination of these sets, matching its number in binary: position 6 is 110 in binary, so it is covered by the bits for 4 and 2.
Worked example: finding the flipped bit
Send the data 1011. 1. Place it at positions 3, 5, 6 and 7. 2. Bit 1 checks positions 3, 5 and 7, which hold 1, 0 and 1, so it is 0. 3. Bit 2 checks 3, 6 and 7, which hold 1, 1 and 1, so it is 1. 4. Bit 4 checks 5, 6 and 7, which hold 0, 1 and 1, so it is 0. 5. The codeword is 0110011. Suppose 0110001 arrives. 6. Re-check each set: set 1 has an even number of 1s and passes; set 2 has an odd number and fails; set 4 also fails. 7. Add the numbers of the failing checks: 4 + 2 = 6. 8. Flip position 6 back to get 0110011, and read the data 1011 from positions 3, 5, 6 and 7.
Common mistakes to avoid
A passed parity check does not prove the data is correct; two flips go unnoticed. Under odd parity the same data needs the opposite parity bit from even parity, so sender and receiver must agree. Hamming distance compares patterns position by position; it is not the difference between their values as numbers. A code with minimum distance 3 cannot correct two errors: it may confidently decode the wrong symbol. In the (7,4) code, the parity bits go at positions 1, 2 and 4, not at the end.
Key takeaways
Error control adds redundant bits. A parity bit makes the count of 1s even or odd, catching any odd number of flipped bits but missing an even number. Checksums and CRCs detect errors in long blocks, which are then resent. Hamming distance counts the positions where two patterns differ; a code with minimum distance d detects up to \(d - 1\) errors and corrects up to half of \(d - 1\), rounded down. The Hamming (7,4) code adds 3 parity bits to 4 data bits, and the failing checks add up to the position of a single flipped bit.
Flashcards
Flashcard
Extra bits that let data check itself
Test your understanding
Question 1 of 5
Using even parity with the parity bit on the left, how is the 7-bit pattern 1101001 sent?
Question 2 of 5
Which errors does a single even-parity bit always detect?
Question 3 of 5
What is the Hamming distance between 1100101 and 1010110?
Question 4 of 5
A code has a minimum Hamming distance of 5. What can it do?
Question 5 of 5
In a received Hamming (7,4) codeword, parity checks 1 and 4 fail and check 2 passes. Which position holds the error?
