Insertion-deletion correcting codes are designed to correct insertions and deletions of characters. Insertion-deletion distance measures the minimum number of insertions and/or deletions required to transform one word into another.

Define D_q(n,d) to be the number of codewords in an optimal q-ary code of length n and minimum insertion-deletion distance d. We consider the variable-length case, in which n is the length of the longest codeword.

The earliest versions of the tables below appeared in: S.Baker, R.Flack and S.Houghten, "Optimal Variable-Length Insertion-Deletion Correcting Codes and Edit Metric Codes", Congressus Numerantium 186 (2008), 65-80. For each of the tables, upper and lower bounds are provided where exact values are not known.

Table of Bounds on Optimal Binary Insertion-Deletion Correcting Codes

n\d	1	2	3	4	5	6	7	8	9	10	11	12
1	3	2	1	1	1	1	1	1	1	1	1	1
2	7	5	2	2	1	1	1	1	1	1	1	1
3	15	10	3	2	2	2	1	1	1	1	1	1
4	31	21	6	5	2	2	2	2	1	1	1	1
5	63	42	9	7	3	2	2	2	2	2	1	1
6	127	85	15	12	6	5	2	2	2	2	2	2
7	255	170	25-31	18	7	6	3	2	2	2	2	2
8	511	341	41-63	31-37	10	8	6	5	2	2	2	2
9	1023	682	67-127	49-75	16-21	13	7	6	3	2	2	2
10	2047	1365	116-255	83-151	20-43	18-27	8	7	6	5	2	2
11	4095	2730	205-511	143-303	30-87	24-55	11-17	9	6	6	3	2
12	8191	5461	360-1023	255-607	45-175	36-111	15-35	14-19	8	7	6	5

Table of Bounds on Optimal Ternary Insertion-Deletion Correcting Codes

n\d	1	2	3	4	5	6	7	8	9	10	11	12
1	4	3	1	1	1	1	1	1	1	1	1	1
2	13	10	3	3	1	1	1	1	1	1	1	1
3	40	30	6	5	3	3	1	1	1	1	1	1
4	121	91	13	12	4	3	3	3	1	1	1	1
5	364	273	29-40	25-37	7	6	3	3	3	3	1	1
6	1093	820	67-121	55-112	14	12	5	5	3	3	3	3
7	3280	2460	158-364	122-337	24-43	21-37	8	7	4	3	3	3
8	9841	7381	396-1093	310-1012	43-130	36-112	15-25	13-22	6	6	3	3
9	29524	22143	1022-3280	792-3037	92-391	75-337	20-76	18-67	9-19	8-19	5	5
10	88573	66430	2678-9841	2064-9112	187-1174	152-1012	32-229	28-202	13-58	13-58	7-16	7-16

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