Learn
2.2 | PARITY, CHECKSUM, CHECK DIGIT AND ARQ
01 | WHY CHECK RECEIVED DATA?
A sender transmits 01000001, but the receiver reads 01000000. Only one bit changed, yet the value is different.
Interference can cause data to be changed, gained or lost during transmission. Noise, a damaged connection or a disrupted signal can make the received data differ from the original.
Error detection looks for evidence of an error. It is different from correcting the data, encrypting it or checking whether the original information was sensible. A check can miss some error patterns.
02 | PARITY: COUNT THE ONES
A parity bit is added so that the total number of 1s in the data and parity bit follows an agreed rule.
- Even parity: the total number of 1s must be even.
- Odd parity: the total number of 1s must be odd.
| Data bits | Number of 1s | Even parity bit | Odd parity bit |
|---|---|---|---|
| 1011001 | 4 | 0 | 1 |
| 1011000 | 3 | 1 | 0 |
| 0000000 | 0 | 0 | 1 |
Zero is an even count. Parity concerns the number of 1s, not whether the binary value is an odd or even number.
Both sides must agree the rule and the parity-bit position. In these examples the parity bit is placed after the data.
03 | WHAT PARITY CAN AND CANNOT DETECT
Send 1011001 with even parity bit 0. The complete unit contains four 1s. If one bit flips, the count becomes odd and the check fails.
If two bits flip, the count may stay even. For example, changing the first two data bits gives 0111001 with parity bit 0. The data changed but still contains four 1s, so the error is missed.
Simple parity detects an odd number of bit flips in the checked unit, including a flipped parity bit. It does not reliably detect an even number of flips, identify the incorrect bit or repair it.
04 | PARITY BYTES AND BLOCK CHECKS
A block can be arranged into rows of data bits. A parity byte supplies parity bits for the columns. A two-dimensional parity block check adds row parity as well as column parity.
| Row | Column 1 | Column 2 | Column 3 | Column 4 | Row parity |
|---|---|---|---|---|---|
| Data row 1 | 1 | 0 | 1 | 1 | 1 |
| Data row 2 | 0 | 1 | 0 | 1 | 0 |
| Data row 3 | 1 | 1 | 0 | 0 | 0 |
| Column parity row | 0 | 0 | 1 | 0 | 1 |
Every row and column has an even number of 1s. The bottom row here is a short teaching example; with eight data columns, the column parity bits form a parity byte.
If the bit at data row 2, column 3 changes from 0 to 1, both that row and that column fail. Their intersection locates a single-bit error, assuming only one bit changed.
Multiple errors can be ambiguous. Four flips at the corners of a rectangle can preserve every row and column parity. Do not claim that block parity always finds or corrects all errors.
05 | TRY IT: SET THE PARITY BIT
Change one bit and calculate again. Then change two bits. Explain why the required parity bit may return to its original value.
06 | CHECKSUM: CALCULATE, SEND, COMPARE
A checksum is a value calculated from a block of data. The sender calculates it using an agreed algorithm and sends it with the data. The receiver calculates a checksum from the received data using the same algorithm and compares the values.
A mismatch indicates an error. A match means no error was detected by that check, not that errors are impossible.
| Step | Illustrative calculation |
|---|---|
| Algorithm | Add the byte values and keep the remainder after division by 256 |
| Original bytes | 10, 20, 30 |
| Sender checksum | (10 + 20 + 30) mod 256 = 60 |
| Received bytes with a change | 10, 21, 30 |
| Receiver checksum | 61; different from 60, so the check fails |
If 10, 20, 30 becomes 11, 19, 30, the sum is still 60. This error is missed by the example algorithm. Swapping byte order also leaves this particular sum unchanged.
Real checksum algorithms vary. Follow the method given in the question rather than assuming every checksum is a simple sum.
07 | ECHO CHECK: SEND IT BACK
In an echo check, the receiver sends the received data back to the sender. The sender compares the returned data with the original.
For example, the sender transmits 10110. If the receiver echoes 10010, the sender finds a mismatch and can arrange another transmission.
Echoing adds return traffic and time because the data is transmitted again. A return-path error can also affect the comparison. A matching echo is not an absolute guarantee against every possible error pattern.
08 | CHECK DIGITS: CHECK DATA ENTRY
A check digit is calculated from the other digits of a code and included in that code. It helps detect mistakes when the code is typed or scanned, such as a changed digit or some transpositions.
ISBNs and many product barcodes include check digits. A check digit does not establish that the book, product or entered information is the right one. It checks consistency under an algorithm.
For a simple classroom rule, choose the final digit so that the sum of all digits is a multiple of ten. For data digits 4, 2, 7, 1, the sum is 14, so the check digit is 6. The complete code is 42716.
If someone enters 42726, the total is 21, so the check fails. Swapping two digits leaves this simple sum unchanged, so that error is missed. This classroom rule is not the ISBN algorithm.
09 | WORKED ISBN-13 EXAMPLE
ISBN-13 uses alternating weights of 1 and 3 for the first twelve digits. Choose the check digit so that the weighted total including the final digit is divisible by ten.
| First twelve digits | Weights | Weighted products |
|---|---|---|
| 9 7 8 0 3 0 6 4 0 6 1 5 | 1 3 1 3 1 3 1 3 1 3 1 3 | 9 21 8 0 3 0 6 12 0 18 1 15 |
The products total 93. The next multiple of ten is 100, so the check digit is 7 and the complete ISBN is 9780306406157.
If the weighted sum already ends in 0, the check digit is 0, not 10. You do not need to assume all check-digit systems use these weights; use the algorithm supplied.
10 | ARQ: CHECK, ACKNOWLEDGE, RETRY
Automatic repeat query (ARQ) combines an error check with acknowledgements and retransmission. It provides a way to request data again when a check fails or an expected response does not arrive.
- The sender transmits a block or packet and starts a timer.
- The receiver checks the data using the agreed error-detection method.
- If the check passes, the receiver sends a positive acknowledgement, ACK.
- If the check fails, a negative acknowledgement, NAK, can request retransmission.
- If the sender receives a NAK, it retransmits the relevant data.
- If no expected acknowledgement arrives before the timeout, the sender retransmits.
The acknowledgement itself can be lost. Sequence identifiers help a reliable protocol recognise retransmitted duplicates rather than treating them as new data. Some ARQ designs rely on timeouts without explicit NAKs.
ARQ is not the calculation that detects the error. It uses a check and a response process to recover. Continued faults can prevent completion, and an undetected error can still pass a weak check.
11 | FOLLOW AN ARQ EXCHANGE
| Event | Receiver / sender response |
|---|---|
| Packet 1 arrives with detected corruption | Receiver sends NAK |
| Sender receives NAK | Sender retransmits packet 1 |
| Packet 1 now passes its check | Receiver sends ACK |
| ACK is lost | Sender gets no expected response |
| Timer expires | Sender retransmits packet 1 again |
| Receiver recognises a duplicate | Avoids delivering the data twice and sends ACK again |
A timeout is a waiting limit, not proof that the data packet was corrupted. It may mean the packet or its acknowledgement was lost or delayed.
12 | KEEP THE METHODS DISTINCT
| Method | Core idea | Important limitation |
|---|---|---|
| Parity | Check whether the count of 1s obeys an odd/even rule | Even numbers of flips can be missed |
| Parity block | Check rows and columns | Multiple errors can be ambiguous or undetected |
| Checksum | Compare calculated values for a data block | Different data can give the same value |
| Echo check | Compare returned data with the original | Adds return traffic; return errors can affect checking |
| Check digit | Check consistency of an entered code | Does not verify meaning or catch every entry mistake |
| ARQ | Use checks, acknowledgements and timeouts to trigger repeats | Needs communication to succeed; depends on error checks |
FURTHER READING