A check digit catches mistakes made when a person types a number, such as a book number or a bar code. An automatic repeat query makes sure transmitted data arrives without error, using acknowledgements and a timeout. This lesson teaches both.
about 30 min1 simulation1 practice question
Lesson 3 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
Errors at the keyboard
The checks so far look for errors in transmission. Errors also happen in data entry, when a person types a number or a scanner misreads it. A check digit catches these.
A check digit is an extra digit added to the end of a number. It is calculated from the other digits. When the number is entered, the computer works out the check digit again from the other digits and compares it with the one entered. If they differ, the number is rejected and must be entered again.
A check digit can find errors such as these.
A wrong digit:5 typed instead of 8.
Two digits swapped (a transposition): 47 typed as 74.
A digit left out or an extra digit typed.
Where check digits are used
ISBN. Every book has an international standard book number. The modern ISBN has 13 digits, and the last one is a check digit.
Bar codes. The 13-digit numbers under the bar codes on products use the same method as the ISBN.
The 13-digit method (ISBN-13 and bar codes).
Multiply the first 12 digits by 1,3,1,3,… from the left.
Add the results.
The check digit is the number you must add to make the total a multiple of 10. If the total is already a multiple of 10, the check digit is 0.
Example: the first 12 digits are 978190598311. The weighted total is 103. To reach 110 we add 7, so the check digit is 7 and the full number is 9781905983117.
To check a full 13-digit number, use the weights 1,3,1,3,… on all 13 digits. The total must be a multiple of 10.
Other check digit methods exist. The older 10-digit ISBN uses modulo 11: weights 10,9,8,…,2 on the first nine digits, then the check digit is 11 minus the remainder after dividing by 11. A result of 10 is written as X, and 11 is written as 0. In the exam, the question gives you the method to use.
Automatic repeat query (ARQ)
An automatic repeat query (ARQ) makes sure that transmitted data is received without error. It uses acknowledgements and a timeout.
A timeline with the sender on the left and the receiver on the right, time running down the page. Packet 1 crosses and a positive acknowledgement comes back. Packet 2 crosses, an error is found, and a negative acknowledgement comes back, so packet 2 is sent again and gets a positive acknowledgement. Packet 3 is lost on the way; the sender's timer runs out at the timeout, and packet 3 is sent again and acknowledged.
The sender sends a packet of data and starts a timer.
The receiver checks the packet for errors, for example with a checksum.
If there is no error, the receiver sends a positive acknowledgement back.
If there is an error, the receiver sends a negative acknowledgement back, and the sender sends the packet again.
If the sender gets no acknowledgement before the timeout, it assumes the packet was lost and sends it again automatically.
This goes on until a positive acknowledgement arrives, or until a set number of tries has been made.
The timeout is a fixed time that the sender waits. If it is too short, the sender resends packets that were only slow. If it is too long, a lost packet holds everything up.
Practise with new numbers
Try it in Python
The first program works out the check digit of a book number and shows a swap of two digits being caught. The second follows an ARQ with a timeout.
Common mistakes
Using a check digit for transmission errors. A check digit is for data entry, such as typing or scanning a number.
Giving the remainder as the check digit. In the 13-digit method, the check digit is what you add to reach a multiple of 10.
Mixing up the acknowledgements. Positive means received without error. Negative means an error was found.
Forgetting the timeout. If no acknowledgement arrives in time, the sender resends.
Remember these
A check digit is worked out from the other digits and catches data entry errors, such as swapped digits.
ISBN-13 and bar codes: weights 1,3,1,3,…; the total with the check digit is a multiple of 10.