Error Detection — Parity & Checksum

Syllabus & Goals 3 min

Cambridge 2.2 · Methods of error detection Paper 1 · Computer Systems

By the end of this lesson you can:

1. Explain why errors happen during transmission and why they must be detected.
2. Set and check parity bits (odd and even), and use a parity block to locate and correct an error.
3. Describe how a checksum and an echo check detect errors.

Textbook: Chapter 2, §2.2.1–2.2.2 (pp. 54–59) — the need for error checking; parity, checksum and echo checks.

Recap / Warm-Up 5 min

Lesson 2 showed that long parallel cables can deliver skewed bits. Lesson 1 showed that packets can go missing. Today: how does the receiver know something went wrong?

Quick starter

Count the 1-bits: 10110110. Is the count odd or even?

Key Concept 14 min

1 · Why errors happen

When data is transmitted, it can be corrupted, lost or even gained. There are three main causes:

A person can often read a sentence with jumbled letters, like "Tihs is esay to raed". A computer cannot. If a word is not in its dictionary, or a byte is wrong, the data is useless. So every receiver must check data after transmission. Three methods do this: parity checks, checksum and echo check.

2 · Parity checks

A parity check is based on the number of 1-bits in a byte. Sender and receiver first agree the protocol: even parity (an even number of 1s) or odd parity (an odd number of 1s). One bit — usually the most significant (left-most) bit — is reserved as the parity bit. It is set to make the count of 1s fit the protocol.

The receiver recounts the 1s in every byte. If even parity was agreed but a byte has an odd number of 1s, the parity has changed, so a transmission error is flagged.

3 · The weakness of a single parity bit

If two bits change, the count can stay even (or stay odd). Then no error is flagged, even though the byte is wrong. And even when one error is flagged, the receiver cannot tell which bit is wrong.

4 · Parity blocks — find the bit, not just the byte

A block of bytes is sent. Parity is checked horizontally (each byte) and vertically (each bit column). The vertical parity bits form an extra parity byte, sent at the end; it also marks the end of the block. A wrong row and a wrong column cross at the exact bit that changed.

5 · Checksum

A checksum is an extra value sent at the end of a block of data:

6 · Echo check

Worked Example 12 min

(a) Set and check parity bits

1. Count the 1s in the 7 data bits. the parity bit only depends on this count.
2. Even parity: if the count is already even, the bit is 0; if odd, it is 1.
3. Odd parity is the opposite choice. the two protocols always give opposite parity bits.
4. Checking a received byte under even parity: 10110110 has five 1s — odd, so an error is flagged. 01100110 has four 1s — accepted.

(b) Locate and correct an error in a parity block

Use the block drawn in the Key Concept (even parity agreed).

1. Count the 1s in each byte (row). Bytes 1, 2, 3 and 6 have four; byte 5 has six. Byte 4 00001011 has 3 — odd ✗.this tells us which byte is wrong.
2. Count the 1s in each column, including the parity byte. Every column totals 4, except bit 6, which totals 3 — odd ✗.this tells us which position is wrong.
3. The error is where row 4 meets column 6. That bit arrived as 0.only one bit sits in both the bad row and the bad column.
4. Flip it: byte 4 should be 00001111. Now row 4 has four 1s and column 6 has four 1s — both even ✓.always re-check both the row and the column after correcting.

(c) Calculate and verify a checksum

Agreed algorithm (example): add the byte values; the checksum is the remainder after dividing the total by 256. A block holds the bytes 150, 64, 200, 33 and 95.

1. Sender adds the bytes: 150 + 64 + 200 + 33 + 95 = 542.
2. 542 ÷ 256 = 2 remainder 30 (2 × 256 = 512; 542 − 512 = 30). Checksum = 30, sent after the block.the remainder keeps the checksum small enough to fit in one byte.
3. Receiver gets 150, 66, 200, 33, 95 (the second byte was corrupted). Total = 544; 544 − 512 = 32.
4. 32 does not match 30, so an error is detected and the receiver asks for the block to be re-sent.the receiver cannot tell which byte is wrong — only that the block is.

The parity check as an algorithm

// Even parity bit for 7 data bits
DECLARE Bits : ARRAY[1:7] OF INTEGER
DECLARE Index : INTEGER
DECLARE Ones : INTEGER
DECLARE ParityBit : INTEGER
Bits[1] ← 1
Bits[2] ← 0
Bits[3] ← 1
Bits[4] ← 1
Bits[5] ← 0
Bits[6] ← 0
Bits[7] ← 1
Ones ← 0
FOR Index ← 1 TO 7
  IF Bits[Index] = 1
    THEN
      Ones ← Ones + 1
  ENDIF
NEXT Index
IF Ones MOD 2 = 0
  THEN
    ParityBit ← 0
  ELSE
    ParityBit ← 1
ENDIF
OUTPUT "Even parity bit is ", ParityBit

# Even parity bit for 7 data bits
bits = [1, 0, 1, 1, 0, 0, 1]
ones = 0
for bit in bits:
    if bit == 1:
        ones = ones + 1
if ones % 2 == 0:
    parity_bit = 0
else:
    parity_bit = 1
print("Even parity bit is", parity_bit)

Even parity bit is 0

Try It Yourself 12 min

📝 Exam Practice 10 min

Recap & Key Terms 3 min

Interference, packet problems and skew corrupt data. A parity bit makes each byte odd or even; a parity block finds the exact bit. A checksum is recalculated by the receiver. An echo check returns the data to the sender for comparison.

Parity check

A method to check data was transferred correctly, using even parity (an even number of 1-bits) or odd parity (an odd number of 1-bits).

Parity bit

A bit (0 or 1) added to a byte, usually in the most significant position, so the byte matches the agreed parity.

Parity block

A horizontal and vertical parity check on a block of data being transmitted.

Parity byte

An extra byte sent at the end of a parity block, made of the parity bits from the vertical check.

Checksum

A value calculated from a block of data and sent after it; the receiver recalculates it to check the data was not altered.

Echo check

Data is sent to a receiver and immediately sent back; the sender checks the returned data matches what was sent.

Homework 1 min

Task (≤ 15 min): Rory sends files to a server 100 m away. Identify two methods of error checking the system could use, and describe how each works. [6]