The Laws of Cryptography:
Digression: Verhoeff's Error Detection

by Neal R. Wagner

NOTE: This site is obsolete. See book draft (in PDF):

Here is Verhoeff's scheme using the dihedral group using special permutations. Notice that all adjacent transpositions are detected.

```// ErrorDetection.java: base class for single-digit error detection
public class ErrorDetection {

public static void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
if (a[i] == 10)
System.out.print("X ");
else
System.out.print(a[i]);
if (i%5 == 0) System.out.print(" ");
}
System.out.println();
}

public static void printUnchecked(int[] a) {
System.out.print("? ");
for (int i = 1; i < a.length; i++) {
System.out.print(a[i]);
if (i%5 == 0) System.out.print(" ");
}
System.out.println();
}
}

// VerhoeffErrorDetection.java: Implement Verhoeff's decimal error detection
public class VerhoeffErrorDetection extends ErrorDetection {

private static int[][] op= {
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{1, 2, 3, 4, 0, 6, 7, 8, 9, 5},
{2, 3, 4, 0, 1, 7, 8, 9, 5, 6},
{3, 4, 0, 1, 2, 8, 9, 5, 6, 7},
{4, 0, 1, 2, 3, 9, 5, 6, 7, 8},
{5, 9, 8, 7, 6, 0, 4, 3, 2 ,1},
{6, 5, 9, 8, 7, 1, 0, 4, 3, 2},
{7, 6, 5, 9, 8, 2, 1, 0, 4, 3},
{8, 7, 6, 5, 9, 3, 2, 1, 0, 4},
{9, 8, 7, 6, 5, 4, 3, 2, 1, 0} };

private static int[] inv = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};
private static int[][] F = new int[8][];
private static int[] F0 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
private static int[] F1 = {1, 5, 7, 6, 2, 8, 3, 0, 9, 4};

public VerhoeffErrorDetection() {
F[0] = F0;
F[1] = F1;
for (int i = 2; i < 8; i++) {
F[i] = new int[10];
for (int j = 0; j < 10; j++)
F[i][j] = F[i-1] [F[1][j]];
}
}

public static int insertCheck(int[] a) {
int check = 0;
for (int i = 1; i < a.length; i++)
check = op[check][ F[i % 8][a[i]] ];
a[0] = inv[check];
return a[0];
}

public static boolean doCheck(int[] a) {
int check = 0;
for (int i = 0; i < a.length; i++)
check = op[check][ F[i % 8][a[i]] ];
if (check != 0) return false;
else return true;
}

// main function
public static void main (String[] args) {
VerhoeffErrorDetection v = new VerhoeffErrorDetection();
int[] a = new int[15];
boolean checkFlag = false;
for (int i = 1; i < a.length; i++)
a[i] = (int)(Math.random() * 10.0);
VerhoeffErrorDetection.printUnchecked(a);
VerhoeffErrorDetection.insertCheck(a);
VerhoeffErrorDetection.printArray(a);
System.out.println(VerhoeffErrorDetection.doCheck(a));
a[4] = (a[4] + 1)%10;

VerhoeffErrorDetection.printArray(a);
System.out.println(VerhoeffErrorDetection.doCheck(a));

for (int p1 = 0; p1 < 10; p1++)
for (int p2 = 0; p2 < 10; p2++) {
if (p1 != p2) {
a[8] = p1; a[9] = p2;
VerhoeffErrorDetection.insertCheck(a);
// interchange
a[8] ^= a[9];
a[9] ^= a[8];
a[8] ^= a[9];
if (VerhoeffErrorDetection.doCheck(a)) {
System.out.println("Warning: Interchange of " + p1 +
" and " + p2 + " not detected");
checkFlag = true;
}
}
}
if (checkFlag)
System.out.println("At least one transposition undetected");
else
System.out.println("All transpositions detected");

} // end of main
}
```
Here is the output, showing a simple test, and a test of all adjacent interchanges. All interchange errors are detected.
```? 75787 12372 9429
1 75787 12372 9429
true
1 75797 12372 9429
false