Check digit
A check digit is a form of redundancy check used for error detection on identification numbers, such as bank account numbers, which are used in an application where they will at least sometimes be input manually. It is analogous to a binary parity bit used to check for errors in computer-generated data. It consists of one or more digits (or letters) computed by an algorithm from the other digits (or letters) in the sequence input.[1]
With a check digit, one can detect simple errors in the input of a series of characters (usually digits) such as a single mistyped digit or some permutations of two successive digits.
Design
Check digit algorithms are generally designed to capture human transcription errors. In order of complexity, these include the following: [2]
- letter/digit errors, such as l → 1 or O → 0
- single-digit errors, such as 1 → 2
- transposition errors, such as 12 → 21
- twin errors, such as 11 → 22
- jump transpositions errors, such as 132 → 231
- jump twin errors, such as 131 → 232
- phonetic errors, such as 60 → 16 ("sixty" to "sixteen")
In choosing a system, a high probability of catching errors is traded off against implementation difficulty; simple check digit systems are easily understood and implemented by humans but do not catch as many errors as complex ones, which require sophisticated programs to implement.
A desirable feature is that left-padding with zeros should not change the check digit. This allows variable length numbers to be used and the length to be changed. If there is a single check digit added to the original number, the system will not always capture multiple errors, such as two replacement errors (12 → 34) though, typically, double errors will be caught 90% of the time (both changes would need to change the output by offsetting amounts).
A very simple check digit method would be to take the sum of all digits (
A slightly more complex method is to take the
To illustrate this, for example if the weights for a four digit number were 5, 3, 2, 7 and the number to be coded was 4871, then one would take 5×4 + 3×8 + 2×7 + 7×1 = 65, i.e. 65 modulo 10, and the check digit would be 5, giving 48715.
Systems with weights of 1, 3, 7, or 9, with the weights on neighboring numbers being different, are widely used: for example, 31 31 weights in
The ISBN-10 code instead uses modulo 11, which is prime, and all the number positions have different weights 1, 2, ... 10. This system thus detects all single-digit substitution and transposition errors (including jump transpositions), but at the cost of the check digit possibly being 10, represented by "X". (An alternative is simply to avoid using the serial numbers which result in an "X" check digit.) ISBN-13 instead uses the GS1 algorithm used in EAN numbers.
More complicated algorithms include the Luhn algorithm (1954), which captures 98% of single-digit transposition errors (it does not detect 90 ↔ 09) and the still more sophisticated Verhoeff algorithm (1969), which catches all single-digit substitution and transposition errors, and many (but not all) more complex errors. Similar is another abstract algebra-based method, the Damm algorithm (2004), that too detects all single-digit errors and all adjacent transposition errors. These three methods use a single check digit and will therefore fail to capture around 10%[citation needed] of more complex errors. To reduce this failure rate, it is necessary to use more than one check digit (for example, the modulo 97 check referred to below, which uses two check digits—for the algorithm, see International Bank Account Number) and/or to use a wider range of characters in the check digit, for example letters plus numbers.
Examples
UPC, EAN, GLN, GTIN, numbers administered by GS1
The final digit of a Universal Product Code, International Article Number, Global Location Number or Global Trade Item Number is a check digit computed as follows:[3][4]
- Add the digits in the odd-numbered positions from the left (first, third, fifth, etc.—not including the check digit) together and multiply by three.
- Add the digits (up to but not including the check digit) in the even-numbered positions (second, fourth, sixth, etc.) to the result.
- Take the remainder of the result divided by 10 (i.e. the modulo 10 operation). If the remainder is equal to 0 then use 0 as the check digit, and if not 0 subtract the remainder from 10 to derive the check digit.
A GS1 check digit calculator and detailed documentation is online at GS1's website.[5] Another official calculator page shows that the mechanism for GTIN-13 is the same for Global Location Number/GLN.[6]
For instance, the UPC-A barcode for a box of tissues is "036000241457". The last digit is the check digit "7", and if the other numbers are correct then the check digit calculation must produce 7.
- Add the odd number digits: 0+6+0+2+1+5 = 14.
- Multiply the result by 3: 14 × 3 = 42.
- Add the even number digits: 3+0+0+4+4 = 11.
- Add the two results together: 42 + 11 = 53.
- To calculate the check digit, take the remainder of (53 / 10), which is also known as (53 modulo 10), and if not 0, subtract from 10. Therefore, the check digit value is 7. i.e. (53 / 10) = 5 remainder 3; 10 - 3 = 7.
Another example: to calculate the check digit for the following food item "01010101010x".
- Add the odd number digits: 0+0+0+0+0+0 = 0.
- Multiply the result by 3: 0 x 3 = 0.
- Add the even number digits: 1+1+1+1+1=5.
- Add the two results together: 0 + 5 = 5.
- To calculate the check digit, take the remainder of (5 / 10), which is also known as (5 modulo 10), and if not 0, subtract from 10: i.e. (5 / 10) = 0 remainder 5; (10 - 5) = 5. Therefore, the check digit x value is 5.
ISBN 10
The final character of a ten-digit
ISBN 13
ISBN 13 (in use January 2007) is equal to the
NCDA
The NOID Check Digit Algorithm (NCDA),
Other examples of check digits
International
- The International SEDOL number.
- The final digit of an IMO Number.
- The International Securities Identifying Number(ISIN).
- Object Management Group FIGI standard final digit.[10]
- The International CAS registry number's final digit.
- Modulo 10 check digits in credit card account numbers, calculated by the Luhn algorithm.
- Also used in the Norwegian KID (customer identification number) numbers used in bank giros (credit transfer),
- Used in IMEI of mobile phones.
- Last check digit in EAN/UPC serialisation of Global Trade Identification Number (GTIN). It applies to GTIN-8, GTIN-12, GTIN-13 and GTIN-14.
- The final digit of a DUNS number (though this is scheduled to change, such as that the final digit will be chosen freely in new allocations, rather than being a check digit).
- The third and fourth digits in an International Bank Account Number (Modulo 97 check).
- The final digit in an International Standard Text Code.
- The final character encoded in a magnetic stripe card is a computed Longitudinal redundancy check.
In the USA
- The tenth digit of the National Provider Identifier for the US healthcare industry.
- The final digit of a POSTNET code.
- The North American CUSIP number.
- The final (ninth) digit of the ABA routing transit number, a bank code used in the United States.
- The ninth digit of a Vehicle Identification Number (VIN).
- Mayo Clinic patient identification numbers used in Arizona and Florida include a trailing check digit[citation needed].
- The eleventh digit of a Customs & Border Protectionentry number.
In Central America
- The Guatemalan Tax Number (NIT – Número de Identificación Tributaria) based on modulo11.
In Eurasia
- The UK NHS Numberuses the modulo 11 algorithm.
- The Spanish fiscal identification number (número de identificación fiscal, NIF) (based on modulo 23).
- The Dutch Burgerservicenummer (BSN) (national identifier) uses the modulo 11 algorithm.
- The ninth digit of an Teudat Zehut(Identity Card) number.
- The 13th digit of the Former Yugoslav Unique Master Citizen Number(JMBG). (but not all of them, due to errors or non-residency)
- The last two digits of the 11-digit Turkish Identification Number (Turkish: TC Kimlik Numarası).
- The ninth character in the 14-character EU cattle passport number (cycles from 1 to 7: see British Cattle Movement Service).
- The ninth digit in an Kennitala(national ID number).
- Modulo 97 check digits in a Belgian and Serbian bank account numbers. Serbia sometimes also uses modulo 11, for reference number.
- The ninth digit in a Hungarian TAJ number (social insurance number).
- For the residents of Aadhaar has a trailing 12th digit that is calculated with the Verhoeff algorithm.[11]
- The Intellectual Property Office of Singapore (IPOS) has confirmed a new format for application numbers of registrable intellectual property (IP, e.g., trademarks, patents, registered designs). It will include a check character calculated with the Damm algorithm.[12]
- The last digit of Chinese citizen ID number (second generation) is calculated by modulo 11-2 as specified in Chinese GuoBiao (aka national standard) GB11643-1999 which adopts ISO 7064:1983. 'X' is used if the calculated checking digit is 10.
- The 11th digit of Isikukood(Personal Identification Code).
- The last letter on Vehicle registration plates of Singapore.
In Oceania
- The Australian modulo11).
- The seventh character of a New Zealand NHI Number.
- The last digit in a New Zealand locomotive's Traffic Monitoring System (TMS) number.
Algorithms
Notable algorithms include:
- Luhn algorithm (1954)
- Verhoeff algorithm (1969)
- Damm algorithm (2004)
See also
- Checksum
- Casting out nines – similar modular sum check
- Check bit– binary equivalent
References
- ^ "What is Check Digit? - Definition from Techopedia". Techopedia.com. Retrieved 2022-03-16.
- ISBN 978-0-88385-720-5.
- ^ "GS1 Check Digit Calculator". GS1 US. 2006. Archived from the original on 2008-05-09. Retrieved 2008-05-21.
- ^ "How to calculate a check digit manually". GS1.
- ^ "Check Digit Calculator". GS1. 2005. Retrieved 2008-05-21.
- ^ "Check Digit Calculator, at GS1 US official site". GS1 US. Archived from the original on 2016-11-21. Retrieved 2012-08-09.
- ^ "ISBN Users Manual". International ISBN Agency. 2005. Archived from the original on 2014-04-29. Retrieved 2008-05-21.
- ^ Kunze, John A. "noid - Nice Opaque Identifier Generator commands". metacpan.org. Archived from the original on 2022-05-22. Retrieved 2022-10-15.
- ^ David Bressoud, Stan Wagon, "Computational Number Theory", 2000, Key College Publishing
- ^ "OpenFIGI: Unlock the Power of Efficiency with Open Symbology". OpenFIGI. Archived from the original on 2022-08-09. Retrieved 2022-10-15.
- ^ "Unique Identification Card" (PDF). Geek Gazette. Autumn 2011. p. 16. Archived from the original (PDF) on 2014-06-26.
- ^ Chong-Yee Khoo (20 January 2014). "New Format for Singapore IP Application Numbers at IPOS". Singapore Patent Blog. Cantab IP. Archived from the original on 14 July 2014. Retrieved 6 July 2014.
External links
- Identification numbers and check digit schemes (a mathematical explanation of various check digit schemes)
- UPC, EAN, and SCC-14 check digit calculator
- GS1 check digit calculator