Verhoeff algoritm

Verhoeff -algoritmen är en kontrollsummaformel för feldetektering utvecklad av den holländska matematikern Jacobus Verhoeff och publicerades första gången 1969. Det var den första decimala kontrollsiffransalgoritm som upptäcker alla ensiffriga fel, och alla transponeringsfel som involverar två intilliggande siffror, vilket ansågs vid den tiden vara omöjligt med en sådan kod.

Mål

Verhoeff hade som mål att hitta en decimalkod - en där kontrollsiffran är en enda decimalsiffra - som upptäckte alla ensiffriga fel och alla transponeringar av intilliggande siffror. På den tiden gjorde förmodade bevis på att dessa koder inte fanns, bas-11-koder populära, till exempel i ISBN-kontrollsiffran .

Hans mål var också praktiska, och han baserade utvärderingen av olika koder på livedata från det holländska postsystemet, med hjälp av ett viktat poängsystem för olika typer av fel. Analysen delade upp felen i ett antal kategorier: för det första efter hur många siffror som är felaktiga; för de med två siffror felaktiga finns transpositioner ( ab → ba ), tvillingar ( aa → 'bb'), hopptranspositioner ( abc → cba ), fonetiska ( 1a → a0 ) och hopptvillingar ( aba → cbc ). Dessutom finns utelämnade och tillagda siffror. Även om frekvensen för vissa av dessa typer av fel kan vara små, kan vissa koder vara immuna mot dem förutom de primära målen att upptäcka alla singlar och transpositioner.

Särskilt de fonetiska felen visade språkliga effekter, för på nederländska läses siffror vanligtvis i par; och även medan 50 låter som 15 på holländska, låter 80 inte som 18.

Med sexsiffriga siffror som exempel rapporterade Verhoeff följande klassificering av felen:.

Felaktiga siffror	Klassificering	Räkna	Frekvens
1	Transkription	9,574	79,05 %
2	Transponeringar	1 237	10,21 %
	tvillingar	67	0,55 %
	Fonetisk	59	0,49 %
	Annat intilliggande	232	1,92 %
	Hoppa översättningar	99	0,82 %
	Hoppa tvillingar	35	0,29 %
	Andra hoppfel	43	0,36 %
	Övrig	98	0,81 %
3		169	1,40 %
4		118	0,97 %
5		219	1,81 %
6		162	1,34 %
Total		12.112

Beskrivning

Den allmänna idén med algoritmen är att representera var och en av siffrorna (0 till 9) som element i den dihedriska gruppen $D_{5}$ . Det vill säga mappa siffror till ${\displaystyle D_{5}} ,$ manipulera dessa och mappa sedan tillbaka till siffror. Låt denna mappning vara $m:[0,9]\to D_{5}$

$7&8&r&9 2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\end{pmatrix}}}$

Låt den n:te siffran vara $a_{n}$ och låt antalet siffror vara $k$ .

Till exempel med koden 248 är $k$ 3 och $a_{3}=m(8)=r^{3}s$ .

Definiera nu permutationen $f:D_{5}\to D_{5}$

$f={ \begin{pmatrix}e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\\r&s&r^{2}s&rs&r^{2}&r^ {3}s&r^{3}&e&r^{4}s&r^{4}\end{pmatrix}}$

Till exempel $f(r^{3})=rs$ . Ett annat exempel är $f^{2}(r^{3})=r^{3}$ eftersom $f(f(r^{3}))=f(rs)=r^{3}$

Genom att använda multiplikativ notation för gruppoperationen av $D_{5}$ är kontrollsiffran då helt enkelt ett värde $c$ så att

$f(a_{1})\cdot f^{2}(a_ {2})\cdot \ldots \cdot f^{k}(a_{k})\cdot f^{k+1}(c)=e$

$c$ ges explicit av invers permutation

$c=f^{-1-k}\left(\prod _{n=1}^{k} f^{n}(a_{n})^{-1}\höger)$

Till exempel är kontrollsiffran för 248 5. För att verifiera detta, använd mappningen till $D_{5}$ och infoga i LHS för föregående ekvation

$f(r^{2})\cdot f^{2}(r^{ 4})\cdot f^{3}(r^{3}s)\cdot f^{4}(s)=e$

För att snabbt utvärdera denna permutation använd det

$f^{4}(s)=f^{3}(r^ {3}s)=f^{2}(r^{4})=f(r^{2})=r^{2}s$

att få det

$r^{2}s\cdot r^{2}s\cdot r^{2}s\cdot r^{2}s =e$

