Jävla algoritm
Vid feldetektering är Damm - algoritmen en kontrollsifferalgoritm som upptäcker alla ensiffriga fel och alla angränsande transponeringsfel . Den presenterades av H. Michael Damm 2004.
Styrkor och svagheter
Styrkor
Damm-algoritmen liknar Verhoeff-algoritmen . Den kommer också att upptäcka alla förekomster av de två vanligast förekommande typerna av transkriptionsfel , nämligen att ändra en enstaka siffra eller överföra två intilliggande siffror (inklusive transponeringen av den efterföljande kontrollsiffran och den föregående siffran). Damm-algoritmen har fördelen att den inte har de dedikerat konstruerade permutationerna och dess positionsspecifika krafter från Verhoeff-schemat . En tabell med inverser kan också undvaras när alla huvuddiagonala poster i operationstabellen är noll.
Damm-algoritmen genererar endast 10 möjliga värden och undviker behovet av ett icke-siffrigt tecken (som X i det 10-siffriga ISBN- kontrollsiffran ).
Inledande nollor påverkar inte kontrollsiffran (en svaghet för koder med variabel längd).
Det finns totalt antisymmetriska kvasigrupper som upptäcker alla fonetiska fel associerade med det engelska språket ( 13 ↔ 30 , 14 ↔ 40 , ..., 19 ↔ 90 ). Tabellen som används i det illustrerande exemplet är baserad på ett sådant fall.
Svagheter
För alla kontrollsummaalgoritmer, inklusive Damm-algoritmen, påverkar inte inledande nollor kontrollsiffran, så 1, 01, 001, etc. producerar samma kontrollsiffra. Koder med variabel längd bör därför inte verifieras tillsammans.
Design
Dess väsentliga del är en kvasigrupp av ordning 10 (dvs. med en 10 × 10 latinsk kvadrat som kroppen på sitt operationsbord ) med den speciella egenskapen att den är svagt totalt antisymmetrisk . Damm avslöjade flera metoder för att skapa totalt antisymmetriska kvasigrupper av ordning 10 och gav några exempel i sin doktorsavhandling. Med detta motbevisade Damm också en gammal gissning om att totalt antisymmetriska kvasigrupper av ordning 10 inte existerar.
En kvasigrupp ( Q , ∗) kallas totalt antisymmetrisk om för alla c , x , y ∈ Q , följande implikationer gäller:
- ( c ∗ x ) ∗ y = ( c ∗ y ) ∗ x ⇒ x = y
- x ∗ y = y ∗ x ⇒ x = y ,
och det kallas svagt totalt antisymmetriskt om bara den första implikationen håller. Damm bevisade att förekomsten av en totalt antisymmetrisk kvasigrupp av ordningen n är ekvivalent med förekomsten av en svag totalt antisymmetrisk kvasigrupp av ordningen n . För Damm-algoritmen med kontrollekvationen 0 (...((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x = 0 , en svag totalt antisymmetrisk kvasigrupp med egenskapen x ∗ x = 0 behövs. En sådan kvasigrupp kan konstrueras från vilken totalt antisymmetrisk kvasigrupp som helst genom att omarrangera kolumnerna på ett sådant sätt att alla nollor ligger på diagonalen. Och å andra sidan, från vilken som helst svag totalt antisymmetrisk kvasigrupp kan en totalt antisymmetrisk kvasigrupp konstrueras genom att omarrangera kolumnerna på ett sådant sätt att den första raden är i naturlig ordning.
Algoritm
Giltigheten för en siffersekvens som innehåller en kontrollsiffra definieras över en kvasigrupp. En kvasigrupptabell färdig att användas kan hämtas från Damms avhandling (sidorna 98, 106, 111). Det är användbart om varje huvuddiagonalpost är 0, eftersom det förenklar beräkningen av kontrollsiffran.
Validerar ett nummer mot den inkluderade kontrollsiffran
- Ställ in en interimssiffra och initiera den till 0.
- Bearbeta siffran siffra för siffra: Använd numrets siffra som kolumnindex och interimsiffran som radindex, ta tabellposten och ersätt mellansiffran med den.
- Numret är giltigt om och endast om den resulterande interimssiffran har värdet 0.
Beräknar kontrollsiffran
Förutsättning: De huvudsakliga diagonala posterna i tabellen är 0.
- Ställ in en interimssiffra och initiera den till 0.
- Bearbeta siffran siffra för siffra: Använd numrets siffra som kolumnindex och interimsiffran som radindex, ta tabellposten och ersätt mellansiffran med den.
- Den resulterande interimssiffran ger kontrollsiffran och kommer att läggas till som eftersiffra till numret.
Exempel
Följande operationstabell kommer att användas. Den kan erhållas från den totalt antisymmetriska kvasigruppen x ∗ y i Damms doktorsavhandling sida 111 genom att ordna om raderna och ändra posterna med permutationen φ x ⋅ y φ −1 ( φ ( x ) ∗ y ) = (1 2 9 5 4 8 6 7 3) och definiera .
| ⋅ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
| 1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
| 2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
| 3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
| 4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
| 5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
| 6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
| 7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
| 8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 5 |
| 9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
Antag att vi väljer numret (sifferföljden) 572 .
Beräknar kontrollsiffran
| siffra som ska bearbetas → kolumnindex | 5 | 7 | 2 |
|---|---|---|---|
| gammal mellansiffra → radindex | 0 | 9 | 7 |
| tabellpost → ny interimssiffra | 9 | 7 | 4 |
Den resulterande interimssiffran är 4 . Detta är den beräknade kontrollsiffran. Vi lägger det till numret och får 5724 .
Validerar ett nummer mot den inkluderade kontrollsiffran
| siffra som ska bearbetas → kolumnindex | 5 | 7 | 2 | 4 | |
|---|---|---|---|---|---|
| gammal mellansiffra → radindex | 0 | 9 | 7 | 4 | |
| tabellpost → ny interimssiffra | 9 | 7 | 4 | 0 |
0 Den resulterande interimssiffran är , därför är numret giltigt .
Grafisk illustration
Detta är exemplet ovan som visar detaljerna i algoritmen som genererar kontrollsiffran (streckad blå pil) och verifierar siffran 572 med kontrollsiffran.
