Damm algorithm: Difference between revisions

Revision as of 05:05, 24 January 2013

Revision as of 17:31, 26 January 2013

Line 1:

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. 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 TA-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 TA-quasigroups of order 10 do not exist.<ref name=damm2003 />

== Algorithm ==

Line 6:

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

#Set up an interim digit and initialize it to 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 bywith it.

#The number is valid if and only if the resulting interim digit has the value of 0.

Line 12:

'''Prerequisite:''' The diagonal entries of the table are 0.

#Set up an interim digit and initialize it to 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 bywith it.

#The resulting interim digit gives the check digit and will be appended as trailing digit to the number.

Line 122:

== References ==

{{reflist|refs=

<ref name=dhmd>{{cite book |last=Damm |date=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://archiv.ub.uninbn-marburgresolving.de/diss/urn:nbn:de:hebis:04-z2004/0516/-05162 urn:nbn:de:hebis:04-z2004-05162]}}{{De icon}}</ref>

<ref name=damm2003>{{cite journal | last=Damm | date=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 | url=http://link.springer.com/article/10.1007%2Fs00607-003-0017-3 |issn=0010-485X |doi=10.1007/s00607-003-0017-3 }}</ref>

<ref name=Kirtland2001damm2007>{{cite bookjournal | last=KirtlandDamm | date=20012007 | first=JosephH. |Michael |title=IdentificationTotally Numbersanti-symmetric andquasigroups Checkfor Digitall Schemesorders ''n''&ne;2,6 | publisherjournal=Mathematical Association ofDiscrete AmericaMathematics | seriesvolume=Classroom Resource Materials307 |issue=6 |pages=4-5715–729 | url=http://bookswww.googlesciencedirect.com/books?id=npTxORxmLosC&pg=PA4science/article/pii/S0012365X06004225 |issn=0012-365X isbn|doi=978088385720510.1016/j.disc.2006.05.033 }}</ref>

<ref name=Kirtland2001>{{cite book |last=Kirtland |date=2001 |first=Joseph |title=Identification Numbers and Check Digit Schemes |publisher=Mathematical Association of America |series=Classroom Resource Materials |pages=4-5 |url=http://books.google.com/books?id=npTxORxmLosC&pg=PA4 |isbn=978-0-88385-720-5 }}</ref>

}}

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

<ref group=lower-roman name=BIS2003 >{{cite journal |date=2003 |author1=[http://www.math.md/people/beliavscaia-galina/ Beliavscaia Galina] |author2=[http://www.math.md/people/izbas-vladimir/ Izbaş Vladimir] |author3=[http://www.math.md/people/scerbacov-victor/ Şcerbacov Victor] |title=Check character systems over quasigroups and loops |journal=[http://www.math.md/en/publications/qrs/ 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 |date=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/ |editor1=Feng Gao |editor2=Xijun Zhu |publisher=[http://www.academypublisher.com/ Academy Publisher] |isbn=978-952-5726-06-0 }} See page 324.</ref>

}}

*{{cite journal | last=Damm | date=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 | url=http://www.sciencedirect.com/science/article/pii/S0012365X06004225 }}

== External links ==

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

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