Year 10 · Computer Science · Autumn 2

Data transmission and Boolean logic · Lesson 3 of 5

Error checking and ARQ

Unplugged2.2 Methods of error detection

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

You will learn to

  • Explain why errors happen during transmission, for example because of interference.
  • Use odd and even parity, and a parity block, to find a corrupted bit.
  • Calculate an ISBN-13 check digit, and describe a checksum and an echo check.
  • Describe automatic repeat query (ARQ), using acknowledgements and timeouts.

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Success criteria

You have got it when you can say:

  • I can add the right parity bit to a byte, for even and for odd parity.
  • I can find the wrong bit in a parity block, using its row and column.
  • I can work out an ISBN-13 check digit with the weights 1 and 3.
  • I can explain what happens in ARQ when no acknowledgement arrives.

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Retrieval starter

Questions from before. Write your answers, then show them.

  1. Last lesson

    A truth table for 3 inputs has…

    A 3 rowsB 8 rowsC 6 rows

    B. 8 rows

  2. Last unit

    Which of these is lossy?

    A JPEGB ZIPC PNG

    A. JPEG

  3. Earlier this unit

    XOR gives 1 when…

    A Both inputs are 1B Neither input is 1C Exactly one input is 1

    C. Exactly one input is 1

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Key words (1 of 3)

Packet
A small piece of data sent across a network, with a header, payload and trailer.
Packet switching
Sending each packet separately, possibly by different routes, then reordering them at the destination.
Interference
Unwanted outside signals that can corrupt data on the way.

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Key words (2 of 3)

Parity bit
An extra bit that makes the number of 1s in a byte odd or even.
Checksum
A value calculated from a block of data, recalculated by the receiver to check for errors.
Echo check
The receiver sends the data back so the sender can compare it with the original.
Check digit
A digit calculated from the other digits of a number, used to catch typing errors.

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Key words (3 of 3)

ARQ
Automatic repeat query: acknowledgements and timeouts make the sender re-send data that is wrong or lost.

The explanation · step 1 of 7 · part 1 of 2

Why errors happen

Bits travel as electrical pulses, light or radio waves. These can be disturbed on the way.

Interference is unwanted signal from outside, such as from a motor, a microwave oven or lightning.

Because of interference, data can suffer data loss (bits go missing), data gain (extra bits appear) or data change (a 1 becomes a 0, or a 0 becomes a 1).

The explanation · step 1 of 7 · part 2 of 2

Why errors happen (continued)

?Why?

One wrong bit can change a whole number. If 01000001 (65) becomes 01000011 (67), a bank amount or a letter changes. So the receiver must be able to spot errors.

The explanation · step 2 of 7 · part 1 of 3

Parity check: odd and even

A parity check adds one extra bit, the parity bit, to each byte. Usually it is the leftmost bit.

In even parity, the total number of 1s in the byte must be even. In odd parity, the total must be odd.

The sender and receiver agree the type first. The receiver counts the 1s. If the count is wrong, there is an error.

The explanation · step 2 of 7 · part 2 of 3

Parity check: odd and even (continued)

e.g.Example
Data bits (7): 1011001. Count the 1s: 1+0+1+1+0+0+1 = 4. Even parity: 4 is already even, so the parity bit is 0 → 01011001 Odd parity: 4 is even, so the parity bit is 1 to make 5 → 11011001 Try it in the toy: choose Even parity, then press Send with noise (1 bit flips). The count becomes odd and the error is found. Then try Send with 2 bits flipped.

The explanation · step 2 of 7 · part 3 of 3

Parity check: odd and even (continued)

!Watch out

Parity cannot find an error if two bits flip. The count changes by 2, so it stays even (or odd). It also cannot say which bit is wrong.

There is something to try for this step in the IGCSE library.

The explanation · step 3 of 7 · part 1 of 3

Parity byte and parity block

To find which bit is wrong, we send a block of bytes, each with its own parity bit.

Then we add a parity byte at the end. Each bit of the parity byte gives parity for one column.

If one bit flips, one row fails and one column fails. The wrong bit is where they cross, so the receiver can even correct it.

The explanation · step 3 of 7 · part 2 of 3

Parity byte and parity block (continued)

e.g.Example
Even parity. Four bytes, parity bit first: Byte 1: 0 1 0 1 1 0 0 1 Byte 2: 0 1 1 0 0 0 1 1 Byte 3: 1 0 1 1 0 1 0 0 Byte 4: 0 1 0 0 1 1 1 0 Parity byte: 1 1 0 0 0 0 0 0 (each column now has an even number of 1s) Now bit 5 of byte 3 flips from 0 to 1: byte 3 becomes 1 0 1 1 1 1 0 0. Row check: byte 3 has five 1s (odd) → error in row 3. Column check: column 5 has three 1s (odd) → error in column 5. The error is at row 3, column 5. Flip it back.

The explanation · step 3 of 7 · part 3 of 3

Parity byte and parity block (continued)

?Why?

Rows and columns work like grid references on a map. One wrong row plus one wrong column points to a single square.

The explanation · step 4 of 7 · part 1 of 3

Checksum

A checksum is a value calculated from all the data in a block, using an agreed method.

The sender calculates the checksum and sends it with the data.

The receiver calculates the checksum again from the data it received. If the two values match, the data is probably correct. If not, it asks for the data again.

The explanation · step 4 of 7 · part 2 of 3

Checksum (continued)

e.g.Example
One simple method: add the byte values, and keep the remainder after dividing by 256 (so it fits in one byte). Data bytes: 150, 200, 75, 30 Total: 150 + 200 + 75 + 30 = 455 455 ÷ 256 = 1 remainder 199 → checksum = 199 If 75 arrives as 77, the receiver gets 457 → remainder 201. 201 ≠ 199, so there is an error.

The explanation · step 4 of 7 · part 3 of 3

Checksum (continued)

!Watch out

Cambridge does not ask for one exact checksum method. In the exam, describe the process: calculate at the sender, send, recalculate at the receiver, compare.

The explanation · step 5 of 7

Echo check

In an echo check, the receiver sends a copy of the data straight back to the sender.

The sender compares the copy with the original. If they are the same, the data arrived correctly. If not, the sender sends it again.

!Watch out

An echo check doubles the traffic. Also, if the copies differ, you cannot tell if the error happened on the way there or on the way back.

The explanation · 2 more steps

More on the lesson page

The lesson page has the rest of the explanation, step by step:

  • Check digits
  • Automatic repeat query (ARQ)

Open the lesson page

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Quick quiz · 1 of 3

With A = 1 and B = 1, A OR B is…

  1. A 1
  2. B 0
  3. C 2

A. 1

OR is true when at least one input is 1, including both.

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Quick quiz · 2 of 3

X = (A AND B) OR C with A = 0, B = 1, C = 1 gives…

  1. A 0
  2. B Cannot tell
  3. C 1

C. 1

A AND B = 0. Then 0 OR 1 = 1.

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Quick quiz · 3 of 3

A NOT gate has…

  1. A One input
  2. B Three inputs
  3. C Two inputs

A. One input

It flips a single bit.

Year 10 · Computer Science · Data transmission and Boolean logic · Lesson 3 of 5

Exit ticket

Answer on paper before you go. Then check.

  1. A packet's header holds…

    A Only the dataB The whole fileC The sender's and receiver's addresses and the packet number

    C. The sender's and receiver's addresses and the packet number The header is the label. The payload is the data.

  2. Sending one bit at a time down one wire is…

    A ParallelB DuplexC Serial

    C. Serial Parallel sends several bits at once down several wires.