The Laws of Cryptography:
Digression: Dihedral Error Detection

by Neal R. Wagner

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

Here is the a scheme using the dihedral group without any special permutations. Notice that 2/3 of all adjacent transpositions are detected (60 out of 90).

```// 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();
}
}

// DihedralErrorDetection.java: the dihedral group for decimal error detection
public class DihedralErrorDetection 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};

public static int insertCheck(int[] a) {
int check = 0;
for (int i = 1; i < a.length; i++)
check = op[check][ 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][ a[i] ];
if (check != 0) return false;
else return true;
}

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

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

System.out.println("\nThe straight dihedral group");
for (int p1 = 0; p1 < 10; p1++)
for (int p2 = 0; p2 < 10; p2++) {
if (p1 != p2) {
a[8] = p1; a[9] = p2;
DihedralErrorDetection.insertCheck(a);
// interchange
a[8] ^= a[9];
a[9] ^= a[8];
a[8] ^= a[9];
if (DihedralErrorDetection.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. Notice that 30 (out of 90) adjacent transpositions go undetected.
```? 49588 58802 3606
8 49588 58802 3606
true
8 49598 58802 3606
false

The straight dihedral group

Warning: Interchange of 0 and 1 not detected
Warning: Interchange of 0 and 2 not detected
Warning: Interchange of 0 and 3 not detected
Warning: Interchange of 0 and 4 not detected
Warning: Interchange of 0 and 5 not detected
Warning: Interchange of 0 and 6 not detected
Warning: Interchange of 0 and 7 not detected
Warning: Interchange of 0 and 8 not detected
Warning: Interchange of 0 and 9 not detected
Warning: Interchange of 1 and 0 not detected
Warning: Interchange of 1 and 2 not detected
Warning: Interchange of 1 and 3 not detected
Warning: Interchange of 1 and 4 not detected
Warning: Interchange of 2 and 0 not detected
Warning: Interchange of 2 and 1 not detected
Warning: Interchange of 2 and 3 not detected
Warning: Interchange of 2 and 4 not detected
Warning: Interchange of 3 and 0 not detected
Warning: Interchange of 3 and 1 not detected
Warning: Interchange of 3 and 2 not detected
Warning: Interchange of 3 and 4 not detected
Warning: Interchange of 4 and 0 not detected
Warning: Interchange of 4 and 1 not detected
Warning: Interchange of 4 and 2 not detected
Warning: Interchange of 4 and 3 not detected
Warning: Interchange of 5 and 0 not detected
Warning: Interchange of 6 and 0 not detected
Warning: Interchange of 7 and 0 not detected
Warning: Interchange of 8 and 0 not detected
Warning: Interchange of 9 and 0 not detected
At least one transposition undetected
```

Revision date: 2001-12-31. (Please use ISO 8601, the International Standard.)