fbpx
Wikipedia

Check digit

December 26, 2022

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 (digital sum) modulo 10. This would catch any single-digit error, as such an error would always change the sum, but does not catch any transposition errors (switching two digits) as re-ordering does not change the sum.

A slightly more complex method is to take the weighted sum of the digits, modulo 10, with different weights for each number position.

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 UPC codes, 13 13 weights in EAN numbers (GS1 algorithm), and the 371 371 371 weights used in United States bank routing transit numbers. This system detects all single-digit errors and around 90% of transposition errors. 1, 3, 7, and 9 are used because they are coprime with 10, so changing any digit changes the check digit; using a coefficient that is divisible by 2 or 5 would lose information (because 5×0 = 5×2 = 5×4 = 5×6 = 5×8 = 0 modulo 10) and thus not catch some single-digit errors. Using different weights on neighboring numbers means that most transpositions change the check digit; however, because all weights differ by an even number, this does not catch transpositions of two digits that differ by 5 (0 and 5, 1 and 6, 2 and 7, 3 and 8, 4 and 9), since the 2 and 5 multiply to yield 10.

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% 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

The final digit of a Universal Product Code is a check digit computed as follows:[3]

  1. Add the digits in the odd-numbered positions from the right (first, third, fifth, etc.—not including the check digit) together and multiply by three.
  2. Add the digits (up to but not including the check digit) in the even-numbered positions (second, fourth, sixth, etc.) to the result.
  3. Take the remainder of the result divided by 10 (ie. 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.

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.

  1. Add the odd number digits: 0+6+0+2+1+5 = 14.
  2. Multiply the result by 3: 14 × 3 = 42.
  3. Add the even number digits: 3+0+0+4+4 = 11.
  4. Add the two results together: 42 + 11 = 53.
  5. 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".

  1. Add the odd number digits: 0+0+0+0+0+0 = 0.
  2. Multiply the result by 3: 0 x 3 = 0.
  3. Add the even number digits: 1+1+1+1+1=5.
  4. Add the two results together: 0 + 5 = 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

Further information: International Standard Book Number § ISBN-10 check digits

The final character of a ten-digit International Standard Book Number is a check digit computed so that multiplying each digit by its position in the number (counting from the right) and taking the sum of these products modulo 11 is 0. The digit the farthest to the right (which is multiplied by 1) is the check digit, chosen to make the sum correct. It may need to have the value 10, which is represented as the letter X. For example, take the ISBN 0-201-53082-1: The sum of products is 0×10 + 2×9 + 0×8 + 1×7 + 5×6 + 3×5 + 0×4 + 8×3 + 2×2 + 1×1 = 99 ≡ 0 (mod 11). So the ISBN is valid. Note that positions can also be counted from left, in which case the check digit is multiplied by 10, to check validity: 0×1 + 2×2 + 0×3 + 1×4 + 5×5 + 3×6 + 0×7 + 8×8 + 2×9 + 1×10 = 143 ≡ 0 (mod 11).

ISBN 13

Further information: International Standard Book Number § ISBN-13 check digit calculation

ISBN 13 (in use January 2007) is equal to the EAN-13 code found underneath a book's barcode. Its check digit is generated the same way as the UPC except that the even digits are multiplied by 3 instead of the odd digits.[4]

EAN (GLN, GTIN, EAN numbers administered by GS1)

EAN (European Article Number) check digits (administered by GS1) are calculated by summing each of the odd position numbers multiplied by 3 and then by adding the sum of the even position numbers. Numbers are examined going from right to left, so the first odd position is the last digit in the code. The final digit of the result is subtracted from 10 to calculate the check digit (or left as-is if already zero). 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]

NCDA

The NOID Check Digit Algorithm (NCDA),[7] in use since 2004, is designed for application in persistent identifiers and works with variable length strings of letters and digits, called extended digits. It is widely used with the ARK identifier scheme and somewhat used with schemes, such as the Handle System and DOI. An extended digit is constrained to betanumeric characters, which are alphanumerics minus vowels and the letter 'l' (ell). This restriction helps when generating opaque strings that are unlikely to form words by accident and will not contain both O and 0, or l and 1. Having a prime radix of R=29, the betanumeric repertoire permits the algorithm to guarantee detection of single-character and transposition errors[8] for strings less than R=29 characters in length (beyond which it provides a slightly weaker check). The algorithm generalizes to any character repertoire with a prime radix R and strings less than R characters in length.

