Content deleted Content added
→Source code: Removing section: this adds nothing to the already clear description: it has no illustrative value |
m Reverted edits by 2603:8001:4500:1199:D4A5:3404:C186:3731 (talk) (AV) |
||
| (109 intermediate revisions by 54 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 {{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" />
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
# 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
#The resulting interim digit gives the check digit and will be appended as trailing digit to the number.<ref name=fenwick2014 />
== Example ==
The
{| class="skin-invert wikitable" style="text-align:center
|- style="color:#00A000"
|
|
|
|
|
|
|
|
|
|
|
|-
| 0
Line 64 ⟶ 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'''.
=== Graphical illustration ===
[[File:Check digit TA quasigroup dhmd111rr illustration eg5724.svg]]▼
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.
▲== 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 error]]s.)<ref name=dhmd /> But the Damm algorithm has the benefit that it makes do without the dedicatedly constructed [[permutation]]s and its position specific [[Exponentiation#In_abstract_algebra|powers]] being inherent in the [[Verhoeff algorithm|Verhoeff scheme]]. Furthermore, a table of [[Inverse element|inverses]] can be dispensed with provided all diagonal entries of the operation table are zero.
▲[[File:Check digit TA quasigroup dhmd111rr illustration eg5724.svg]]
▲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#ISBN-10_check_digit_calculation|ISBN-10]] [[Check_digit#ISBN_10|check digit]] scheme).
== References ==▼
▲Prepending leading zeros does not affect the check digit.
{{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'' ≠ 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|last1=Beliavscaia|first1=Galina|last2=Izbaş|first2=Vladimir|last3=Şcerbacov|first3=Victor|title=Check character systems over quasigroups and loops |journal=Quasigroups and Related Systems |volume=10 |issue=1|pages=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<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 ==
▲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.
{{Wikibooks|Algorithm Implementation/Checksums/Damm Algorithm}}
*[[b:Algorithm Implementation/Checksums/Damm Algorithm|Damm validation & generation code in several programming languages]]
*[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]
▲== References ==
*[https://rosettacode.org/wiki/Damm_algorithm At RosettaCode.org, Implementations of the Damm algorithm in many programming languages]
{{DEFAULTSORT:Damm Algorithm}}
Line 129 ⟶ 164:
[[Category:Latin squares]]
[[Category:Group theory]]
[[Category:2004 introductions]]
| |||