by Neal R. Wagner
Copyright © 2001 by Neal R. Wagner. All rights reserved.
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));
// test all adjacent transpositions
System.out.println("\nThe straight dihedral group");
System.out.println("\nTest all adjacent transpositions");
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
}
? 49588 58802 3606 8 49588 58802 3606 true 8 49598 58802 3606 false The straight dihedral group Test all adjacent transpositions 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