Detta är samma reflektion som multipliceras iterativt. Använd att reflektioner är deras egen invers.

$(r^{2}s\cdot r^{2}s)\cdot (r^{2 }s\cdot r^{2}s)=e^{2}=e$

I praktiken implementeras algoritmen med enkla uppslagstabeller utan att behöva förstå hur man genererar dessa tabeller från den underliggande grupp- och permutationsteorin. Detta anses mer korrekt vara en familj av algoritmer, eftersom andra permutationer också fungerar. Verhoeffs noterar att den speciella permutationen, som ges ovan, är speciell eftersom den har egenskapen att detektera 95,3% av de fonetiska felen.

Algoritmens styrkor är att den upptäcker alla translitterations- och transponeringsfel, och dessutom de flesta tvilling-, tvillinghopp-, hopptranspositions- och fonetiska fel.

Den största svagheten med Verhoeff-algoritmen är dess komplexitet. De beräkningar som krävs kan inte enkelt uttryckas som en formel i säg ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$ . Uppslagstabeller krävs för enkel beräkning. En liknande kod är Damm-algoritmen , som har liknande egenskaper.

Tabellbaserad algoritm

Verhoeff-algoritmen kan implementeras med hjälp av tre tabeller: en multiplikationstabell d , en inverstabell inv och en permutationstabell p .

$d(j,k)$		k
		0	1	2	3	4	5	6	7	8	9
j	0	0	1	2	3	4	5	6	7	8	9
	1	1	2	3	4	0	6	7	8	9	5
	2	2	3	4	0	1	7	8	9	5	6
	3	3	4	0	1	2	8	9	5	6	7
	4	4	0	1	2	3	9	5	6	7	8
	5	5	9	8	7	6	0	4	3	2	1
	6	6	5	9	8	7	1	0	4	3	2
	7	7	6	5	9	8	2	1	0	4	3
	8	8	7	6	5	9	3	2	1	0	4
	9	9	8	7	6	5	4	3	2	1	0

j	$inv(j)$
0	0
1	4
2	3
3	2
4	1
5	5
6	6
7	7
8	8
9	9

$p(pos,num)$		num
		0	1	2	3	4	5	6	7	8	9
pos (mod 8)	0	0	1	2	3	4	5	6	7	8	9
	1	1	5	7	6	2	8	3	0	9	4
	2	5	8	0	3	7	9	6	1	4	2
	3	8	9	1	6	0	4	3	5	2	7
	4	9	4	5	3	1	2	6	8	7	0
	5	4	2	8	6	5	7	3	9	0	1
	6	2	7	9	3	8	0	6	4	1	5
	7	7	0	4	6	9	1	3	2	5	8

Den första tabellen, d , är baserad på multiplikation i den dihedriska gruppen D ₅ . och är helt enkelt Cayley-bordet i gruppen. Observera att denna grupp inte är kommutativ , det vill säga för vissa värden på j och k , d ( j , k ) ≠ d ( k , j ).

Den inversa tabellen inv representerar den multiplikativa inversen av en siffra, det vill säga värdet som uppfyller d ( j , inv ( j )) = 0.

Permutationstabellen p tillämpar en permutation på varje siffra baserat på dess position i talet. Detta är faktiskt en enda permutation (1 5 8 9 4 2 7 0)(3 6) tillämpad iterativt; dvs p ( i + j , n ) = p ( i , p ( j , n )).

Verhoeffs kontrollsummaberäkning utförs enligt följande:

1. ₀ Skapa en array n av de individuella siffrorna i numret, tagna från höger till vänster (siffran längst till höger är n , etc.).
2. Initiera kontrollsumman c till noll.
3. För varje index i i arrayen n, med början på noll, ersätt c med $d(c,p(i{\bmod {8}},n_{ i}))$ .

Det ursprungliga numret är giltigt om och endast om $c=0$ .

0 För att generera en kontrollsiffra, lägg till en , utför beräkningen: den korrekta kontrollsiffran är $inv(c)$ .

Exempel

Generera en kontrollsiffra för 236 :

i	n i	p ( i,n i )	c
0	0	0	0
1	6	3	3
2	3	3	1
3	2	1	2

c är 2, så kontrollsiffran är inv (2), vilket är 3.

Validera kontrollsiffran 2363 :

i	n i	p ( i,n i )	c
0	3	3	3
1	6	3	1
2	3	3	4
3	2	1	0

c är noll, så kontrollen är korrekt.

externa länkar

• Detaljerad beskrivning av Verhoeff-algoritmen