On Multiple Deletion Codes


Autoria(s): Landjev, Ivan; Haralambiev, Kristiyan
Data(s)

16/09/2009

16/09/2009

2007

Resumo

In 1965 Levenshtein introduced the deletion correcting codes and found an asymptotically optimal family of 1-deletion correcting codes. During the years there has been a little or no research on t-deletion correcting codes for larger values of t. In this paper, we consider the problem of finding the maximal cardinality L2(n;t) of a binary t-deletion correcting code of length n. We construct an infinite family of binary t-deletion correcting codes. By computer search, we construct t-deletion codes for t = 2;3;4;5 with lengths n ≤ 30. Some of these codes improve on earlier results by Hirschberg-Fereira and Swart-Fereira. Finally, we prove a recursive upper bound on L2(n;t) which is asymptotically worse than the best known bounds, but gives better estimates for small values of n.

Identificador

Serdica Journal of Computing, Vol. 1, No 1, (2007), 13p-26p

1312-6555

http://hdl.handle.net/10525/330

Idioma(s)

en_US

Publicador

Institute of Mathematics and Informatics Bulgarian Academy of Sciences

Palavras-Chave #Insertion/Deletion Codes #Varshamov-Tennengolts Codes #Multiple Insertion/Deletion Codes
Tipo

Article