The Laws of Cryptography:
Table for Repetition Codes

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 will generate the entire table, for any input probability p:


// Table.java: given p, calculate a table for different numbers of duplicates
//   p: the channel probability for a binary symmetric channel
public class Table {

   // main function to do calculation
   public static void main (String[] args) {
      double p = (Double.valueOf(args[0])).doubleValue(); // channel probability
      int[] values = {1, 3, 5, 7, 9, 11, 25, 49, 99, 199};
      System.out.println("<table BORDER NOSAVE >");
      System.out.println("<tr><td align=center><b>Number of</b>");
      System.out.println(" <br><b>Duplicates</b></td>");
      System.out.println(" <td align=center><b>Transmission</b>");
      System.out.println(" <br><b>Rate</b></td>");
      System.out.println(" <td align=center><b>Error</b>");
      System.out.println(" <br><b>Rate</b></td>");
      System.out.println(" <td align=center><b>Success</b>");
      System.out.println(" <br><b>Rate</b></td></tr>");
      for (int len = 0; len < values.length; len++) {
         int n = values[len];
         double result = 0;
         for (long i = n; i > n/2; i--)
            result += comb(n,i)*Math.pow(p,i)*Math.pow(1-p,n-i);
         System.out.println("<tr><td>" + n + "</td><td>" +
             100.0/n + "%</td><td>" + (100.0 - 100.0*result) + "%</td><td>" + 
             100.0*result + "%</td></tr>" );
      }
      System.out.println("</table>");
   } // end of main

   // comb(n, i): the number of combinations of n things taken i at a time
   private static double comb(long n, long i) {
      double result = 1.0;
      if (i < n/2) i = n-i;
      for (long j = n; j > i; j--)
         result *= ((double)j/(j-i));
      return result;
   }
} 

Here is the table generated for p = 2/3:

Number of
Duplicates
Transmission
Rate
Error
Rate
Success
Rate
1100.0%33.3333333333334%66.6666666666666%
333.333333333333336%25.925925925926023%74.07407407407398%
520.0%20.987654320987772%79.01234567901223%
714.285714285714286%17.329675354366827%82.67032464563317%
911.11111111111111%14.484580602550523%85.51541939744948%
119.090909090909092%12.208504801097504%87.7914951989025%
254.0%4.151367840779045%95.84863215922095%
492.0408163265306123%0.7872479136560173%99.21275208634398%
991.0101010101010102%0.030913686260717554%99.96908631373928%
1990.5025125628140703%6.250990635692233E-5%99.99993749009364%

Here is the same table ``cleaned up'' a bit by hand:

Number of
Duplicates
Transmission
Rate
Error
Rate
Success
Rate
1100.0% 33.3%66.7%
3  33.3% 25.9%74.1%
5  20.0% 20.99%79.01%
7  14.3% 17.33%82.67%
9  11.1% 14.48%85.52%
11    9.1% 12.21%87.79%
25    4.0%   4.15%95.85%
49    2.0%   0.787%99.213%
99    1.0%   0.0309%99.9691%
199    0.5%   0.0000625%99.9999375%


Revision date: 2002-01-05. (Please use ISO 8601, the International Standard.)