Content deleted Content added
→Strengths and weaknesses: fixing grammar, assuming the sentence was negative |
m Reverted edits by 2603:8001:4500:1199:D4A5:3404:C186:3731 (talk) (AV) |
||
| (14 intermediate revisions by 10 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 ==
Line 27 ⟶ 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=''φ'' = (1 2 9 5 4 8 6 7 3)}} and defining {{math|1=''x'' ⋅ ''y'' = ''φ''<sup>
{| class="skin-invert wikitable" style="text-align:center
|- style="color:#00A000"
|
|
|
|
|
|
|
|
|
|
|
|-
| 0
Line 89 ⟶ 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"
!
|
|
|
▲| style="width:1.5em" | 4
|-
!
| '''0'''
| 9
| 7
| 4
|-
!
| 9
| 7
| 4
| '''0'''▼
▲|'''0'''
|}
The resulting interim digit is '''0''', hence the number is '''valid'''.
Line 144 ⟶ 142:
<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>
Line 157 ⟶ 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]
| |||