Content deleted Content added
Protegmatic (talk | contribs) No edit summary |
|||
| (12 intermediate revisions by 6 users not shown) | |||
Line 1:
{{oldafdfull| date = 22 December 2012 (UTC) | result = '''keep''' | page = Damm algorithm }}{{WikiProject banner shell|class=Start}}
{{Broken anchors|links=
* <nowiki>[[Exponentiation#In abstract algebra|powers]]</nowiki> The anchor (#In abstract algebra) has been [[Special:Diff/1042507126|deleted by other users]] before. <!-- {"title":"In abstract algebra","appear":{"revid":297269046,"parentid":297268883,"timestamp":"2009-06-19T00:29:27Z","removed_section_titles":["Generalizations of exponentiation","Exponentiation in abstract algebra","Exponentiation over sets","Exponentiation in category theory","Exponentiation of cardinal and ordinal numbers"],"added_section_titles":["Generalizations","In abstract algebra","Over sets","In category theory","Of cardinal and ordinal numbers"]},"disappear":{"revid":1042507126,"parentid":1042500891,"timestamp":"2021-09-05T10:01:01Z","removed_section_titles":["In abstract algebra"],"added_section_titles":[]}} -->
}}
==Contested PROD==
Line 34 ⟶ 37:
The scheme, nevertheless, appears to work exactly because of the fixed initial 0.
The recent [https://en.wikipedia.org/w/index.php?title=Damm_algorithm&diff=prev&oldid=614858206 edit] added possible justification for this stating that for this modified equation only a weak totally anti-symmetric quasigroup with additional property of {{math|1=''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? — [[User:MwGamera|mwgamera]] ([[User talk:MwGamera|talk]]) 19:11, 29 June 2014 (UTC)
:The reference is:
:{{cite book |last=Fenwick |year=2014 |first=Peter |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 }}
<blockquote>
Assuming a number with digits numbered left to right <i>d<sub>1</sub>d<sub>2</sub>d<sub>3</sub>d<sub>4</sub></i> . . . and a “working digit” <i>w</i> we then –
# Set <i>w</i> = 0
# Successively set <i>w</i> = <i>M[w, d<sub>i</sub>]</i>, working from the left (row <i>w</i>, column <i>d<sub>i</sub></i> of the matrix).
# Append the final <i>w</i> as the check digit.
</blockquote>
:--[[User:W96|W96]] ([[User talk: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. — [[User:MwGamera|mwgamera]] ([[User talk: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).
<br>(In the example is e=0.)
Then find the fixed point f of the column permutation in the column with the header e.
<br>(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.
--[[User:W96|W96]] ([[User talk: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... [[User:BlackFingolfin|BlackFingolfin]] ([[User talk: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 ''a''14 ≠ ''a''41 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. — [[User:MwGamera|mwgamera]] ([[User talk: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 :). [[User:BlackFingolfin|BlackFingolfin]] ([[User talk: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. [[User:Johnhwoods|Johnhwoods]] ([[User talk: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.
| |||