Check Digit Damm

    KDPVThe check digit is often added to identifiers that people can write or transmit with errors so that they can later detect these errors.

    Examples include the last digit of a credit card number , the ninth digit of a VIN of cars sold in the USA, or the last digit of an ISBN . Van Damme's

    check digit algorithm is relatively new and therefore little known. It was published in 2004. The algorithm detects all errors in one digit and all single permutations of adjacent digits. It is noticeably simpler than the Verhuff algorithm , comparable in capabilities , and does not require the use of special characters (such as X in a 10-digit ISBN).




    The algorithm is based on a completely antisymmetric quasigroup. Below is an example of order 10. Prior to Damm's dissertation [1], it was believed that such quasigroups do not exist.

    The quasigroup is selected so that, among other things, it determines the maximum number of phonetic errors characteristic of the English language (13 instead of 30, etc.)
    Intermediate digitInput digit
     0 1 2 3 4 5 6 7 8 9
     0 0 3 1 7 5 9 8 6 4 2
     1 7 0 9 2 1 5 4 8 6 3
     2 4 2 0 6 8 7 1 3 5 9
     3 1 7 5 0 9 8 3 4 2 6
     4 6 1 2 3 0 4 5 9 7 8
     5 3 6 7 4 2 0 9 5 8 1
     6 5 8 6 9 7 2 0 1 3 4
     7 8 9 4 5 3 6 2 0 1 7
     8 9 4 3 8 6 1 7 2 0 5
     9 2 5 8 1 4 3 6 7 9 0

    In addition to the quasigroup, the algorithm uses one intermediate digit, initialized to zero, and essentially consists of only one assignment operation interim_digit_ = quasigroup[interim_digit_][digit].

    Check Digit Example


    Suppose we need to compute a check digit for a sequence of 572 .

    1. Initialize the intermediate digit with the value 0.
    2. We find the number in column 5 (this is the first digit of the input sequence) and line 0 (this is the value of the intermediate digit). There 9. We assign this value to an intermediate digit.
    3. We find the number in column 7 (this is the second digit of the input sequence) and line 9 (this is the value of the intermediate digit). There 7. We assign this value to an intermediate digit.
    4. We find the number in column 2 (this is the third digit of the input sequence) and line 7 (this is the value of the intermediate digit). There 4. Assign this value to an intermediate digit.
    5. The input sequence has ended. The last value of the intermediate digit (4) is the control digit. Add it to the end of the sequence and get 5724 .


    Check Digit Example


    Check the sequence of numbers 5724 . If there are no errors, the check digit should be 0.

    1. Initialize the intermediate digit with the value 0.
    2. We find the number in column 5 (this is the first digit of the input sequence) and line 0 (this is the value of the intermediate digit). There 9. We assign this value to an intermediate digit.
    3. We find the number in column 7 (this is the second digit of the input sequence) and line 9 (this is the value of the intermediate digit). There 7. We assign this value to an intermediate digit.
    4. We find the number in column 2 (this is the third digit of the input sequence) and line 7 (this is the value of the intermediate digit). There 4. Assign this value to an intermediate digit.
    5. We find the number in column 4 (this is the fourth digit of the input sequence) and line 4 (this is the value of the intermediate digit). There 0. Assign this value to an intermediate digit.
    6. The input sequence has ended. The last value of the intermediate digit is 0, as expected.

    Full source code


    #include 
    #include 
    class Damm {
      public:
        Damm() : interim_digit_(0) {}
        void push(int digit) {
          static const int quasigroup[10][10] = {
            {0, 3, 1, 7, 5, 9, 8, 6, 4, 2},
            {7, 0, 9, 2, 1, 5, 4, 8, 6, 3},
            {4, 2, 0, 6, 8, 7, 1, 3, 5, 9},
            {1, 7, 5, 0, 9, 8, 3, 4, 2, 6},
            {6, 1, 2, 3, 0, 4, 5, 9, 7, 8},
            {3, 6, 7, 4, 2, 0, 9, 5, 8, 1},
            {5, 8, 6, 9, 7, 2, 0, 1, 3, 4},
            {8, 9, 4, 5, 3, 6, 2, 0, 1, 7},
            {9, 4, 3, 8, 6, 1, 7, 2, 0, 5},
            {2, 5, 8, 1, 4, 3, 6, 7, 9, 0}
          };
          assert(digit >= 0);
          assert(digit <= 9);
          interim_digit_ = quasigroup[interim_digit_][digit];
        }
        int check_digit(void) const {
          return interim_digit_;
        }
        void clear(void) {
          interim_digit_ = 0;
        }
      private:
        int interim_digit_;
    };
    int main(void)
    {
      Damm d;
      d.push(5);
      d.push(7);
      d.push(2);
      int check_digit = d.check_digit();
      std::cout << "Check digit (572) = " << check_digit << ", expected 4\n";
      d.clear();
      d.push(5);
      d.push(7);
      d.push(2);
      d.push(4);
      check_digit = d.check_digit();
      std::cout << "Check digit (5724) = " << check_digit << ", expected 0\n";
      return 0;
    }
    

    Link to the source


    [1] Damm, H. Michael Total anti-symmetrische Quasigruppen PDF

    Also popular now: