The Laws of Cryptography:
Digression: Dihedral Error Detection

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 }

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

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


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