Check Digit by Damme Method

The check digit is often added to identifiers that people can write or transmit with errors, in order to detect these errors.

Examples include the last digit of the credit card number , the ninth digit of the VIN of vehicles sold in the United States, or the last digit of the ISBN .

The Van Damme check digit algorithm is relatively new and therefore little known. It is published in 2004.
')
The algorithm detects all errors in a single digit and all single permutations of adjacent digits. It is noticeably simpler than the Verhuff's 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 fully antisymmetric quasigroup. Below is one of the examples of order 10. Before Damme's thesis [1], it was believed that similar quasigroups do not exist.

The quasigroup is chosen so as to determine, among other things, the maximum number of phonetic errors characteristic of the English language (13 instead of 30, etc.)

Intermediate figure	Input digit
	0	one	2	3	four	five	6	7	eight	9
0	0	3	one	7	five	9	eight	6	four	2
one	7	0	9	2	one	five	four	eight	6	3
2	four	2	0	6	eight	7	one	3	five	9
3	one	7	five	0	9	eight	3	four	2	6
four	6	one	2	3	0	four	five	9	7	eight
five	3	6	7	four	2	0	9	five	eight	one
6	five	eight	6	9	7	2	0	one	3	four
7	eight	9	four	five	3	6	2	0	one	7
eight	9	four	3	eight	6	one	7	2	0	five
9	2	five	eight	one	four	3	6	7	9	0

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

Check Digit Calculation Example

Suppose we need to calculate a check digit for the sequence 572 .

1. Initialize the intermediate digit with the value 0.
2. We find the digit 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. Assign this value to the intermediate figure.
3. We find the digit 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. Assign this value to the intermediate figure.
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 the intermediate figure.
5. The input sequence has ended. The last value of the intermediate digit (4) is the check 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 must be 0.

1. Initialize the intermediate digit with the value 0.
2. We find the digit 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. Assign this value to the intermediate figure.
3. We find the digit 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. Assign this value to the intermediate figure.
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 the intermediate figure.
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. We assign this value to an intermediate digit.
6. The input sequence has ended. The last value of the intermediate figure is 0, as expected.

Source code completely

 #include <iostream> #include <cassert> 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