Talk:Damm algorithm

Contested PROD

This article was proposed for deletion with rationale This article presents original research, which is not permitted by our policies. Unless you can add reliable and independent sources, which attest to the subject's notability, your article will be deleted. Thank you for your understanding. This seems wrong and I have contested the PROD since the article does indeed cite reliable sources, namely a peer-reviewed academic journal, and our policy on original research is a prohibition on editors directly publishing their own unsupported work in an article -- it does not mean that we cannot report research published in independent reliable sources, which this appears to do. Deltahedron (talk) 07:33, 22 December 2012 (UTC)

totally anti-symmetric

What does "totally anti-symmetric" mean in the context of this article? What other wikipedia article talks about the kind of "anti-symmetric" and "totally anti-symmetric" alluded to here?

At first I thought maybe that phrase should link to antisymmetric matrix, but the table given in this article doesn't seem to meet the definition given in that article. --DavidCary (talk) 17:29, 30 May 2014 (UTC)

The references define this. Example:

A quasigroup (Q,*) is called totally anti-symmetric if (c*x)*y=(c*y)*x ⇒ x=y and x*y=y*x ⇒ x=y.

Good catch, though, this article should define this. —Quondum 20:32, 30 May 2014 (UTC)

Dear reader,

I suspect this idea of a "totally anti-symmetric quasigroup" may be more widely useful than this one particular algorithm, and so should be mentioned -- or perhaps already is mentioned, using some other name -- in other Wikipedia articles.

If you know some other name for this idea, or some other Wikipedia article where it is relevant, please mention it here or in the article.

Thank you, Quondum, for adding that definition to the article. --DavidCary (talk) 19:57, 8 June 2014 (UTC)

Algorithm?

I can't find description of algorithm that would match the one given in this article and used in example. References define that an m-digit sequence $d_{m}d_{m-1}d_{m-2}\ldots d_{1}$ with a check digit $d_{0}$ shall satisfy $((\ldots ((d_{m}*d_{m-1})*d_{m-2})*\ldots )*d_{1})*d_{0}=0$ where $d_{m},\ldots ,d_{0}\in Q$ and $(Q,*)$ is a totally anti-symmetric quasigroup. The step-by-step description of algorithm in this article uses interim digit with fixed initial value of 0 which means that a slightly different equation is used, i.e. $((\ldots ((0*d_{m})*d_{m-1})*\ldots )*d_{1})*d_{0}=0$. I don't see any problem with this itself, because it's the same as computing with tacitly leading zero prefix, so all the properties should still hold. However, the example then uses a quasigroup which not totally anti-symmetric, because, for example 2 * 5 = 5 * 2. It is only weak totally anti-symmetric. With weak totally anti-symmetric quasigroup, check digit calculated using the original formula as given in references would fail to detect adjacent transpositions, e.g. both 257 and 527 would have a correct check digit. The scheme, nevertheless, appears to work exactly because of the fixed initial 0. The recent edit added possible justification for this stating that for this modified equation only a weak totally anti-symmetric quasigroup with additional property of x ∗ x = 0 is needed. I can easily see that other statements (definition of weak totally anti-symmetric, and that existence of weak of given order implies existence of totally anti-symmetric and that one can be constructed from another with appropriate permutation) are present in the referenced dissertation (and they are restated later in English in ScienceDirect article, referenced as well), but I can't find anything about using fixed prefix. Did I miss something or are we missing some important references? — mwgamera (talk) 19:11, 29 June 2014 (UTC)

The reference is:

Fenwick, Peter (2014). "Checksums and Error Control". Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9.

Assuming a number with digits numbered left to right d₁d₂d₃d₄ . . . and a “working digit” w we then –

1. Set w = 0
2. Successively set w = M[w, d_i], working from the left (row w, column d_i of the matrix).
3. Append the final w as the check digit.

--W96 (talk) 18:58, 18 January 2015 (UTC)

Sorry for lack of earlier reply even though I especially bugged you about this. I can't check that reference, but I imagine it must have description of conditions that M[·,·] must satisfy and WTA-quasigroup operation satisfies them — in which case, that's what was needed here. Thanks for adding it. — mwgamera (talk) 23:51, 26 January 2015 (UTC)

In which cases does rearranging the rows not work?

Rearranging the rows of the body of the table in conjuntion with changing the entries correspondingly is done as follows:

Let e be the digit that shall be in the main diagonal (x*x=e for all x∈Q).
(In the example is e=0.)

Then find the fixed point f of the column permutation in the column with the header e.
(In the example is f=0.)

Create a new empty operation table.

Copy the header row of column headers from the old to the new table.

Do for each row of the old table the following:

• Find the column where the entry f is located and take its header value.
• Set the row header of this row in the new table to the held value of the column header of the old table.
• Furthermore, for all entries of the body of the old table that have the same value as this row header set these entries in the new table to the held value of the column header of the old table.

(Because of having different row headers, the rows in the new table are in a different order then the columns.)

Sort the rows of the new table into the same order as the columns with respect to the headers by rearranging the complete rows including their headers.

As we see, rearranging the rows does not work if and only if the column permutation in the column with the header e has no fixed point. Yet Damm has proved that in a TA/WTA-quasigroup each column permutation has exactly one fixed point. (See Damm's doctoral dissertation page 104, Lemma 7.2) Consequently, rearranging the rows works in all cases of quasigroups used in Damm algorithm.

--W96 (talk) 19:10, 18 January 2015 (UTC)

I am not quite sure what you mean with "rearranging the rows works" -- perhaps that the resulting quasigroup is still totally anti-symmetric? Well, I have not thought about your argument, but what I can say is that the table given on this Wikipedia page is not totally anti-symmetric, and hence the resulting checksum code does *not* detect all transposition errors. E.g. 41 and 14 both have checksum 1. While I am at it, I am confused as to why one would copy the quasigroup multiplication table from page 111 in Damm's thesis, which is inside a screenshot, instead of, say, taking the one on page 106... BlackFingolfin (talk) 08:49, 23 March 2015 (UTC)

After rearranging rows, the resulting quasigroup is weakly totally anti-symmetric. As you noticed 14 = 41, which violates the second requirement for TA-quasigroups. But notice that a14 ≠ a41 for all a ∈ Q and the algorithm described in the article uses a fixed prefix of a = 0 (interim digit initialized to 0), thus still detecting all adjacent transpositions. — mwgamera (talk) 16:18, 23 March 2015 (UTC)

You are of course completely right -- I stupidly overlooked the initial 0 in the algorithm and examples, ouch. Thanks for taking the time to set me straight :). BlackFingolfin (talk) 08:26, 24 March 2015 (UTC)

Trailing zeros?

The article explains that leading zeros have no effect on the checksum but that is probably not a weakness but a strength. If there is a weakness, surely it is that trailing zeros have no effect? 13, 130, 1300 and 13000 are all valid. An easy defence would be to reject all numbers ending in (one or more) zeros. Johnhwoods (talk) 08:44, 14 April 2024 (UTC)

Whilst I'm thinking about zeros, the weaknesses section says that no checksum algorithm is affected by leading zeros. But it looks to me like Verhoeff is.