Choosing a checksum for short code to prevent typing errors

Question

i need to choose a checksum algorithm to detect when users mistyped a 4 character [A-Z0-9] code by adding 1 character at the end of the code (in [A-Z0-9] also).

Summing ASCII codes and applying a modulo is a bad solution, since inverting 2 key strokes won't be noticed.

I would probably use the Fletcher algorithm, but i would like to know is anyone knows an algorithm designed for this use case (very very small amount of byte, position dependant) ?

Thank you.

Answer 1

You can try the ISO 7064 Mod x,y algorithms. According to the ISO description:

The check character systems specified in ISO/IEC 7064:2002 can detect ( http://www.iso.org/iso/home/store/catalogue_ics/catalogue_detail_ics.htm?csnumber=31531 ):

• all single substitution errors (the substitution of a single character for another, for example 4234 for 1234);
• all or nearly all single (local) transposition errors (the transposition of two single characters, either adjacent or with one character between them, for example 12354 or 12543 for 12345);
• all or nearly all shift errors (shifts of the whole string to the left or right);
• a high proportion of double substitution errors (two separate single substitution errors in the same string, for example 7234587 for 1234567);
• high proportion of all other errors.

There are some partial implementations you can find like:

• http://code.google.com/p/checkdigits/wiki/CheckDigitSystems (includes Java and Javascript implementations of several checksums algorithms).
• http://www.codeproject.com/Articles/16540/Error-Detection-Based-on-Check-Digit-Schemes (explains and includes VC implementations).

For example, you could use ISO 7064 Mod 37,36, which can use 0-9 and A-Z (the data and the check character). The detailed description of the algorithm (if you don't feel like buying the ISO) can be found in:

• http://www.cdfa.ca.gov/ahfss/animal_health/pdfs/NAIS/Program_Standard_and_Technical_Reference10-07.pdf (it's used for animal identification)
• http://www.ifpi.org/content/library/GRid_Standard_v2_1.pdf (also used by the music industry)
• http://www.ddex.net/sites/default/files/DDEX-DPID-10-2006.pdf (other media companies)