Optimal Binary Edit-Metric Codes

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 E₂(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 the technical report: S.K.Houghten, D.Ashlock and J.Lenarz, "Bounds on Optimal Edit-Metric Codes"and was ultimately published as "Construction of Optimal Edit Metric Codes", Proceedings of the 2006 IEEE Workshop on Information Theory (ITW 2006), 259-263.

Modifications since that time:

E₂(10,4) = 21 and thus E₂(11,4) ≤ 42 and E₂(12,4) ≤ 84 (S.Houghten, July 2005)
E₂(11,3) ≥ 94 and E₂(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)
E₂(9,3) = 34, and thus E₂(10,3) ≤ 68 and E₂(11,3) ≤ 136 (S.Houghten, August 2005)
E₂(12,5) ≥ 16 and E₂(12,5) ≤ 20 (S.Houghten, August 2005)
E₂(12,5) ≤ 18 (S.Houghten, August 2006)
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", Congressus Numerantium, 2008.

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

This page last modified 6th August 2008