Why do errors happen?
Bits travel as electric pulses, light flashes or radio waves. Noise (heat, lightning, a scratch on a disc, weak signal) can turn a 0 into a 1 or a 1 into a 0. A small change can be a big problem: 1 0 1 1 is 11, but 1 1 1 1 is 15.
Two ideas help us:
- Error detection: find out that a mistake happened.
- Error correction: also find which bit is wrong and fix it.
Both need redundancy: extra bits that carry no new data, only checking information.
Parity bit: detecting one error
With even parity we add one bit so that the total number of 1s (data plus parity bit) is even.
- Data 1 0 1 1 has three 1s. Add parity bit 1. Now four 1s.
- Data 1 0 0 1 has two 1s. Add parity bit 0. Still two 1s.
The receiver counts the 1s. Even means "looks fine". Odd means "an error!" (With odd parity the rule is the opposite: total must be odd.)
Limits: one parity bit catches 1, 3, 5 ... flipped bits (an odd number) but misses 2, 4 ... flips, because the count becomes even again. It also cannot tell which bit is wrong, so the message must be sent again.
Row and column parity: finding and fixing
Arrange the data bits in a grid. Add a parity bit to the end of every row and the bottom of every column (and one corner bit). If one bit is wrong, exactly one row and one column become odd. The wrong bit is where they cross, so the receiver flips it back. This is a simple error-correcting code.
- Only a row is odd: the wrong bit is that row's own parity bit.
- Only a column is odd: the wrong bit is that column's parity bit.
- Two bits wrong: detected, but may not be fixed correctly.
For a grid of r rows and c columns of data, the message carries r × c data bits and (r + 1)(c + 1) − r × c check bits.
Hamming code: smarter check bits
Richard Hamming made a code where each check bit looks at a different group of positions. The check bits sit at positions 1, 2, 4, 8 ... and together they point to the exact position of a single wrong bit (the failed checks, added up, give the position number). With m data bits we need r check bits where 2r ≥ m + r + 1. For 4 data bits r = 3, so the famous Hamming (7,4) code has 7 bits in all. It corrects any single flipped bit using far fewer check bits than a big grid.
Transmission time
The speed of a channel is measured in bits per second (bit/s). The time to send a message is
time = number of bits ÷ speed
Check bits are also sent, so they add time. Sending 16 bits (9 data + 7 check) at 8 bit/s takes 2 s; the 9 data bits alone would take 1.125 s. If the receiver finds an error and asks for a re-send, the message goes twice and the time doubles. A detecting code (cheap) plus occasional re-send, or a correcting code (more bits but no re-send), is a trade-off between time and safety.
Remember the units: 1 byte = 8 bits, and 1 kbit/s = 1000 bit/s.
Try it
Try it with 7 friends. Each friend holds up a card with 0 or 1. Count the 1s: you need an even count, so add an eighth friend (parity) who holds up 0 or 1 to make it even. Now let one friend secretly turn the card over. Count again: odd! You found the error. Now arrange 9 friends in a 3 × 3 grid with row and column helpers and find the flipped card by seeing which row and which column are odd. In the 3D above, use the first slider to flip any of the 16 bits and read what the grid says.
Key formulas and definitions
- Even parity: total number of 1s (data + parity bit) is even
- Parity bit = (number of 1s in the data) mod 2
- Transmission time = number of bits ÷ speed (bit/s)
- Hamming: 2^r ≥ m + r + 1 (m data bits, r check bits)
- Grid with r × c data bits sends (r + 1)(c + 1) bits in all
- 1 byte = 8 bits; 1 kbit/s = 1000 bit/s
Worked examples
1. Find the even-parity bit for the data 1 1 0 1 0 0 1.
Count the 1s: 1 + 1 + 0 + 1 + 0 + 0 + 1 = 4 ones. That is already even, so the parity bit is 0. Message: 1 1 0 1 0 0 1 0.
2. A receiver gets 1 0 1 1 0 1 0 1 with even parity (last bit is the parity bit). Is there an error?
Count the 1s: 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5. Five is odd, but even parity needs an even count. So an error is detected (an odd number of bits flipped).
3. Data 1 0 1 1 was sent with parity bit 1 (so 1 0 1 1 1). Two bits flipped and the receiver got 0 1 1 1 1. Does the parity check notice?
The 1s in 0 1 1 1 1 number 4, which is even. The check misses the error, because two bits flipped (the first 1 became 0 and the second 0 became 1). A single parity bit misses an even number of flips. If only the first bit had flipped (0 0 1 1 1), the count would be 3, odd, and the error would be found.
4. How long does it take to send 1 200 bits at 300 bit/s?
time = bits ÷ speed = 1200 ÷ 300 = 4 s.
5. A file of 600 bytes is sent at 2 400 bit/s. How long does it take? How long if a parity bit is added to every byte?
600 bytes = 600 × 8 = 4800 bits. Time = 4800 ÷ 2400 = 2 s. With a parity bit per byte each byte becomes 9 bits: 600 × 9 = 5400 bits. Time = 5400 ÷ 2400 = 2.25 s. The check costs 0.25 s.
6. A 3 × 3 grid of data uses row and column parity (with a corner bit). In the received grid, row 3 and column 1 are odd. Where is the wrong bit, and what do you do?
The wrong bit is where row 3 and column 1 cross: row 3, column 1. Flip that bit back (0 to 1 or 1 to 0). The code has corrected the error, with no re-send.
7. How many check bits does a Hamming code need for 11 data bits?
We need 2^r ≥ m + r + 1 with m = 11. Try r = 3: 8 ≥ 15? No. Try r = 4: 16 ≥ 16? Yes. So r = 4 check bits; the code word is 15 bits long (Hamming (15,11)).
Common mistakes
- Thinking a parity bit can fix an error. It can only detect that a mistake happened (for an odd number of flips). Fixing needs a grid or a Hamming code.
- Forgetting that two flipped bits cancel out in a single parity check, so the error is missed.
- Counting the parity bit itself out. The parity bit is part of the message: count all the 1s, data and parity bit together.
- Forgetting check bits when finding transmission time. Time = (data bits + check bits) ÷ speed. Also mixing bytes and bits: multiply bytes by 8.