algorithmerror-correctioncheck-digit

Error correction based on Damm check digit


If you use the Damm algorithm to generate check digits, is there a method to try correcting the error if the code doesn't validate?


Solution

  • Nope, the algorithm can only be used to detect errors, not correct errors.

    This can be demonstrated with a simple example. Let's say that you receive a number containing the digits 9857. When you run the algorithm on that number, the result is 6. So one of the digits has been changed. But which one?

    With a brute force search, you can determine that the original number could be any of the following:

    original                                                resulting
     number             error that occurred                  number
      1857      the first  digit got changed from 1 to 9      9857
      9157      the second digit got changed from 1 to 8      9857
      9827      the third  digit got changed from 2 to 5      9857
      9850      the fourth digit got changed from 0 to 7      9857
    

    So a number that contains an error does not uniquely identify the original number.

    In general, it's possible to get a correct checksum by changing any one of the digits. Which is to say that if you receive a number with N digits, and the checksum is not 0, then it's possible to change any one of the N digits to get a correct checksum.