On Single-Deletion-Correcting Codes

N. J. A. Sloane  

AT&T Shannon Labs
180 Park Avenue, Florham Park, NJ 07932-0971
njas@research.att.com


Dedicated to Dijen Ray-Chaudhuri on the occasion of his 65th birthday

Jan 10, 2000. Revised Jan 20, 2000, Nov 07 2002.

An earlier version of this paper appeared in
Codes and Designs, Ohio State University, May 2000 (Ray-Chaudhuri Festschrift),
ed. K. T. Arasu and A. Seress, Walter de Gruyter, Berlin, 2002, pp. 273--291.



Abstract

This paper gives a brief survey of binary single-deletion-correcting codes. 
The Varshamov-Tenengolts codes appear to be optimal, but many 
interesting unsolved problems remain. 
The connections with shift-register sequences also 
remain somewhat mysterious. 

Classification
Primary 94B60; secondary 94A55.

For the full version, see
http://www.research.att.com/~njas/doc/dijen.pdf  or
http://www.research.att.com/~njas/doc/dijen.ps