2.2 Methods of error detection
Data can be changed, lost or corrupted while it is transmitted or entered. This topic explains why error checking matters and how parity checks, parity blocks, checksums, echo checks, check digits and Automatic Repeat Requests are used to detect problems and trigger correction or re-transmission.
What you need to understand
By the end of Topic 2.2 you should be able to explain why transmitted data needs checking; use and interpret even and odd parity; explain parity blocks, checksums and echo checks; calculate or verify check digits when an algorithm is supplied; and describe how ARQ uses acknowledgements, timeouts and re-transmission.
The need to check for errors
Whenever data is transmitted, there is a risk that the data received will not be identical to the data that was sent. The supplied textbook identifies three important causes of transmission error.
Interference
Electrical interference can affect a cable and change, corrupt or even cause the loss of data.
Packet-switching problems
Packets can be lost during their journey, and problems in transmission can leave the receiver with missing or incorrect data.
Skew
During parallel transmission, bits travelling along separate wires can arrive out of synchronisation. This can corrupt the reconstructed data.
People can sometimes recognise a word even when letters have been rearranged, but a computer depends on exact bit patterns and codes. Corruption therefore has to be detected rather than guessed around.
The textbook introduces three transmission-checking methods at this point: parity checks, checksum and echo check. Check digits are then used for data-entry errors, and ARQ provides a re-transmission procedure.
Parity checks, checksum and echo checks
Parity checks
A parity check uses the number of 1-bits in a byte. Before transmission, sender and receiver agree to use either even parity or odd parity. One bit in the byte is reserved as the parity bit, usually shown as the left-most bit in the textbook examples.
| Parity type | Rule after the parity bit is included |
|---|---|
| Even parity | The complete byte must contain an even number of 1-bits. |
| Odd parity | The complete byte must contain an odd number of 1-bits. |
Worked parity examples
Suppose the seven data bits are 1101100. They already contain four 1-bits.
- With even parity, the parity bit is 0, giving 01101100.
- With odd parity, the parity bit is 1, giving 11101100.
Using parity to detect an error
The receiver counts the 1-bits again. If even parity was agreed but the received byte contains an odd number of 1-bits, an error is flagged. The same idea applies in reverse for odd parity.
Parity blocks
A parity block applies parity both horizontally and vertically across a block of bytes. A separate parity byte contains the vertical parity bits. If one bit changes, the row with incorrect parity and the column with incorrect parity intersect at the faulty bit.
In the book's example, byte 8 has the wrong row parity and bit 5 has the wrong column parity. Their intersection identifies the bit that must be changed. The system can correct that bit or request that the block be transmitted again.
Checksum
A checksum is an additional value calculated from a block of data. Sender and receiver use the same agreed algorithm.
- Before transmission, the sender calculates a checksum from the data block.
- The checksum is transmitted with the block.
- The receiver calculates a new checksum from the received data using the same algorithm.
- The two checksum values are compared.
- If they match, the block is accepted as having no detected transmission error. If they do not match, the block is requested again.
Echo check
With an echo check, the receiving device sends a copy of the received data back to the sender. The sender compares the returned data with the original.
- If the two copies are identical, the transmission is treated as successful.
- If the copies differ, an error occurred somewhere in the outward or return transmission.
- The weakness is that the sender cannot tell from the comparison alone whether the error happened on the original journey or on the return journey.
Check digits
A check digit is a final digit calculated from the other digits in a code. Unlike parity, checksum and echo check, this section is mainly about detecting data-entry errors, such as mistyping a code or mis-scanning a barcode.
The textbook gives International Standard Book Numbers (ISBNs) and Vehicle Identification Numbers (VINs) as examples.
Errors a check digit can help detect
- Incorrect digit: one digit is entered wrongly.
- Transposition: two digits change places.
- Omitted or extra digit: a digit is missing or an extra digit is added.
- Phonetic error: a spoken number is misunderstood, for example thirteen instead of thirty.
ISBN-13 check digit
For a 13-digit ISBN, the thirteenth digit is the check digit. The book shows both how to generate the check digit from the first 12 digits and how to verify a complete 13-digit ISBN.
Generating an ISBN-13 check digit
- Add the digits in the odd-numbered positions.
- Add the digits in the even-numbered positions and multiply that result by 3.
- Add the two totals.
- Find the remainder when the total is divided by 10. If the remainder is 0, the check digit is 0; otherwise subtract the remainder from 10.
For the book's 12 digits 978034098382, the odd-position sum is 36 and three times the even-position sum is 75. The total is 111, giving remainder 1, so the check digit is 9.
Verifying a full ISBN-13
When the check digit is already included, the same weighting idea is used. The complete calculation should give a total that is exactly divisible by 10. A remainder of 0 means the ISBN passes the check.
Modulo-11
The textbook also demonstrates a modulo-11 check-digit method. The number can be different lengths, which makes the idea useful for codes such as product codes or VINs.
- Give the digits descending weights, starting from a value determined by the length of the code.
- Multiply every digit by its weight and add all the products.
- Divide the total by 11.
- For generation, subtract the remainder from 11 to obtain the check digit. In the book's method, if the result that has to be represented is 10, X is used.
- For verification, include the check digit with weight 1. The code is valid if the total has remainder 0 when divided by 11.
Automatic Repeat Requests (ARQs)
An Automatic Repeat Request (ARQ) is a method that combines error detection with acknowledgements and automatic re-transmission. Its aim is to ensure that the sender keeps trying until the receiver confirms that the data arrived correctly, or until a set retry limit is reached.
Positive acknowledgement
The receiver reports that the data was received correctly. The sender can continue.
Negative acknowledgement
The receiver reports that an error was detected and requests the data again.
Timeout
The sender waits for an acknowledgement for a pre-set time. If none arrives before the time limit, the sender automatically transmits the data again.
ARQ sequence
- The sender transmits data together with an error-detection code; the textbook gives a CRC as a typical example.
- The receiver checks the error-detection code.
- If no error is detected, the receiver sends a positive acknowledgement.
- If an error is detected, the receiver sends a negative acknowledgement and asks for re-transmission.
- If the sender receives no acknowledgement before the timeout expires, it sends the data again automatically.
- Re-transmission continues until a positive acknowledgement is received or a pre-determined retry limit is reached.