2.1 EAN-13 code and error detection
In the EAN-13 code, the first 12 digits of the number identify the item the code is attached to, and the final digit is a ‘check digit’.
The check digit for an EAN-13 code is calculated as follows:
- Count digit positions from the left to the right, starting at 1.
- Sum all the digits in odd positions. (In the example shown in Figure 9, this is 9 + 8 + 5 + 1 + 2 + 5 = 30 – note that the final 5 is not included since this is the check digit, which is what we are currently trying to calculate.)
- Sum all the digits in even positions and multiply the result by 3. (In the example, this is (7 + 0 + 2 + 4 + 5 + 7) × 3 = 75.)
- Add the results of step 2 and step 3, and take just the final digit (the ‘units’ digit) of the answer. This is equivalent to taking the answer modulo-10. (In the example, the sum is 30 + 75 = 105, so the units digit is 5.)
- If the answer to step 4 was 0, this is the check digit. Otherwise the check digit is given by ten minus the answer from step 4. (In the example, this is 10 – 5 = 5.)
- The check digit is appended to the right of the 12 identification digits. The check digit can have any value from 0 to 9.
Activity 8 Self assessment
The code below shows the first 12 digits of an EAN-13 code. Note: the hyphen between the 8 and the 0 has no bearing on the code. It is for convenience of reading, separating different elements of the identification. The 978 identifies this item as a book. (Not all EAN-13 codes have a hyphen in the same place.)
Calculate the check digit, and so derive the full EAN-13 code.
978–014102662.
Answer
Adding together the odd digits gives:
9 + 8 + 1 + 1 + 2 + 6 = 27.
Adding together the even digits and multiplying by 3 gives:
(7 + 0 + 4 + 0 + 6 + 2) × 3 = 19 × 3 = 57.
Adding the two together gives:
27 + 57 = 84.
The units digit is 4, so the check digit is given by:
10 − 4 = 6.
The full EAN-13 code is therefore 978–0141026626.
One way to check a received EAN-13 code for errors is to remove the received check digit and recalculate it based on the 12-digit identification code. If the recalculated value differs from the received value, there must be an error.
Alternatively, there is a shortcut to checking for errors because of the way the check digit is derived. You take the full 13-digit received code and do steps 1 to 4 from the calculation used above. If the code is correct, the value at step 4 will be 0. If the code is wrong, it will have some other value.
Activity 9 Self assessment
Check whether the following codes are valid:
- a.978–0521425575
- b.978–1405322274
Answer
- a.978–0521425575 is a 12-digit identification code 978–052142557 with a check digit of 5. Recalculating the check digit from the identification code gives 5, so the code is correct.
Alternatively, using the ‘shortcut’, we take all 13 digits and go through steps 1 to 4.
Adding together the odd digits gives:
9 + 8 + 5 + 1 + 2 + 5 + 5 = 35.
Adding together the even digits and multiplying by 3 gives:
(7 + 0 + 2 + 4 + 5 + 7) × 3 = 25 × 3 = 75.
Adding the two together gives:
35 + 75 = 110.
The units digit is 0, which shows that this is a valid EAN-13 code.
- b.978–1405322274 is a 12-digit identification code 978–140532227 with a check digit of 4. Recalculating the check digit from the identification code gives 0, so the code is incorrect.
Alternatively, using the ‘shortcut’, we take all 13 digits and go through steps 1 to 4. This gives 34 + 20 × 3 = 94, which results in a units digit of 4. Since this is not zero, this is not a valid EAN-13 code.
One thing to notice about EAN-13 is that the numbers were treated as a string of separate digits, not as a single number. It was, for example, 9, 7, 8, 0, 5, 2, 1, 4, 2, 5, 5, 7, not 978 052 142 557 (i.e. not nine hundred and seventy-eight billion, fifty-two million, one hundred and forty-two thousand, five hundred and fifty-seven).
In EAN-13 the digits are denary: numbers to base 10. In base 10 a digit can be any one of 10 symbols, which we represent as 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9. (The word ‘symbol’ is used here in a different, though parallel, sense from the symbols of modulation schemes.)
The check digit included in the 13-digit EAN code is an example of redundancy. This is a standard term for bits appended to data for error control. Unfortunately the term ‘redundancy’ suggests that these additional bits serve no purpose, which is not true. They are redundant, though, in the sense that they are not part of the message data.
All forms of error control involve the augmentation of a message with error control bits, which could be described as adding redundancy. If the number of bits (or bytes) in the message is k, and the augmented length is n bits (or bytes), the ratio k/n is known as the code rate. This is an important parameter.
Code rate is a measure of how much redundancy has been added to the code. If lots of check digits (that is, lots of redundancy) are appended to a small number of message digits, the code rate will be small (much less than 1). If only a few check digits are appended to a big message, the code rate will be close to 1. (It can never exceed 1.) Code rates found in, for example, mobile communications and WiFi typically range from 1/4 to 5/6.
Sometimes a code is specified by the numbers (n, k), in that order, with brackets around them and a comma between the numbers. Codes which take k message digits and create an n digit code word are described as (n, k) block codes.
Activity 10 Self assessment
- a.Describe an EAN-13 code using the (n, k) notation
- b.What is the code rate of an EAN code?
Answer
- a.There are 12 digits in an EAN-13 code, to which one check digit is added, so it is a (13,12) code
- b.The code rate of an EAN-13 code is k/n = 12/13
Next, we will look at how Reed–Solomon codes are used for error control on data that is structured into sequences of eight-bit bytes.