In my previous post on VIN numbers, I commented that if a check sum has to be one of 11 characters, it cannot detect all possible changes to a string from an alphabet of 33 characters.
The number of possible check sum characters must be at least as large as the number of possible characters in the string.
Now suppose you wanted to create a check sum for text typed on a computer keyboard.
You want to detect any change where a single key was wrongly typed by using an adjacent key.
You don’t need many characters for the check sum because you’re not trying to detect arbitrary changes, such as typing H for A on a QWERTY keyboard.
You’re only trying to detect, for example, if someone typed Q, W, S, or Z for A.
In fact you would only need one of five characters for the check sum.
Here’s how to construct the check sum.
Think of the keys of the keyboard as a map, say by drawing boundaries through the spaces between the keys.
By the four color theorem, you can assign the numbers 0, 1, 2, and 3 to each key so that no two adjacent keys have the same number.
Concatenate all these digits and interpret it as a base 4 number.
Then take the remainder when the number is divided by 5.
That’s your check sum.
As proved here, this will detect any typo that hits an adjacent key.
It will also detect transpositions of adjacent keys.
Note that this doesn’t assume anything about the particular keyboard.
You could have any number of keys, and the keys could have any shape.
You could even define “adjacent” in some non-geometrical way as long as your adjacency graph is planar.
.. More details