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).
?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.
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.
e.g.ExampleData 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.
!Watch outParity 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.
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.
e.g.ExampleEven 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.
?Why?Rows and columns work like grid references on a map. One wrong row plus one wrong column points to a single square.
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.
e.g.ExampleOne 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.
!Watch outCambridge does not ask for one exact checksum method. In the exam, describe the process: calculate at the sender, send, recalculate at the receiver, compare.
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 outAn 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.
Check digits
A check digit is an extra digit added to the end of a number, such as an ISBN (book number) or a supermarket barcode.
It is calculated from the other digits. It catches data entry errors: a digit typed wrongly, or two digits swapped (transposed).
This is different from parity and checksums. Those catch errors in transmission; a check digit catches human errors when a number is typed or scanned.
e.g.ExampleISBN-13 for the first 12 digits 978030640615:
Step 1: multiply digits by 1, 3, 1, 3, … in turn
9×1=9, 7×3=21, 8×1=8, 0×3=0, 3×1=3, 0×3=0, 6×1=6, 4×3=12, 0×1=0, 6×3=18, 1×1=1, 5×3=15
Step 2: add them: 9+21+8+0+3+0+6+12+0+18+1+15 = 93
Step 3: 93 MOD 10 = 3
Step 4: 10 − 3 = 7 → check digit is 7. Full ISBN: 9780306406157
Check: weighted total of all 13 digits = 93 + 7 = 100, and 100 MOD 10 = 0, so it is valid.
Try it in the toy: the first 12 digits above are already filled in. Under Check a full ISBN-13, press Make a typo or change one digit yourself, and see the check fail.
?Why?The weights 1 and 3 mean that swapping two neighbouring digits usually changes the total. So swaps are caught as well as wrong digits.
!Watch outIf the remainder in step 3 is 0, the check digit is 0, not 10. That is why the rule is (10 − remainder) MOD 10.
There is something to try for this step in the IGCSE library.
Automatic repeat query (ARQ)
ARQ uses an error check (such as a checksum) plus messages back to the sender.
If the data arrives correctly, the receiver sends a positive acknowledgement. If it finds an error, it sends a negative acknowledgement and the sender sends the data again.
The sender also starts a timeout: a set time to wait. If no acknowledgement arrives before the time runs out, the sender re-sends the data automatically.
e.g.ExamplePacket 7 is sent. The sender starts a 2-second timer.
Case A: packet arrives fine → receiver sends a positive acknowledgement → sender sends packet 8.
Case B: checksum fails → receiver sends a negative acknowledgement → sender re-sends packet 7.
Case C: packet is lost → nothing comes back → after 2 seconds the timeout ends → sender re-sends packet 7.
?Why?The timeout handles the case where the data, or the acknowledgement, is lost completely. Without it, the sender would wait forever.