Content deleted Content added
m Reverted edits by 2603:8001:4500:1199:D4A5:3404:C186:3731 (talk) (AV) |
|||
| (31 intermediate revisions by 21 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
== 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
The Damm algorithm
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.
== 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=(
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
{| class="skin-invert wikitable" style="text-align:center
|- style="color:#00A000"
|
|
|
|
|
|
|
|
|
|
|
|-
| 0
Line 93 ⟶ 90:
=== Calculating the check digit ===
{| class="skin-invert wikitable" style="text-align:center
|- style="color:#00A000"
!
|
|
|
|-
!
| '''0'''
| 9
| 7
|-
!
| 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
|- style="color:#00A000"
!
|
|
|
|
|-
!
| '''0'''
| 9
| 7
| 4
|-
!
| 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 (
[[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'' + 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''
<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
<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<sub>2</sub><sup>n</sup>,
}}
Line 158 ⟶ 155:
{{Wikibooks|Algorithm Implementation/Checksums/Damm Algorithm}}
*[[b:Algorithm Implementation/Checksums/Damm Algorithm|Damm validation & generation code in several programming languages]]
*[
*[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}}
| |||