The Tight Upper Bound for the Size of Single Deletion Error Correcting Codes of Length 11

A single deletion error correcting code (SDECC) over binary alphabet is a set of fixed-length sequences consisting of two types of symbols, 0 and 1, such that the original sequence can be recovered for at most one deletion error. There is a conjecture “the upper bound for the size of SDECC is equal to the size of Varshamov- Tenengolts (VT) code.” This conjecture had been shown to be true when the code length is ten or less. In this paper, we discuss a method for calculating this upper bound by providing an integer linear programming solver with several linear constraints. As a new result, we obtained that the tight upper bound for the size of a single deletion error correcting code of length 11 is 172. In other words, we could prove that the conjecture is true for the case where the length is 11.