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 Other examples of check digits 2.5.1 International 2.5.2 In the USA 2.5.3 In Central America 2.5.4 In Eurasia 2.5.5 In Oceania 3 Algorithms 4 See also 5 References 6 External links

Design This 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: [1] 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 digits 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 to 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.

Algorithms Notable algorithms include: Luhn algorithm (1954) Verhoeff algorithm (1969) Damm algorithm (2004)

See also Casting out nines, similar modular sum check Check bit, binary equivalent

References ^ 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.  ^ http://openfigi.com ^ "Unique Identification Card". Geek Gazette. IEEE Student Branch (Autumn 2011): 16. Archived from the original on 2012-10-24.  ^ Dr. 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 Wikimedia Commons has media related to Check digit. Retrieved from "https://en.wikipedia.org/w/index.php?title=Check_digit&oldid=827002407" Categories: Error detection and correctionHidden categories: Articles needing additional references from April 2010All articles needing additional referencesAll articles with unsourced statementsArticles with unsourced statements from April 2010Articles containing Turkish-language text