Content deleted Content added
→External links: added link to quasigroups for the Damm algorithm |
m Reverted edits by 2603:8001:4500:1199:D4A5:3404:C186:3731 (talk) (AV) |
||
| (78 intermediate revisions by 43 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 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
=== 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
A quasigroup {{math|(''Q'', ∗)}} is called totally anti-symmetric if for all {{math|''c'', ''x'', ''y'' ∈ ''Q''}}, the following implications hold:<ref name="damm2007" />▼
▲Its essential part is a [[quasigroup]] of [[Order (group theory)|order]] 10 (i.e. having a 10×10 [[Latin square]] as [[Cayley table|operation table]]) with the special feature of being totally anti-symmetric. <ref name=dhmd /><ref name=damm2007 /><ref group=lower-roman name=BIS2003 /><ref group=lower-roman name=Chen2009 /> Damm revealed several methods to create such 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 />
▲A quasigroup {{math|(''Q'', ∗)}} is called totally anti-symmetric if for all {{math|''c'', ''x'', ''y'' ∈ ''Q''}}, the following implications hold:<ref name=damm2007 />
# {{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<sub>m</sub>'') ∗ ''x''<sub>''m''−1</sub>) ∗ ...) ∗ ''x''<sub>0</sub> = 0}},
a weak totally anti-symmetric quasigroup with the property
{{math|1=''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.<ref name="dhmd" />
== 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
=== 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 83 ⟶ 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 127 ⟶ 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 133 ⟶ 140:
== References ==
{{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]
<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
<ref name="damm2007">{{cite journal |last=Damm |year=2007 |first=H. Michael |title=Totally anti-symmetric quasigroups for all orders ''n''
<ref name=
<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=
<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>,⊕) |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>
}}
== External links ==
{{Wikibooks|Algorithm Implementation/Checksums/Damm Algorithm}}
*[[b:Algorithm Implementation/Checksums/Damm Algorithm|Damm validation & generation code in
*[https://www.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}}
Line 152 ⟶ 164:
[[Category:Latin squares]]
[[Category:Group theory]]
[[Category:2004 introductions]]
▲*[http://www.md-software.de/math/DAMM_Quasigruppen.txt Quasigroups for the Damm algorithm up to order 64]
| |||