The Laws of Cryptography:
The Hamming Mod 11 Code: Double 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 a Java program that simulates random double errors. There are two input parameters on the command line: the number of simulation trials to run, and the number of digits to use. The program identifies various outcomes:

Outcome % for 18 digits % for 121 digits
Positions 1 and 11 give location of error,
but position 0 gives amount of error as 0.
    9.19%  10.00%
The check tries to correct an error with
location out of range of the number.
  75.01%    0.00%
Check tries to do single error correction
with a ten (X) somewhere besides
positions 0, 1, or 11
    1.30%    8.51%
Misses error: miscorrects as if
there were a single error
  14.44%  81.48%

Thus, with 18 digits, only 14.4% of double errors get "corrected" as if there were a single error, while with 121 digits 81.5% are miscorrected in this way.


// H11ED.java: Implement the mod 11 Hamming code public class H11ED { public static int[] inv = {0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; public static int totalTrials, misCorrected = 0, errorZero = 0, toTen = 0, subscriptRange = 0, allZero = 0; public static int arraySize; // Using the sum1 check sum, if have error e and check1 result c, // then pos[e][c] gives the position in error (modulo 11), // using the first check equation. // If the error is e and check11 result is c, // then pos[e][c] gives the value position/11. public static int[][] pos = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {0, 6, 1, 7, 2, 8, 3, 9, 4, 10, 5}, {0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7}, {0, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8}, {0, 9, 7, 5, 3, 1, 10, 8, 6, 4, 2}, {0, 2, 4, 6, 8, 10, 1, 3, 5, 7, 9}, {0, 8, 5, 2, 10, 7, 4, 1, 9, 6, 3}, {0, 7, 3, 10, 6, 2, 9, 5, 1, 8, 4}, {0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6}, {0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}}; 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("? "); // position 0 System.out.print("?"); // position 1 for (int i = 2; i < a.length; i++) { if (i == 11) System.out.print("?"); // position 11 else System.out.print(a[i]); if (i%5 == 0) System.out.print(" "); } System.out.println(); } public static void insertCheck(int[] a) { a[1] = inv[sum1NoCheck(a)]; a[11] = inv[sum11NoCheck(a)]; a[0] = inv[sum0NoCheck(a)]; // if (!doCheck(a)) // System.out.println("Failure in insertCheck"); } public static boolean doCheck(int[] a) { int error = sum0(a); // amount of error int check1 = sum1(a); int check11 = sum11(a); if (error == 0 && check1 == 0 && check11 == 0) { allZero++; return true; } if (error == 0) { // System.out.println("Double error: check 0 is zero"); errorZero++; return false; // a double error } int position = pos[error][check11]*11 + pos[error][check1]; if (position >= a.length) { subscriptRange++; // System.out.println("Doouble error:" + // " subscript error, position: " + position + // ", error: " + error + ", check1: " + check1 + // ", check11: " + check11); // System.exit(0); return false; } a[position] = (a[position] - error + 11)%11; if (a[position] == 10 && (position != 0 && position != 1 && position != 11)) { // System.out.println("Double error: corrected to 10"); toTen++; return false; } // System.out.println("Position " + position + " corrected to " + // a[position]); misCorrected++; return true; } public static int sum0(int[] a) { int check = 0; for (int i = 0; i < a.length; i++) check = (check + a[i])%11; return check; } public static int sum0NoCheck(int[] a) { int check = 0; for (int i = 1; i < a.length; i++) check = (check + a[i])%11; return check; } public static int sum1(int[] a) { int check = 0; for (int i = 0; i < a.length; i++) check = (check + (i%11)*a[i])%11; return check; } public static int sum1NoCheck(int[] a) { int check = 0; for (int i = 2; i < a.length; i++) check = (check + (i%11)*a[i])%11; return check; } public static int sum11(int[] a) { int check = 0; for (int i = 0; i < a.length; i++) check = (check + ((i/11)%11)*a[i])%11; return check; } public static int sum11NoCheck(int[] a) { int check = 0; for (int i = 12; i < a.length; i++) check = (check + ((i/11)%11)*a[i])%11; return check; } // main function public static void main (String[] args) { totalTrials = Integer.parseInt(args[0]); // total num of trials arraySize = Integer.parseInt(args[1]); // size of array int[] a = new int[arraySize]; int loc1, loc2; boolean checkFlag = false; // start with random word for (int i = 2; i < a.length; i++) if (i != 11) a[i] = (int)(Math.random() * 10.0); H11ED.insertCheck(a); for (int i = 0; i < totalTrials; i++) { // try random pair of errors, choose 2 distinct random ints loc1 = (int)(Math.random() * a.length); do { loc2 = (int)(Math.random() * a.length); } while (loc1 == loc2); // System.out.print("Locs: " + loc1 + " " + loc2); // System.out.print(", Values: " + a[loc1] + " " + a[loc2]); // make a random pair of changes a[loc1] = (a[loc1] + (int)(Math.random() * 9.0 + 1.0))%10; a[loc2] = (a[loc2] + (int)(Math.random() * 9.0 + 1.0))%10; // System.out.println(", New Values: " + a[loc1] + " " + a[loc2]); H11ED.doCheck(a); // System.out.println(doCheck(a)); } if (totalTrials != (misCorrected + errorZero + toTen + subscriptRange + allZero)) System.out.println("Count Off"); System.out.println("Total: " + totalTrials + ", errorZero: " + errorZero + ", toTen: " + toTen + ", subscript: " + subscriptRange + ", misCorrected: " + misCorrected + ", allZero: " + allZero); } // end of main }

Here are the results of two runs, the first using 18 digits (15 data digits) and the second using the maximum of 121 digits (118 data digits). In each case a large number of double errors were deliberately introduced. In the first case, all but 14.9% of these double errors were detected. In the second case only 18.5% of double errors were detected.

% myjava H11ED 10000000 18 Total: 10000000, errorZero: 919248, toTen: 130462, subscript: 7501457, misCorrected: 1444074, allZero: 4759 % myjava H11ED 1000000 121 Total: 1000000, errorZero: 100002, toTen: 85080, subscript: 0, misCorrected: 814827, allZero: 91