A Table of Bounds on Optimal Fixed-Length Binary Edit-Metric Codes

 n\d 1 2 3 4 5 6 7 8 9 10 11 12
 1 2 1 1 1 1 1 1 1 1 1 1 1
 2 4 2 1 1 1 1 1 1 1 1 1 1
 3 8 4 2 1 1 1 1 1 1 1 1 1
 4 16 8 2 2 1 1 1 1 1 1 1 1
 5 32 16 4 2 2 1 1 1 1 1 1 1
 6 64 32  7 4 2 2 1 1 1 1 1 1
 7 128 64 12 5 2 2 2 1 1 1 1 1
 8 256 128 19 9 4 2 2 2 1 1 1 1
 9 512 256 34 13 5 4 2 2 2 1 1 1
 10 1024 512 54-68 21 8 4 2 2 2 2 1 1
 11 2048 1024 94-136 30-42 11 6 4 2 2 2 2 1
 12 4096 2048 174-256 50-84 16-18 9 4 4 2 2 2 2
 16 65536 32768 1062   65              
 20 1048576 524288 6208   379   35          
 23 8388608 4194304 16927   1268   97          
 24 16777216 8388608 14089   1489   132          
 32 2^32 2^31     211170   1667          

The above table shows E2(n,d), the number of codewords in an optimal binary code of fixed length n and minimum edit distance d. Where exact values are not known, upper and lower bounds are provided.

The earliest version of this table appeared in: S.K.Houghten, D.Ashlock and J.Lenarz, "Bounds on Optimal Edit-Metric Codes" Technical Report

Modifications since that time:

  1. E2(10,4) = 21 and thus E2(11,4) ≤ 42 and E2(12,4) ≤ 84 (S.Houghten, July 2005)
  2. E2(11,3) ≥ 94 and E2(12,3) ≥ 174 (V.I.Levenshtein, calculated from bounds given in: V.I.Levenshtein, "Binary codes capable of correcting deletions, insertions and reversals", Sov. Phys. Dokl., vol. 10 no.8 (1966), 707-710)
  3. E2(9,3) = 34, and thus E2(10,3) ≤ 68 and E2(11,3) ≤ 136 (S.Houghten, August 2005)
  4. E2(12,5) ≥ 16 and E2(12,5) ≤ 20 (S.Houghten, August 2005)
  5. E2(12,5) ≤ 18 (S.Houghten, August 2006)
  6. Lower bounds for lengths of 16 or more updated from: R.Flack and S.Houghten, "Generation of Good Edit Codes from Classical Hamming Distance Codes", submitted to Congressus Numerantium, May 2008.

If you have improvements, comments, etc, please e-mail houghten@brocku.ca

This page last modified 6th August 2008
© Copyright Sheridan Houghten, 2005-2008