Searching for Optimal Deletion Correcting Codes: New Properties and Extensions of Tenengolts Codes

Codes capable of correcting insertions or deletions due to synchronization errors are of increasing importance as the speed of transmission grows. Finding optimal deletion-correcting codes is particularly difficult because unlike traditional codes defined over Hamming distance, the sizes of the spheres about the code words are of varying sizes. Our research focuses on the Tenengolts codes, a class of non-binary one-deletion-correcting codes. These codes are asymptotically near-optimal. We examine parameters for which the largest Tenengolts codes are to be expected and consider how to extend these to construct larger codes. Several hypotheses, which are supported by the results of experiments, are made and partially proven.