Damm algorithm

In error detection, the Damm algorithm is a check digit algorithm that detects all single-digit errors and all adjacent transposition errors. It was presented by H. Michael Damm in 2004. Its essential part is a quasigroup of order 10 (i.e. having a 10×10 Latin square as operation table) with the special feature of being totally anti-symmetric. Damm revealed several methods to create such TA-quasigroups of order 10 and gave some examples in his doctoral dissertation. With this, Damm also disproved an old conjecture that TA-quasigroups of order 10 do not exist.

Algorithm

The validity of a digit sequence containing a check digit is defined over a quasigroup. A quasigroup table ready for use can be taken from Damm's dissertation (pages 98, 106, 111). It is useful to rearrange the rows and to change the entries correspondingly so that each diagonal entry is 0, because it simplifies the check digit calculation.

Validating a number against the included check digit

1. Set up an interim digit and initialize it to 0.
2. Process the number digit by digit: Use the number's digit as column index and the interim digit as row index, take the table entry and replace the interim digit by it.
3. The number is valid if and only if the resulting interim digit has the value of 0.

Calculating the check digit

Prerequisite: The diagonal entries of the table are 0.

1. Set up an interim digit and initialize it to 0.
2. Process the number digit by digit: Use the number's digit as column index and the interim digit as row index, take the table entry and replace the interim digit by it.
3. The resulting interim digit gives the check digit and will be appended as trailing digit to the number.

Example

The TA-quasigroup is taken from Damm's doctoral dissertation page 111. It is modified by rearranging the columns and changing the entries correspondingly as described above.

	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

Suppose we choose the number (digit sequence) 572.

Calculating the check digit

digit to be processed → column index	5	7	2
old interim digit → row index	0	9	7
table entry → new interim digit	9	7	4

The resulting interim digit is 4. This is the calculated check digit. We append it to the number and obtain 5724.

Validating a number against the included check digit

digit to be processed → column index	5	7	2	4
old interim digit → row index	0	9	7	4
table entry → new interim digit	9	7	4	0

The resulting interim digit is 0, hence the number is valid.

Graphical illustration

Source code

C

char Taq(char* number)
{
  const char taqDhmd111rr[]=
    "0317598642""7092154863""4206871359""1750983426""6123045978"
    "3674209581""5869720134""8945362017""9438617205""2581436790";
  char interim='0';
  char* p;
  for(p=number;*p!='\0';++p){
    if((unsigned char)(*p-'0')>9)
      return '-'; //minus sign indicates an error: character is not a digit
    interim=taqDhmd111rr[(*p-'0')+(interim-'0')*10];
  }
  return interim;
}

char CalculateCheckDigit(char* numberWithoutCheckDigit)
{
  return Taq(numberWithoutCheckDigit);
}

typedef int BOOL;
BOOL IsCheckDigitValid(char* numberWithCheckDigit)
{
  return Taq(numberWithCheckDigit)=='0';
}

Swift

let table: [[Int8]] = [
    [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]
]

// Core algorithm: calculate check digit via iterative lookup from
// table, above.
func checkDigit(ints: [Int8]) -> Int8 {
    let lookup: (Int8, Int8) -> Int8 = { table[Int($0)][Int($1)] }
    return ints.reduce(0, lookup)
}

func validate(ints: [Int8]) -> Bool {
    return checkDigit(ints: ints) == 0
}


/* Below this line: string handling (conversion), validation, sample main. */

enum DammChecksumError: Error {
    case charNotADigit
}

func digits(string: String) throws -> [Int8] {
    return try string.characters.map {
        switch $0 {
        case "0":
            return 0
        case "1":
            return 1
        case "2":
            return 2
        case "3":
            return 3
        case "4":
            return 4
        case "5":
            return 5
        case "6":
            return 6
        case "7":
            return 7
        case "8":
            return 8
        case "9":
            return 9
        default:
            throw DammChecksumError.charNotADigit
        }
    }
}

func dammChecksum(forText: String) throws -> String {
    let asInts = try digits(string: forText)
    let digit: Int8 = checkDigit(ints: asInts)
    return "\(forText)\(digit)"
}


for arg in CommandLine.arguments {
    if let withChecksum = try? dammChecksum(forText: arg) {
        print("\(arg) -> \(withChecksum)")
    }
}

Strengths and weaknesses

The Damm algorithm is similar to the Verhoeff algorithm. It too will detect all occurrences of altering one single digit and all occurrences of transposing two adjacent digits. (These are the two most frequently appearing types of transcription errors.) But the Damm algorithm has the benefit that it makes do without the dedicatedly constructed permutations and its position specific powers being inherent in the Verhoeff scheme. Furthermore, a table of inverses can be dispensed with provided all diagonal entries of the operation table are zero.

The Damm algorithm does not suffer from exceeding the number of 10 possible values, resulting in the need for using a non-digit character (as the X in the ISBN-10 check digit scheme).

Prepending leading zeros does not affect the check digit.

There are totally anti-symmetric quasigroups that detect all phonetic errors associated with the English language (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). The table used in the illustrating example above represents an instance of such kind.

Despite its desirable properties in typical contexts where similar algorithms are used, the Damm algorithm is largely unknown and scarcely used in practice.

References

• Damm, H. Michael (2007). "Totally anti-symmetric quasigroups for all orders n≠2,6" Discrete Mathematics 307 (6): 715–729.