Damm algorithm: Difference between revisions

Revision as of 18:49, 14 April 2020

Latest revision as of 01:47, 8 June 2025

(29 intermediate revisions by 19 users not shown)

Line 1:

{{Short description|Check digit algorithm}}

In [[error detection]], the '''Damm algorithm''' is a [[check digit]] [[algorithm]] that detects all [[Transcription error|single-digit errors]] and all [[Transcription error#Transposition error|adjacent transposition errors]]. It was presented by H. Michael Damm in 2004.,<ref name="fenwick2014" /> as a part of his PhD dissertation entitled ''Totally Antisymmetric Quasigroups.''

== 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 error]]s, namely altering onea single digit, andor transposing two adjacent digits (including the transposition of the trailing check digit and the preceding digit).<ref name="fenwick2014" /><ref name="Salomon2005" /> But theThe Damm algorithm has the benefit that it makesdoes donot withouthave the dedicatedly constructed [[permutation]]s and its position -specific [[Exponentiation#In abstract algebra|powers]] being inherent inof the [[Verhoeff algorithm|Verhoeff scheme]]. Furthermore, aA table of [[Inverse element|inverses]] can also be dispensed with providedwhen all main diagonal entries of the operation table are zero.

The Damm algorithm doesgenerates not suffer from exceeding the number ofonly 10 possible values, resulting inavoiding the need for using a non-digit character (such as the [[X]] in the [[ISBN#ISBN-10 check digit calculation|10-digit ISBN]] [[Check digit#ISBN_10|check digit]] scheme).

Prepending leading zeros does not affect the check digit (a weakness for variable-length codes).<ref name="fenwick2014" />

There are totally anti-symmetric quasigroups that detect all phonetic errors associated with the English language ({{nowrap|13 ↔ 30}}, {{nowrap|14 ↔ 40}}, ..., {{nowrap|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,<ref name="fenwick2014" /> so 1, 01, 001, etc. produce the same check digit. Consequently variable-length codes should not be verified together.

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

Since prepending leading zeros does not affect the check digit<ref name="fenwick2014" />, variable length codes should not be verified together since, e.g., 0, 01, and 001, etc. produce the same check digit. However, all checksum algorithms are vulnerable to this.

== Design ==

Its essential part is a [[quasigroup]] of [[Order (group theory)|order]] 10 (i.e. having a {{nowrap|10 × 10}} [[Latin square]] as the body of its [[Cayley table|operation table]]) with the special feature of being [[Quasigroup#Total antisymmetry|weakly totally anti-symmetric]].<ref name="dhmd" /><ref name="damm2007" /><ref group="lower-roman" name="BIS2003" /><ref group="lower-roman" name="Chen2009" /><ref group="lower-roman" name="Mileva2009" /> Damm revealed several methods to create totally anti-symmetric quasigroups of order 10 and gave some examples in his doctoral dissertation.<ref name="dhmd" /><ref group="lower-roman" name="BIS2003" /> With this, Damm also disproved an old conjecture that totally anti-symmetric quasigroups of order 10 do not exist.<ref name="damm2003" />

Line 23 ⟶ 21:

# {{math|1=(''c'' ∗ ''x'') ∗ ''y'' = (''c'' ∗ ''y'') ∗ ''x'' ⇒ ''x'' = ''y''}}

# {{math|1=''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 {{math|''n''}} is equivalent to the existence of a weak totally anti-symmetric quasigroup of order {{math|''n''}}. For the Damm algorithm with the check equation

{{math|1=(…...((0 ∗ ''x_m'') ∗ ''x''_''m''−1) ∗ …...) ∗ ''x''₀ = 0}},

a weak totally anti-symmetric quasigroup with the property

{{math|1=''x'' ∗ ''x'' = 0}}

Line 31 ⟶ 28:

== 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).<ref name="dhmd" /> It is useful if each main diagonal entry is {{math|0}},<ref name=fenwick2014 /> because it simplifies the check digit calculation.

=== Validating a number against the included check digit ===

# Set up an interim digit and initialize it to {{math|0}}.

# 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.

# The number is valid if and only if the resulting interim digit has the value of {{math|0}}.<ref name=fenwick2014 />

=== Calculating the check digit ===

'''Prerequisite:''' The main diagonal entries of the table are {{math|0}}.

#Set up an interim digit and initialize it to {{math|0}}.

#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.

#The resulting interim digit gives the check digit and will be appended as trailing digit to the number.<ref name=fenwick2014 />

== Example ==

The following operation table will be used.<ref name="fenwick2014" /> It may be obtained from the totally anti-symmetric quasigroup {{math|''x'' ∗ ''y''}} in Damm's doctoral dissertation page 111<ref name="dhmd" /> by rearranging the rows and changing the entries with the permutation {{math|1=''&phi;φ'' = (1&nbsp;2&nbsp;9&nbsp;5&nbsp;4&nbsp;8&nbsp;6&nbsp;7&nbsp;3)}} and defining {{math|1=''x'' &sdot;⋅ ''y'' = ''&phi;φ''^''&minus;1''(''&phi;φ''(''x'') ∗ ''y'')}}.

{| class="skin-invert wikitable" style="text-align:center;background:none;color:#E000E0"

|- style="color:#00A000"

| style="width:1.5em" | {{math|1=&sdot;⋅}}

| style="width:1.5em" | 0

| style="width:1.5em" | 1

| style="width:1.5em" | 2

| style="width:1.5em" | 3

| style="width:1.5em" | 4

| style="width:1.5em" | 5

| style="width:1.5em" | 6

| style="width:1.5em" | 7

| style="width:1.5em" | 8

| style="width:1.5em" | 9

|-

| 0

Line 93 ⟶ 90:

=== Calculating the check digit ===

{| class="skin-invert wikitable" style="text-align:center;background:none;color:#E000E0"

|- style="color:#00A000"

! style="color:black" | <span style="color:#00A000">digit to be processed</span> → column index

| style="width:1.5em" | 5

| style="width:1.5em" | 7

| style="width:1.5em" | 2

|-

! style="color:black" | old <span style="color:#E000E0">interim digit</span> → row index

| '''0'''

| 9

| 7

|-

! style="color:black" | table entry → new <span style="color:#E000E0">interim digit</span>

| 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 ===

{| class="skin-invert wikitable" style="text-align:center;background:none;color:#E000E0"

|- style="color:#00A000"

! style="color:black" | <span style="color:#00A000">digit to be processed</span> → column index

| style="width:1.5em" | 5

| style="width:1.5em" | 7

| style="width:1.5em" | 2

| style="width:1.5em" | 4

|-

! style="color:black" | old <span style="color:#E000E0">interim digit</span> → row index

| '''0'''

| 9

| 7

| 4

|-

! style="color:black" | table entry → new <span style="color:#E000E0">interim digit</span>

| 9

| 7

| 4

| '''0'''

|}

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

Line 137 ⟶ 134:

=== Graphical illustration ===

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

[[File:Check digit TA quasigroup dhmd111rr illustration eg5724.svg]]

Line 144 ⟶ 141:

{{reflist|refs=

<ref name="dhmd">{{cite book |last=Damm |year=2004 |first=H. Michael |title=Total anti-symmetrische Quasigruppen |type=Dr. rer. nat. |publisher=Philipps-Universität Marburg |url=http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf |id=[http://nbn-resolving.de/urn:nbn:de:hebis:04-z2004-05162 urn:nbn:de:hebis:04-z2004-05162]|language=de}}</ref>

<ref name="damm2003">{{cite journal |last=Damm |year=2003 |first=H. Michael |title=On the Existence of Totally Anti-Symmetric Quasigroups of Order 4''k''&nbsp;+&nbsp;2 |journal=Computing |volume=70 |issue=4 |pages=349–357 |issn=0010-485X |doi=10.1007/s00607-003-0017-3 |s2cid=31659430 }}</ref>

<ref name="damm2007">{{cite journal |last=Damm |year=2007 |first=H. Michael |title=Totally anti-symmetric quasigroups for all orders ''n''&ne; ≠ 2, 6 |journal=Discrete Mathematics |volume=307 |issue=6 |pages=715–729 |issn=0012-365X |doi=10.1016/j.disc.2006.05.033 |doi-access=free }}</ref>

<ref name="fenwick2014">{{cite book |last=Fenwick |year=2014 |first=Peter |editor1-first=Peter |editor1-last=Fenwick |title=Introduction to Computer Data Representation |chapter=Checksums and Error Control |doi=10.2174/9781608058822114010013 |pages=[http://ebooks.benthamscience.com/sample/9781608058822/51/ 191–218] |publisher=Bentham Science Publishers |isbn=978-1-60805-883-9 }}</ref>

<ref name="Salomon2005">For the types of common errors and their frequencies, see {{cite book |last=Salomon |year=2005 |first=David |title=Coding for Data and Computer Communications |publisher=Springer Science+Business Media, Inc. |pages=36 |url=https://books.google.com/books?id=Zr9bjEpXKnIC&pg=PA36 |isbn=978-0387-21245-6 }}</ref>

}}

{{reflist|group=lower-roman|refs=

<ref group="lower-roman" name="BIS2003" >{{cite journal |year=2003 |author1last1=[http://www.math.md/people/beliavscaia-galina/ Beliavscaia |first1=Galina] |author2last2=[http://www.math.md/people/izbas-vladimir/ Izbaş |first2=Vladimir] |author3last3=[http://www.math.md/people/scerbacov-victor/ Şcerbacov |first3=Victor] |title=Check character systems over quasigroups and loops |journal=Quasigroups and Related Systems |volume=10 |issue=[http://www.math.md/en/publications/qrs/issues/v10–n1/ 1] |pages=[http://www.math.md/en/publications/qrs/issues/v10–n1/10592/ 1–28] |url=http://www.math.md/files/qrs/v10-n1/v10-n1-(pp1-28).pdf |issn=1561-2848 }} See page 23.</ref>

<ref group="lower-roman" name="Chen2009">{{cite book |author=Chen Jiannan |year=2009 |chapter=The NP-completeness of Completing Partial anti-symmetric Latin squares |pages=[http://www.academypublisher.com/proc/iwisa09/papers/iwisa09p322.htm 322–324] |chapter-url=http://www.academypublisher.com/proc/iwisa09/papers/iwisa09p322.pdf |title=Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009) |url=http://www.academypublisher.com/proc/iwisa09/ |publisher=Academy Publisher |isbn=978-952-5726-06-0 }} See page 324.</ref>

<ref group="lower-roman" name="Mileva2009">{{cite journal |date=2009 |last1=Mileva |first1=A. |last2=Dimitrova |first2=V. |title=Quasigroups constructed from complete mappings of a group (Z₂ⁿ,&oplus;⊕) |journal=Contributions, Sec. Math. Tech. Sci., MANU/MASA |volume=XXX |issue=1–2 |pages=75–93 |url=http://manu.edu.mk/contributions/NMBSci/Papers/2009_5_Mileva.pdf |issn=0351-3246 }} See page 78.</ref>

}}

Line 158 ⟶ 155:

{{Wikibooks|Algorithm Implementation/Checksums/Damm Algorithm}}

*[[b:Algorithm Implementation/Checksums/Damm Algorithm|Damm validation & generation code in several programming languages]]

*[httphttps://blogwww.cantab-ip.com/blog/2014/01/20/new-format-for-singapore-ip-application-numbers-at-ipos/ Practical application in Singapore]

*[http://www.md-software.de/math/DAMM_Quasigruppen.txt Quasigroups for the Damm algorithm up to order 64]

*[https://rosettacode.org/wiki/Damm_algorithm At RosettaCode.org, Implementations of the Damm algorithm in many programming languages]

{{DEFAULTSORT:Damm Algorithm}}