Other examples of check digits

International

In the USA

In Central America

  • The Guatemalan Tax Number (NIT – Número de Identificación Tributaria) based on modulo 11.

In Eurasia

In Oceania

Algorithms

Notable algorithms include:

See also

References

  1. ^ "What is Check Digit? - Definition from Techopedia". Techopedia.com. Retrieved 2022-03-16.
  2. ^ Kirtland, Joseph (2001). Identification Numbers and Check Digit Schemes. Classroom Resource Materials. Mathematical Association of America. pp. 4–6. ISBN 978-0-88385-720-5.
  3. ^ . GS1 US. 2006. Archived from the original on 2008-05-09. Retrieved 2008-05-21.
  4. ^ "ISBN Users Manual". International ISBN Agency. 2005. Retrieved 2008-05-21.
  5. ^ "Check Digit Calculator". GS1. 2005. Retrieved 2008-05-21.
  6. ^ "Check Digit Calculator, at GS1 US official site". GS1 US. Retrieved 2012-08-09.
  7. ^ John, A. Kunze. "noid - Nice Opaque Identifier Generator commands". metacpan.org. from the original on 2022-05-22. Retrieved 2022-10-15.
  8. ^ David Bressoud, Stan Wagon, "Computational Number Theory", 2000, Key College Publishing
  9. ^ "OpenFIGI: Unlock the Power of Efficiency with Open Symbology". OpenFIGI. from the original on 2022-08-09. Retrieved 2022-10-15.
  10. ^ (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. 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

    December 26, 2022
    check, digit, check, digit, form, redundancy, check, used, error, detection, identification, numbers, such, bank, account, numbers, which, used, application, where, they, will, least, sometimes, input, manually, analogous, binary, parity, used, check, errors, . 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 Contents 1 Design 2 Examples 2 1 UPC 2 2 ISBN 10 2 3 ISBN 13 2 4 EAN GLN GTIN EAN numbers administered by GS1 2 5 NCDA 2 6 Other examples of check digits 2 6 1 International 2 6 2 In the USA 2 6 3 In Central America 2 6 4 In Eurasia 2 6 5 In Oceania 3 Algorithms 4 See also 5 References 6 External linksDesign EditThis section does not cite any sources Please help improve this section by adding citations to reliable sources Unsourced material may be challenged and removed April 2010 Learn how and when to remove this template message 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 digital sum modulo 10 This would catch any single digit error as such an error would always change the sum but does not catch any transposition errors switching two digits as re ordering does not change the sum A slightly more complex method is to take the weighted sum of the digits modulo 10 with different weights for each number position 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 UPC codes 13 13 weights in EAN numbers GS1 algorithm and the 371 371 371 weights used in United States bank routing transit numbers This system detects all single digit errors and around 90 of transposition errors 1 3 7 and 9 are used because they are coprime with 10 so changing any digit changes the check digit using a coefficient that is divisible by 2 or 5 would lose information because 5 0 5 2 5 4 5 6 5 8 0 modulo 10 and thus not catch some single digit errors Using different weights on neighboring numbers means that most transpositions change the check digit however because all weights differ by an even number this does not catch transpositions of two digits that differ by 5 0 and 5 1 and 6 2 and 7 3 and 8 4 and 9 since the 2 and 5 multiply to yield 10 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 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 EditUPC Edit The final digit of a Universal Product Code is a check digit computed as follows 3 Add the digits in the odd numbered positions from the right 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 ie 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 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 Edit Further information International Standard Book Number ISBN 10 check digits The final character of a ten digit International Standard Book Number is a check digit computed so that multiplying each digit by its position in the number counting from the right and taking the sum of these products modulo 11 is 0 The digit the farthest to the right which is multiplied by 1 is the check digit chosen to make the sum correct It may need to have the value 10 which is represented as the letter X For example take the ISBN 0 201 53082 1 The sum of products is 0 10 2 9 0 8 1 7 5 6 3 5 0 4 8 3 2 2 1 1 99 0 mod 11 So the ISBN is valid Note that positions can also be counted from left in which case the check digit is multiplied by 10 to check validity 0 1 2 2 0 3 1 4 5 5 3 6 0 7 8 8 2 9 1 10 143 0 mod 11 ISBN 13 Edit Further information International Standard Book Number ISBN 13 check digit calculation ISBN 13 in use January 2007 is equal to the EAN 13 code found underneath a book s barcode Its check digit is generated the same way as the UPC except that the even digits are multiplied by 3 instead of the odd digits 4 EAN GLN GTIN EAN numbers administered by GS1 Edit EAN European Article Number check digits administered by GS1 are calculated by summing each of the odd position numbers multiplied by 3 and then by adding the sum of the even position numbers Numbers are examined going from right to left so the first odd position is the last digit in the code The final digit of the result is subtracted from 10 to calculate the check digit or left as is if already zero 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 NCDA Edit The NOID Check Digit Algorithm NCDA 7 in use since 2004 is designed for application in persistent identifiers and works with variable length strings of letters and digits called extended digits It is widely used with the ARK identifier scheme and somewhat used with schemes such as the Handle System and DOI An extended digit is constrained to betanumeric characters which are alphanumerics minus vowels and the letter l ell This restriction helps when generating opaque strings that are unlikely to form words by accident and will not contain both O and 0 or l and 1 Having a prime radix of R 29 the betanumeric repertoire permits the algorithm to guarantee detection of single character and transposition errors 8 for strings less than R 29 characters in length beyond which it provides a slightly weaker check The algorithm generalizes to any character repertoire with a prime radix R and strings less than R characters in length Other examples of check digits Edit International Edit The International SEDOL number The final digit of an ISSN code or IMO Number The International Securities Identifying Number ISIN Object Management Group FIGI standard final digit 9 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 Edit 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 amp Border Protection entry number In Central America Edit The Guatemalan Tax Number NIT Numero de Identificacion Tributaria based on modulo 11 In Eurasia Edit The UK NHS Number uses the modulo 11 algorithm The Spanish fiscal identification number numero de identificacion fiscal NIF based on modulo 23 The Dutch Burgerservicenummer BSN national identifier uses the modulo 11 algorithm The ninth digit of an Israeli Teudat Zehut Identity Card number The 13th digit of the Serbian and 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 Numarasi 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 Icelandic 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 India the unique identity number named Aadhaar has a trailing 12th digit that is calculated with the Verhoeff algorithm 10 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 11 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 Estonian Isikukood Personal Identification Code In Oceania Edit The Australian tax file number based on modulo 11 The seventh character of a New Zealand NHI Number The last digit in a New Zealand locomotive s Traffic Monitoring System TMS number Algorithms EditNotable algorithms include Luhn algorithm 1954 Verhoeff algorithm 1969 Damm algorithm 2004 See also EditChecksum Casting out nines similar modular sum check Check bit binary equivalentReferences Edit What is Check Digit Definition from Techopedia Techopedia com Retrieved 2022 03 16 Kirtland Joseph 2001 Identification Numbers and Check Digit Schemes Classroom Resource Materials Mathematical Association of America pp 4 6 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 ISBN Users Manual International ISBN Agency 2005 Retrieved 2008 05 21 Check Digit Calculator GS1 2005 Retrieved 2008 05 21 Check Digit Calculator at GS1 US official site GS1 US Retrieved 2012 08 09 John A Kunze 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 alternate url Chong Yee Khoo 20 January 2014 New Format for Singapore IP Application Numbers at IPOS Singapore Patent Blog Cantab IP Retrieved 6 July 2014 External links EditIdentification 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 Retrieved from https en wikipedia org w index php title Check digit amp oldid 1128339949, wikipedia, wiki, book, books, library,

    article

    , read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.