Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Damm algorithm
Check digit algorithm presented by H. Michael Damm

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, as a part of his PhD dissertation entitled Totally Antisymmetric Quasigroups.

We don't have any images related to Damm algorithm yet.
We don't have any YouTube videos related to Damm algorithm yet.
We don't have any PDF documents related to Damm algorithm yet.
We don't have any Books related to Damm algorithm yet.
We don't have any archived web articles related to Damm algorithm yet.

Strengths and weaknesses

Strengths

The Damm algorithm is similar to the Verhoeff algorithm. It too will detect all occurrences of the two most frequently appearing types of transcription errors, namely altering a single digit or transposing two adjacent digits (including the transposition of the trailing check digit and the preceding digit).23 The Damm algorithm has the benefit that it does not have the dedicatedly constructed permutations and its position-specific powers of the Verhoeff scheme. A table of inverses can also be dispensed with when all main diagonal entries of the operation table are zero.

The Damm algorithm generates only 10 possible values, avoiding the need for a non-digit character (such as the X in the 10-digit ISBN check digit scheme).

Prepending leading zeros does not affect the check digit (a weakness for variable-length codes).4

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 is based on an instance of such kind.

Weaknesses

For all checksum algorithms, including the Damm algorithm, prepending leading zeroes does not affect the check digit,5 so 1, 01, 001, etc. produce the same check digit. Consequently variable-length codes should not be verified together.

Design

Its essential part is a quasigroup of order 10 (i.e. having a 10 × 10 Latin square as the body of its operation table) with the special feature of being weakly totally anti-symmetric.678910 Damm revealed several methods to create totally anti-symmetric quasigroups of order 10 and gave some examples in his doctoral dissertation.1112 With this, Damm also disproved an old conjecture that totally anti-symmetric quasigroups of order 10 do not exist.13

A quasigroup (Q, ∗) is called totally anti-symmetric if for all c, x, y ∈ Q, the following implications hold:14

  1. (c ∗ x) ∗ y = (c ∗ y) ∗ x ⇒ x = y
  2. x ∗ y = y ∗ x ⇒ x = y,

and it is called weak totally anti-symmetric if only the first implication holds. Damm proved that the existence of a totally anti-symmetric quasigroup of order n is equivalent to the existence of a weak totally anti-symmetric quasigroup of order n. For the Damm algorithm with the check equation (...((0 ∗ xm) ∗ xm−1) ∗ ...) ∗ x0 = 0, a weak totally anti-symmetric quasigroup with the property x ∗ x = 0 is needed. Such a quasigroup can be constructed from any totally anti-symmetric quasigroup by rearranging the columns in such a way that all zeros lay on the diagonal. And, on the other hand, from any weak totally anti-symmetric quasigroup a totally anti-symmetric quasigroup can be constructed by rearranging the columns in such a way that the first row is in natural order.15

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).16 It is useful if each main diagonal entry is 0,17 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 with it.
  3. The number is valid if and only if the resulting interim digit has the value of 0.18

Calculating the check digit

Prerequisite: The main 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 with it.
  3. The resulting interim digit gives the check digit and will be appended as trailing digit to the number.19

Example

The following operation table will be used.20 It may be obtained from the totally anti-symmetric quasigroup x ∗ y in Damm's doctoral dissertation page 11121 by rearranging the rows and changing the entries with the permutation φ = (1 2 9 5 4 8 6 7 3) and defining x ⋅ y = φ−1(φ(x) ∗ y).

⋅0123456789
00317598642
17092154863
24206871359
31750983426
46123045978
53674209581
65869720134
78945362017
89438617205
92581436790

Suppose we choose the number (digit sequence) 572.

Calculating the check digit

digit to be processed → column index572
old interim digit → row index097
table entry → new interim digit974

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 index5724
old interim digit → row index0974
table entry → new interim digit9740

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

Graphical illustration

This is the above example showing the detail of the algorithm generating the check digit (dashed blue arrow) and verifying the number 572 with the check digit.

Wikibooks has a book on the topic of: Algorithm Implementation/Checksums/Damm Algorithm

References

  1. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  2. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  3. For the types of common errors and their frequencies, see Salomon, David (2005). Coding for Data and Computer Communications. Springer Science+Business Media, Inc. p. 36. ISBN 978-0387-21245-6. 978-0387-21245-6 ↩

  4. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  5. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  6. Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (in German). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162. http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf ↩

  7. Damm, H. Michael (2007). "Totally anti-symmetric quasigroups for all orders n ≠ 2, 6". Discrete Mathematics. 307 (6): 715–729. doi:10.1016/j.disc.2006.05.033. ISSN 0012-365X. https://doi.org/10.1016%2Fj.disc.2006.05.033 ↩

  8. Beliavscaia, Galina; Izbaş, Vladimir; Şcerbacov, Victor (2003). "Check character systems over quasigroups and loops" (PDF). Quasigroups and Related Systems. 10 (1): 1–28. ISSN 1561-2848. See page 23. http://www.math.md/files/qrs/v10-n1/v10-n1-(pp1-28).pdf ↩

  9. Chen Jiannan (2009). "The NP-completeness of Completing Partial anti-symmetric Latin squares" (PDF). Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009). Academy Publisher. pp. 322–324. ISBN 978-952-5726-06-0. See page 324. 978-952-5726-06-0 ↩

  10. Mileva, A.; Dimitrova, V. (2009). "Quasigroups constructed from complete mappings of a group (Z2n,⊕)" (PDF). Contributions, Sec. Math. Tech. Sci., MANU/MASA. XXX (1–2): 75–93. ISSN 0351-3246. See page 78. http://manu.edu.mk/contributions/NMBSci/Papers/2009_5_Mileva.pdf ↩

  11. Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (in German). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162. http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf ↩

  12. Beliavscaia, Galina; Izbaş, Vladimir; Şcerbacov, Victor (2003). "Check character systems over quasigroups and loops" (PDF). Quasigroups and Related Systems. 10 (1): 1–28. ISSN 1561-2848. See page 23. http://www.math.md/files/qrs/v10-n1/v10-n1-(pp1-28).pdf ↩

  13. Damm, H. Michael (2003). "On the Existence of Totally Anti-Symmetric Quasigroups of Order 4k + 2". Computing. 70 (4): 349–357. doi:10.1007/s00607-003-0017-3. ISSN 0010-485X. S2CID 31659430. /wiki/Doi_(identifier) ↩

  14. Damm, H. Michael (2007). "Totally anti-symmetric quasigroups for all orders n ≠ 2, 6". Discrete Mathematics. 307 (6): 715–729. doi:10.1016/j.disc.2006.05.033. ISSN 0012-365X. https://doi.org/10.1016%2Fj.disc.2006.05.033 ↩

  15. Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (in German). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162. http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf ↩

  16. Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (in German). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162. http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf ↩

  17. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  18. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  19. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  20. Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9. 978-1-60805-883-9 ↩

  21. Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (in German). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162. http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf ↩